# Hat-Check Problem

## Classic 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 Number of Permutations of a set of size $n$ is $n!$.

- The Closed Form for Number of Derangements on Finite Set of size $n$ is:
- $D_n = n! \left({1 - \dfrac 1 {1!} + \dfrac 1 {2!} - \dfrac 1 {3!} + \dotsb + \left({-1}\right)^n \dfrac 1 {n!} }\right)$

So:

- $p_n = 1 - \dfrac 1 {1!} + \dfrac 1 {2!} - \dfrac 1 {3!} + \dotsb + \left({-1}\right)^n \dfrac 1 {n!}$

Finally:

- $1 - \dfrac 1 {1!} + \dfrac 1 {2!} - \dfrac 1 {3!} + \dotsb$

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 \ge 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.

## Also known as

This problem is also known as the **envelope problem**, couched in the language of an incompetent secretary placing letters at random into the envelopes without checking the address on the envelope matches the addressee of the letter.

## Sources

- 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $0 \cdotp 36787 \, 94411 \, 71442 \, 32159 \, 55237 \, 70161 \, 46086 \, 74458 \, 11131 \, 031$