The length of the longest increasing subsequence of Mallows permutation models with $L^1$ and $L^2$ distances

Abstract

Introduced by Mallows in statistical ranking theory, Mallows permutation model is a class of non-uniform probability measures on the symmetric group $S_n$ that depend on a distance metric $d(\sigma ,\tau )$ on $S_n$ and a scale parameter $\beta$. Taking the distance metric to be the $L^1$ and $L^2$ distances--which are respectively known as Spearman's footrule and Spearman's rank correlation in the statistics literature--leads to Mallows permutation models with $L^1$ and $L^2$ distances. In this paper, we study the length of the longest increasing subsequence of random permutations drawn from Mallows permutation models with $L^1$ and $L^2$ distances. For both models and various regimes of the scale parameter $\beta$, we determine the typical order of magnitude of the length of the longest increasing subsequence and establish a law of large numbers for this length. For Mallows permutation model with the $L^1$ distance, when $\beta \sim \theta n^{-1}$ for some fixed $\theta >0$, the typical length of the longest increasing subsequence is of order $\sqrt{n}$; when $n^{-1}\ll \beta \ll 1$, this typical length is of order $n\sqrt{\beta }$. For Mallows permutation model with the $L^2$ distance, when $\beta \sim \theta n^{-2}$ for some fixed $\theta >0$, the typical length of the longest increasing subsequence is of order $\sqrt{n}$; when $n^{-2}\ll \beta \ll 1$, this typical length is of order $n{\beta }^{\frac{1}{4}}$.

113 pages