The Length of the Longest Common Subsequence of Two Independent Mallows Permutations

Abstract

The Mallows measure is a probability measure on $S_n$ where the probability of a permutation $\pi$ is proportional to $q^{l(\pi )}$ with $q>0$ being a parameter and $l(\pi )$ the number of inversions in $\pi$. We prove a weak law of large numbers for the length of the longest common subsequences of two independent permutations drawn from the Mallows measure, when $q$ is a function of $n$ and $n(1-q)$ has limit in $\mathbb{R}$ as $n\to \infty$.

56 pages

References in corpus (1)

• The Limit of the Empirical Measure of the Product of Two Independent Mallows Permutations

Cited by in corpus (2)

• Mallows permutations as stable matchings
• On an alternative sequence comparison statistic of Steele