I’ve spent a lot of time at airports recently. And whenever I’m at an airport I find myself thinking about combinatorial problems having to do with airplanes. While flying from SFO to BOS recently, I stumbled across something I found really surprising.
Suppose people board a plane in a random order. Each person has a seat number assigned to them, and whenever someone gets to their seat, they pause for a moment to put their luggage in the overhead bin.
Whenever someone is pausing for their luggage, they prevent anyone in back of them from passing. Suppose that it takes each person time to walk by a given seat, and time to put away their luggage once they get to their seat. The question is:
How long will it take for everyone to sit down?
In the worst case the passengers are arranged in decreasing numerical order. This means everyone will have to wait on everyone in front of them, and boarding will take time roughly . If, on the other hand, the passengers arrive in the correct (increasing) order, then they’ll each be able to walk straight to their seats, boarding in time .
But what if the passengers arrive in a random order? Then how much parallelism do we get?
The answer, as it turns out, is quite a lot. In fact, the expected time to board the plane will be
This has some pretty weird consequences. For example, it means that for any fixed and , and for a large enough plane-size , the boarding time will become dominated by the time necessary to walk down to the end of the plane. The time spent waiting on people to put their luggage overhead becomes a non-issue!
A Simplifying Assumption: To make our analysis easier, we’ll make a simplifying assumption that turns out not to affect the outcome of the analysis. In particular, we’ll treat each of the passengers as though they don’t take any space in the aisle. For example, if one passenger is paused at seat , and there are there are some passengers waiting behind him that want to get past seat , then that won’t stop the passenger behind them from getting to seat .
On top of this, we’re already making the simplifying assumption that each row has only one seat. It turns out that both of these assumptions can be removed without changing the end result. I’ll talk about this more at the end of the post.
The Combinatorics: The key insight to analyze the algorithm is this: Think of the people as a permutation of seat numbers. If the longest decreasing subsequence in the line of people has length , then it turns out the time to board the plane will be within a factor of two of .
To see this, consider some person as they walk to their seat. Let be the final person on whom waits before gets to their seat. Then the total time spends waiting on others will be at most greater than the total time that spends waiting on others. Similarly there is some person who is the last person on whom waits; and spends at most time more in total waiting than does . Continuing like this, we can find a subsequence of people
such that the right-most person in the sequence doesn’t have to wait at all, and such that each person spends at most longer than waiting. This means that our original person spends time at most waiting on others.
The sequence of people also has the property that their seat numbers are in decreasing order. So what we’ve really shown is that if is the length of the longest decreasing subsequence in the permutation of people, then no person will have to wait for time more than , and everyone will have boarded after time .
On the other hand, it’s not hard to see that the left-most person in the length- decreasing sequence will require time at least to board the plane; and that the left-most person in the entire line will require time at least to board. This means that the true boarding time will be within a factor of two of .
So the real question becomes: On average, how large is , the length of the longest decreasing subsequence in a random permutation?
Bounding the longest decreasing subsequence: We’ll start by considering a different question. For a given length , how many different decreasing subsequences of length should we expect in our permutation? (We count two subsequences as different even if they differ in only a single element.)
This is easy to compute by linearity of expectation: Each -element subsequence has a probability of being in decreasing order. And there are different -element subsequences. So the expected number of decreasing subsequences is
A useful fact about is that it’s at least as large as . So the expected number of decreasing -element subsequences is at most
When , this reduces to at most .
Of course, if the expected number of -element decreasing subsequences is so small, then so is the probability of any such subsequence appearing.
So with extremely high probability, no decreasing subsequence will be of length more than . And this implies that the expected length is also at most .
What about a lower bound? We’ve just shown that the expected length of the longest decreasing subsequence is at most . But is that tight?
For this, we can use a classical result from permutation combinatorics. The Erdös-Szekeres Theorem says that any permutation of length must either contain either a decreasing or an increasing subsequence of length . For a random permutation, this means that with probability at least , there will be a decreasing subsequence of length . So the expected length of the longest decreasing subsequence is at least .
The full version of the problem: Near the beginning of the post I mentioned we were making two assumptions: (1) That passengers don’t take up any space in the aisle; and (2) that each row has a single seat.
Removing these assumptions makes the problem considerably harder. But it turns out the end conclusion is basically the same. A 2009 math paper on the topic analyzed the problem in its full complexity, and found that as long as each person takes up roughly one row worth of space in the aisle, and the number of seats in each row is constant, the boarding time remains