STANDARD DEVIATION OF THE LONGEST COMMON SUBSEQUENCE
Jüri Lember, Heinrich Matzinger · 2013
Abstract. Let Ln designate 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 deviation of Ln is n, provided the parameter of the Bernoulli variables is small enough. This validates Waterman’s conjecture in this situation [13]. The order