# Lengths of Monotone Subsequences in a Mallows Permutation

Research paper by **Nayantara Bhatnagar, Ron Peled**

Indexed on: **21 Mar '14**Published on: **21 Mar '14**Published in: **Mathematics - Probability**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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 pi in S_n is proportional to
q^{inv(pi)} where q is a real parameter and inv(pi) is the number of inversions
in pi. 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) -> infty. 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)^(1/2),
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.