The Rate of Convergence of the Mean Length of the Longest Common Subsequence
The Rate of Convergence of the Mean Length of the Longest Common Subsequence
复制标题
最长公共子序列平均长度的收敛率
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
K. S. Alexander
中科院分区：
文献类型：
--
作者：
K. S. Alexander
给定两个 i.i.d.有限字母表中的 n 个字母的序列，可以考虑最长序列的长度 Ln，该最长序列是两个给定序列的子序列。众所周知，对于某些 y E [0, 1]，ELn 会像 yn 一样增长。这里表明yn ? ELn？ yn C(n log n)l/2 表示不依赖于字母分布的显式数值常量 C。在 n = 100,000 的模拟中，ELn/n 可以通过 k 个此类试验确定，置信度在 0.0055/k 范围内，置信度为 95%，这里的结果表明，对于任意字母分布，可以在 0.0225 + 0.0055/k 范围内确定 y，置信度为 95%。
Given two i.i.d. sequences of n letters from a finite alphabet, one can consider the length Ln of the longest sequence which is a subsequence of both the given sequences. It is known that ELn grows like yn for some y E [0, 1]. Here it is shown that yn ? ELn ? yn C(n log n)l/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/ k, and the results here show that y can then be determined with 95% confidence to within 0.0225 + 0.0055/ k, for an arbitrary letter distribution.