7
$\begingroup$

Many people will be familiar with the set up of this problem: you have an aeroplane with 100 seats, and 100 passengers who have been allocated unique seats. The first passenger forgets their ticket, and so takes a random seat. The remaining passengers enter the plane. If their seat is empty, they take it. If it is occupied, they take a random seat on the plane.

At this point, the question that is usually asked it "what is the probability that the 100th person gets their allocated seat". This was asked here.

My question is a bit different. By the time all the passengers have boarded what is the expected number of passengers in the wrong seat? I have seen many people ask this as a follow up question to the first on some other online forums, but there doesn't appear to be a convincing answer anywhere.

Attempt:

Looking at smaller sized planes, we can come up with a conjecture than for a plane of size $n$, we have $$\text{expectation}=\begin{cases}1+\frac12+\cdots+\frac1{n-1}&n\text{ is even}\\\frac12+\frac13+\cdots+\frac1n&n\text{ is odd}\end{cases}$$

When trying to compute the expectation for even $n$ as a sum, we get a very complicated expression, of the form $$\frac1n\left(2\sum_{i=1}^{n-1}\frac1i+3\sum_{i\ne j,i,j=1}^{n-1}\frac1{ij}+4\sum_{i\ne j\ne k,i,j,k=1}^{n-1}\frac1{ijk}\cdots\right)$$

How can we derive the result I have conjectured?


$\small\text{Edit:}$

$\small\text{The conjecture was wrong in the odd case - the expectation is always equal to }\small\sum_{i=1}^{n-1}\frac1i\small\text{whether }n\small\text{ is even or odd. (As shown by the answers and @Akababa's comment)}$

$\endgroup$
2
  • $\begingroup$ But when $n=3$ I got $\frac32$ $\endgroup$
    – Akababa
    Aug 9, 2018 at 1:43
  • $\begingroup$ @akababa the answers given don't seem to assume anything about it being even, so I suppose you're right... $\endgroup$
    – John Doe
    Aug 9, 2018 at 8:14

2 Answers 2

5
$\begingroup$

Let $X_k$ be the number of incorrect seats occupied by passenger $k$. Obviously $X_k$ is either $0$ or $1$; by this answer we have $$P(X_k=1)=\frac1{n+2-k}\quad\hbox{for $k=2,3,\ldots,n$}\ ;$$ hence $$E(X_k)=0\cdot P(X_k{=}0)+1\cdot P(X_k{=}1)=\frac1{n+2-k}\ .$$ Similarly, $$E(X_1)=\frac{n-1}n=1-\frac1n\ .$$ The total number of passengers in the wrong seat is $T_n=X_1+\cdots+X_n$, and by linearity its expected value is $$E(X_1)+E(X_2)+E(X_3)+\cdots+E(X_n) =\Bigl(1-\frac1n\Bigr)+\frac1n+\frac1{n-1}+\cdots+\frac12\ ,$$ that is, $$E(T_n)=1+\frac12+\cdots+\frac1{n-1}\ ,$$ provided $n>1$.

$\endgroup$
3
$\begingroup$

Each configuration is associated to a cycle like $1\mapsto 5\mapsto 8\mapsto 72\mapsto 1$, meaning that the first person takes the fifth place, the fifth person takes the eighth place, $\ldots$, the $72$th persone takes the first place. If this occurs any other person besides $1,5,8,72$ takes his/her place. The probability that $1\mapsto 5\mapsto 8\mapsto 72\mapsto 1$ occurs is $\frac{1}{101-1}\cdot\frac{1}{101-5}\cdot\frac{1}{101-8}\cdot\frac{1}{101-72}$ and by this way there are four people in the wrong place.

The probability that $0$ people are in the wrong place is $\frac{1}{100}$.
The probability that just $1$ person is in the wrong place is zero.
The probability that $2$ people are in the wrong place (configurations $1\mapsto m\mapsto 1$) is given by $\frac{1}{100}$ times the sum of $\frac{1}{101-k}$ for $k$ that goes from $2$ to $100$, i.e. by the coefficient of $x^2$ in

$$ g(x)=\frac{x}{101-1}\left(1+\frac{x}{101-2}\right)\cdot\left(1+\frac{x}{101-3}\right)\cdot\ldots\cdot\left(1+\frac{x}{101-100}\right).$$ Similarly, the probability that $k\geq 2$ people are in the wrong place is given by the coefficient of $x^k$ in $g(x)$. In particular the average value of the number of people in the wrong place is given by $$ \sum_{k\geq 2} k\cdot [x^k]g(x) = \left.\frac{d}{dx}\left(g(x)-\frac{x}{100}\right)\right|_{x=1}=g'(1)-\frac{1}{100}=\frac{g'(1)}{g(1)}-\frac{1}{100}.$$ On the other hand $\log(g(x))=\log(x)-\log(100)+\log\left(1+\frac{x}{99}\right)+\ldots+\log\left(1+\frac{x}{1}\right)$, hence

$$ \frac{g'(x)}{g(x)}=\frac{1}{x}+\frac{1}{99+x}+\frac{1}{98+x}+\ldots+\frac{1}{1+x} $$ and $\frac{g'(1)}{g(1)}$ equals the $100$th harmonic number $H_{100}$.
It follows that the wanted average value is $H_{99}\approx 5.17738$.

The same argument works for any other number of seats $s\geq 3$ and it does not depend on the parity of the number of seats. By considering $g''(x)$ you may also compute the variance of the random variable $W$ giving the number of people in the wrong place:

$$\operatorname{Var}[W]=\mathbb{E}[W^2]-\mathbb{E}[W]^2 = -H_{s-1}^2+\sum_{n\geq 2}n^2\cdot [x^n]g(x) $$ equals $$ -H_{s-1}^2+H_{s-1}+g''(1) = H_{s-1}-H_{s-1}^2+H_s^2+\left.\frac{d}{dx}\left(\frac{g'(x)}{g(x)}\right)\right|_{x=1}$$ such that $$\operatorname{Var}[W]=H_{s-1}\left(1+\frac{2}{s}\right)-H_{s-1}^{(2)}. $$ For large values of $s$ the distribution of $W$ is very well approximated by a Poisson distribution.

$\endgroup$
2
  • $\begingroup$ I liked this answer too, since it seemed more intuitive to me to start in a similar way with those sums. The trick with derivatives was very neat, though I did not spot this (or think to define such a $g(x)$). I accepted the other answer though since it was more elementary though. Thanks for the answer! $\endgroup$
    – John Doe
    Aug 9, 2018 at 10:39
  • $\begingroup$ +1. Would you care to derive your claim in the last sentence, which I have posed as a question math.stackexchange.com/q/3256953/64809? $\endgroup$
    – Hans
    Jun 10, 2019 at 2:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .