4 People 4 Hats, probably exactly 0,1,2,3,4 get their hats back

Question

This is the famous hat check problem. Let's say there are 4 people and 4 hats. They are randomly given back to their owners as they walk out the door.

I'm looking to find the expected value of the number of people who get their hats back.

So since expectation requires the summation of xP(x),

I'm assuming the first step is to find the probability that exactly x people get their hat back for cases 0 through 4.

Is that correct?

If so, how do I find the probability of that exactly 0 people get their hat back, as well as 1 person, then 2 people etc...

Answer 1

You don't need to work out the individual probabilities. You can use linearity of expectation. Let's do the $n$ people and $n$ hats case. The number of people who get back their own hats is $Y=X_1+X_2+\cdots+X_n$ where $X_j$ is the indicator function of the event that person $j$ regains her/his hat. So $E(Y)=E(X_1)+\cdots+E(X_n)$. But $E(X_j)$ is the probability that person $j$ regains his/her hat. What is that?

As a follow-up, you could use a similar method to work out the variance of $Y$.

Answer 2

You can calculate the expectation directly as pointed out, but if you were interested in how to calculate the probabilities:

There are four hats, and four people, so there are $4 \times 3 \times 2 \ \times 1 = 24$ possible assignments of the hats. Let's use the notation $ADCB$ which is the assignment in which the first person got hat A, second person got hat D, third person got hat C..

Out of these $24$ possible assignments, there is only one assignment in which they all get their respective hats, that is: ABCD, which therefore has a probability of $1/24$

How many assignments in which three get the correct hat? Well, if 3 have the correct hat, the last hat must also be given to its respective owner, so the only case where this is true is again ABCD, so the probability of only $3$ correct hats is zero.

How many assignments in which exactly two get the correct hat? We can fix two of the hats and see how many spots there are left, for example, lets fix AB, then the only way to proceed is to assign ABDC, so there is only only one allocation that works given that we fixed two hats. Now, how many ways are there to fix 2 hats, $4C2 = 6$, and so we have $6$ cases of only two correct hat allocations, $6/24$

Continue the logic to find the remaining probabilities..