## Lost Boarding Pass

### July 21, 2020

We begin with a function that simulates the boarding process:

```(define (board n)
(let loop ((pax 0) (free (range n)) (seated (list)))
(cond ((= pax n) seated) ; return in reverse order
((or (= pax 0) (not (member pax free)))
(let ((seat (fortune free)))
(loop (+ pax 1) (remove seat free) (cons seat seated))))
(else (loop (+ pax 1) (remove pax free) (cons pax seated))))))```

Let’s run that a few times and see what happens:

```> (board 10)
(9 8 7 6 5 4 3 2 1 0)
> (board 10)
(9 8 0 6 5 4 3 2 1 7)
> (board 10)
(0 8 7 6 5 4 3 2 1 9)
> (board 10)
(0 8 7 6 5 4 9 3 1 2)```

In the first scenario, the first passenger (zero, with the lost boarding pass) randomly chooses the correct seat; everyone else also gets to sit in their assigned seat. In the second scenario, the first passenger sits in seat seven, passengers one through six sit in their assigned seats, passenger seven randomly sits in seat zero, and passengers eight and nine sit in their assigned seats. In the third scenario, the first passenger sits in seat nine, passengers one through eight sit in their assigned seats, and passenger nine sits in the seat the first passenger should have occupied. In the fourth scenario, the first passenger chooses seat two, passenger one sits in his own seat, passenger two sits in seat three, passenger three sits in seat nine, passengers four through eight sit in their assigned seats, and the last passenger sits in the seat the first passenger should have occupied. The last passenger sits in his assigned seat half the time, depending on whether or not some passenger has taken the seat assigned to the first passenger (the one who lost his boarding pass).

We simulate boarding the airplane many times to demonstrate the probability is 50%:

```(define (sim n)
(let loop ((n n) (own-seat 0))
(if (zero? n) own-seat
(if (= (car (board 100)) 99)
(loop (- n 1) (+ own-seat 1))
(loop (- n 1) own-seat)))))```
```> (sim 1000)
502```

So in 1000 simulations, the last passenger was in his assigned seat 502 times. Running that program five times yielded 490, 520, 503, 495 and 502, demonstrating the 50% probability.

The code is assembled at https://ideone.com/uJGGx3, but it doesn’t run, for some reason that is not clear to me. I assure you the code does run in Chez on my regular machine.

Pages: 1 2

### 4 Responses to “Lost Boarding Pass”

1. Daniel said

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)
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)
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:

```0.499728
```
2. Daniel said

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.

```1/100, (1/100)*(1/99), (1/99)*(1/98), (1/98)*(1/97), ..., (1/3)*(1/2), (1/2)(1/1)
```

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 = 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:

```1/2
```
3. Daniel said

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 = 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:

```0 1/100 (0.01000000)
1 1/9900 (0.00010101)
2 1/9702 (0.00010307)
3 1/9506 (0.00010520)
4 1/9312 (0.00010739)
5 1/9120 (0.00010965)
6 1/8930 (0.00011198)
7 1/8742 (0.00011439)
8 1/8556 (0.00011688)
9 1/8372 (0.00011945)
...
90 1/110 (0.00909091)
91 1/90 (0.01111111)
92 1/72 (0.01388889)
93 1/56 (0.01785714)
94 1/42 (0.02380952)
95 1/30 (0.03333333)
96 1/20 (0.05000000)
97 1/12 (0.08333333)
98 1/6 (0.16666667)
99 1/2 (0.50000000)
```
4. Daniel said

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.

```1/(n – x + 1) = 1/n + (1/n) * (1/(n-1)) + (1/(n-1)) * (1/(n-2)) + ... + (1/(n – x + 2)) * (1/(n – x + 1))
```

The base case is x = 2, and the inductive step shows that the equation for x = k implies the equation for x = k + 1.