Longest common subsequences of two random sequences

Summary Given two random k -ary sequences of length n, what is f ( n,k ), the expected length of their longest common subsequence? This problem arises in the study of molecular evolution. We calculate f ( n,k ) for all k, where n ≦ 5, and f ( n, 2) where n ≦ 10. We study the limiting behaviour of n –1 f ( n,k ) and derive upper and lower bounds on these limits for all k. Finally we estimate by Monte-Carlo methods f (100, k ), f (1000,2) and f (5000,2).