Planes Over Holy Island

Just in case you were wondering, I have indeed realised that there’s been a disproportionate amount of US political smack-talk going around in these parts lately. I’m very much hoping to redress the balance. A wee bit of lunatic dialogue here, some X-Men related musings there (I really will get round to Gambit’s SS v X soon; I’m just still finding it hard to put together full sentences about him without the phrase GAY PINK BODYARMOUR LOLZ spontaneously appearing), and, contained herein, a little bit of probability to keep us all going.

Yesterday morning, whilst I was busy rearranging the ghost-shaped salt cellars in a Lindisfarne coffee shop into a highly disciplined phantasmal phalanx, Brutal Snake ambushed me with the following question. A 100-seat plane flight has been fully booked. Each passenger has an assigned seat, but the first passenger to get on board has lost their ticket, and sits in a random seat. Each following passenger has their ticket, and will sit in their assigned seat if it is still free. If it isn’t, they will choose a seat at random.

The question is: what's the probability that the final passenger to board will find the only seat remaining is actually the one listed on their ticket? Anyone who actually feels like sitting down and thinking about this be warned: the answer is directly below.

Said answer might be intuitively surprising: it’s one half. In fact, it’s one half irrespective of how many seats the plane contains, so long as there’s more than one and the flight is fully booked.

For a two-seater plane, the truth of the answer is obvious; passenger one (henceforth called #1) either gets the right seat or the wrong one, and their choice forces #2's. The three seat case is only slightly more complicated, though takes a little longer to consider. In this case there are three things #1 can do, each one with probability 1/3. They can find their correct seat, guaranteeing #2 and #3 find theirs too; they can sit in #3's seat, guaranteeing #3 is out of luck; or they can sit in #2’s seat. This third option is the most interesting, because it then leads to two further possibilities for #2, who will now sit either in #1’s seat, or passenger three’s. That means that overall there is a 1/3 x 1/2 = 1/6 chance that first #1 will sit in #2’s seat and #2 will then sit in #1’s.

In total, then, the chance of #3 getting their own seat is 1/2 + 1/3 x 1/2 = 1/2, because we need to consider both the chance #1 gets the right seat and also the chancethey take #2's seat but this turns out not to matter. This is what we were expecting to find, of course, but the true importance of the three-seat example is that it contains the secret for cracking the entire problem: if #1 does take #2's seat, then the resulting behaviour of #2 and #3 is identical to the behaviour of the two-seat case. One need simply assign what was once #1’s seat to #2 instead.

This handy trick works in the general case as well. Let’s move on to the dizzying complexities of the four-seat case. Now there are four choices for #1. They might choose their own seat, or #4’s, both of which fix the final result immediately. They might instead choose #2's seat, then we just label what was #1’s seat as #2’s, and immediately return to the three-seat case. Lastly, #1 might sit in #3’s seat. In that event, #2 will get to sit where they were supposed to, and we can return to the two-seat case by reassigning #1’s intended seat to #3. And, as we know, both the three-seat and two-seat cases have a ½ probability of working out.

This time each possibility carries with it a probability of ¼, which means the overall chance of #4 getting their correct chair is 1/4 +1/4 * 1/2 + 1/4 * 1/2 = 1/2.

See the pattern? Whatever seat #1 chooses, unless it’s their own or the last passengers, it immediately allows us to consider a case involving a smaller series of chairs. This is what we call a recursion relation, a situation in which the value of each case can be calculated by considering the values of previous cases. If we call the number of chairs n, and denote by P(n) the probability of passenger n getting to sit in the right seat, then we have:

P(n) = 1/n x P(n-1) + 1/n x P(n-2) + 1/n x P(n-3) + ... + 1/n x P(2) + 1/n x P(1)

where of course P(1) = 1 because if there’s only one seat and one passenger, a match is inevitable.

The last trick is the most sneaky, and uses a mathematical procedure called induction. In words, induction works like this. If knowing something is true for step n-1 must mean it’s true for step n, and if it’s true for step 1, then it must be true for all steps, because the truth at step 1 guarantees its truth at step 2, which guarantees in turn its truth at step 3, and so on ad infinitum. The above equation requires a slight variance on that idea; in this case we argue that if P(1)=P(2)=...P(n-1)=1/2 is true for all steps up to and including n-1, it must be true for n as well.

How does this work? Well, if we assume that the answer has been 1/2 every time right up to and including n-1, our equation above becomes:

P(n) = 1/n x 1/2 + 1/n x 1/2 + .... + 1/n x 1/2 + 1/n x 1/2 + 1/n = 1/n + (n-2)/2n = n/2n = 1/2.

So, if the probability has been a half for every seat-number above 1 and before n, then it must be 1/2 for n as well. Since we already know that it was indeed a half for two, three and four seats, then it must be 1/2 for five seats as well, and then for six seats, and seven, and...

So there you go. I’m not so lunatic as to imagine that you found any of that quite so riveting as I did. You may also question, as indeed did I, what point lies in travelling 80 miles on your day off to an national landmark merely to drink coffee and discuss probability which is already your freaking job. I do think it's a nice little thing to think about, however, and if nothing else, it's less likely to be blocked by work filters than another round of political ranting/crowing.