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

2019/08/14 by Banerjee, Naya, Jin, Ke
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1908.05246

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 π is proportional to q^Inv(π) where q is a positive parameter and Inv(π) is the number of inversions in π. We consider the length of the longest common subsequence (LCS) of two independently permutations drawn according to μ_n,q and μ_n,q' for some q,q' >0. We show that when 0

Related

• Limit Theorems for Longest Monotone Subsequences in Random Mallows Permutations
• The length of the longest increasing subsequence of Mallows permutation models with L¹ and L² distances
• On the Cycle Structure of Mallows Permutations
• The Limit of the Empirical Measure of the Product of Two Independent Mallows Permutations
• On the Longest Common Pattern Contained in Two or More Random\n Permutations