Return to Answer

Solution using conditional probability: we have seen that if seat $1$ is chosen before the last passenger is seated, then that passenger sits in their assigned seat; if seat $N$ is chosen before the last passenger is seated, then the last passenger is displaced and must take seat $1$. Let $E_k$ be the event that the $k$th passenger to be seated is the first to take one of seats $1$ and $N$. Then $$ \Pr(\text{$N$ gets their assigned seat})=\sum_{k=1}^{N-1}\Pr(\text{$k$ sits in $1$}\mid E_k)\Pr(E_k)=\frac{1}{2}\sum_{k=1}^{N-1}\Pr(E_k)=\frac{1}{2}. $$ Diagrammatically, this calculation is shown below. The probability that $N$ gets their assigned seat is the sum of the probabilities that one of passengers $1$ through $N-1$ takes seat $1$.

Solution using conditional probability: we have seen that if seat $1$ is chosen before the last passenger is seated, then that passenger sits in their assigned seat; if seat $N$ is chosen before the last passenger is seated, then the last passenger is displaced and must take seat $1$. Let $E_k$ be the event that the $k$th passenger to be seated is the first to take one of seats $1$ and $N$. Then $$ \Pr(\text{$N$ gets their assigned seat})=\sum_{k=1}^{N-1}\Pr(\text{$k$ sits in $1$}\mid E_k)\Pr(E_k)=\frac{1}{2}\sum_{k=1}^{N-1}\Pr(E_k)=\frac{1}{2}. $$ Diagrammatically, this calculation is shown below. The probability that $N$ gets their assigned seat is the sum of the probabilities that each of passengers $1$ through $N-1$ takes seat $1$.

Solution using conditional probability: we have seen that if seat $1$ is chosen before the last passenger is seated, then that passenger sits in their assigned seat; if seat $N$ is chosen before the last passenger is seated, then the last passenger is displaced and must take seat $1$. Let $E_k$ be the event that the $k$th passenger to be seated is the first to take one of seats $1$ and $N$. Then $$ \Pr(\text{$N$ gets their assigned seat})=\sum_{k=1}^{N-1}\Pr(\text{$k$ sits in $1$}\mid E_k)\Pr(E_k)=\frac{1}{2}\sum_{k=1}^{N-1}\Pr(E_k)=\frac{1}{2}. $$

Solution using conditional probability: we have seen that if seat $1$ is chosen before the last passenger is seated, then that passenger sits in their assigned seat; if seat $N$ is chosen before the last passenger is seated, then the last passenger is displaced and must take seat $1$. Let $E_k$ be the event that the $k$th passenger to be seated is the first to take one of seats $1$ and $N$. Then $$ \Pr(\text{$N$ gets their assigned seat})=\sum_{k=1}^{N-1}\Pr(\text{$k$ sits in $1$}\mid E_k)\Pr(E_k)=\frac{1}{2}\sum_{k=1}^{N-1}\Pr(E_k)=\frac{1}{2}. $$ Diagrammatically, this calculation is shown below. The probability that $N$ gets their assigned seat is the sum of the probabilities that one of passengers $1$ through $N-1$ takes seat $1$.

Solution using a bijection between cycles: (This completes a final, needed step in hunter's answer dated Dec. 4 2013.) The seating process results in a permutation of the passengers, and this permutation always consists of a single cycle containing passenger $1$ followed by displaced passengers, an ascending order. So for $N=100$ the cycle $(1,46,53,75,88)$ represents the situation where passenger $1$ displaces passenger $46$, $46$ displaces $53$, $53$ displaces $75$, $75$ displaces $88$, and $88$ sits in passenger $1$'s seat. Passengers $89$ and up, and passenger $100$ in particular, will sit in their assigned seats. The cycle $(1,46,53,75,88,100)$ represents a similar situation, except that passenger $88$ displaces passenger $100$. Passengers $89$ through $99$ will sit in their assigned seats, and passenger $100$ will have only one choice of seat: passenger $1$'s seat.

Solution using a bijection between cycles: (This completes a final, needed step in hunter's answer.) The seating process results in a permutation of the passengers, and this permutation always consists of a single cycle containing passenger $1$ followed by displaced passengers, an ascending order. So for $N=100$ the cycle $(1,46,53,75,88)$ represents the situation where passenger $1$ displaces passenger $46$, $46$ displaces $53$, $53$ displaces $75$, $75$ displaces $88$, and $88$ sits in passenger $1$'s seat. Passengers $89$ and up, and passenger $100$ in particular, will sit in their assigned seats. The cycle $(1,46,53,75,88,100)$ represents a similar situation, except that passenger $88$ displaces passenger $100$. Passengers $89$ through $99$ will sit in their assigned seats, and passenger $100$ will have only one choice of seat: passenger $1$'s seat.