# 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.

-
Could the general probability not be, for $m>1$, $X_m=1-\left(\sum_{k=0}^{m-2}\binom{m-2}{k}\frac{(n-k-1)!}{n!}\right)$? Perhaps prove by induction? –  Alyosha Aug 10 '13 at 23:19
The MSE treatment of the original problem: math.stackexchange.com/questions/5595/taking-seats-on-a-plane –  Byron Schmuland Aug 23 '13 at 17:41

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.

-
There are a few things I do not follow in your explanation. Firstly, if passenger 1 sits in seat 1, the expected number of correct seats is n, because everyone sits in their correct seat if it is available, so excluding that possibility materially affects the answer. Secondly, it can be shown (see below where I answered the wrong question) that regardless of of the number of people, the probability that the last person sits in his or her proper seat is \frac{1}{2}. As any one person could be the last one, the long-term proportion should approach 1/2. In my attempt at a correct answer it does. –  Avraham Aug 23 '13 at 19:19
What do you mean by 'any one person could be the last one'? And why does that mean that the long term proportion should approach $1/2$? –  Donkey_2009 Aug 24 '13 at 10:54
If you read my answer carefully, you will see that I do not exclude the possibility that passenger $1$ sits in seat $1$; instead, I treat it separately. The long term proportion approaches $1$, so I think you might be answering a different question. –  Donkey_2009 Aug 24 '13 at 10:55

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$.

-
Oops, sorry about the $p_i \rightarrow X_i$ change. And you are write about $X_4$. Thanks for your answer, that seems correct. –  narcissa Aug 10 '13 at 23:59

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}$

-
The answer (see my post) is $n-H_{n-1}$, but this is probably the right way to go. –  Donkey_2009 Aug 11 '13 at 0:56

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

-
I feel bad for all your work, but the question was the expected number of people in correct seats. –  Lord_Farin Aug 23 '13 at 8:17

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.

-
Your recurrence is wrong, as are your values for $E_k$ where $k\ge3$. I'm not really sure what your argument is; are you free to take this to chat some time today? –  Donkey_2009 Aug 24 '13 at 12:06
Sure. If I'm wrong, I'm eager to learn why and how to correct it. If you want, you can e-mail me directly as well; thank you. –  Avraham Aug 26 '13 at 1:18
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.
This answer is wrong. The probability that the second person is in the right seat is $1$ if the first person didn't sit in their seat. I think kilgol was assuming that people just sit in their seats randomly, whereas they in fact always sit in their own seat if it is free (and they're not the first person). –  Donkey_2009 Aug 11 '13 at 0:49