Bounding the Expected Length of Longest Common Subsequences and Forests

Ricardo Baeza-Yates, Ricard Gavaldá and Gonzalo Navarro

We present two techniques to find lower and upper bounds for the expected length of longest common subsequences and forests of two random sequences of the same length, over a fixed size, uniformly distributed alphabet. We emphasize the power of the methods used, which are Markov chains and Kolmogorov complexity. As a corollary, we obtain some new lower and upper bounds for the problems mentioned.