Standard deviation of the longest common subsequence

Abstract

Let $L_n$ be the length of the longest common subsequence of two independent i.i.d. sequences of Bernoulli variables of length $n$. We prove that the order of the standard deviation of $L_n$ is $\sqrt{n}$, provided the parameter of the Bernoulli variables is small enough. This validates Waterman's conjecture in this situation [Philos. Trans. R. Soc. Lond. Ser. B 344 (1994) 383--390]. The order conjectured by Chvatal and Sankoff [J. Appl. Probab. 12 (1975) 306--315], however, is different.

Published in at http://dx.doi.org/10.1214/08-AOP436 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Extensive Simulations for Longest Common Subsequences: Finite Size Scaling, a Cavity Solution, and Configuration Space properties
• Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets
• Optimal alignments of longest common subsequences and their path properties

Cited by in corpus (5)

• A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
• Optimal alignments of longest common subsequences and their path properties
• On the Variance of the Optimal Alignments Score for Binary Random Words and an Asymmetric Scoring Function
• Letter Change Bias and Local Uniqueness in Optimal Sequence Alignments
• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets