We study the lengths of monotone subsequences for permutations drawn from the Mallows measure. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation @math is proportional to @math where @math is a positive parameter and @math is the number of inversions in @math . In our main result we show that when @math , the limiting distribution of the longest increasing subsequence (LIS) is Gaussian, answering an open question in [Bhatnagar and Peled, PTRF, 2015]. This is in contrast to the case when @math where the limiting distribution of the LIS when scaled appropriately is the GUE Tracy-Widom distribution. We also obtain a law of large numbers for the length of the longest decreasing subsequence (LDS) and identify the precise constant in the order of the expectation, answering a further open question in [Bhatnagar and Peled, PTRF, 2015].
Subsequently, in @cite_22 , Bhatnagar and Peled established the leading order behavior of @math in the regime that @math and @math . They analyzed an insertion process which they called the Mallows process for randomly generating Mallows distributed permutations and showed that @math in @math for @math as @math . They established the order of @math and showed that it grows at different rates for different regimes of @math as a function of @math (in particular they showed @math when @math is fixed) and proved large deviation bounds for @math and @math . They also established a linear upper bound on the variance of @math and left open the questions of determining the precise variance and the distribution of @math for all regimes of @math and @math .
@cite_22
1989633256
We study the length of the longest increasing and longest decreasing subsequences of random permutations drawn from the Mallows measure. Under this measure, the probability of a permutation ( S_n ) is proportional to (q^ Inv ( ) ) where (q ) is a real parameter and ( Inv ( ) ) is the number of inversions in ( ). The case (q=1 ) corresponds to uniformly random permutations. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics. We determine the typical order of magnitude of the lengths of the longest increasing and decreasing subsequences, as well as large deviation bounds for them. We also provide a simple bound on the variance of these lengths, and prove a law of large numbers for the length of the longest increasing subsequence. Assuming without loss of generality that (q<1 ), our results apply when (q ) is a function of (n ) satisfying (n(1-q) ). The case that (n(1-q)=O(1) ) was considered previously by Mueller and Starr. In our parameter range, the typical length of the longest increasing subsequence is of order (n 1-q ), whereas the typical length of the longest decreasing subsequence has four possible behaviors according to the precise dependence of (n ) and (q ). We show also that in the graphical representation of a Mallows-distributed permutation, most points are found in a symmetric strip around the diagonal whose width is of order (1 (1-q) ). This suggests a connection between the longest increasing subsequence in the Mallows model and the model of last passage percolation in a strip.