improved bounds on the average length of longest common subsequences
Let L n be the length of the longest common subsequence of two random binary strings of length n; we consider the expected value of L n . It is known (see [3]) that there exists a, ? > 0 such that E[ L n ] ~ ? 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.
longest common subsequences dynamic programming average-case analysis arratia-steele conjecture