Probability nobody gets their own hat

Question

n hats are returned to their n owners in a uniformly random permutation. What is the probability that no one receives their own hat? What does it converge to as n 	o \infty?

Accepted Answer

We want the probability the permutation is a derangement (no fixed points). Let Ak = "person k matches". For any specific set of k people all matching, P(A{i1} \cap \cdots \cap A{ik}) = \frac{(n-k)!}{n!}, and there are \binom{n}{k} such sets. Inclusion-exclusion: P\left(\bigcup Akight) = \sum{k=1}^{n} (-1)^{k+1}\binom{n}{k}\frac{(n-k)!}{n!} = \sum{k=1}^{n} \frac{(-1)^{k+1}}{k!}. Therefore P(	ext{no match}) = 1 - \sum{k=1}^{n}\frac{(-1)^{k+1}}{k!} = \sum{k=0}^{n} \frac{(-1)^k}{k!}. This is the truncated series for e^{-1}: P(	ext{no match}) \xrightarrow{n	o\infty} \frac{1}{e} \approx 0.367…

Probability nobody gets their own hat

Your answer

More Probability questions