THE RATE OF THE CONVERGENCE OF THE MEAN SCORE IN RANDOM SEQUENCE COMPARISON

• 成果类型: Article
• 署名作者: Lember, Jueri; Matzinger, Heinrich; Torres, Felipe
• 署名单位: University of Tartu; University System of Georgia; Georgia Institute of Technology; University of Bielefeld
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/11-AAP778
• 发表日期: 2012
• 页码: 1046-1058
• 关键词: longest common subsequence; expected length; approximation; bounds

摘要

We consider a general class of superadditive scores measuring the similarity of two independent sequences of n i.i.d. letters from a finite alphabet. Our object of interest is the mean score by letter l(n). By subadditivity l(n) is nondecreasing and converges to a limit l. We give a simple method of bounding the difference l - l(n) and obtaining the rate of convergence. Our result generalizes the previous result of Alexander [Ann. Appl. Probab. 4 (1994) 1074-1082], where only the special case of the longest common subsequence was considered.