On the length of the longest common subsequence of two independent Mallows permutations
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
The Mallows measure is a probability measure on Sn where the probability of a permutation π is proportional to q l(π) with q > 0 being a parameter and l(π) the number of inversions in π. We prove three weak laws of large numbers and a central limit theorem for the length of the longest common subsequences of two independent permutations drawn from the Mallows measure for different regimes of the parameter q.
Description
Keywords
Applied sciences, Longest common subsequence, Longest increasing subsequence, Mallows permutation