# matching hats problem, expected value of number of matching hats

I've been reading a book where the following problem is stated

"Suppose that $n$ people throw their hats in a box and then each picks up one hat at random. What is the expected value of X, the number of people that get back their own hat? "

It then continues to say:

" For the $i$th person, we introduce a random variable $X_i$ that takes the value $1$ if the person selects his/her own hat, and takes the value $0$ otherwise

Since $P(X_i = 1) = \frac{1}{n}$ and $P(X_i = 0) = 1 − \frac{1}{n}$, the mean of $X_i$ is

$E[X_i] = \sum_k k \cdot P(x_i = k) = \frac{1}{n}$

The total number of people with their own hat is $X = X_1 + X_2 + ··· + X_n$

and

$E[X] = E[X_1] + E[X_2] + ··· + E[X_n] = n\cdot \frac{1}{n} = 1$ "

However, this seems a little suspicious to me.

The probabilities of each $X_i$ are not independent of one another. If they were, the probability of having exactly $n-1$ people grabbing their hats would be non-zero. However, we know it has to be zero since you cannot everybody but one grabbing their hats, that would mean the last person also grabs theirs. So there's an interaction among the different possibilities.

But the calculation above seems to work! Running on a simulation, the result is actually 1. So I'm a bit confused as to why the argument above works? To me, this cannot be modeled by $n$ random variables that happily take values independently from one another.

• Think about it as everyone getting assigned a random hat at the same time. Or as everyone grabbing a random hat at the same time. This is the same as choosing a random hat from the box for each person. We expect this to result in exactly one person coincidentally getting their own hat. – The Count Aug 9 '18 at 16:47

This is a crucial concept called the linearity of expectation. You don't need the variables to be independent to be able to add the expectations. As an example, think of flipping a coin. The expected number of heads is $\frac 12$, as is the expected number of tails. These are not independent, they are perfectly anticorrelated. Even so, the expected number of faces is $\frac 12+\frac 12=1$