Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks

Details Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks

2010-01-08

arxiv.org/abs/1001.1273v3

Mathematics

Probability

PDFLatex, 40 pages

Scientific paper

The problem of the fluctuation of the Longest Common Subsequence (LCS) of two i.i.d. sequences of length $n>0$ has been open for decades. There exist contradicting conjectures on the topic. Chvatal and Sankoff conjectured in 1975 that asymptotically the order should be $n^{2/3}$, while Waterman conjectured in 1994 that asymptotically the order should be $n$. A contiguous substring consisting only of one type of symbol is called a block. In the present work, we determine the order of the fluctuation of the LCS for a special model of sequences consisting of i.i.d. blocks whose lengths are uniformly distributed on the set $\{l-1,l,l+1\}$, with $l$ a given positive integer. We showed that the fluctuation in this model is asymptotically of order $n$, which confirm Waterman's conjecture. For achieving this goal, we developed a new method which allows us to reformulate the problem of the order of the variance as a (relatively) low dimensional optimization problem.

Affiliated with

Also associated with

No associations

Rating

Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks 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 Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502495