Probability · Markov chains and random walks · Hard
The nineteenth passenger
Twenty passengers board a twenty-seat plane one at a time, each holding a ticket for a different seat. The first passenger ignores the ticket and sits in a seat chosen uniformly at random from all twenty. Every later passenger sits in their own seat if it is free, and otherwise in a seat chosen uniformly at random from those still free. What is the probability that the nineteenth passenger to board sits in their own seat?
Answer and solution
Answer
2/3 ≈ 0.6667
Solution
Of three seats (the first passenger's, the nineteenth's, the twentieth's) the one chosen first settles it, and each is equally likely to be first.
A random chooser who takes the first passenger's seat ends the trouble: everyone after sits correctly. One who takes the twentieth's seat leaves only the twentieth passenger displaced, so the nineteenth sits correctly. One who takes the nineteenth's seat displaces the nineteenth. Any other choice passes the problem to a later passenger with all three seats still free. By symmetry each of the three is first with probability 1/3, so the nineteenth passenger sits correctly with probability 2/3.
Markov chains and random walks comes up in 4 firms' roundsCitadel Securities · D. E. Shaw · Jump Trading · +1
These 6 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.