The Hat Check Problem and Derangements

The expected number of matched hats is always exactly one regardless of group size, while the chance of zero matches converges to about 0.368.

n people check their hats and the hats are returned in a uniformly random order. The expected number of people who receive their own hat back is exactly one, regardless of how large n is. The probability that nobody gets their own hat back, a complete derangement, converges to about 0.368, which is one over e, and is already within a few thousandths of that limit by the time n reaches five.

There are n hats and n owners, and the hats are handed back according to a uniformly random permutation of the n people, so every one of the n factorial possible assignments is equally likely. A match occurs when a person receives their own hat back. Two separate questions are usually asked together, the expected number of matches, and the probability of zero matches.

Both questions use the same random permutation, but they call for different tools. The expected number of matches only needs linearity of expectation, while the probability of zero matches needs the stronger, more careful machinery of inclusion-exclusion.

Define an indicator variable for each person that equals one if that person receives their own hat back and zero otherwise. Since the permutation is uniformly random, any specific person receives their own hat with probability exactly one over n, the same as the chance that hat lands in any one of the n positions. The expected value of each indicator is therefore one over n.

Linearity of expectation says the expected value of a sum equals the sum of the expected values, and this holds regardless of whether the indicators are independent, which they are not here, since one person getting their own hat changes the odds for everyone else. Summing n indicators, each with expected value one over n, gives n times one over n, which equals exactly one, for every value of n from one upward.