Hat-Check Problem

Problem

The traditional wording of the question is as follows.

A hat-check girl completely loses track of which of $n$ hats belong to which owners, and hands them back at random to their $n$ owners as the latter leave.

What is the probability $p_n$ that nobody receives their own hat back?

Solution

Put into bald mathematical language, this boils down to:

For a set $S$ of $n$ elements, what is the number of derangements of $S$ divided by the number of permutations of $S$?

The answer is: approximately $\dfrac 1 e$, which can be demonstrated as follows.

Let $D_n$ be the number of derangements of a set of size $n$.

We have that:

• The total number of permutations of a set of size $n$ is $n!$.

• The total number of derangements of a set of size $n$ is:

$\displaystyle D_n = n! \left({1 - \frac 1 {1!} + \frac 1 {2!} - \frac 1 {3!} + \cdots + \left({-1}\right)^n \frac 1 {n!} }\right)$

So:

$\displaystyle p_n = 1 - \frac 1 {1!} + \frac 1 {2!} - \frac 1 {3!} + \cdots + \left({-1}\right)^n \frac 1 {n!} $

Finally:

$\displaystyle 1 - \frac 1 {1!} + \frac 1 {2!} - \frac 1 {3!} + \cdots$

converges to $\dfrac 1 e$ by Taylor Series Expansion for Exponential Function.

$\blacksquare$

Note

This answer is accurate only for large $n$.

For example when $n = 1$ there is only one hat to hand back, so $p_n = 0$.

Taking say $n \geq 8$, the answer is $1/e$ accurate to within $10^{-5}$ of the true value, with the accuracy increasing with increasing $n$.

If the venue in question is Hilbert's Hotel, then the answer is precise.