文章基本信息

标题：Deviation from Mean in Sequence Comparison with a Periodic Sequence
本地全文：下载
作者：Heinrich Matzinger, Jüri Lember ; Clement Durringer
期刊名称：Latin American Journal of Probability and Mathematical Statistics
电子版ISSN：1980-0436
出版年度：2007
卷号：III
出版社：Instituto Nacional De Matemática Pura E Aplicada
摘要：
Let Ln denote the length of the longest common subsequence of two
sequences 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). For such setup, our result
rejects the Chvatal-Sanko conjecture (1975) that VAR[Ln] = o(n
2
3 ) and answers
to Waterman's question (1994), whether the linear bound on VAR[Ln] can be im-
proved.
关键词：Sequence Comparison;Periodic Sequences;Conjecture