Variance of the number of hat matches

Question

n \ge 2 hats are returned to their n owners in a uniformly random permutation. Let X be the number of people who receive their own hat (fixed points). What is \mathrm{Var}(X)?

Accepted Answer

Write X = \sum{k=1}^n Ik where Ik indicates person k matches. We know E[Ik] = \frac1n, so E[X] = 1. Second moment. Expand: E[X^2] = \sumk E[Ik^2] + \sum{j 
e k} E[Ij Ik] = \sumk E[Ik] + \sum{j 
e k} P(Ij = 1, Ik = 1). Two specific people both match iff the permutation fixes both positions: P(Ij = Ik = 1) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}. There are n(n-1) ordered pairs j 
e k, so E[X^2] = n \cdot \frac1n + n(n-1)\cdot\frac{1}{n(n-1)} = 1 + 1 = 2. Variance. \mathrm{Var}(X) = E[X^2] - (E[X])^2 = 2 - 1 = 1. Both the mean and variance are exactly 1, for every n \ge 2, no asymptotics requi…

Variance of the number of hat matches

Your answer

More Probability questions