The Lost Boarding Pass

Question

One hundred passengers board a full flight in order. The first passenger has lost their boarding pass and sits in a uniformly random seat. Every passenger after that takes their own seat if it is free, and otherwise picks uniformly at random among the seats still empty. What is the probability the hundredth passenger ends up in their own assigned seat?

Accepted Answer

The two-seat symmetry Call the disrupted seat 1 (the first passenger's own seat) and the seat we care about 100. The process ends in exactly one of two ways: somebody eventually sits in seat 1, or somebody eventually sits in seat 100. Once seat 1 is taken, every remaining passenger finds their own seat free, including passenger 100. Once seat 100 is taken by an impostor, passenger 100 certainly does not get it. Now the key step. Consider any passenger who is forced to choose at random, starting with passenger 1. Among the seats still empty, seats 1 and 100 are both available whenever the game is still undecided, and a uniform choice is equally likely to land on either. The choice may also land on some other seat, which simply passes the problem along to a later passenger and repeats the same situation with a smaller set. So the contest between "seat 1 gets taken first" and "seat 100 gets taken first" is decided by a sequence of fair coin flips between those two outcomes, with irrelevant detours in between. By symmetry the two are equally likely. P(textpassenger 100 gets their own seat) = frac12. Check it on small cases With two passengers: passenger 1 picks a seat at random, so pas

The Lost Boarding Pass

Problem

Your answer

Hints

More Probability to train on