The Matching Problem (probability)

• TheMathNoob
In summary: There are 3 ways that card 4 can match with any card in the deck: it can match with 1, 2, or 3. So the probability of it matching is 3/8.Similarly, for 5...There are 3 ways that card 5 can match with any card in the deck: it can match with 1, 2, or 3. So the probability of it matching is 3/12.Now let's look at the case where the cards are placed in a row.In this case, there are only 2 possible matches: card 1 can match with card 4, and card 2 can match with card 5. So the probability of at least one match is 2/5.
TheMathNoob

Homework Statement

Suppose that all the cards in a deck of n different cards are placed in a row, and that the cards in another similar deck are then shufﬂed and placed in a row on top of the cards in the original deck. It is desired to determine the probability Pn that there will be at least one match between the corresponding cards from the two decks

Homework Equations

P(AUB)= P(A)+P(B)-P(AnB)

The Attempt at a Solution

I already posted this problem before, but it was deleted because of the format. People tell me that my logic is wrong and I think that they are right, but I don't know why I am wrong.

This is how I see it

A B C D E...
C B A D E...

we shall determine the probability that at least one pair will match.

Simpler case

A B C D
A
A good way to do it would be to find the prob that no pair matches. In this case there 3 ways how this can happen so it would be 3/4 the prob that no pair matches in this case.

Similarly

A B C D
A B

The number of outcomes in this case would be 3*3

So for n cards it would be (n-1)(n-1)... n times

so the prob would be

1-π(n-1)/n^2

I am still learning how to use the system in this forum. The multiplicative iterator goes from i=1 to n

Hi there, mathwiz !

Did you consider reversing this problem too ?

BvU said:
Hi there, mathwiz !

Did you consider reversing this problem too ?
Hi BvU, I already read the other method for solving this problem and it made sense to me. They just set Ai as the event where some card i matches up and then they compute the prob of A1 U A2 U A3 U A4 all they way down to n cards. This makes sense because in sets, union can be looked as or statements so they are basically saying that one of them shall work in order to satisfy the statement, but I am just wondering why mine doesn't work.

My inroad was that for the first card you can pick 51 out of 52, for the second 50 out of 51, etcetera... to get no matches at all. A bit of normalization and then 1 minus that is your answer. I'm not giving the answer on a plate (i have no idea, to be honest), just suggesting a way to look at this problem. Good luck.

 it's not right anyway ...

Last edited:
This is known as the derangement problem.
You describe a method in terms of A1 U A2 U A3 U ... , but without seeing more details I cannot comment whether it works. It is not straightforward since the events are not independent. Certainly that looks like a flaw in your solution, but I'm not sure I understood what your argument was.

An approach which does work uses the principle of inclusion and exclusion. Are you familiar with that?
Another sets up a recurrence relation on the probability of n objects being deranged, as a function of n. Are you accustomed to recurrence relations?

TheMathNoob said:

Homework Statement

Suppose that all the cards in a deck of n different cards are placed in a row, and that the cards in another similar deck are then shufﬂed and placed in a row on top of the cards in the original deck. It is desired to determine the probability Pn that there will be at least one match between the corresponding cards from the two decks

Homework Equations

P(AUB)= P(A)+P(B)-P(AnB)

The Attempt at a Solution

I already posted this problem before, but it was deleted because of the format. People tell me that my logic is wrong and I think that they are right, but I don't know why I am wrong.

This is how I see it

A B C D E...
C B A D E...

we shall determine the probability that at least one pair will match.

Simpler case

A B C D
A
A good way to do it would be to find the prob that no pair matches. In this case there 3 ways how this can happen so it would be 3/4 the prob that no pair matches in this case.

Similarly

A B C D
A B

The number of outcomes in this case would be 3*3

So for n cards it would be (n-1)(n-1)... n times

so the prob would be

1-π(n-1)/n^2

I am still learning how to use the system in this forum. The multiplicative iterator goes from i=1 to n

Do you really mean ##1 - \prod_{i=1}^n (n-1)/n##---exactly as you wrote? That equals ## 1 - [(n-1)/n]^n##. I have no idea how you arrive at this, because you do not show your logic.

However, it is incorrect.

Let's look at your simple case of 4 objects:
$$\begin{array}{ccccc} \Box & \Box & \Box & \Box& \text{Row 1} \\ A&B & C & D&\text{Row 2} \end{array}$$
We want to put letters A, B, C, D into the boxes in Row 1 and look at the matches with Row 2. Your claim above is that the probability of no match equals ##\text{claimed-}P0 = 1- (3/4)^4= 175/256 \doteq 0.6836##, and that the probability of ##\geq 1## match is ##\text{claimed-}P_{\geq 1} =81/256 \doteq 0.3164##. In fact, the actual probabilities of no match and ##\geq 1## matches in this case are ##\text{true-}P0 = 3/8 = 0.375## and ##\text{true-}P_{\geq 1} = 5/8 = 0.625##. These come from careful and detailed application of the inclusion-exclusion principle.

As I said: I cannot tell where you went wrong because you do not explain your method or your logic.

1. What is the Matching Problem in probability?

The Matching Problem in probability is a mathematical concept that deals with the likelihood of finding identical objects in a set of objects. It can also refer to the probability of finding a pair of identical items in a set of items. This problem is often used in fields such as statistics, computer science, and genetics.

2. How do you calculate the probability of a matching problem?

The probability of a matching problem can be calculated using the formula P(A) = n!/(n^k * (n-k)!) where n is the total number of objects and k is the number of objects being matched. This formula is known as the "Birthday Problem" formula and is commonly used in probability calculations for matching problems.

3. What is the significance of the Matching Problem?

The Matching Problem has many practical applications, such as predicting the probability of duplicate credit card numbers or determining the likelihood of matching DNA sequences in genetics. It is also used in game theory to analyze strategies and outcomes in various games.

4. Can the Matching Problem be solved using other methods besides the Birthday Problem formula?

Yes, there are other methods for solving the Matching Problem, such as the Inclusion-Exclusion principle and the Combinatorial method. These methods can be used for more complex matching problems involving multiple sets of objects.

5. How does the size of the set of objects affect the probability of a matching problem?

The size of the set of objects has a direct impact on the probability of a matching problem. As the number of objects increases, the probability of finding a match also increases. This is because there are more possible combinations and chances for a match to occur in a larger set of objects.

• Precalculus Mathematics Homework Help
Replies
18
Views
600
• Precalculus Mathematics Homework Help
Replies
5
Views
2K
• Precalculus Mathematics Homework Help
Replies
9
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
886
• Precalculus Mathematics Homework Help
Replies
12
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
823
• Calculus and Beyond Homework Help
Replies
31
Views
3K
• Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
• Precalculus Mathematics Homework Help
Replies
14
Views
1K
• Precalculus Mathematics Homework Help
Replies
5
Views
2K