Two Decks Puzzle

You have two regular decks of playing cards. You hand one to your friend, and keep the other. Both of you shuffle your decks thoroughly.

In unison you both deal the top card off your deck face-up. Then the next, then the next; dealing the cards out in parallel pairs.

What is that probability that at least one of the pairs dealt will be an exact match? (Get’s turned up at the same time as its twin in the other pack).

Before calculating the answer, what’s your gut feeling? Is it very likely, very unlikely, or close to a coin flip?

Rather than dealing with suits and values, let’s just imagine that each card has a distinct number in the range [1-52].

Because both decks are shuffled, without loss of generality, we can imagine the first deck to be in sorted order [1-52] and the second deck random, so the problem reduces to finding the probability that a numbered card in the second deck is in the ordinal position as its value (and would thus match the card in the first deck).

Mathematicians call these arrangements Derangements. It is the number of permutations such that no element appears in its original position (which we can then divide by the total number of permutations to get the probability).

However, if we just want to perform a 'back of the envelope' approximation, we can greatly simplify by assuming the card turns are independent events (You can see this is not strictly true with a thought experiment involving a deck of just two cards: If the first pair match, then the second pair also have to match, and vice-versa).

For any pair of cards, if we approximate that there is a 51/52 chance there is no match, then, as there are 52 cards in a deck, the chances that none of them match up with their twins is (51/52)⁵² ≈ 36.43%. So the chance getting at least one matching pair is 63.57%

I don’t know about you, but my first thought about the chances of this happening is that it would be much lower.

The total number of derangments for 52 elements is:

29,672,484,407,795,138,298,279,444,403,649,511,427,278,111,361,911,893,663,894,333,196,201

(This is the total number of ways to arrange a deck [1-52], so that no card is in its original position (its value matching its ordinal position).

The total number of perumations for 52 elements is (52!):

80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000

Dividing one by the other gives ≈ 36.7879%, to give the answer that a percentage chance of at least one match as ≈ 63.2121%, which is pretty close to our gut approximation.

What happens if we have a much larger deck?

For a deck of n cards, then the chance of at least one match is 1-((n-1)/n)ⁿ

What’s interesting is that the success percentage quickly asymptotes to the limit 1-1/e. Once the deck gets above just a few cards the chances are about the same, and no matter how big the deck is the chance of at least one match never falls below 63.21%

Derangement problems come up quite a lot in mathematics. It's often given colloquial names such as The Secretary Letter Problem (where an abscent minded secratary inserts n personalised letters into n pre-labelled envelopes, at random, and the probility that no person gets their own letter), or The hat-check problem (where patrons deposit their hats at a booth, and then they are handed back out at random).

In more real world examples, it can be used to calculate the number of ways to teacher can redistribute test papers to her students to grade so that no student gets his/her own paper back, or how many ways can couples dance so that none of them is dancing with their own spouse.