Deviation from mean in sequence comparison with a periodic sequence
Heinrich Matzinger, Clément Durringer, António Machado · 2007
Abstract. Let Ln denote the length of the longest common subsequence of two se-quences of length n. We draw one of the sequences i.i.d., but the other is non-random and periodic. We prove that VAR[Ln] = Θ(n). This confirms the conjecture of Waterman [9] in the special case when one sequence is periodic.