Improved bounds on the average length of longest common subsequences

ABSTRACT

Let Ln be the length of the longest common subsequence of two random binary strings of length n; we consider the expected value of Ln. It is known (see [3]) that there exists a, γ > 0 such that E[Ln] ~ γn; the exact value of γ is not known, but determination of bounds on its value has drawn attention. For some history and more references, see [4, 5, 6]. To my knowledge, the best previous bounds on γ are those of [4, 5], namely, a lower bound of 0.773911 and upper bound of 0.837623. (Improved bounds for related problems are presented in [2], but they do not improve the bounds for the constant γ considered here.) We improve the lower bound to 0.7880 and the upper bound to 0.8263. As in [4, 5], our method is essentially the analysis of a Markov chain corresponding to a finite automaton that reads pairs of strings. In our work, rather than using carefully constructed automata, we use computation on automata with very many states, based on the well-known dynamic programming solution to the longest common subsequence problem, that can fairly easily be constructed mechanically.

REFERENCES

• 1: K. S. Alexander. The rate of convergence of the mean length of the longest common subsequence. Annals of Applied Probability, 4(4):1074--1082, 1994.
• 2: R. A. Baeza-Yates, R. Gavaldà, G. Navarro, and R. Scheihing. Bounding the expected length of longest common subsequences and forests. Theory Comput. Systems, 32:435--452, 1999.
• 3: V. Chvátal and D. Sankoff. Longest common subsequences of two random sequences. Journal o} Applied Probability, 12:306--315, 1975.
• 4: V. Dančík. Expezted Length of Longest Common Subsequences. PhD thesis, Department of Computer Science, University of Warwick, Sept. 1994.
• 5: Vlado Dančík , Mike Paterson, Upper bounds for the expected length of a longest common subsequence of two binary sequences, Random Structures & Algorithms, v.6 n.4, p.449-458, July 1995 [doi>10.1002/rsa.3240060408]
• 6: J. M. Steele. Probability Theory and Combinatorial Optimization. CMBS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Measurement, Theory