The Hat Check Problem

Question

Four people check their hats. The hats are returned uniformly at random, one to each person. What is the probability that nobody gets their own hat back? What does the answer approach for n people as n to infty?

Accepted Answer

By inclusion–exclusion on the events A_i = "person i gets own hat": P(textno fixed point) = sum_k=0^n frac(-1)^kk!. For n=4: 1 - 1 + frac12 - frac16 + frac124 = frac924 = frac38 = 0.375. (Equivalently: D_4 = 9 derangements of 24 permutations.) As n to infty the series converges to frac1e approx 0.3679, astonishingly fast, already at n=4 you're within 0.008 of the limit. So "about 37%, nearly independent of n" is the headline fact worth memorizing. Where it shows up: matching problems, the probability a random permutation has no fixed points, and as a sanity check in any "random assignment" estimation. The rapid convergence is also a classic example of an alternating series error bound: truncation error is at most the first omitted term frac1(n+1)!.

The Hat Check Problem

Problem

Your answer

Hints

More Probability to train on