Will Someone Be Sitting In Your Seat On The Plane?

There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?

The Riddler, FiveThirtyEight(original post)

Solution

Follow the trail of displacement. The first passenger sits somewhere at random. If he happens to choose seat $1$ (his own), every later passenger including you then finds their seat free. If he chooses seat $100$ (yours), you are out of luck. If he chooses some seat $k$ in between, then passengers $2,\dots,k-1$ all sit normally, and passenger $k$ arrives to find their seat taken and becomes the new random chooser, facing exactly the same situation among the remaining seats: seat $1$ and seat $100$ are still the only two that matter.

So the whole process is a chain of random choosers, and it ends the first time one of them picks seat $1$ (you win) or seat $100$ (you lose). At each such choice those two seats are both still available and are equally likely to be the one picked. By this symmetry the two endings are equally likely, and your seat is free with probability $$\boxed{\tfrac12}.$$ The argument never used the number $100$, so the answer is $\tfrac12$ for any plane with at least two seats.

The computation

Simulate the actual boarding: the first passenger takes a uniformly random seat, each later passenger takes their own seat if free and otherwise a uniformly random open one, and record whether the last seat survives for you. Running it for a small and a large cabin shows the frequency sits at $\tfrac12$ regardless of size.

import numpy as np
def last_seat_free(n, runs, seed=0):
    rng = np.random.default_rng(seed); ok = 0
    for _ in range(runs):
        taken = [False] * n
        taken[rng.integers(n)] = True        # first passenger sits at random
        for p in range(1, n - 1):            # passengers 2 .. n-1
            if not taken[p]:
                taken[p] = True              # own seat free: sit in it
            else:
                free = [s for s in range(n) if not taken[s]]
                taken[rng.choice(free)] = True   # else a random open seat
        ok += not taken[n - 1]               # is your seat still free?
    return ok / runs
print(last_seat_free(10, 200_000))           # ~0.5
print(last_seat_free(100, 40_000))           # ~0.5