Probability riddle

A probability question that seems to be quite common in quant interviews is the airplane boarding problem. Imagine that there are $100$ people in a queue waiting to board a plane with $100$ seats numbered seats. The first passenger takes a random seat. Passenger $n>1$ will either take seat $n$ if it is not already taken or take a random available seat. What is the probability that the last passenger is seated? You are typically expected to answer such a question in $2$-$5$ minutes. Take some time if you want to try this problem on your own. 

Passengers queueing to board a plane

Without much thinking, many would expect the probability of such an event to be rather small. Perhaps in the order of $1/100$? In this problem intuition can be misleading.

Let's consider simple cases. Instead of boarding $100$ people, consider $2$ instead. If there are $2$ seats, the probability that the second passenger takes the second seat is the probability that the first passenger does not take it i.e. $1/2$. If there are $3$ people boarding the flight, then 

• if passenger $1$ takes seat $1$, passenger $2$ and $3$ will take seats $2$ and $3$ respectively, so $\mathbb{P}=1$
• if passenger $1$ takes seat $3$, clearly passenger $3$ can not unseat them, so  $\mathbb{P}=0$, and
• if passenger $1$ takes seat $2$, then passenger $2$ will randomly take seat $1$ or $3$, so  $\mathbb{P}=1/2$.

Since passenger $1$ takes their seat uniformly at random, the probability that the last passenger takes the last seat is $1/3\cdot 1+1/3\cdot 1/2+1/3\cdot 0=1/2$. Repeating the same exhaustive argument for the case of $4$ passengers, gives the same probability $1/2$. Naturally, the conjecture is that the probability is $1/2$ regardless of the size of the problem. 

Simulation 

First we need to verify the conjecture by running the python simulation code. The "counts" list is set so that counts[$i$] is the number of simulations where the last passenger got seat $i$. The total number of simulations is $10000$. Of these, $5022$ had the last passenger getting the last seat and $4978$ getting the first seat. None of the other seats where feasible for the last passenger. This complies with the conjecture and strengthens it by suggesting that the last passenger will either get the first seat of the last seat, each event happening with probability $1/2$. 

Solution 1

Consider running a simulation of the boarding process. When some passenger takes the first seat, it is guaranteed that the last passenger will take the last seat. Clearly if  some passenger takes the last seat, the last passenger won't be able to. Therefore, the simulation ends when some passenger takes the first or last seat.

Suppose that passenger $S$ has to take a random seat (start with $S=1$). Seats $2,\dots ,S-1$ have already been taken, but the first seat is still available (otherwise the simulation would have terminated). Passenger $S$ can take the first or last seat with the same probability or move to seat $S^{\prime }$ with $S<S^{\prime }<100$. Then passenger $S^{\prime }$ will have to take a random seat. The same argument needs to be applied a finite number of passengers $1=S<S^{\prime }<\cdots <S^{(n)}<100$. At any stage, the probability of choosing the first or last seat is the same, so the probability is $1/2$.

Solution 2 (Strong induction)

Let $n$ be the number of people boarding the plane and the number of seats available. The inductive statement is 

$$\mathcal{P}(n):p_n:=\mathbb{P}(\text{last passenger gets last seat})=\frac{1}{2},n\ge 2$$

The base case for $n=2$ has already been proved.

For $n+1$, condition on the random seat of the first passenger. If they do not take the first or last seat, they will take seat $S$ and the problem would reduce in size to $n+1-S$. Hence, by strong induction

$$p_{n+1}=\frac{1}{n+1}(1+\frac{1}{2}+\cdots +\frac{1}{2}+0)=\frac{1}{2}$$