Improved Bounds on the Average Length of Longest Common Subsequences

摘要

It has long been known [Chvatal and Sankoff 1975] that the average length of the longest common subsequence of two random strings of length n over an alphabet of size k is asymptotic to yγ_kn for some constant γ_k depending on k. The value of these constants remains unknown, and a number of papers have proved upper and lower bounds on them. We discuss techniques, involving numerical calculations with recurrences on many variables, for determining lower and upper bounds on these constants. To our knowledge, the previous best-known lower and upper bounds for γ_2 were those of Dancfk and Paterson, approximately 0.773911 and 0.837623 [Dancfk 1994; Dancik and Paterson 1995]. We improve these to 0.788071 and 0.826280. This upper bound is less than the γ_2 given by Steele's old conjecture (see Steele [1997, page 3]) that γ_2 = 2/(1 + 2~(1/2)) ≈ 0.828427. (As Steele points out, experimental evidence had already suggested that this conjectured value was too high.) Finally, we show that the upper bound technique described here could be used to produce, for any k, a sequence of upper bounds converging to γ_k, though the computation time grows very quickly as better bounds are guaranteed.