The Hat-Check Problem and Expected Fixed Points

The problem. $n$ people check their hats at a party. The coat-check attendant loses the tickets and hands hats back in a uniformly random order. In expectation, how many people get their own hat back? A related, harder question — what's the probability nobody gets their own hat back — is the classic "derangement" problem, and it's worth seeing why the expectation question is easy while that one is hard.

Setting it up with indicators

Label the people $1$ through $n$. Define $X_i = 1$ if person $i$ receives their own hat, and $0$ otherwise. The total number of people who get their own hat back is $X = X_1 + \cdots + X_n$. By linearity of expectation, $E[X] = \sum_{i=1}^n E[X_i]$, and each $E[X_i] = P(X_i = 1)$, the probability person $i$'s hat happens to land back with them. Since the hats are returned in a uniformly random order, person $i$ is equally likely to receive any of the $n$ hats, so $P(X_i = 1) = \frac{1}{n}$.

$$E[X] = \sum_{i=1}^n \frac{1}{n} = n \cdot \frac{1}{n} = 1.$$

In plain English: no matter how many people are at the party — 5 or 500 — the expected number who get their own hat back is exactly 1. This is the same skeleton as the card-shuffle fixed-point puzzle, because a random hat return and a random card shuffle are the same mathematical object: a uniformly random permutation of $n$ items.

Worked example: n = 4 by brute-force check

With $n=4$ people, there are $4! = 24$ equally likely hat-return orders. Counting fixed points across all 24 permutations: the number of permutations with exactly $k$ fixed points is given by $\binom{4}{k}$ times the number of derangements of the remaining $4-k$ items. Summing $k$ times that count over all permutations and dividing by 24 gives the average — and it comes out to exactly $\frac{24}{24} = 1$, matching the indicator-variable answer without needing $n$ to be large for the result to hold. The clean value of 1 isn't an asymptotic approximation; it's exact for every $n \geq 1$.

Drag the rate parameter to 1 on the explorer above: the number of fixed points in a large random permutation is well approximated by a Poisson(1) distribution — mean 1, but with real probability mass at 0, 1, 2, and beyond, illustrating that "expected value 1" does not mean "always exactly 1."

Why the harder question — nobody gets a match — needs more machinery

Asking for $E[X]$ only needed $P(X_i=1)$ for each $i$ individually — the indicators can be dependent and it still works. But asking $P(X = 0)$, the probability of zero matches (a derangement), genuinely requires the joint structure: whether person 1 misses their hat is not independent of whether person 2 misses theirs, because they're drawing from the same shrinking pool. That probability converges to $e^{-1} \approx 36.8\%$ as $n$ grows, via inclusion-exclusion — a much heavier calculation than the one-line expectation. The contrast is the lesson: expectation questions often dissolve into simple indicator sums even when the corresponding probability question is hard.