Thursday, 25 March 2010

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.

5 comments:

Senior Spielbergo said...

Might I suggest another way of viewing the problem (that doesn’t involve maths)?

I’m pretty sure you can view it in another way, simply by a slight twist in the logic and basically viewing all the passengers (including the Granny but not the last) as being completely interchangeable and simply modelling it slightly differently. Basically instead of the lady sits down in a random seat and then if someone else comes along and finds their seat taken moving off to another random seat, consider instead if they simply go “oy granny that’s my seat, shift it”, so the Granny then stands up and moves to a different random seat. As the Granny and the other passengers are directly interchangeable this is in fact the identical problem. Now in this model it becomes really obvious because the Granny bounces around a whole bunch of times (the number being irrelevant) but when the final passenger boards the plane, every other passenger (apart from maybe Granny) is in the correct seat, leaving Granny with only two possible seats – Hers or the final passenger – Thus 50% probability.

Hah! I ignore your maths and substitute logic!

Senior Spielbergo said...

wibble

Tomsk said...

I like Spielbergo's explanation better! But I wonder if there's a flaw at the end - just because the Granny has only two possible seats, does that necessarily mean there's a 50% chance of her being in either one? To prove that probability I think you've still got to recursively add up all the chances of her moving into one of those seats as each passenger gets on.

SpaceSquid said...

You can't substitute logic for maths, Spielbergo, you can merely substitute the mathematical description of logic for a linguistic one.

And I'm going to take Tomsk's side on this, your explanation is much more concise and flavorful, but it's not a proof of anything. Granny is either in her seat or the final passenger's seat, but there is no reason to believe those two events are equally likely.

However, you can complete your "mathless" argument fairly briefly. All you need argue is that after each eviction Granny is just as likely to pick her own seat as that of the last passenger's. There's also the probability that she ends up in neither seat, but if that happens it is guaranteed that she will be evicted again, and once more have the same chance of choosing her seat as she does the last passenger's. Wash, rinse, repeat.

Gooder said...

The real question is how likely is the flight to be ambushed by militant BA staff?