Expected number of people sitting in the right seats.

Solution 1:

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.

Solution 2:

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

Solution 3:

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

Solution 4:

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