Expected number of people sitting in the right seats. 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.
 A: 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.  
A: Your overall approach looks technically correct, you are using linearity of expectation for counting and then writing down a formula for each $p_i$ (although it seems you switched notation and started using $X_i$ in your formulas instead of $p_i$).  However I believe the equation for $X_4$ i.e. $p_4$ is actually
$$X_4 = 1 - (1/n + 1/n(n-1) + 1/n(n-2) + 1/n(n-1)(n-2))$$
and the generalization for $X_i$ for arbitrary $i$ is obtained by your basic reasoning, just writing down the probability for each way the $i$th person's seat might already be taken, taking into account each case e.g. for $X_4$ the term $1/n(n-2)$ corresponds to the case that the first person takes the third person's seat, and the third person takes the fourth person's seat.  I'm not sure if/what an easy formula would be for when you add up all the $X_i$ terms to get the total answer.  However it is easy to see that the general rule to get the equation for $X_i$ when $i > 1$ is to have $X_i = 1 - q_i$ where $q_i$ is the sum of all terms you can make of the form $1/n(n-k_1)(n-k_2)\ldots$ where you have $0$ or more distinct values $k_j$, and $k_1 < k_2 \ldots < i-1$.
A: I found this question and the answer might be relevant.
Seating of $n$ people with tickets into $n+k$ chairs with 1st person taking a random seat
The answer states that the probability of a person not sitting in his seat is $\frac{1}{k+2}$ where $k$ is the number of seats left after he takes a seat. This makes sense because for person $i$, if anyone sits in chairs $1, i+1, ... n$ then he must sit in his own seat, so the probability of that happening is $\frac{n-i+1}{n-i+2}$. So $k = 0$ for the last person and $k =  n-1$ for the second person. The answer then should just be
$1/n + \sum_{i = 2}^{n} \frac{n-i+1}{n-i+2}$
A: Correct answer to incorrect question: please see second answer
The answer is $\frac{1}{2}$ as was said.
The general pattern is that for $n$ people, there is a $\frac{1}{n}$ probability of success, $\frac{1}{n}$ probability of failure, and an $\frac{n-2}{n}$ probability that the problem repeats itself on the $n-1$ scale.
Case $n=2$: The probability that the first picks the correct seat is $\frac{1}{2}$, and then the last person sits in proper seat with probability 1. The probability that the first picks the wrong seat is $\frac{1}{2}$, and then the last person sits in proper seat with probability 0. So the probability in total is:
$$
\frac{1}{2}\cdot1+\frac{1}{2}\cdot0=\frac{1}{2}
$$
Case $n=3$: The probability that the first picks the correct seat is $\frac{1}{3}$, and then the last person sits in proper seat with probability 1. The probability that the first picks the last person's seat is $\frac{1}{3}$, and then the last person sits in proper seat with probability 0. The probability that the first picks the middle person's seat is $\frac{1}{3}$, and now there is a $\frac{1}{2}$ that the second person picks the last seat or the first seat (Case 2) since two non-last people switching seats means everyone else takes their own seat. So:
$$
\frac{1}{3}\cdot1+\frac{1}{3}\cdot0+\frac{1}{3}\cdot\frac{1}{2} = \frac{2}{6} + \frac{1}{6} = \frac{3}{6} = \frac{1}{2}
$$
Proof by induction.
Assume it holds true for $n$ that the probability of the last person sitting in the proper seat is $\frac{1}{2}$. Now if there are $n+1$ people, we have a $\frac{1}{n+1}$ chance that the last-seat probability is 1 (correct seat), a $\frac{1}{n+1}$ chance that the last-seat probability is 0 (last seat), and an $\frac{n-1}{n+1}$ chance that the probability is $\frac{1}{2}$, since we know the $n$ case.
$$
\frac{1}{n+1} + \frac{0}{n+1} + \frac{n-1}{2(n+1)}\\
=\frac{2}{2(n+1)}+\frac{n-1}{2(n+1)}\\
=\frac{n+1}{2(n+1)}\\
=\frac{1}{2}
$$
QED
A: Now that I have cleaned my glasses, I'll try again. Thank you, Lord Farin.
Some observations.
The answer must be greater than 1. The probability that the first person, regardless of the number of people, sits in the proper seat is $\frac{1}{n}$, and there are $n$ people, so that expectation is 1. Even if the first person sits in the wrong seat, there is non-zero probability of other people sitting in the correct seat, so the answer must be greater than or equal to 1, and I'm pretty sure equality only exists in the case $n=2$.
There is some form of recurrence going on here. Enumerating the possibilities, I get (if I haven't erred):
$$
E_2 = \frac{1}{2}\cdot 2 + \frac{1}{2}\cdot 0 = 1\\
E_3 = \frac{1}{3}\cdot 3 + \frac{2}{3}\left[\frac{1}{2}\cdot 1 + \frac{1}{2}\cdot 0\right] = 1+\frac{1}{3}=\frac{4}{3}\\
E_4 = \frac{1}{4}\cdot 4 + \frac{3}{4}\left[\frac{1}{3}\cdot2 + \frac{2}{3}\left[\frac{1}{2}\cdot 1 + \frac{1}{2}\cdot 0\right]\right] = 1+\frac{3}{4}\cdot\left(\frac{2}{3}+\frac{1}{3}\right)=\frac{7}{4}\\
E_5 = \frac{1}{5}\cdot 5 + \frac{4}{5}\left[\frac{1}{4}\cdot3 + \frac{3}{4}\left[\frac{1}{3}\cdot2 + \frac{2}{3}\left[\frac{1}{2}\cdot 1 + \frac{1}{2}\cdot 0\right]\right]\right] = 1+\frac{4}{5}\left(\frac{3}{4} + \frac{3}{4}\cdot\left(\frac{2}{3}+\frac{1}{3}\right)\right)=\frac{11}{5}\\
$$
Let $E_k$ be the expected number of people in the correct seats when the starting population is k. The relationship seems to be:
$$
E_k = 1 + \left(E_{k-1} - 1 + \frac{k-2}{k-1}\right)\frac{k-1}{k}
$$
The first 1 is the expected value of person 1 taking the correct seat. The next term is broken into two parts. If the first person did not take the correct seat, then the second person can "fix" the error by swapping and taking the previous person's seat, leaving the remaining $n-2$ people their proper seats. If the second person also takes the wrong seat, the problem restarts on the $n-1$ scale. In both the latter two cases, there is "one less" correct seat than the initial, since the previous term used up a seat with an incorrect choice. If the above supposition is correct, the expected value would just be the sum of the recurrence relation applied to $n$ or $\sum_{k=1}^n E_k$. 
Generating the first few terms using this relationship gives:
$$
1, 1, \frac{4}{3}, \frac{7}{4}, \frac{11}{5}, \frac{16}{6}, \frac{22}{7}, \frac{29}{8}, \frac{37}{9}, \frac{46}{10}, \ldots
$$
The numerator is a quadratic and the denominator is just $n$ so the expected value should be:
$$
E_n = \frac{n^2-n+2}{2n}
$$
Edit: The long-term proportion of people sitting in the proper seats intuitively would be $$
\lim_{n \to \infty} \frac{E_n}{n}\\
=\lim_{n \to \infty} \frac{n^2-n+2}{2n^2}\\
=\frac{1}{2}
$$
Which dovetails nicely with the long-term probability of the last person sitting in his or her proper seat.
A: This is old (and answered) but let me add another quick approach. The space of valid seat arrangements is equivalent to the set of cyclic permutations $(j_1\cdots j_k n)$ on the set $[n] = \{1,\dots,n\}$ that are increasing in the sense that $j_1<\cdots<j_k<n$. Given a set $J\subset [n-1]$ denote by $s_J$ the unique seating arrangement corresponding to the increasing cyclic permutation of $[n]$ with cycle $J\cup\{n\}$. The map $J\mapsto s_J$ is bijective into the space of seating arrangements and the probability law of the problem statement is defined on this space by the relations
\begin{align*}
P(s=s_J) = \frac{1}{n}\prod_{j\in J}\frac{1}{j}.
\end{align*}
See also Byron's answer here to the original interview question.
Since $s_J$ changes precisely $|J|+1$ seats unless $|J|=0$, in which case $s_J$ changes no seats, the expected number of seat changes is
\begin{align*}
-\frac{1}{n} + \frac{1}{n}\sum_{J\subset [n-1]} (|J|+1)\prod_{j\in J}\frac{1}{j}.
\end{align*}
The sum on the right is $F'(1)+F(1)$ for the generating function
\begin{align*}
F(t) &= \frac{1}{n}\sum_{J\subset [n-1]} t^{|J|}\prod_{j\in J}\frac{1}{j} = \frac{1}{n}\sum_{J\subset [n-1]}\prod_{j\in J} \frac{t}{j} = \frac{1}{n} \prod_{j=1}^{n-1}\left(1+\frac{t}{j}\right).
\end{align*}
Now $F(1)=1$ (either because it is the total probability that $s=s_J$ for some $J\subset [n-1]$ or by computation) and
\begin{align*}
F'(t) = \sum_{j=1}^{n-1} \frac{1}{j}\left(1+\frac{t}{j}\right)^{-1}F(t),
\end{align*}
so $F'(1)+F(1) = H_n$ and the expected number of changed seats is $H_n-1/n=H_{n-1}$. Since the total number of seats is always $n$, the expected number of unchanged seats is therefore $n-H_{n-1}$.
A: It's 1. The probability that the $i$th person is in the right seat is $1/n$ for every $i$. This is clearly true for $i=1$, for $i=2$ you get $$P(\text{1st person not in 2nd person's seat, 2nd person in right seat}) = \frac{n-1}{n} \frac{1}{n-1} = 1/n,$$ and so on down the line as you can check for yourself. 
