STANDARD DEVIATION OF THE LONGEST COMMON SUBSEQUENCE

被引：22

作者：

Lember, Jueri ^{[1
]}

Matzinger, Heinrich ^{[2
]}

机构：

[1] Univ Tartu, Inst Stat Math, EE-50409 Tartu, Estonia

[2] Georgia Tech, Sch Math, Atlanta, GA 30332 USA

来源：

ANNALS OF PROBABILITY | 2009年 / 37卷 / 03期

关键词：

Longest common subsequence; variance bound; Chvatal-Sankoff conjecture; EXPECTED LENGTH;

D O I：

10.1214/08-AOP436

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

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.

引用

页码：1192 / 1235

页数：44

共 17 条

[1] THE RATE OF CONVERGENCE OF THE MEAN LENGTH OF THE LONGEST COMMON SUBSEQUENCE [J].

Alexander, Kenneth S. .

ANNALS OF APPLIED PROBABILITY, 1994, 4 (04) :1074-1082

[2]

Amsalu S., 2007, ESAIM-PROBAB STAT, V11, P281

[3]

[Anonymous], 1975, J APPL PROBAB

[4]

[Anonymous], 1995, Introduction to computational biology: maps, sequences and genomes

[5] `A PHASE TRANSITION FOR THE SCORE IN MATCHING RANDOM SEQUENCES ALLOWING DELETIONS [J].

Arratia, Richard ;

Waterman, Michael S. .

ANNALS OF APPLIED PROBABILITY, 1994, 4 (01) :200-225

[6] Bounding the expected length of longest common subsequences and forests [J].

BaezaYates, RA ;

Gavaldà, R ;

Navarro, G ;

Scheihing, R .

THEORY OF COMPUTING SYSTEMS, 1999, 32 (04) :435-452

[7]

Bonetto F., 2006, ALEA-LAT AM J PROBAB, V2, P195

[8] Extensive simulations for longest common subsequences - Finite size scaling, a cavity solution, and configuration space properties [J].

de Monvel, JB .

EUROPEAN PHYSICAL JOURNAL B, 1999, 7 (02) :293-308

[9]

DEVROY L, 1996, APPL MATH NEW YORK, V31

[10] Large deviations-based upper bounds on the expected relative length of longest common subsequences [J].

Hauser, Raphael ;

Martinez, Servet ;

Matzinger, Heinrich .

ADVANCES IN APPLIED PROBABILITY, 2006, 38 (03) :827-852

← 1 2 →