Probability theory is full of surprises. Possibly the best-known paradoxical results are the Monty Hall Problem and the two-envelope problem, but there are many others. Here we consider a simple problem using playing cards, first analysed by Pierre Raymond de Montmort (1678–1719).
Take two piles of cards faced down, one with the 13 spades, the other with the 13 hearts. Assume the two piles are well-shuffled, and turn over a single card at a time from each pile. The two cards may or may not have matching values. The question is this: what is the probability that none of the 13 pairs of cards match?
With no loss of generality, we may assume that the pile of spades is in order from Ace up to King, while the hearts are in random order. Then we see that the problem is equivalent to the game that Montmort called the Jeu de Treize: given a bag with 13 balls labelled from one to thirteen, pick them out one by one. The question now is: what is the probability that no label of a ball matches its place in the sequence of draws.
Given a set of elements, such as cards or balls, there are permutations of the set. A derangement is a permutation that leaves no element in its original position. In other words, a derangement is a permutation with no fixed points. The number of derangements of elements is written , known as a subfactorial or, sometimes, a de Montmort number.
The first few values of the permutations and derangements are as in the Table above. We see that the pattern is not obvious. There are several expressions for the derangement number . There is a recurrence relation for subfactorials:
Using this, we can easily extend the table above: the sequence of derangement numbers is .
To prove (*) let us assume is known for all up to . Now consider a derangement of elements . Element can be in any of positions. Suppose it is in position . There are two possibilities: is in position and there are derangements of the remaining elements; or is elsewhere, and there are derangements of the remaining elements. Thus we have
It can be shown (see Wikipedia: Derangements) that:
Using this formula it follows that
Returning to Montmort’s problem, we see that the required probability is
The surprising result is that, even for moderate values of , this probability is remarkably close to . This means that in about four out of every ten trials we may expect no matches.
There are various equivalent formulations of Montmort’s problem. Suppose we have individual letters each addressed to a different person, and also pre-addressed envelopes. A scatter-brained secretary places the letters in the envelopes in a haphazard manner; what is the probability that no letter will be in the correct envelope? Again, suppose hats are held in a music-hall cloakroom. After the performance, the concert-goers rush out, grabbing the first hat they can get. The probability that nobody gets their own hat is about .
The problem was analysed by William Feller in his book An Introduction to Probability Theory and Its Applications. He uses the basic result giving the probability that two events and will occur, in terms of the probabilities of either or both:
If the events are mutually exclusive (cannot both occur) then the probability of one or other occurring is simply the sum of the probabilities of each: . There is a theorem in set theory known as the inclusion-exclusion principle that allows this result to be extended to events. This enables us to derive an expression for the probability of a derangement (see Feller, 1957, Chapter IV).
Feller, William, 1957: An Introduction to Probability Theory and Its Applications. John Wiley & Sons Inc.
Gorroochurn, Prakash, 2012: Classic Problems of Probability. John Wiley & Sons Inc.
Wikipedia: Inclusion–exclusion principle.