Expected number of people who get their own hat back

Question

At a coat check, n people hand in their hats, and at the end the n hats are returned in a completely random order (a uniformly random permutation). What is the expected number of people who get their own hat back?

Accepted Answer

Let Ik indicate that person k receives their own hat, so the number of correct returns is M = \sum{k=1}^{n} Ik. By symmetry, person k is equally likely to receive any of the n hats, so their own comes back with probability \frac{1}{n}: E[Ik] = \frac{1}{n}. By linearity of expectation (the indicators are dependent, since one person's hat affects who is left for others, but linearity ignores that): E[M] = \sum{k=1}^{n} \frac{1}{n} = n \cdot \frac{1}{n} = 1. The expected number of people who get their own hat back is exactly 1, regardless of n. Whether 10 people or 10 million, on average one luc…

Expected number of people who get their own hat back

Your answer

More Probability questions