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].
The normalizing constant @math in the Mallows distribution has a closed form formula which Diaconis and Ram @cite_28 observed to be the Poincar ' e polynomial The formula for @math implies a straightforward method for generating a random Mallows distributed permutation.
@cite_28
2094040972 1511376624 1989633256 1723089725
The Mallows measure on the symmetric group S n is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i π j . We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1−q) has a limit in R. Asymptotics of the normalizing constant is computed for a class of one parameter exponential families on permutations which includes Mallows model with Spearmans's Footrule and Spearman's Rank Correlation Statistic. The MLE, and a computable approximation of the MLE are shown to be consistent. The pseudo-likelihood estimator of Besag is shown to be @math -consistent. An iterative algorithm (IPFP) is proved to converge to the limiting normalizing constant. The Mallows model with Kendall's Tau is also analyzed to demonstrate flexibility of the tools of this paper. 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. For a positive number @math the Mallows measure on the symmetric group is the probability measure on @math such that @math is proportional to @math -to-the-power- @math where @math equals the number of inversions: @math equals the number of pairs @math . One may consider this as a mean-field model from statistical mechanics. The weak large deviation principle may replace the Gibbs variational principle for characterizing equilibrium measures. In this sense, we prove absence of phase transition, i.e., phase uniqueness.