[Math] If n people randomly pick one hat out of $n$ hats, why is the probability of a match $1/n$? What about order of previous hats

probability

For a standard matching problem

There are $n$ people with hats at a party.
Each person randomly grabs a hat.
A match occurs if a person gets his own hat.

Define the number of matches $N$ as
$$
N=\sum_{k=1}^n X_k,
$$
where $X_k$ is the indicator function
$$
X_k= I\{\text{person } k\text{ grabs his own hat}\}.
$$
Why is
$$
P(X_k=1)=\frac{1}{n}?
$$

I expect $P(X_k=1)$ to depend on the order, so I don't see why $P(X_k=1)$ simplifies to $1/n$.

Best Answer

This is a standard conceptual misunderstanding. What's the probability that the second person gets the right hat? Lots of people respond instantly that it depends on whether the first person got the right hat. That's the right answer to the wrong question.

The conditional probability that the second person gets the right hat given that the first person got the right hat, or that the first person got the wrong hat, does depend on whether the first person got the right hat or not.

But that's the wrong question. What's the probability that the second person gets the right hat, in the absence of any information about the first person's fate? It's $1/n$ because there are $n$ hats and none is more likely than another to be the one that that person gets.

But if you insist on thinking about those conditional probabilities, here's how to do it: \begin{align} & \Pr(\text{2nd right}) = \Pr(\text{(1st right and 2nd right) or (1st wrong and 2nd right)}) \\[10pt] = {} & \Pr(\text{1st right})\Pr(\text{2nd right}\mid\text{1st right}) \\ & {} + \Pr(\text{1st wrong and got 2nd one's hat}) \cdot \Pr(\text{2nd right}\mid\text{1st wrong and got 2nd one's hat}) \\ & {} + \Pr(\text{1st wrong and didn't get 2nd one's hat}) \cdot\Pr(\text{2nd right} \mid \text{1st wrong and $\cdots$ [etc.]}) \\[10pt] = {} & \left(\frac1n\cdot\frac{1}{n-1}\right) + \left(\frac 1 n \cdot 0\right) + \left( \frac{n-2} n \cdot \frac 1 {n-1} \right) \\[10pt] = {} & \frac 1 n. \end{align}

Related Question