I was reading up on the linearity of expectations on http://www.geeksforgeeks.org/linearity-of-expectation/.
One of the problems given and explained was the hat-check problem:
Let there be group of n men where every man has one hat. The hats are redistributed and every man gets a random hat back. What is the expected number of men that get their original hat back?
The solution was that 1 person is expected to get the correct hat since
Pr[Guest 1 gets correct hat] + Pr[Guest 2 gets correct hat] + … + Pr[Guest n gets correct hat]
= 1/n + 1/n + … + 1/n = n(1/n) = 1
What I am not understanding is, why wouldn't it be 1/n + 1/(n-1) + 1/(n-2) + …
since the "pool of hats" is getting smaller with each guest receiving a hat?
Best Answer
The number $\dfrac 1 {n-1}$ would be the conditional probability that the second guest gets the right hat given that the first guest gets the right hat.
But that is not what is needed here; what is needed is the marginal (or "unconditional") probability that the second guest gets the right hat, in ignorance of whether the first guest go the right hat or not. Since there are $n$ hats and all of them are equally likely to be the one that that guest gets, the probability is $1/n$.
If you simply must work with probabilities conditional on the first guest's outcome, you can do this: \begin{align} & \Pr(\text{2nd guest gets the right hat}) \\[10pt] = {} & \phantom{{}+{}} \Pr(\text{1st right})\cdot\Pr(\text{2nd right} \mid \text{1st right}) \\ & {} + \Pr(\text{1st gets 2nd guest's hat})\cdot\Pr(\text{2nd right}\mid\text{1st gets 2nd guest's hat}) \\ & {} + \Pr(\text{1st gets someone else's hat})\cdot\Pr(\text{2nd right}\mid \text{1st gets someone else's hat}) \\[12pt] = {} & \left(\frac 1 n \cdot \frac 1 {n-1}\right) + \left(\frac 1 n \cdot 0\right) + \left(\frac{n-2} n \cdot \frac 1 {n-1}\right) \\[12pt] = {} & \frac 1 n. \end{align}