Lost Boarding Pass
July 21, 2020
We have today a fun little problem from probability:
On a sold-out flight, 100 people line up to board the plane. The first passenger in the line has lost his boarding pass but was allowed in, regardless. He takes a random seat. Each subsequent passenger takes his or her assigned seat if available, or a random unoccupied seat, otherwise. What is the probability that the last passenger to board the plane finds his seat unoccupied?
Your task is to determine the requested probability, either by reasoning mathematically or by writing a program to demonstrate the probability. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Here’s a solution in Python.
from fractions import Decimal import random def board(num_seats=100): """Returns True if the last passenger takes their assigned seat""" assignments = list(range(num_seats)) random.shuffle(assignments) # Assign seat for initial passenger randomly initial = random.sample(range(num_seats), 1)[0] assignments.pop() # and remove that passenger's assignment occupied = {initial} unoccupied = {x for x in range(num_seats) if x != initial} while len(assignments) > 1: seat = assignments.pop() if seat in occupied: seat = random.sample(unoccupied, 1)[0] unoccupied.remove(seat) occupied.add(seat) assert len(assignments) == len(unoccupied) == num_seats - len(occupied) == 1 return unoccupied.pop() == assignments.pop() trials = 1_000_000 numerator = sum(board() for _ in range(trials)) print(Decimal(numerator) / trials)Output:
Here’s a mathematical solution (using 0-indexing) followed by another Python solution.
For any passenger after the initial 0th passenger, the probability that they take the 99th passenger’s seat is the probability that an earlier passenger took their seat times the probability that they take the 99th passenger’s seat from the remaining seats.
The 0th passenger has a 1/100 probability of taking the 99th passenger’s seat.
The 1st passenger has a (1/100 * 1/99 = 1/9900) probability of taking the 99th passenger’s seat, which is the probability that the 0th passenger took the 1st passenger’s seat, times the probability that the 1st passenger takes the 99th passenger’s seat from the 99 remaining seats.
The probability that the 2nd passenger’s seat is taken is (1/100 + 1/9900 = 1/99), the probability that either passenger 0 or passenger 1 is in their seat. Given the inherent symmetry of the problem, 1/100 and 1/9900 are the same probabilities from the earlier calculations above. Since the events are mutually exclusive, the probabilities can be added. Thus, the 2nd passenger has a (1/99 * 1/98 = 1/9702) probability of taking the 99th passenger’s seat, which is the probability that the 0th passenger or 1st passenger took the 2nd passenger’s seat, times the probability that the 2nd passenger takes the 99th passenger’s seat from the 98 remaining seats.
A pattern emerges where for x > 0, the probability that passenger x’s seat is taken is 1/(100 – x + 1), and the the probability that the x’th passenger is in the 99th passenger’s seat is (1/(100 – x + 1))*(1/(100 – x)).
Here’s the corresponding sequence that shows the probability of the x’th passenger being in the 99th passenger’s seat.
Similar reasoning can be used for a different number of initial seats, where 1/2 would still be the resulting probability that the last passenger’s seat is taken.
Here’s a dynamic programming solution in Python. It calculates the sequence described above and returns the last element. The probability of a passenger’s seat being taken is calculated as a cumulative sum from prior elements in the sequence, as I wrote this prior to noticing the pattern above (which permits a simpler program).
from fractions import Fraction def prob(n=100): array = [None] * n array[0] = Fraction(1, n) for i in range(1, n): array[i] = sum(array[j] for j in range(i)) * Fraction(1, n - i) return array[-1] print(prob())Output:
Here’s another version, which utilizes the pattern described in my last post (as opposed to the less efficient dynamic programming approach).
Rather than only returning the probability that the last passenger’s seat is taken, it returns the sequence of probabilities for each passenger being in the last passenger’s seat.
The last value is the probability that the last passenger occupies their own seat (the answer to the question).
from fractions import Decimal, Fraction def probs(n=100): array = [None] * n array[0] = Fraction(1, n) for i in range(1, n): array[i] = Fraction(1, 100 - i + 1) * Fraction(1, 100 - i) return array for idx, p in enumerate(probs()): print(f'{idx} {p} ({round(p.numerator / Decimal(p.denominator), 8)})')Output:
The update from my dynamic programming solution to the solution in my last post was based on a pattern that I noticed, where for x > 0, the probability that passenger x’s seat is taken is 1/(100 – x + 1).
Induction can alternatively be used to prove the following equation, which is a more principled justification for using that formula.
The base case is x = 2, and the inductive step shows that the equation for x = k implies the equation for x = k + 1.