文章基本信息
- 标题：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
