Although Tanae Rao was just a high school graduate when he wrote his solution below, it's the most clear out of the solutions I read.

1. I don't understand the step, that I colored in red. Why must Seats 2-99 be occupied, before Passenger 100 boards the plane?

2. Why couldn't one of Passengers 2-99 sit in Seat 1?

3. Why couldn't one of Passengers 2-99 sit in Seat 100?

From this point forward, I refer to passengers and their assigned seats in order of entry, such that the first passenger to board is Passenger 1 and the last to board is Passenger 100. Similarly, Seat 1 is the assigned seat of Passenger 1, and so forth.

Fact: Passenger 100 will sit in either Seat 100 (his assigned seat) or Seat 1.

I best understand this observation through the perspective of each passenger boarding in-between the first and last. There are two possibilities for Passengers 2–99.

1. The passenger’s assigned seat is empty. They sit in that seat.
2. The passenger’s assigned seat is occupied. They sit in some other seat at random.

After each of these passengers takes a seat on the plane, it is necessarily true that their assigned seat is occupied. Either it was previously unoccupied (option 1 above) and they sit in it, or it was already occupied (option 2).

Before the last passenger boards the plane, $\color{red}{\text{the assigned seats of Passengers 2–99 are occupied}}$. At this point, 99 people (including Passenger 1) have taken a seat, meaning that only one seat remains vacant.

Since there is one seat left and Seats 2–99 are guaranteed to be occupied, the vacant seat must be Seat 1 or Seat 100. It is impossible for both Seat 1 and Seat 100 to be occupied before the last passenger boards, because that would mean all 100 seats on the plane are occupied by only 99 passengers.

Fact: there is an equal probability of the last passenger sitting in Seat 1 and Seat 100.

By the time the last passenger boards, the outcome of the lost boarding pass problem is already determined, as there is only one seat for them to choose. We must therefore look at the decisions faced by Passengers 1–99.

For Passenger 1, there is equal probability of choosing any of the 100 seats. By extension, the probability of him choosing his own assigned seat and the probability of him choosing the last passenger’s assigned seat are equal.

The only way Passengers 2–99 sit in Seat 1 or Seat 100 is if their assigned seat is occupied. In this case, there is also an equal probability of sitting in any available seat.

While both Seat 1 and Seat 100 are unoccupied, it is equally probable that either seat will be chosen. After one of these two seats is occupied, the other seat is guaranteed to remain unoccupied until the last passenger boards. The probability that Seat 100 is occupied by a previous passenger is 1/2.

Here's the statement of the question from Blitzstein, Introduction to Probability (2019 2 ed), Chapter 1, Exercise 61, p 42.

61. There are 100 passengers lined up to board an airplane with 100 seats (with each seat assigned to one of the passengers). The first passenger in line crazily decides to sit in a randomly chosen seat (with all seats equally likely). Each subsequent passenger takes their assigned seat if available, and otherwise sits in a random available seat. What is the probability that the last passenger in line gets to sit in their assigned seat? (This is a common interview problem, and a beautiful example of the power of symmetry.)

posted over 3 years ago

CC BY-SA 4.0

3y ago

DNB‭

-107 reputation 73 1 -105 128