Standard deviation of the longest common subsequence

Details Standard deviation of the longest common subsequence Standard deviation of the longest common subsequence

2009-07-29

arxiv.org/abs/0907.5137v1

Annals of Probability 2009, Vol. 37, No. 3, 1192-1235

Mathematics

Probability

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

Scientific paper

10.1214/08-AOP436

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.

Affiliated with

Also associated with

No associations

Rating

Standard deviation of the longest common subsequence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Standard deviation of the longest common subsequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Standard deviation of the longest common subsequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521709