A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations

2017/03/22 by Houdré, Christian, Xu, Chen
#60C05 #FOS: Mathematics #Primary 05A05 #Probability (math.PR)

paper · doi:10.48550/arxiv.1703.07691

Abstract

We address a question and a conjecture on the expected length of the longest common subsequences of two i.i.d. random permutations of [n]:=\1,2,...,n\. The question is resolved by showing that the minimal expectation is not attained in the uniform case. The conjecture asserts that √(n) is a lower bound on this expectation, but we only obtain √[3]n for it.

Related

• On the Longest Common Pattern Contained in Two or More Random\n Permutations
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• Expected Length of the Longest Common Subsequence of Multiple Strings
• Longest Common Subsequences in Sets of Permutations
• Limit Theorems for the Length of the Longest Common Subsequence of Mallows Permutations