S. Alexander, Kenneth, The Rate of Convergence of the Mean Length of the Longest Common Subsequence, Annals of applied probability , 4(4), 1994, pp. 1074-1082
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.