Return to Answer

OP failed to source. I emended typos.

Source Link

edit approved Jul 27, 2021 at 0:17

user53259

This problem appears in Blitzstein and Hwang'sBlitzstein's Introduction to ProbabilityProbability (Chapter 12019 2 ed) Ch 1, Exercise 61, p 42. There is a solution for it available online:Here's the answer from p 10 of the Selected Solutions PDF.

    Solution: The seat for the last passenger is either seat 1 or seat 100; for example, seat
42 can’t be available to the last passenger since the 42nd passenger in line would have
sat there if possible. Seat 1 and seat 100 are equally likely to be available to the last
passenger, since the previous 99 passengers view these two seats symmetrically. So the
probability that the last passenger gets seat 100 is 1/2.

Solution: The seat for the last passenger is either seat 1 or seat 100; for example, seat 42 can’t be available to the last passenger since the 42nd passenger in line would have sat there if possible. Seat 1 and seat 100 are equally likely to be available to the last passenger, since the previous 99 passengers view these two seats symmetrically. So the probability that the last passenger gets seat 100 is 1/2.

This solution doesn't really satisfy me, because I couldn't really get the symmetry argument and also I didn't understand why "seat 42 can't be available". I had to convince myself. Here's how I did itconvinced myself.

Let's assume that $P_1=S_{99}$. Again, note that there is a 1/n chance of this seat selection, same as all the other seats. When $P_2$ boards the plane, she is able to take her seat $P_2=S_2$. Similarly, $P_3=S_3$ and so on until $P_{98}=S_{98}$. Ok, now $P_{99}$ boards the plane and sees $S_1$ and $S_{100}$ are the only two available seats. Her own seat was taken by $P_1$. She now must randomly choose. Clearly, given the previous seating order there is now a 50/50 chance that either $P_{99}=S_{1}$ or $P_{99}=S_{100}$. If $P_{99}=S_{1}$ then $P_{100}$ gets to sit in her assigned seat ($P_{100}=S_{100}$), otherwise she must sit in seat 1, so $P_{100}=S_{100}$$P_{100}=S_{1}$. Note that the final 50/50 choice between $S_1$ and $S_{100}$ is the "game" that other answers have referred to here. It also provides the recursive base case that many answers here discuss. To see this, let's play another "game" and see what happens.

This problem appears in Blitzstein and Hwang's Introduction to Probability (Chapter 1). There is a solution for it available online:

    Solution: The seat for the last passenger is either seat 1 or seat 100; for example, seat
42 can’t be available to the last passenger since the 42nd passenger in line would have
sat there if possible. Seat 1 and seat 100 are equally likely to be available to the last
passenger, since the previous 99 passengers view these two seats symmetrically. So the
probability that the last passenger gets seat 100 is 1/2.

Let's assume that $P_1=S_{99}$. Again, note that there is a 1/n chance of this seat selection, same as all the other seats. When $P_2$ boards the plane, she is able to take her seat $P_2=S_2$. Similarly, $P_3=S_3$ and so on until $P_{98}=S_{98}$. Ok, now $P_{99}$ boards the plane and sees $S_1$ and $S_{100}$ are the only two available seats. Her own seat was taken by $P_1$. She now must randomly choose. Clearly, given the previous seating order there is now a 50/50 chance that either $P_{99}=S_{1}$ or $P_{99}=S_{100}$. If $P_{99}=S_{1}$ then $P_{100}$ gets to sit in her assigned seat ($P_{100}=S_{100}$), otherwise she must sit in seat 1, so $P_{100}=S_{100}$. Note that the final 50/50 choice between $S_1$ and $S_{100}$ is the "game" that other answers have referred to here. It also provides the recursive base case that many answers here discuss. To see this, let's play another "game" and see what happens.

This problem appears in Blitzstein's Introduction to Probability (2019 2 ed) Ch 1, Exercise 61, p 42. Here's the answer from p 10 of the Selected Solutions PDF.

Solution: The seat for the last passenger is either seat 1 or seat 100; for example, seat 42 can’t be available to the last passenger since the 42nd passenger in line would have sat there if possible. Seat 1 and seat 100 are equally likely to be available to the last passenger, since the previous 99 passengers view these two seats symmetrically. So the probability that the last passenger gets seat 100 is 1/2.

This solution doesn't satisfy me, because I couldn't get the symmetry argument and I didn't understand why "seat 42 can't be available". Here's how I convinced myself.

Let's assume that $P_1=S_{99}$. Again, note that there is a 1/n chance of this seat selection, same as all the other seats. When $P_2$ boards the plane, she is able to take her seat $P_2=S_2$. Similarly, $P_3=S_3$ and so on until $P_{98}=S_{98}$. Ok, now $P_{99}$ boards the plane and sees $S_1$ and $S_{100}$ are the only two available seats. Her own seat was taken by $P_1$. She now must randomly choose. Clearly, given the previous seating order there is now a 50/50 chance that either $P_{99}=S_{1}$ or $P_{99}=S_{100}$. If $P_{99}=S_{1}$ then $P_{100}$ gets to sit in her assigned seat ($P_{100}=S_{100}$), otherwise she must sit in seat 1, so $P_{100}=S_{1}$. Note that the final 50/50 choice between $S_1$ and $S_{100}$ is the "game" that other answers have referred to here. It also provides the recursive base case that many answers here discuss. To see this, let's play another "game" and see what happens.

Source Link

created Feb 18, 2020 at 18:06

Evan Zamir

This problem appears in Blitzstein and Hwang's Introduction to Probability (Chapter 1). There is a solution for it available online:

    Solution: The seat for the last passenger is either seat 1 or seat 100; for example, seat
42 can’t be available to the last passenger since the 42nd passenger in line would have
sat there if possible. Seat 1 and seat 100 are equally likely to be available to the last
passenger, since the previous 99 passengers view these two seats symmetrically. So the
probability that the last passenger gets seat 100 is 1/2.

Let's call the first passenger $P_1$. There are 100 possible seats $S_i\:(i=1,2...100)$ she can randomly select. First let's cover the two "edge" cases, seat 1 and seat 100. Suppose she selects $S_1$ by chance. For notation purposes we'll say $S_1=P_1$ using equality operator as seat selection. If this happens there is no change in seating order, $P_2=S_2$, $P_3=S_3$, and eventually $P_{100}=S_{100}$. In the other "edge" case, $P_1=S_{100}$. In this case it should be clear that $P_2=S_2$, $P_3=S_3$, and so on. When $P_{100}$ gets on the plane she realizes that her seat is taken and the only available option is $S_1$ so $P_1=S_1$. Notice that the probability of $P_{100}=S_1$ and $P_{100}=S_{100}$ are the same for these two cases. Further notice I am not saying the probability of each occurence is 1/2. Clearly the probability of each of these events is 1/100 or 1/n, where n is in general the number of seats. It will turn out that n does not matter due to symmetry, which will be the fundamental insight into this problem. For now let's continue with more concrete cases...

Let's assume that $P_1=S_{99}$. Again, note that there is a 1/n chance of this seat selection, same as all the other seats. When $P_2$ boards the plane, she is able to take her seat $P_2=S_2$. Similarly, $P_3=S_3$ and so on until $P_{98}=S_{98}$. Ok, now $P_{99}$ boards the plane and sees $S_1$ and $S_{100}$ are the only two available seats. Her own seat was taken by $P_1$. She now must randomly choose. Clearly, given the previous seating order there is now a 50/50 chance that either $P_{99}=S_{1}$ or $P_{99}=S_{100}$. If $P_{99}=S_{1}$ then $P_{100}$ gets to sit in her assigned seat ($P_{100}=S_{100}$), otherwise she must sit in seat 1, so $P_{100}=S_{100}$. Note that the final 50/50 choice between $S_1$ and $S_{100}$ is the "game" that other answers have referred to here. It also provides the recursive base case that many answers here discuss. To see this, let's play another "game" and see what happens.

Let's now assume that $P_1=S_{98}$. Similar to above, $S_1$ is left open, $P_2=S_2$, $P_3=S_3$ and so on until $P_{97}=S_{97}$. Now, $P_{98}$ boards the plane and see that $S_1$, $S_{99}$, and $S_{100}$ are available. Well, let's go through these 3 possible choices. Assume $P_{98}=S_1$. Now, $P_{99}=S_{99}$ and $P_{100}=S_{100}$. The "game" ends with Passenger 100 getting their assigned seat. Continuing, imagine $P_{98}=S_{100}$. In that scenario, $P_{99}=S_{99}$ and $P_{100}=S_1$. In this case the game ended with Passenger 100 sitting in Seat 1. Notice that the probability of each outcome was exactly the same. Ok, one last possibility. Let's imagine that $P_{98}=S_{99}$. Ahhhh, now we've "kicked" $P_{99}$ out of her seat, and when she boards the plane she must choose between $S_1$ and $S_{100}$. Hey wait a minute. Didn't we already cover that case? Yes! And so here we are. Hopefully, by now you can recognize the recursion in this problem, the base case, the symmetry, and the "game" that every single simulation will play out the same way with Passenger 100 having equal probability of sitting in Seat 1 or Seat 100, with absolutely zero probability of sitting anywhere else. Therefore P=1/2!

Tada!