A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words

Abstract

Let $(X_i{)}_{i\ge 1}$ and $(Y_i{)}_{i\ge 1}$ be two independent sequences of independent identically distributed random variables taking their values in a common finite alphabet and having the same law. Let $L{C}_n$ be the length of the longest common subsequences of the two random words $X_1\cdots X_n$ and $Y_1\cdots Y_n$. Under a lower bound assumption on the order of its variance, $L{C}_n$ is shown to satisfy a central limit theorem. This is in contrast to the limiting distribution of the length of the longest common subsequences in two independent uniform random permutations of $\{1,\dots ,n\}$, which is shown to be the Tracy-Widom distribution.

Revised arguments, main result unchanged; Corrected typos; Added references

References in corpus (9)

• A new method of normal approximation
• On Stein's Method for Infinitely Divisible Laws With Finite First Moment
• Standard deviation of the longest common subsequence
• Sparse long blocks and the variance of the longest common subsequences in random words
• Minimal spanning trees and Stein's method
• A Central Limit Theorem for the Optimal Alignments Score in Multiple Random Words
• On the limiting law of the length of the longest common and increasing subsequences in random words
• Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences
• Simulations, Computations, and Statistics for Longest Common Subsequences

Cited by in corpus (11)

• New Kolmogorov bounds for functionals of binomial point processes
• A Central Limit Theorem for the Optimal Alignments Score in Multiple Random Words
• On the limiting law of the length of the longest common and increasing subsequences in random words
• Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences
• Concentration of Geodesics in Directed Bernoulli Percolation
• Simulations, Computations, and Statistics for Longest Common Subsequences
• The Length of the Longest Common Subsequence of Two Independent Mallows Permutations
• On the longest common subsequence of independent random permutations invariant under conjugation
• A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations
• On an alternative sequence comparison statistic of Steele
• Power Lower Bounds for the Central Moments of the Last Passage Time for Directed Percolation in a Thin Rectangle