Expected number of hat matches

Question

100 people check their hats at a party. At the end, the hats are handed back in a uniformly random order (a uniform random permutation). What is the expected number of people who receive their own hat?

Accepted Answer

Let X be the number of matches and define indicators Ik = 1 if person k gets their own hat. Then X = I1 + I2 + \cdots + I{100}. In a uniform permutation, each person's hat is equally likely to be any of the 100 hats, so E[Ik] = P(	ext{person } k 	ext{ matches}) = \frac{1}{100}. Linearity of expectation requires no independence (and the Ik here are certainly dependent): E[X] = \sum{k=1}^{100} E[Ik] = 100 \cdot \frac{1}{100} = 1. The expected number of matches is exactly \boxed{1}, for any number of people n, since n \cdot \frac{1}{n} = 1. Remarkably, more is true: the number of matches is ap…

Expected number of hat matches

Your answer

More Probability questions