Taking Seats on a Plane with Seat Bumping

Question

A line of $n$ passengers is waiting to board an airplane with $n$ seats. The first passenger, Joe, to board the plane forgets their assigned seat and chooses a seat uniformly at random. As the remaining $n-1$ passengers board the plane, one at a time, if Joe is sitting in their seat, Joe gets up and chooses another unoccupied seat, uniformly at random. This is repeated for all $n-1$ passengers until all $n$ passengers have boarded and are sitting in their assigned seat.

This is a problem I am trying to solve for a practice exam. I was not given solutions to the practice exam and would like a way to double check my answers. I have written my justifications for each subproblem. I was unable to solve the last subproblem. Any comments on what is correct/incorrect or if my explanation was incorrect/incomplete would be very helpful. With the help of the commenters below, all solutions for the subproblems are now correct. Thank you!

1. what is the exact probability that Joe never moves after choosing his first seat?

• Answer: $1/n$
• Explanation: The only way Joe will never have to move after randomly choosing his first seat is if he correctly selected his assigned seat when boarding the plane. Thus, there is $1$ correct seat to choose out of the $n$ unoccupied seats.

2. What is the exact probability that the $k$th passenger to board the plane asks Joe to move?

• Answer: $\frac{1}{n-k+2}$
• Explanation: A passenger boarding the plane is independent of previously boarded passengers, so we only need to consider the current state of the plane. Before the $k$th passenger boards the plane, there are $n-k+2$ unoccupied seats from which Joe could have chosen to sit. Of these seats, one seat belongs to the $k$th passenger, so the likelihood of the $k$th passenger asking Joe to move is just $\frac{1}{n-k+2}$.

3. What is the exact expected number of times Joe changes seats?

• Answer: $log(n) - 1$
• Explanation: I am very unsure about this one. I took $\sum_{i=2}^{n}E[X_i]$ where $X_k$ is an indicator variable. $X_k = 1$ when Joe is asked to move by the $k$th passenger and $X_k=0$ otherwise. This simplifies to: $\sum_{i=2}^{n}E[X_i] = \sum_{i=2}^{n}Pr[i$th passenger asks Joe to move$] = \sum_{i=2}^{n}\frac{1}{n-i+2} = \frac{1}{n} + \frac{1}{n-1} + \dots + \frac{1}{2} = H_n - 1 = log(n) - 1$ .

4. What is the exact probability that Joe moves exactly once?

• Answer: $\sum_{i=2}^{n}\frac{1}{n}*\frac{1}{n-i+1}$
• Explanation: This was answered below by a user; however, the summation enumerates all of the different ways Joe could be asked to move by a passenger. $\frac{1}{n}$ is the probability that Joe sits in a particular passenger $i$'s seat and $\frac{1}{n-i+1}$ is the probability of Joe correctly choosing his assigned seat when he moves.
• Intuition: I would like to use $C(n-1, 1)p(1-p)^{n-2} = (n-1)p(1-p)^{n-2}$, but I'm not sure what $p$ would be here because $p$ changes as each passenger boards the plane.

Answer 1

Your reasoning for part $3$ is completely correct (though the equation $H_n-1=\log n-1$ is only approximately true).

Hint for part $4$:

You should enumerate all of the ways that Joe can move exactly once, then add up the probabilities of each occurring. Let us number all $n-1$ people besides Joe from $1$ to $n-1$, in the order they sit down. It could be the case that Joe initially takes person $1$'s seat, and then moves to Joe's seat. The probability of this is $\frac1{n}\cdot \frac1{n-1}$. What are the other ways, and the other probabilities?