The question is as follows:
In a group of $n>3$ people, everyone puts his or her hat in a box. The hats are mixed up. One by one, each person randomly pulls out a hat. The order in which everyone pulls out a hat is irrelevant. The processes stops when someone pulls out his or her hat, or until all of the hats are drawn. What is the probability that the second person who pulls out a hat chooses his or her own?
I know that the probability that no one picks their own hat as the group size $n$ approaches infinity is
$$\frac{1}{e} \approx .3679.$$
I also know that the expected value of people that choose their own hat is simply equal to $1.$
Lastly, the question is asking the probability of the second person choosing his or her hat. This means that the first person did $\textit{not}$ choose their own hat.
Does anyone know how to approach this problem? Am I thinking about information that is not needed?
Thanks in advance!
Best Answer
Yes you are thinking about information that is not needed. I think lulu's approach in the first comment is very good.
For the counting perspective, a different way to think about it is to ignore the idea that the process "stops" when someone gets their hat. So you have $n$ people $\{1,...,n\}$ and they will pick $n$ hats in some order, i.e. you are thinking about permutations of $\{1,...,n\}$.
You are interested in permutations $\sigma$ where $\sigma(1) \neq 1$ or $2$ (first person does not get their own hat or that of person 2) and $\sigma(2) = 2$ (second person does get their hat). You don't care which hats the other people would pick were the process to continue.