Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets

2004/10/18 by F. Bonetto, Bonetto, F., H. Matzinger +1
Mathematics · #60C05 (primary) 92D20 (secondary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:60C05 #msc:92D20

paper · pdf · doi:10.48550/arxiv.math/0410404

arxiv created 2004/10/18 · arxiv updated 2009/12/01

Abstract

We investigate the asymptotic standard deviation of the Longest Common Subsequence (LCS) of two independent i.i.d. sequences of length n. The first sequence is drawn from a three letter alphabet 0,1,a, whilst the second sequence is binary. The main result of this article is that in this asymmetric case, the standard deviation of the length of the LCS is of order square root of n. This confirms Waterman's conjecture for this special case. Our result seems to indicate that in many other situations the order of the standard deviation is also square root of n.

Related

• Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks
• Repetition-free longest common subsequence of random sequences
• Expected length of the longest common subsequence for large alphabets
• Longest common subsequences between words of very unequal length
• On the Variance of the Length of the Longest Common Subsequences in Random Words With an Omitted Letter