pith. sign in

arxiv: 0907.5137 · v1 · submitted 2009-07-29 · 🧮 math.PR

Standard deviation of the longest common subsequence

classification 🧮 math.PR
keywords bernoullicommondeviationlengthlongestorderstandardsubsequence
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.