Hat-Check Problem

From ProofWiki
Jump to: navigation, search

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?


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)$


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


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

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



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.