Standard deviation of the longest common subsequence

DOI10.1214/08-AOP436MaRDI QIDQ2270612zbMATH OpenFDO

Authors J. Lember, Heinrich Matzinger

Publication date 28 July 2009

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

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)

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.

Recommendations

• Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
• scientific article; zbMATH DE number 5205668
• The rate of convergence of the mean length of the longest common subsequence
• Expected length of the longest common subsequence for large alphabets
• scientific article; zbMATH DE number 5873671

Cites work

• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 5205668 (Why is no real title available?)
• A phase transition for the score in matching random sequences allowing deletions
• An Efron-Stein inequality for nonsymmetric statistics
• Bounding the expected length of longest common subsequences and forests
• Expected length of the longest common subsequence for large alphabets
• Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• Longest common subsequences of two random sequences
• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
• On the longest common increasing binary subsequence
• Optimal alignments of longest common subsequences and their path properties
• Sequence comparison significance and Poisson approximation
• The rate of convergence of the mean length of the longest common subsequence

Cited in

(19)

• 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
• Lower bounds for moments of global scores of pairwise Markov chains
• Length of the longest common subsequence between overlapping words
• On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
• Rate of convergence of the mean for sub-additive ergodic sequences
• A general method for lower bounds on fluctuations of random variables
• 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 the longest common increasing binary subsequence
• On an alternative sequence comparison statistic of Steele
• Thermodynamical approach to the longest common subsequence problem
• Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
• On the order of the central moments of the length of the longest common subsequences in random words
• Lower bounds for fluctuations in first-passage percolation for general distributions

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)