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 Lₙ of the longest sequence which is a subsequence of both the given sequences. It is known that ELₙ grows like γ n for some γ ∈ 0, 1. Here it is shown that γ n ≥ ELₙ ≥ γ 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, ELₙ/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.