# 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?

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$.

-
assume they all get one at the same time. – karakfa Dec 27 '12 at 21:25

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: $$\Pr(\text{2nd right}) = \Pr(\text{(1st right and 2nd right) or (1st wrong and 2nd right)})$$ $$=\Pr(\text{1st right})\Pr(\text{2nd right}\mid\text{1st right}) + \Pr(\text{1st wrong})\Pr(\text{2nd right}\mid\text{1st wrong})$$ $$= \frac1n\cdot\frac{1}{n-1} + \frac{n-1}{n}\cdot\frac{1}{n-1}\qquad = \frac1n.$$

-

Person $k$ is equally likely to grab any of the $n$ hats, so he grabs hat $i$ with probability $\frac1n$ for $i=1,\dots,n$. In particular, he grabs hat $k$ with probability $\frac1n$.

If that’s not convincing, there are $n!$ possible permutations of the hats among the people, and $(n-1)!$ of those permutations have person $k$ getting his own hat. The $n!$ permutations are equally likely, so

$$P(X_k=1)=\frac{(n-1)!}{n!}=\frac1n\;.$$

-

Because there are $n!$ different ways to order the hats, and $(n-1)!$ ways to distribute the hats so that persion $k$ gets his own hat, so the probability that $k$ gets his own hat is $$\frac{(n-1)!}{n!}=\frac{1}{n}$$

Your intuition reflects the fact that two $X_i$ and $X_j$ are not independent variables. That is a useful intuition, but it does not affect the odds of person $k$ getting his hat.

Alternatively, let's just say you are looking at $P(X_2=1)$ and person $1$ picks a hat first.

The probability that person $1$ chose person $2$'s hat is $\frac{1}{n}$. So the probability that person $2$ picks his hate amongst the rest is the probability that person $1$ did not choose that hat, times the probability that person $2$ picks the hat from the remaining $n-1$ hats. That is:

\begin{align}P(X_2=1)= &P(\text{person 1 did not choose hat 2})\times\\ &P(\text{person 2 chooses hat 2 from the remaining }n-1\text{ hats})\\ =&\left(1-\frac{1}{n}\right)\frac{1}{n-1} = \frac{1}{n}\end{align}

-