There was a popular interview question from a while back: there are $n$ people getting seated an airplane, and the first person comes in and sits at a random seat. Everyone else who comes in either sits in his seat, or if his seat has been taken, sits in a random unoccupied seat. What is the probability that the last person sits in his correct seat?
The answer to this question is $1/2$ because everyone looking to sit on a random seat has an equal probability of sitting in the first person's seat as the last person's.
My question is: what is the expected number of people sitting in their correct seat?
My take: this would be $\sum_{i=1}^n p_i$ where $p_i$ is the probability that person $i$ sits in the right seat..
$X_1 = 1/n$
$X_2 = 1 – 1/n$
$X_3 = 1 – (1/n + 1/n(n-1))$
$X_4 = 1 – (1/n + 2/n(n-1) + 1/n(n-1)(n-2))$
Is this correct? And does it generalize to $X_i$ having an $\max(0, i-1)$ term of $1/n(n-1)$, a $\max(0, i-2)$ term of $1/n(n-1)(n-2)$ etc?
Thanks.
Best Answer
Sorry for the second answer (I will delete the first one):
I will aim to show that the expected number of people sitting in their correct seats is given by:
$$ n-1-\frac12-\frac13-\dots-\frac1{n-1}=n-H_{n-1} $$
To do this, we will first find the expected number of people in the wrong seats, which we shall call $s_n$.
Suppose passenger number $1$ sits in seat $i\ne1$. At this point, passengers $2,\dots,i-1$ all sit in their correct seats. We now have a situation where there are $n-i+1$ empty seats left, and passenger $i$ is going to sit in a random seat.
This is very similar to the situation we had at the start, just with fewer seats. The only difference is that passenger $i$'s seat is taken, and there's a seat (seat $1$) which belongs to none of the people standing up.
This is a bit of a problem, so we'll change things around a bit. We'll pretend that seat number $1$ doesn't, in fact, belong to any of the passengers. So wherever passenger $1$ sits, they're in the wrong seat. We'll use the letter $t_n$ to denote the expected number of people sitting in the wrong seat if seat $1$ doesn't belong to anybody.
What we now get, is that the situation after passenger $1$ has sat in seat $i\ne1$, and passengers $2,\dots,n-1$ have sat in their correct seats is exactly the same as the situation at the beginning, but with $n-i+1$ seats rather than $n$: there's a passenger about to choose a random seat which doesn't belong to him (I decided the sex of passenger $i$ by tossing a coin): there's a seat ($1$) which doesn't belong to anybody, and the rest of the seats belong to the remaining passengers. So at this point, the expected number of passengers sitting in the wrong seats is $1+t_{n-i+1}$: $1$ for passenger $1$, who's sat in the wrong seat, and $t_{n-i+1}$ because afterwards we're in exactly the same situation as before, but with $n-i+1$ seats.
What if passenger $1$ sits in seat $1$? Then all the remaining passengers sit in the right seats, so the expected number of people sitting in the wrong seats at the end is just $1$ (remember, passenger $1$ no longer owns seat $1$).
Passenger $1$ chooses between the $n$ seats at random, so this gives us the recurrence:
\begin{align} t_1 &= 1\\ t_n &= 1+\frac1n\sum_{i=2}^nt_{n-i+1} = 1+\frac1n\sum_{i=1}^{n-1}t_i \end{align}
We are now ready to prove the following:
Claim: $t_n=H_n$
Proof of claim: induction on $n$. $\mathbf{n=1}$ : $t_1=1=H_1$.
$\mathbf{n>1}$ : $t_n=1+\frac1n\sum_{i=1}^{n-1}t_i=1+\frac1n\sum_{i=1}^{n-1}H_i$ (by the inductive hypothesis). A well known identity involving harmonic numbers tells us that:
$$ \sum_{i=1}^{n-1}H_i = nH_{n-1}-(n-1) $$
So $t_n=1+H_{n-1}-1+\frac1n=H_n$. $\Box$
How do we get from here to $s_n$? The difference now is that passenger $1$ does own seat $1$, which means that the answer will be smaller by $1$ if and only if passenger $1$ sits in seat $1$. Since passenger $1$ sits in seat $1$ with probability $\frac1n$, we need to subtract $\frac1n$ from $t_n$ to get $s_n$:
$$ s_n=t_n-\frac1n=H_n-\frac1n=H_{n-1} $$
Finally, to get the expected number of people in the right seats, we subtract $s_n$ from $n$ to get:
$$ n-H_{n-1} $$
Note 1: Since $H_n$ grows logarithmically, the proportion of people sitting in their correct seats converges to $1$ as $n\to\infty$.
Note 2: I still find this proof rather unsatisfying, since it uses the identity $\sum_{i=1}^{n-1}H_i = nH_{n-1}-(n-1)$, which I still don't really understand. I'm sure it's easy enough to prove by induction, but if someone could come up with a really nice explanation of why that works, it might yield an even slicker proof of this fact.