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!
- 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.
- 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}$.
- 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$ .
- 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.
Best Answer
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?