Airplane Boarding Problem

Worked Solution

How to Think About It: The first thing to notice is that this process has a surprising recursive structure. When passenger 1 sits in a random seat, three things can happen: they sit in seat 1 (their own -- everyone else is fine), they sit in seat $n$ (passenger $n$ is definitely displaced), or they sit in seat $k$ for some $2 \leq k \leq n-1$ (which "transfers" the randomness to passenger $k$, who now plays the role of the confused passenger). This recursive structure is what makes the problem tractable.

Quick Estimate: Consider $n = 3$. Passenger 1 picks seat 1, 2, or 3 each with probability $1/3$. If seat 1: passenger 3 gets seat 3. If seat 3: passenger 3 does not get seat 3. If seat 2: passenger 2 is displaced and picks randomly from $\{1, 3\}$ -- passenger 3 gets seat 3 with probability $1/2$. So $P = 1/3 + 0 + (1/3)(1/2) = 1/2$. The pattern $P = 1/2$ seems to hold for all $n \geq 2$.

Approach: We prove part 1 by induction/recursion, then use indicator variables for part 2.

Formal Solution:

*Part 1: $P(\text{passenger } n \text{ gets seat } n) = 1/2$ for all $n \geq 2$.*

Let $P_n$ denote this probability. Condition on passenger 1's choice:

• Passenger 1 picks seat 1 (prob $1/n$): everyone sits correctly, so passenger $n$ gets seat $n$. Contribution: $1/n$.
• Passenger 1 picks seat $n$ (prob $1/n$): passenger $n$ cannot sit in seat $n$. Contribution: $0$.
• Passenger 1 picks seat $k$ for $k \in \{2, \dots, n-1\}$ (prob $1/n$ each): passengers $2, \dots, k-1$ find their seats available and sit normally. Passenger $k$ finds their seat taken and must pick uniformly from the remaining $n - k + 1$ seats ($\{1, k+1, k+2, \dots, n\}$). Now passenger $k$ is in exactly the same situation as passenger 1 was, but in a reduced problem of size $n - k + 1$. So the probability passenger $n$ gets seat $n$ is $P_{n-k+1}$.

This gives the recursion:

$$P_n = \frac{1}{n} + \frac{1}{n} \sum_{k=2}^{n-1} P_{n-k+1} = \frac{1}{n} + \frac{1}{n} \sum_{m=2}^{n-1} P_m$$

Base case: $P_2 = 1/2$ (passenger 1 picks seat 1 or seat 2 with equal probability).

Inductive step: assume $P_m = 1/2$ for all $2 \leq m \leq n-1$. Then:

$$P_n = \frac{1}{n} + \frac{1}{n} \cdot (n-2) \cdot \frac{1}{2} = \frac{1}{n} + \frac{n-2}{2n} = \frac{2 + n - 2}{2n} = \frac{n}{2n} = \frac{1}{2}$$

So $P_n = 1/2$ for all $n \geq 2$.

*Part 2: $E[\text{number of displaced passengers}]$.*

Let $X_k = 1$ if passenger $k$ does not sit in seat $k$. We want $E\left[\sum_{k=1}^n X_k\right] = \sum_{k=1}^n P(X_k = 1)$.

• $P(X_1 = 1) = (n-1)/n$ (passenger 1 picks a seat other than seat 1).
• For $2 \leq k \leq n$: $P(X_k = 1) = \dfrac{1}{n-k+2}$.

To see why: passenger $k$ is displaced if and only if seat $k$ is already occupied when they board. Trace the chain of random choices (passenger 1, then each displaced passenger in turn) up to the moment passenger $k$ boards. While the chain lands in $\{2, \dots, k-1\}$, the disruption just gets passed along. Passenger $k$'s fate is settled the first time a random chooser picks a seat in the set $\{1, k, k+1, \dots, n\}$: picking seat 1 ends all displacement (passenger $k$ is safe), picking a seat in $\{k+1, \dots, n\}$ parks the disruption with a passenger who boards after $k$ (again safe), and picking seat $k$ displaces passenger $k$. All $n-k+2$ of these seats are still empty while the chain is running before passenger $k$ boards, and every random choice is uniform over the remaining empty seats -- so the first seat hit within this set is uniform over its $n-k+2$ members. Hence

$$P(X_k = 1) = \frac{1}{n-k+2}, \qquad 2 \leq k \leq n.$$

(Consistency check: $k = n$ gives $1/2$, matching part 1. A tempting wrong guess is $P(X_k = 1) = 1/k$, which would give $E = \frac{n-1}{n} + H_{n-1} - \frac{1}{2}$, i.e. $5/3$ at $n = 3$; direct enumeration at $n = 3$ gives $3/2$, refuting it.)

Therefore:

$$E\left[\sum_{k=1}^n X_k\right] = \frac{n-1}{n} + \sum_{k=2}^{n} \frac{1}{n-k+2}$$

Substituting $m = n - k + 2$ (as $k$ runs from $2$ to $n$, $m$ runs from $n$ down to $2$):

$$E[\text{displaced}] = \left(1 - \frac{1}{n}\right) + \sum_{m=2}^{n} \frac{1}{m} = \left(1 - \frac{1}{n}\right) + (H_n - 1) = H_n - \frac{1}{n} = H_{n-1}$$

where $H_n = \sum_{k=1}^n 1/k$ is the harmonic number.

Sanity check at $n = 3$: $P(X_1) = 2/3$, $P(X_2) = 1/3$, $P(X_3) = 1/2$, so $E = 2/3 + 1/3 + 1/2 = 3/2 = H_2$. Exhaustive enumeration of all seatings for $n = 3, 4, 5, 6$ confirms $E = H_{n-1}$ exactly ($3/2$, $11/6$, $25/12$, $137/60$).

For large $n$, this is approximately $\ln n + \gamma \approx \ln n + 0.577$, where $\gamma \approx 0.5772$ is the Euler-Mascheroni constant.

Answer: (1) The probability that passenger $n$ sits in seat $n$ is exactly $1/2$ for all $n \geq 2$. (2) The expected number of displaced passengers is $H_{n-1} = \sum_{k=1}^{n-1} \frac{1}{k}$, which grows as $\ln n$.