The Rate of Convergence of the Mean Length of the Longest Common Subsequence

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 .n for some ..[0,1]. Here it is shown that .n.ELn..n.C(nlogn)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/.k, and the results here show that . can then be determined with 95% confidence to within 0.0225+0.0055/.k, for an arbitrary letter distribution.