Standard deviation of the longest common subsequence

Jüri Lember, Heinrich Matzinger

Let $L_n$ be the length of the longest common subsequence of two independent i.i.d. sequences of Bernoulli variables of length $n$. We prove that the order of the standard deviatio…