Limit Theorems for the Length of the Longest Common Subsequence of Mallows Permutations

Abstract

The Mallows measure is measure on permutations which was introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation $\pi$ is proportional to $q^{Inv(\pi )}$ where $q$ is a positive parameter and $Inv(\pi )$ is the number of inversions in $\pi$. We consider the length of the longest common subsequence (LCS) of two independently permutations drawn according to ${\mu }_{n,q}$ and ${\mu }_{n,q^{\prime }}$ for some $q,q^{\prime }>0$. We show that when $0<q,q^{\prime }<1$, the limiting law of the LCS is Gaussian. In the regime that $n(1-q)\to \infty$ and $n(1-q^{\prime })\to \infty$ we show a weak law of large numbers for the LCS. These results extend the results of \cite{Basu} and \cite{Naya} showing weak laws and a limiting law for the distribution of the longest increasing subsequence to showing corresponding results for the longest common subsequence.