At a party, 100 guests check their hats at the entrance. Mark is the first person to leave. He is drunk and takes away a hat at random. [duplicate]

Question

Each succeeding person takes his own hat if it is not taken. If it is taken, he picks a hat at random from the remaining hats. What is the probability that the last person gets their own hat?

I'm just a college student trying to make my way in life. This is a homework question, so I'd appreciate some hints! Thank you all very much.

What I've attempted so far: I tried to make a conditional probability tree for all the possibilities that Mark could have. I.e., he could pick the first guest's hat, the second guest's hat, etc., or he could pick his own hat, with each 'branch' having probability $\frac{1}{100}$.

Then the first guest would have 99 hats to choose from. If Mark picked out the first guest's hat, then the first guest has $\frac{1}{99}$ probability of choosing any hat from the remaining. (or, $\frac{1}{99}$ probability of choosing the last hat).

Continuing on this logic, I thought that the probability that the last guest doesn't get their hat would be the sequence $\frac{1}{100} + \frac{1}{100 * 99} + \frac{1}{100 * 99 * 98}$ and so on and so forth.

i.e P(the last person does not get their hat) = ${1} - \sum_{k=0}^{100} \frac{k!}{100!}$

I know this is wrong, because just because an nth guest gets their own hat does not mean that the last guest gets theirs, if I'm making any sense.

Answer 1

After Mark is gone, we have a situation with $n=99$ guests and one wrong hat. When a person leaves, a situation with $n$ guests and $1$ wrong hat turns into a situation with $n-1$ guests and $1$ wrong hat or no wrong hat. Of course, $n$ guests with no wrong hat simply turns into $n-1$ persons with no wrong hat.

Now, the probability of $(n,1)$ turning into $(n-1,0)$ is $\frac 1n$ (for the hatless person to be the person leaving) times $\frac 1n$ (for that person to pick the one wrong hat). Hence the probability of $(n,1)$ turning into $(n-1,1)$ is $1-\frac 1{n^2}$. Therefore, the probability of getting straigt from $(99,1)$ to $(1,1)$ (which is the only way for the last person to get a wrgon hat) is $$ \left(1-\frac1{99^2}\right) \left(1-\frac1{98^2}\right) \left(1-\frac1{97^2}\right)\cdots \left(1-\frac1{2^2}\right)$$ As $1-\frac1{n^2}=\frac{(n+1)(n-1)}{n^2}$, this can be rewritten as $$ \frac{100\cdot 98}{99\cdot 99}\cdot\frac{99\cdot 97}{98\cdot 98}\cdot \frac{98\cdot 96}{97\cdot 97}\cdots \cdot\frac{3\cdot 1}{2\cdot 2}$$ Most terms cancel. All that remains is $\frac{100\cdot 1}{99\cdot 2} $. The final answer is one minus that, i.e., $$\frac{49}{99}. $$

Edit: One second reading, I notice that Mark takes a random hat, not a wrong hat. So it may happen with $\frac1{100}$ that Mark "accidentally" picks the right hat. Therefore, the corrected result is $$ \frac1{100}\cdot 1+\frac{99}{100}\cdot \frac{49}{99}=\frac 12$$ As you can see from the simple result, there is probably a much smarter way to arrive at it than to blindly compute all exact probabilities as above. Can you find it?