Qingqing Liu

On the Variance of the Length of the Longest Common Subsequences in Random Words With an Omitted Letter

2018 · arXiv (Cornell University)

We investigate the variance of the length of the longest common subsequences of two independent random words of size $n$, where the letters of one word are i.i.d. uniformly drawn from $\{α_1, α_2, \cdots, α_m\}$, …