Standard deviation of the longest common subsequence

DOI10.1214/08-AOP436zbMATH Open1182.60004arXiv0907.5137MaRDI QIDQ2270612FDOQ2270612

Heinrich Matzinger, J. Lember

Publication date: 28 July 2009

Published in: The Annals of Probability (Search for Journal in Brave)

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 $sqrtn$, 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.

Full work available at URL: https://arxiv.org/abs/0907.5137

zbMATH Keywords

variance boundLongest common subsequenceChvatal-Sankoff conjecture

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Rate of convergence, degree of approximation (41A25)

Cites Work

• Title not available (Why is that?)
• Expected length of the longest common subsequence for large alphabets
• An Efron-Stein inequality for nonsymmetric statistics
• A phase transition for the score in matching random sequences allowing deletions
• The rate of convergence of the mean length of the longest common subsequence
• Title not available (Why is that?)
• Longest common subsequences of two random sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the longest common increasing binary subsequence
• Sequence comparison significance and Poisson approximation
• Bounding the expected length of longest common subsequences and forests
• Optimal alignments of longest common subsequences and their path properties
• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
• Large deviations-based upper bounds on the expected relative length of longest common subsequences

Cited In (17)

• Optimal alignments of longest common subsequences and their path properties
• Letter change bias and local uniqueness in optimal sequence alignments
• A central limit theorem for the length of the longest common subsequences in random words
• On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words
• Lower bounds for moments of global scores of pairwise Markov chains
• On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
• A general method for lower bounds on fluctuations of random variables
• Rate of convergence of the mean for sub-additive ergodic sequences
• Lower bounds on the generalized central moments of the optimal alignments score of random sequences
• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
• Optimality regions and fluctuations for Bernoulli last passage models
• Microscopic path structure of optimally aligned random sequences
• On an alternative sequence comparison statistic of Steele
• Thermodynamical approach to the longest common subsequence problem
• Length of the Longest Common Subsequence between Overlapping Words
• Lower bounds for fluctuations in first-passage percolation for general distributions

   Recommendations

• Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets 👍 👎
• Title not available (Why is that?) 👍 👎
• The rate of convergence of the mean length of the longest common subsequence 👍 👎
• Expected length of the longest common subsequence for large alphabets 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Standard deviation of the longest common subsequence

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