An experimental approach to the drunk passenger problem
Published:
An apparently common question in quant interviews is as follows:
Suppose that 100 passengers are boarding an airplane, all with assigned seats. The first passenger is drunk, and sits in a random seat. Each following passenger sits in their assigned seat, if it is available, and in a random seat otherwise. What is the probability that the last passenger sits in their assigned seat?
I just wanted to quickly write up what I thought were four nifty proofs, including one “experimental.”
First, you have to observe the fundamental recurrence. Let $p(n)$ be the probability that the last passenger sits in the correct seat given that there are $n$ passengers. It’s easy to check that $p(1) = 1$ and $p(2) = p(3) = 1/2$.
Suppose that there are $n$ passengers. If the drunk sits in his seat, then the probability of success is $1$. If the drunk sits in the $k$th person’s seat with $k > 1$, then the problem has been reduced to a drunk passenger with a total of $n  k + 1$ passengers. (After the drunk sits, passengers $2$ through $k  1$ sit, then passenger $k$ is so irate that they drink themselves into a stupor.) Therefore,
We now have a few ways to go about this.
Guessandcheck
It’s easy to see that $p(2) = p(3) = 1 / 2$, so maybe the sequence is just constant after $n = 2$? In principle we would want to compute a few more terms, but without a computer this gets hard to do in your head. We can jump straight to induction:
Dividing by $n + 1$ gives $1 / 2$, so $p(n)$ is constant beyond $n \geq 2$.
Smarter recurrences
There’s a standard trick to get rid of summations in recurrences, and in this case it works exceptionally well. We can replace $n$ with $n + 1$ in the fundamental recurrence, giving the following two equations:
Having the denominators on the righthand side is a little awkward, so let’s multiply them to the other side, then subtract the two equations:
Simplifying yields
and since $n$ is positive, we see that $p(n)$ is constant for $n \geq 2$.
True guessandcheck
The previous method works so well because $p(n + 1) = p(n)$ falls out, and the first guessandcheck method works because the induction is easy. However, I claim that the true guess and check method is even easier!
We know, a priori, that the sequence $p(n)$ defined by $p(2) = 1 / 2$ and
satisfies a linear recurrence with polynomial coefficients. (We just showed how to prove such a thing in the previous method. Even without getting supremely lucky, the result still holds.) Therefore, since $p(n) = 1 / 2$ for the first dozen terms or so (exercise!), it follows^{1} that $p(n) = 1 / 2$ for all $n \geq 2$.
Generating functions
This is an almost completely different way to do it.
Let $P(z) = \sum_{k \geq 2} p(k) z^k$. The fundamental recurrence can be rewritten as
for $n \geq 2$, and it is an easy application of wellknown generatingfunctionology that this implies
This is a linear differential equation, with general solution given by
for some constant $c$. It is easy to check that $P’‘(0) = 1$, and this gives $c = 0$. Thus
We should note that this approach is almost entirely mechanical. Computers can derive the differential equation and then solve it, almost unaided by humans.
Conclusions
I don’t know what this problem has to do with the stock market, but it sure is fun!

To be completely rigorous, we need to say, “and the order of the recurrence is no larger than $K$,” and then check $K$ terms, but at a glance we know that $K$ is certainly no more than ten, or whatever. ↩