Let Ln 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 Ln 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.
Publié le : 2009-05-15
Classification:
Longest common subsequence,
variance bound,
Chvatal–Sankoff conjecture,
60K35,
41A25,
60C05C
@article{1245434031,
author = {Lember, J\"uri and Matzinger, Heinrich},
title = {Standard deviation of the longest common subsequence},
journal = {Ann. Probab.},
volume = {37},
number = {1},
year = {2009},
pages = { 1192-1235},
language = {en},
url = {http://dml.mathdoc.fr/item/1245434031}
}
Lember, Jüri; Matzinger, Heinrich. Standard deviation of the longest common subsequence. Ann. Probab., Tome 37 (2009) no. 1, pp. 1192-1235. http://gdmltest.u-ga.fr/item/1245434031/