## Friday, February 19, 2016

### Airplane Seating Etiquette

Unlucky you, to be the last person to board a 100 seat plane. This is the setting of this week's riddle from Ollie on FiveThirtyEight.

Here's the problem. The first person to board is a complete asshole. This guy is to airplane boarding as Martin Shkreli is to pharmaceuticals.  When this guy boards, he could care less about what seat he is actually assigned to, so he just chooses one at random.

Each person after will sit in their assigned seat if it is available. If it isn't available, instead of causing a scene, they choose any of the remaining seats at random.

Finally, it is your turn. What is the probability that you get to sit in your assigned seat?

This problem isn't too difficult, so I encourage a little thought on it before reading on.

First, let us simplify the problem by thinking of each passenger as numbers from 1 to 100, where 1 represents the asshole, and 100 represents you. Or should we just call it the collective us? The "royal we" so to speak?

OK, now go through the plane and label all the passengers seats to which they are assigned with the same number.

Now, let's go through one simulation to see how this works. Number 1 chooses a random number between 1 and 100.  Let's say it is 37.

Passengers 2-36 board and sit in their seats. Passenger 37 boards and finds a complete assface in her seat. (Let's mark seat 1 with 37* for simplicity). Passenger 37 chooses a random number between 37 and 100 inclusive. Suppose it is 84.

Passengers 38-83 board and sit in their seats. Passenger 84 boards and finds an unfortunate lady whose seat was taken by a toolbag in his seat. Seat number 37* is now changed to 84* (remember, this is the original asshead's seat).  Passenger 84 chooses a random number between 84 and 100.  Say it is 97.

Passengers 85-96 board and take their seats, seat 84* is changed to 97*, and passenger 97 chooses a random number between 97 and 100.  To get this show on the road, suppose it is 100.  Damn. We lost our seat.  Passengers 98 and 99 take their seat and we get to sit in which seat?  That's right. Douchy McDoucherson's seat.

This is an important observation.

If we play these scenarios to conclusion time and time again, we will notice there are only two possible results for us. We sit in our seat, or the dickhead's. It turns out that either scenario is equally likely, so the answer ends up being 50%.  But let's offer a little more explanation.

Each time a passenger is faced with a random choice (including the first time), choosing seat 1 or seat 100 has the same probability every time this happens. If either is chosen, all randomness is removed, and the rest of the boarding is determined. If seat 1 was chosen, all remaining passengers including us, get to sit in their own seat.  If seat 100 is chosen, all remaining passengers excluding us, get to sit in their own seat. We have to sit in meaniehead's seat.

If another seat is chosen besides seat 1 or 100, then we repeat the situation above. Again, each time this happens, seat 1 and 100 are equally likely to get chosen. Hence, the 50%.

If you are still not convinced, analyze the situation with a 2 seat airplane and then a 3 seat airplane. If you're brave enough try a 4.  If you're really brave, go 5.  They all produce a 1/2 probability of getting to sit in our own seat when we're last to board.  This should convince you that it will remain that way.

The Extension
Let's try and find the average number of passengers that will get to sit in their seats.  The reason I suggested it is because I noticed 1 person on average would get their seat on a 2 seat plane, while 1+1/2 people on average get their seat on a 3 seat plane, 1+1/2+2/3 on a 4 seat plane, and 1+1/2+2/3+3/4 on a 5 seat plane. This led me to guess that an average of 1+1/2+2/3+3/4+...+98/99 (which approximately equals 94.82262) people would get seated on a 100 seat plane.

So, I simulated it 1000 times and plotted a moving average using the following code in R:
This helped me feel very comfortable with my guess. Still not satisfied, I had to think about why this was working out the way it was.

I'm not sure even if this is the correct intuition, but I'll give it a shot.  With probability 1/100, the asshole will select his own seat, which will produce 100 passengers sitting in their own seats.  Given he doesn't select his seat, there is a 1/99 chance that the next person will select the first seat and then leave 98 passengers sitting in their own seats.  Given that the first two didn't sit in their own seats, there is a 1/98 chance that the next person will select seat 1, leaving 97 passengers sitting in their own seats.  And so on. This, when written out, looks like

1/100(100)+1/99(98)+1/98(97)+ ... + 1/2(1) = 1+98/99+97/98+...+2/3+1/2,
which is the same as the sum I described above.

This is far from rigorous, but hopefully it satisfies most of you.