Longest common subsequences between words of very unequal length

Abstract

We consider the expected length of the longest common subsequence between two random words of lengths $n$ and $(1-\epsilon )kn$ over $k$-symbol alphabet. It is well-known that this quantity is asymptotic to ${\gamma }_{k,\epsilon }n$ for some constant ${\gamma }_{k,\epsilon }$. We show that ${\gamma }_{k,\epsilon }$ is of the order $1-c{\epsilon }^2$ uniformly in $k$ and $\epsilon$. In addition, for large $k$, we give evidence that ${\gamma }_{k,\epsilon }$ approaches $1-\frac{1}{4}{\epsilon }^2$, and prove a matching lower bound.

38 pages

References in corpus (3)

• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity
• Tail estimates for sums of variables sampled from a random walk
• On the Limiting Shape of Young Tableaux Associated With Inhomogeneous Random Words