Standard deviation of the longest common subsequence

By Jüri Lember, H. Matzinger. 2009

50 citations recorded by the source corpus.

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 Vn, 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.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/714de67e3eb5e879f85b437ca21d7feb27dcde4e