Large deviations-based upper bounds on the expected relative length of longest common subsequences

Consider the random variable L-n defined as the length of a longest common subsequence of two random strings of length n and whose random characters are independent and identically distributed over a finite alphabet. Chvatal and Sankoff showed that the limit gamma = lim(n-->infinity)E[L-n]/n is well defined. The exact value of this constant is not known, but various methods for the computation of upper and lower bounds have been discussed in the literature. Even so, high-precision bounds are hard to come by. In this paper we discuss how. large deviation theory can be used to derive a consistent sequence of upper bounds, (q(m))(m is an element of N), on gamma, and how Monte Carlo simulation can be used in theory to compute estimates, (q) over cap (m), of the q(m) such that, for given Xi > 0 and Lambda is an element of (0, 1), we have P[gamma < <(q)over cap> < gamma + Xi] >= Lambda. In other words, with high probability the result is an upper bound that approximates gamma to high precision. We establish O((1 - Lambda)(-1) Xi(-(4+epsilon))) as a theoretical upper bound on the complexity of computing <(q)over cap>(m) to the given level of accuracy and confidence. Finally, we discuss a practical heuristic based on our theoretical approach and discuss its empirical behavior.