On the Order of the Central Moments of the Length of the Longest Common Subsequence

On the Order of the Central Moments of the Length of the Longest Common Subsequence - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: On the Order of the Central Moments of the Length of the Longest Common Subsequence
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}$.

Autor: Christian Houdré; Jinyong Ma

Fuente: https://archive.org/