# Expected Number of Happy Passengers

### Solution 1

Assuming the plane seats $n$ passengers, let $F(n)$ the expectation of the the number of unhappy passengers and $F^*(n)$ is a similar expectation, conditioned on the first passenger getting a wrong seat, so that the two are related as shown below:

$\displaystyle F(n)=\frac{1}{n}\cdot 0+\frac{n-1}{n}\cdot F^*(n).$

$F^*(n)$ is thus the number of unhappy passengers in an $n-seats$ plane with an a priori misplaced seat.

Let's now start from the beginning but counting passengers from the end of the line. When the $n^{th}$ passenger (the one without the boarding pass) enters the plane, he chooses any of the $n$ available seats - in particular, his own - with probability $\displaystyle \frac{1}{n}.$ With the same probability he lands in the seat of the $k^{th}$ passenger (from the end of the line). If this happens, all the passengers entering before the $k^{th}$ seat owner will be happy. The latter will have a choice of $k$ seats, of which one is that of the first passenger. With the probability of $\displaystyle \frac{1}{k}$ he'll choose the latter, making the total of $2$ of unhappy passengers and with the probability of $\displaystyle \frac{k-1}{k}$ he'll choose a seat of one of the passengers yet in line, thus adding $1$ to the count of unhappy passengers and reducing the problem to a $k-seats$ plane (with one seat a priori misplaced) which may be described as adding to the total expectation of unhappy passengers the quantity

\displaystyle\begin{align} \frac{2}{n}+\frac{k-1}{k}(1+F^*(k)+1)&=\frac{k+1}{k}+\frac{k-1}{k}F^*(k)\\ &=\frac{k+1}{k}+F(k). \end{align}

Summing up for all possible choices of $k,$

$\displaystyle F(n)=\frac{1}{n}\cdot 0+\frac{1}{n}\sum_{k=1}^{n-1}\left(\frac{k+1}{k}+F(k)\right).$

or, $\displaystyle n\cdot F(n)=\sum_{k=1}^{n-1}\left(\frac{k+1}{k}+F(k)\right).$ For $F(n-1)$ we have a similar expression:

$\displaystyle (n-1)\cdot F(n-1)=\sum_{k=1}^{n-2}\left(\frac{k+1}{k}+F(k)\right).$

Substitution of the latter into the former produces $nF(n)=(n-1)F(n-1)+\frac{n+1}{n}+F(n-1),$ or $\displaystyle F(n)=F(n-1)+\frac{1}{n-1}.$ With $F(1)=0$ we are able to solve the recurrence:

$\displaystyle F(n)=\sum_{k=1}^{n-1}\frac{1}{k},$

so that $\displaystyle F(100)\approx 5.177.$

### Solution 2

The passenger number $n$ counting from the end, gets his/her own seat with the probability $\displaystyle \frac{n}{n+1}.$ (This is because the previous passenger was facing $n+1$ choices, and it does not matter whether the $n^{th}$ passenger seat was among them - another previous passenger could have taken it. See also Solution 4 in the predecessor problem.) Define the random variable $X(n)$ that takes value $1$ with the probability $\displaystyle \frac{n}{n+1}$ and value $0$ with probability $\displaystyle \frac{1}{n+1}.$ Then the expected value $\displaystyle E(X(n))=\frac{n}{n+1}.$

The first (to board the plane) has the probability of $\displaystyle \frac{1}{100}$ to be happy. Then (using the linearity of the expectation) the expected value $E(100)$ of happy passengers is $\displaystyle E(100)=\frac{1}{100}+\sum_{n=1}^{99}E(X(n))=\sum_{n=1}^{99}\frac{n}{n+1}+\frac{1}{100}\approx 94.823.$

The number of unhappy passengers is then about $100-94.823=5.177.$

### Acknowledgment

This is a follow-up on the previous problem; the problem above was suggested to me by Konstantin Knop and to him by Alexander Pipersky. Konstantin also supplied his solution to the problem (Solution 1).