THE LENGTH OF THE LONGEST COMMON SUBSEQUENCE OF TWO INDEPENDENT MALLOWS PERMUTATIONS

• 成果类型: Article
• 署名作者: Jin, Ke
• 署名单位: University of Delaware
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1351
• 发表日期: 2019
• 页码: 1311-1355
• 关键词: increasing subsequence

摘要

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 R as n ->infinity.