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

Publication date: 22 December 2018

Abstract: 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

a l p h a_{1}, a l p h a_{2}, c d o t s, a l p h a_{m}

, while the letters of the other word are i.i.d. drawn from

a l p h a_{1}, a l p h a_{2}, c d o t s, a l p h a_{m}, a l p h a_{m + 1}

, with probability

p > 0

to be

a l p h a_{m + 1}

, and

(1 - p) / m > 0

for all the other letters. The order of the variance of this length is shown to be linear in

n

.

This page was built for publication: On the Variance of the Length of the Longest Common Subsequences in Random Words With an Omitted Letter