Expected number and variance of mutual hat swaps

Question

n \ge 4 hats are returned to their owners in a uniformly random permutation. Say a mutual swap is a pair of people \{i, j\} who end up holding each other's hats (person i gets j's hat and j gets i's). Let X be the number of mutual swaps. What are E[X] and \mathrm{Var}(X)?

Accepted Answer

Write X = \sum{\{i,j\}} I{ij}, an indicator over the \binom{n}{2} unordered pairs, where I{ij} = 1 iff i and j swap. Mean. A specific pair swaps iff the permutation maps i 	o j and j 	o i, with the other n-2 positions arbitrary: P(I{ij} = 1) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}. So E[X] = \binom{n}{2}\cdot\frac{1}{n(n-1)} = \frac{n(n-1)}{2}\cdot\frac{1}{n(n-1)} = \frac12. Variance. Expand E[X^2] = E[X] + \sum{\{i,j\}
e\{k,l\}} P(I{ij} = 1,\, I{kl} = 1). Two mutual swaps cannot share a person (someone can only swap with one partner), so any pair of distinct swaps involves 4 different peop…

Expected number and variance of mutual hat swaps

Your answer

More Probability questions