Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks

2010/01/08 by Heinrich Matzinger, Matzinger, Heinrich, Felipe Torres +1
Computer Science · Mathematics · #60C05 #60F10 #Advanced Algebra and Geometry #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #math.CO #math.PR #msc:60C05 #msc:60F10

paper · pdf · doi:10.48550/arxiv.1001.1273

PDFLatex, 40 pages

openalex publication_date 2010/01/08 · arxiv created 2010/11/12 · arxiv updated 2010/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Random modification effect in the size of the fluctuation of the LCS of two sequences of i.i.d. blocks
• Fluctuations of the Longest Common Subsequence in the Asymmetric Case of 2- and 3-Letter Alphabets
• Repetition-free longest common subsequence of random sequences
• Sparse long blocks and the variance of the longest common subsequences in random words
• Asymptotics of the Longest Increasing Subsequence in Random Permutations