Expected number of people who get their own hat

Question

n hats are returned to their n owners in a uniformly random permutation. Let M be the number of people who receive their own hat. What are E[M] and \operatorname{Var}(M)?

Accepted Answer

The mean, via indicators. Let Ik = 1 if person k gets their own hat. Person k's hat is equally likely to land in any of n positions, so E[Ik] = P(Ik = 1) = 	frac{1}{n}. By linearity (no independence needed), E[M] = \sum{k=1}^{n} E[Ik] = n \cdot \frac{1}{n} = 1. On average exactly one person is reunited, for every n. The variance. For j 
e k, both matching means two specific hats are placed correctly and the rest are free: E[Ij Ik] = P(Ij = 1, Ik = 1) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}. So \operatorname{Cov}(Ij, Ik) = \dfrac{1}{n(n-1)} - \dfrac{1}{n^2}, and each \operatorname{Var}(Ik) = …

Expected number of people who get their own hat

Your answer

More Probability questions