[Math] Matching problem expectation and variance

expectationprobabilityrandom variables

The matching problem: Suppose $n$ gentlemen go out for dinner and leave their hats in the cloakroom. After the dinner (and several glasses of wine) they pick their hats completely randomly. Denote by $X$ the number of gentlemen who take their own hats. Find $E[X]$ and $Var[X]$.

I have seen many answers to this:

$E[X] = \sum_i^nE(I_i)= \sum_i^n 1/n = 1$,

where $I_i$ is the indicator for each person which equals $1$ if the person takes his hat own hat and $0$ otherwise.

I don't understand how the probability of $I_i$ can be $1/n$ for all of $I_i$. Consider the third gentleman to take a hat; wouldn't the probability he take his hat be $1/(n-3)$ rather than $1/n$?

Best Answer

Not quite. $X = I_1+\dotsb+I_n$, so $$E[X] = E[I_1+\dotsb+I_n] =E[I_1]+\dotsb+E[I_n] = n\cdot E[I_1] = n\cdot\frac{1}{n} = 1,$$ since \begin{align*} E[I_k] &= 0\cdot P(I_k = 0)+1\cdot P(I_k = 1) \\ &= P(I_k = 1), \end{align*} and $P(I_k = 1) = \frac{1}{n}$.


Think about it this way, pretend each person is sitting in a line and the each hat has been labeled to match the correct person. With indicators, it is like you distribute each ticket back randomly face down to each person. So the chance that person $k$ got the correct ticket is $\frac{1}{n}$. In this manner, we bar people from choosing the same hat.