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.

Ready for a solution?

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.

 

Random Permutations of Cars in Traffic

You want to drive a little over the speed limit. The person in front of you wants to go exactly the speed limit. This is going to be a long day.

Riddle #9 made the long day much more enjoyable.  Here is the riddle quoted from FiveThirtyEight: 

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

For example, if the car in the very front happens to be slowest, there will be exactly one group — everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be N groups — no car ever gets stuck behind a slower car.

Suppose each car is given a number between 1 and N.  The number 1 means it is the slowest car, and the number N is the fastest car.  There are N! possible permutations (that is "N factorial") of  the cars along the road.  Let's begin with the lead car.

The lead car will define the first group of cars with 100% certainty.  Either it will be in a group by itself (if it is the fastest), a group with several cars (if those several cars are faster than it), or the entire group of cars (if it is the slowest car).  Thus, the lead car will add 1 group to the entire total.

Now, to the second car.  If there are N cars, for every way that you can choose the lead car being faster than the second car, you can flip that permutation so that the lead car is slower than the second car. In other words, there is a 1/2 probability that the second car will define a new group, and a 1/2 probability it will be part of the group that the lead car is in.  Thus, the second car will add 1/2 of a group to the total on average.

To the third car, and beyond!!  For every way you can choose a lead car, 2nd car, and 3rd car, you can order the fastest (F), middle fastest (M), and slowest (S) in the following six different ways:

FMS   FSM   MFS   MSF   SFM   SMF

There are only two of the six permutations in which the slower of the three cars is the 3rd car, in which case, it will create its own group.  That has a 2/6=1/3 probability.  If it is either the fastest or middle fastest, it will become part of a group already in existence.  Thus, the 3rd car will create 1/3 of a group on average.

This continues.  The 4th car will create 1/4 of a group on average, the ith car will create 1/i of a group on average.

If there are N cars, then the line of cars will create $\sum_{i=1}^N \frac{1}{i}$ different groups on average.

I've been trying to figure out how to do math equations on blogspot and have been unsuccessful. Especially if you see code between dollar signs in the previous line. If that is the case it is supposed to be the shorthand notation for:

1+1/2+1/3+1/4+...+1/N

An Ode to Hillary: The Internal Candidate

You work for some institution, and within this institution, things are not really that great.

Someone is about to retire and the majority of you have an internal candidate who is very qualified, well liked, and a shoe-in for the position. There does exist a minority at this institution that is rather disgusted with the idea of this "shoe-in" candidate taking the retiree's position, but that is beside the point that is trying to be made with this post. 

The institution goes through the motions of creating an external ad for the position knowing full well who they intend to hire. In fact, these are exciting times, as history will be made with the hiring of this internal candidate.  This internal candidate is fully qualified, will hold the institution together as it still stands, keep in running as always, and make some promising changes along the way.  Indeed, this will be a good candidate. 

Then the unexpected happens.

An external candidate applies that makes everyone do a double take.  "Who the... what the... wait... what just happened?!?"  

An awkward situation has just occurred.  Not only has a fully qualified external candidate just applied, but it is one that has amazing promise and drive at fixing what is actually broken about the institute. This candidate can get to the root of the problem.  This candidate will not just simply hold the institution together and keep it running smoothly as it has been, but will actually fix what is broken.  By hiring this candidate, the institution has an opportunity to come together stronger than it has ever been before, and make the kind of progress that nearly everyone at the institution can get on board with. 

Indeed, this is another candidate that, if hired, will make history.  It is a different type of history, but it is a more important type of history. 

From the outside, the choice is clear. This institution should select the external candidate. But the struggle inside is real, and should not be ignored. 

A strong case can be made for the internal candidate. It is who the majority is comfortable with. They know this candidate has experience at this institution and knows the ins and outs of the place. Sure, this candidate made some bad decisions in the past, but they've changed their minds for the better. They grew! We know this candidate. We've been following this candidate!  And come on!  History will be made by hiring this candidate! After all, this will be the first female ever to occupy this position! How exciting is that!

What about this external candidate? Even in the toughest situations, this candidate made the unpopular decisions that were correct at the time, and correct now. This candidate, although not having worked directly with the institution, and lacking the experience of the ins and outs of institution as it runs right now, does have the knowledge to make the institution better and make it run as it should.  This external candidate, not only is favorable among those that stand by the internal candidate, but is also favorable to many of the minority, too!  This candidate can bring people together!  This candidate can get to the root of the problem and make the kind of history that is arguably more important than having the first female occupy this role.  

This external candidate is all about putting a female into this position even more plausible in the future. 

Again, it is the clear choice from an outside perspective, but the hard choice from those on the inside. 

Fast forward... we've interviewed the candidates.  Once. Twice, A third and fourth time. The internal candidate is beginning to see she isn't the shoe-in she once was. Her mainstream supporters are getting upset, and are arguing the best they can to try and make it clear she is the better candidate. But it just isn't so. She isn't the best candidate. 

The supporters for the external candidate are getting upset. It is hard for them to understand why the supporters for the internal candidate cannot see the better, yet tougher choice.  

The situation sucks. It truly will be awesome to see the first female in this role! But it would be the inferior choice, and an ultimately bad decision if it were to come to pass now.  

Choose wisely, and Feel the Bern.