2012/04/04 by Saba Amsalu, Amsalu, S., Christian Houdré +3
Computer Science · Mathematics · #05A16 #60C05 #60F05 #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1204.1009
openalex publication_date 2012/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider two independent random strings having same length and taking values uniformly in a common finite alphabet. We study the order of the variance of the length of the longest common subsequences (LCS) of these strings when long blocks, or other types of atypical substrings, are sparsely added into one of them. Under weak conditions on the derivative of the mean LCS-curve, the order of the variance of the LCS is shown to be linear in the length of the strings. We also argue that our proofs carry over to many models used by computational biologists to simulate DNA-sequences. This is the first result where the open question of the order of the fluctuation of the LCS of random strings is solved for a realistic model. Until now, this type of result had only been established for low entropy cases.