I am reading Ross probability book, where a solution to the Problem of the Hats is provided using conditional probabilities. To set it up, we have to picture a few people merrily throwing their hats up and then randomly taking them back. Let me define:
- $E_n$, event that no one ends with their own hats after throwing n hats
- F, first person ends with their own hat
- G, after person 1 takes hat $j$, person $j$ takes hat 1
The argument on the book goes as follows. We start by decomposing the probability of E using F:
$$
P(E_n) = P(E_n|F)P(F) + P(E_n|F^c)P(F^C) = P(E_n|F^c)P(F^c) \\
= P(E_n|F^c)\frac{n – 1}{n}
$$
where the second equality follows from $P(E_n|F) = 0$. Now we consider event G:
- If G occurs, then $P(E_nG|F^c) = P(E_{n-1})$, since person $j$ will take the extra hat 1, thereby leaving $n-1$ people to choose their own $n-1$ hats
- If G does not occur, then the book suggests that:
$$P(E_nG^c|F^c) = P(E_{n-2})/ (n-1)$$
But no explanation is provided. I would like to know why.
Shortly, why is the probability that $n-2$ people do not choose their own hats, when choosing $n-2$ hats from which two are not their own, equal to the expression above?
Best Answer
There is either a transcription error or a typo.
With the work shown, the meaning of $G$ should have been "After person $1$ takes hat $j$ the corresponding person $j$ does not take hat $1$", that is to say the meaning of $G$ was accidentally negated.
Now... all of the work and explanation up to $\Pr(E_n) = \Pr(E_n\mid F^c)\cdot \frac{n-1}{n}$ is correct.
Expanding further as $\left(\Pr(E_nG\mid F^c)+\Pr(E_nG^c\mid F^c)\right)\cdot\frac{n-1}{n}$ is correct.
From here as we explore $\Pr(E_nG\mid F^c)$ and $\Pr(E_nG^c\mid F^c)$ we need to fix the original post and use the correct meaning of $G$.
In the case of $\Pr(E_nG\mid F^c)$ this is the probability where given that the first person did not get their own hat that everyone manages to get a hat different than their own and that our person whose hat was taken by the first person (Who I will call person $j$) gets a hat different than the first person's hat.
For this, we can imagine instead that we renumber our people and hats. Everyone's number stays the same and everyone's hat stays the same with the exception of our person $j$ whose new number becomes number $1$. The hat which was original numbered $1$ remains named number $1$. (If desired, we can also now rename all numbers larger than $j$ with the number one less than what they were).
In doing so, we now have $n-1$ people remaining, each of which have one hat still available that they need to avoid. The nuance here is that who was originally called person $j$ has a hat to avoid that was not the original hat they needed to avoid, not in order to ensure that the event $E_n$ happens but rather to ensure that the event $G$ happens.
We find that $\Pr(E_nG\mid F^c) = \Pr(E_{n-1})$
In the case of $\Pr(E_nG^c\mid F^c)$ this is the probability where given that the first person did not get their own hat that our person whose hat was taken by the first person (person $j$) gets the first person's hat and everyone else remaining avoids their own hat.
Well, we could expand this further as $\Pr(E_nG^c\mid F^c) = \Pr(G^c\mid F^c)\Pr(E_n\mid G^cF^c)$.
The chance that person $j$ gets the first person's hat is simply going to be $\frac{1}{n-1}$. The probability that everyone avoids their own hat given the first person and the $j$'th person swapped hats is going to be $\Pr(E_{n-2})$ as the remaining people are in an identical scenario as though those other two people didn't exist.
Putting all of this together, we find the recurrence relation for our probability as:
$$\Pr(E_n) = \frac{n-1}{n}\cdot\left(\Pr(E_{n-1})+\frac{1}{n-1}\cdot\Pr(E_{n-2})\right)$$
This approach to understanding the problem is equivalent to the recurrence relation for derangements which reads as:
$$!n = (n-1)\cdot (!(n-1)+!(n-2))$$