Content
Probability
Description
There are N passengers boarding on an airplane one by one, with their tickets indicating their seats.
However, the first passenger lost his ticket, he decide to randomly choose a seat(could be his own, or one of the others’). Every following passenger will take their own seat if not taken, otherwise randomly choose one from the vacancies.
What’s the probability that the last(Nth) passenger got his own seat?
Analysis
It’s easy to infer the answer for N=1 and N=2, which are 1 and \(\frac{1}{2}\).
However, the general answer is not \(\frac{1}{N}\). Because it’s obvious that the \(1^{st}\) passenger will take his own seat at the odd of \(\frac{1}{N}\), leaving all the rest passengers get their own seats. So the answer should be lager than that because it is still possible for the \(N^{th}\) to get his own seat if the \(1^{st}\) takes other’s.
Let’s denote the answer as \(P(N)\) and the probability that randomly choose from n others’ seats leaveing the \(N^{th}\) getting his own as \(Q(n)\).
For the \(1^{st}\):
- if takes seat 1 at \(\frac{1}{N}\), then the rest are all set, the last can definately get his own seat.
- if takes seat 2 at \(\frac{1}{N}\), then the \(2^{nd}\) will choose seat 1 at \(\frac{1}{N-1}\), and choose others at \(Q(n-2)\).
- if takes seat i at \(\frac{1}{N}\), then the \(i^{th}\) will choose seat 1 at \(\frac{1}{N -i+1}\), and choose others at \(Q(n-i)\).
\(P(N)=\frac{1}{N}+\frac{N-1}{N}Q(n-1)\)
\(P(N)=\frac{1}{N}+\frac{1}{N}(\frac{1}{N-1}+Q(n-2))+\frac{1}{N}(\frac{1}{N-2}+Q(n-3))\cdots+\frac{1}{N}(\frac{1}{2}+Q(1))\)
\(Q(1)=0\)
Result
We derivative the chain rule of \(Q(i)\):
\(Q(n)=Q(n-1)+\frac{1}{n^2}\\
Q(1)=0\)
Then we can get:
\(Q(n)=\Sigma_{i=2}^{n}\frac{1}{i^2}\\
P(N)=\frac{1}{N}(1+(N-1)\Sigma_{i=2}^{N-1}\frac{1}{i^2})\)