Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks

MaRDI QIDQ6217003zbMATH OpenFDO

Authors Heinrich Matzinger, Felipe Torres

Publication date 8 January 2010

Mathematics Subject Classification ID

Combinatorial probability (60C05) Large deviations (60F10)

Abstract: 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.

This page was built for publication: Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6217003)