matching hats problem, expected value of number of matching hats

Question

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.

Answer 1

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$

Answer 2

Here the basic idea is as Ross Millikan says. But his offered example may be not well fitted to this specific problem since flipping a coin doesn't influence with other flips while here taking hats will if we assume that they take one by one.

This MIT video may well answer this problem. Here I offer one summary of what the video says.

We can think about all possible permutations for the order of taking hats. For example, when 3 people take hats, $(2,3,1)$ means that the 1st person takes the hat of the 2nd person and the rest is similar.

We use the same random variable $X_i$ as the question uses. Then $E[X_i]=\frac{1}{n}$ because only $\frac{1}{n}$ of the $n!$ permutations will make $X_i=1$. So we can get $E[X] = E[X_1] + E[X_2] + ··· + E[X_n] = n\cdot \frac{1}{n} = 1$.