[Math] matching hats problem, expected value of number of matching hats

combinatoricsstatistics

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.

Best Answer

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$