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

MaRDI QIDQ6323665zbMATH OpenFDO

Authors Ke Jin

Publication date 14 August 2019

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 $m{u}_{n,q}$ and $m{u}_{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)oinfty$ and $n(1-q^{\prime })oinfty$ 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.

This page was built for publication: Limit Theorems for the Length of the Longest Common Subsequence of Mallows Permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323665)