The Matching Problem (probability)

[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 shuffled 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

 

[BvU]

Hi there, mathwiz !

I appreciate your effort !

Did you consider reversing this problem too ?

 

[TheMathNoob]

Hi there, mathwiz !

I appreciate your effort !

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.

 

[BvU]

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.

[edit] it's not right anyway ...

 

[haruspex]

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?

 

[Ray Vickson]

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 shuffled 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}<br /> \Box &amp; \Box &amp; \Box &amp; \Box&amp; \text{Row 1} \\<br /> A&amp;B &amp; C &amp; D&amp;\text{Row 2}<br /> \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.