On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words

Abstract

We investigate the order of the $r$-th, $1\le r<+\infty$, central moment of the length of the longest common subsequence of two independent random words of size $n$ whose letters are identically distributed and independently drawn from a finite alphabet. When all but one of the letters are drawn with small probabilities, which depend on the size of the alphabet, a lower bound is shown to be of order $n^{r/2}$. This result complements a generic upper bound also of order $n^{r/2}$.

arXiv commentFinal version, to appear in HDP VII, Progress in Probability, Birkhauser