Tuesday, January 10, 2012

Paine Relief

It was a delight to meet up with Robert (Nick) Paine and his wife and daughter in Neptune's Hall over the festive period. I promised that I would share my solution of the Queasyjet problem - see earlier blog post.
Well here is how I see it:
Assume that there are n+1 passengers, then when the first (and actually special) passenger gets on he will choose from one of the n seats that does not belong to him.
This means that there is a 1/n chance that he sits in the last passenger's allocated seat, leaving no chance that it is correctly allocated. It also means that there is an (n-1)/n that he sits in a seat leaving both his own and that of the last passenger unoccupied.
This second situation is what I call a "steady state" because from here on, the probability that the final passenger gets their allocated seat is 1/2. To understand why it is important to understand the end game - the "game is over" when a passenger sits in the first passenger's seat (in which case the boarding continues smoothly and the remaining passengers, including the last get their allocated seats) or when a passenger sits in the last passenger's seat (in which case it is guaranteed that the last will not get their allocated seat). These two scenarios are equally likely because for each passenger k>1 either their allocated seat is available or they choose one of the endgame scenarios each with probability 1/(k-1).
So if there are n+1 passenger, the probability that the last one will get their seat is
P(doesn't get seat)= [(n-1)/n]*[1/2] = (n-1)/2n=[1/2]-[1/2n]