Question about the Hat Matching Problem

Question

I'm confused about the following probability problem:
N people throw their hats into a box. They then randomly draw a hat out of the box. Find the expected number of people who receive their own hat.
By intuition, it seems that everyone should have an equally likely probability of getting their own hat back. I'm now trying to mathematically prove this, however this doesn't appear to be the case. I'll illustrate with the first two people.
$$P(X_1 = 1) = frac{1}{N}$$
$$P(X_2 = 1) = P(X_2 = 1 | X_1 = 1)P(X_1 = 1) + P(X_2 = 1 | X_1 = 0)P(X_1 = 0) text{   (by total law of probability)}$$
$$P(X_2 = 1) = frac{1}{N-1}frac{1}{N} + frac{1}{N-1}frac{N-1}{N} \ = frac{1}{N(N-1)} + frac{N-1}{N(N-1)} = frac{1}{N-1}$$
So $P(X_2 = 1) neq P(X_1 = 1)$ which contradicts intuition...
However, looking up the problem of finding the expected number of matched hats, this is exactly how they solve it. What am I missing?

Brian M. Scott · Answer

You overlooked the fact that the outcome $X_1=0$ covers two very different cases. If the first person drew the second person’s hat, which happens with probability $frac1N$, the probability that the second person gets the right hat is $0$. If the first person drew a different hat, which occurs with probability $frac{N-2}N$, the probability that the second person gets the right hat is $frac1{N-1}$. The correct total probability is therefore
$$frac1{N-1}cdotfrac1N+0cdotfrac1N+frac1{N-1}cdotfrac{N-2}N;,$$
which simplifies to $frac1N$.

Question about the Hat Matching Problem

One Answer

Add your own answers!

Ask a Question