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

preprint2016arXivOpen access

Abstract

We investigate the order of the rr-th, 1≤r<+∞1\le r < +\infty, central moment of the length of the longest common subsequence of two independent random words of size nn 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 nr/2n^{r/2}. This result complements a generic upper bound also of order nr/2n^{r/2}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.