This is a continuation of our series of posts on the HUJI seminar 2020 open problems. This time the post was kindly written by Eitan Bachmat who proposed the problem.
My summary: understanding of the distribution of largest increasing subsequences for random permutations, and the combinatorics of largest increasing subsequences of general permutations is among the most fascinating stories in modern mathematics. When you also add weights this is largely an uncharted territory.
Heaviest increasing subsequences
Setup: Let X be a bounded distribution with support on an interval [1,T]. Given a permutation of size N, an increasing subsequence is a set of indices such that . If in addition, we attach to each index a weight , the weight of the subsequence is the sum . We are interested in the asymptotic behavior as of , the random variable which is given by the weight of the heaviest increasing subsequence where is chosen uniformly among permutations of size and the are sampled i.i.d from X.
A standard sub-additivity argument shows that with high probability, as , approaches a constant . The theorem of Vershik and Kerov on the longest increasing subsequence in a random permutation states that if X is the Dirac distribution which always takes the value , then . From this result, we can conclude that for any , (Take the longest increasing subsequence, disregarding the weights). Using similar elementary arguments it can be shown also that
Which means that is a much better estimate of than ( can be as large as for distributions with support in [1,T]).
Problem 1: Is it true that for all X
Numerical experimentation with many distributions has failed so far to find a counter example. Even the weaker bound
for some constant is unknown to the best of our knowledge and would also be very nice to have.
We can conjecture a stronger statement, by considering the space of all distributions (say on [1,T]) with its convex structure given by mixtures of distributions. We say that is a mixture of and , if for all , .
Problem 2: Is it true that is a concave function with respect to mixtures, i.e., for any mixture we have
The first problem is essentially this statement for the mixture which expresses as a generalized mixture of the extreme points which are Dirac measures on . We donít have counter examples for the stronger statement either.
The third problem concerns the upper bound.
Problem 3: Is there a constant such that, for all bounded. We believe this is false. In particular, consider the family of Bounded Pareto distributions with parameter , with density given by for and the normalizing constant. We believe that the ratio for this particular family is unbounded (and in some moral sense, thatís the only case).
Problem 4: Compute for ANY distribution which is not a Dirac distribution. Best chance seems to be the exponential or geometric distributions, where Kurt Johansson answers the corresponding last passage percolation problem, https://arxiv.org/pdf/math/9903134.pdf
The problems above are motivated by the study of the asymptotic behavior of certain finite particle (interval) systems which we call “`airplane boarding”‘. The system has a parameter . At any given moment, the system consists of closed moving intervals all of length which we call “passengers” and which can only overlap at endpoints. The index of an interval/passenger is called its “queue location”. The ordering of the intervals according to “queue locations” never changes, i.e., passengers cannot pass each other while “boarding”. The interval is called the “airplane aisle”. Each interval has a target “row” (in the airplane aisle) where is a permutation on (the system can be generalized to handle more than one “passenger” per “row”). To each “passenger” we also attach an “aisle clearing time” . Initially, at time , all the intervals are left of and in descending order of their index, for example, if , we might have , etc., at any given time point, each interval/passenger, ,moves at infinite speed towards its destination “row” and if it is not blocked by other intervals to its right it positions itself with the left endpoint at , i.e., occupies . When a passenger does reach its target “row”, then it waits its aisle clearing time before leaving the system and allowing the passengers behind to advance further towards their row. The “boarding time” is the time when all intervals have left the system and the process terminates. From the description, one can check that the boarding time when is simply the heaviest increasing subsequence for and weights , so its clear that the problems above are relevant to the analysis of “airplane boarding”. To motivate them more specifically, lets introduce one more element, a “boarding policy” which makes the boarding time into a random variable. The simplest policy, which we have already encountered, is Random boarding. In Random boarding we assume that the queue position, the row and the weights are all independent random variables. The first two are chosen uniformly, generating a uniformly random permutation and we think of the as drawn i.i.d. from a distribution , which is the aisle clearing time distribution of all passengers as a single group. We observe that is a normalized asymptotic indicator of the boarding time of the Random policy. Suppose now that we have two (or more in general) subpopulations with different aisle clearing times, say, passengers with no hand luggage and the other passengers, or passengers who need assistant or are travelling with children and the other passengers as a second group. If we denote by Y and Z the aisle clearing time of the first and second subpopulations and by p, the portion of passengers from the first subpopulation, then the aisle clearing time of the whole population will be the mixture . We use as a measure of the slowness or quickness of a group and will assume that the first group with aisle clearing time distribution is the group of ‘slow passengers”, i.e., . Given this scenario, we can naturally define two policies which are practiced by airlines. The first policy is the “Slow First” (SF) policy, where we use a uniformly random permutation , but for the weights, those of the first passengers are drawn i.i.d. from Y and the others are drawn i.i.d. from Z. The other policy is “Fast First” (FF) which as the name suggests, draws the weights of the first passengers i.i.d. from Z and the others from Y.
Now we come to the test your intuition portion of the post. Spoiler alert, please test your intuition before continuing to read below the fold. Assuming “normal” coach class conditions in a full occupancy airplane, , with a realistic portion of slow passengers, say p=0.2, and a realistic effective aisle clearing time ratio of , rank the 3 policies, Random, Slow First and Fast First, from fastest to slowest in terms of average asymptotic boarding time (ascending boarding time order).
\ FOLD \
The ordering is: Slow First, then Fast First, then Random. OK, but what happens if I choose other parameters ? We have the following result of Erland, Kaupuzs, Frette, Pugatch and Bachmat, https://arxiv.org/abs/1906.05018 \
Theorem: (SF is better than FF universally) For any parameters , SF has lower or equal average asymptotic boarding time compared to FF.
It turns out that we donít have a universal comparison between Random and FF. On realistic parameters, FF is faster, but for some small region of parameter space Random is actually faster than FF. We are left with the comparison of SF and Random and here comes problem 2 into play. We have the following result of Erland, Kaupusz, Steiner and Bachmat https://arxiv.org/abs/2012.11246
Theorem: Slow first is universally (for all mixtures and k) faster than Random if and only if is concave on the space of bounded distributions.
The concavity of has been verified on all mixtures coming from empirical observations of aisle clearing times (say, first group is passengers with 0,2,3 luggage items and the other those with 1 or 4).
The third problem and to some extent, the first, have a somewhat different motivation. There is a very different situation where we break a distribution as a mixture and that is express line queues, where the population of customers is broken into fast customers that go to the express line and the others which go to a regular line (assume there is one). We can consider the average waiting time in queue as a function of the mixture. Such systems have a parameter that does not exist in airplane boarding, the utilization . On the other hand, airplane boarding has which does not have an express line counterpart. In addition, in airplane boarding there may be better policies for handling the slow and fast groups (say, slow passengers in back rows at the front of the queue and slow passengers from the front rows at the back of the queue, and more complicated ones).
It has been shown, https://www.sciencedirect.com/science/article/pii/S0377221718310695 , that after proper normalizations to offset these non-mutual parameters, for any mixture, the average response time of the express line queue is approximately the square of the boarding time of the optimal policy for handling the slow and fast groups of the mixture (a complicated policy, the result does not hold for slow first nor fast first). The quality of the approximation essentially depends on the ratio . If it is universally bounded then so is the approximation ratio.
Having such a tight relation between express line queues and airplane boarding is useful, since we can use it to analyze airplane boarding via the simpler and better studied express line queues. In addition, express line queues have an exact and non trivial duality on mixtures which preserves average waiting time via a formula of Riemann which was used in his proof of the functional equation of the zeta function. The duality simplifies the analysis of express line queues on self-dual distributions, these include log-normal distributions, Bounded Pareto distributions (as a family) and distributions whose densities are given by squaring a weight 2 Hecke cusp form (as in the Taniyama-Shimura conjecture) restricted to the positive imaginary axis. The approximate relation allows us to get a non-trivial approximate duality in airplane boarding.
The post is becoming long, so I will leave you with one final insight which is at the heart of the analysis of airplane boarding. Airplane boarding is asymptotically, most naturally understood in terms of evolution in (proper) time of particle clouds in space-time. As a process (consider the passengers which sit down at approximately the same time) it is essentially a discrete version of what is known as a Congruence with respect to proper time of particles, starting with a Cauchy hypersurface. That’s the kind of stuff that Penrose studied (much more deeply) when he proved the singularity theorems that won him a share of the 2020 Noble prize in physics. Maximal length or heaviest increasing subsequences in uniformly random permutations correspond to the simplest case of geodesics in special relativity (straight lines). I will explain some other time, what all this has to do with college admissions.