Chance that at least one card matches between two decks

Question

Two identical decks are each shuffled independently, then turned over one card at a time in parallel. A "coincidence" is a position where both decks show the same card. (Equivalently, fix one deck and let the other be a uniformly random permutation of it.)

What is the probability of at least one coincidence, and what does it converge to as the deck size grows? How many coincidences do you expect?

Accepted Answer

Line up deck one in its order; deck two is then a uniformly random permutation of the same cards. A coincidence at position k is a fixed point of that permutation, so "no coincidence" is a derangement. Using the no-match result, P(	ext{no coincidence}) = \sum{k=0}^{n}\frac{(-1)^k}{k!} \ \longrightarrow\ \frac1e, hence P(	ext{at least one coincidence}) = 1 - \sum{k=0}^{n}\frac{(-1)^k}{k!} \ \xrightarrow{n	o\infty}\ 1 - \frac1e \approx 0.6321. Why it barely depends on n. The series converges so fast that the answer is essentially 1 - 1/e for any deck of modest size. For n = 5: 1 - 44/120 = 7…

Chance that at least one card matches between two decks

Your answer

More Probability questions