THE RATE OF CONVERGENCE OF THE MEAN LENGTH OF THE LONGEST COMMON SUBSEQUENCE
成果类型：
Article
署名作者：
Alexander, Kenneth S.
署名单位：
University of Southern California
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/aoap/1177004903
发表日期：
1994
页码：
1074-1082
关键词：
摘要：
Given two i.i.d. sequences of n letters from a finite alphabet, one can consider the length L-n of the longest sequence which is a subsequence of both the given sequences. It is known that ELn grows like gamma n for some gamma is an element of [0, 1]. Here it is shown that gamma n >= ELn >= gamma n - C(n log n)(1/2) for an explicit numerical constant C which does not depend on the distribution of the letters. In simulations with n = 100,000, ELn/n can be determined from k such trials with 95% confidence to within 0.0055/root k, and the results here show that gamma can then be determined with 95% confidence to within 0.0225 + 0.0055/root k, for an arbitrary letter distribution.