STANDARD DEVIATION OF THE LONGEST COMMON SUBSEQUENCE

• 成果类型: Article
• 署名作者: Lember, Jueri; Matzinger, Heinrich
• 署名单位: University of Tartu; University System of Georgia; Georgia Institute of Technology
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/08-AOP436
• 发表日期: 2009
• 页码: 1192-1235
• 关键词: expected length

摘要

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 deviation of L-n is root n, provided the parameter of the Bernoulli variables is small enough. This validates Waterman's conjecture in this situation [Philos. Trans. R. Soc. Lond. Ser B 344 (1994) 383-390]. The order conjectured by Chvatal and Sankoff [J. Appl. Probab. 12 (1975) 306-315], however, is different.