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

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.

Cited by in corpus (7)

• Standard deviation of the longest common subsequence
• Optimal alignments of longest common subsequences and their path properties
• Sparse long blocks and the variance of the longest common subsequences in random words
• Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences
• General approach to the fluctuations problem in random sequence comparison
• On the Variance of the Length of the Longest Common Subsequences in Random Words With an Omitted Letter
• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets