# Question about the Hat Matching Problem

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?

• How did you compute $P(X_2=1\mid X_1=0)$? – Angina Seng Jul 23 at 3:46
• How do you figure that $P(X_2=1|X_1=0)=\frac1{N-1}$? How does that work out if $N=2$? Are you saying that, if there are two guys and two hats, and if the first guy doesn't get his own hat, then the second guy is sure to get his own hat back? I don't think that's right, because the first guy has the second guy's hat. – bof Jul 23 at 3:46
• If fact, if $N=2$, your result $P(X_2=1)=\frac1{N-1}$ says that the second guy is sure to get his hat back? Is that how it works in general, for any $N$, the last guy is guaranteed to get his own hat back? I am skeptical. – bof Jul 23 at 3:49
• @bof Should I instead be computing $P(X_2 = 1 | X_1 = 0)$ as $P(X_2 = 1 | X_1 \text{ doesn't have the second hat})$ – BigBear Jul 23 at 3:50
• You just shouldn't try to over-complicate a simple problem. What is the probability that the3 17th guy gets his hat back? Well, there are $N$ hats in the box, the hats are all the same, he has the same chance of ending up with one hat as another, so the chance he gets his own hat back is $1/N$ – bof Jul 23 at 3:58

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}\cdot\frac1N+0\cdot\frac1N+\frac1{N-1}\cdot\frac{N-2}N\;,$$
which simplifies to $$\frac1N$$.