Expected length of the longest common subsequence for large alphabets

Abstrakt

We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield that the expectation of L divided by n converges to a constant.

We prove a conjecture of Sankoff and Mainville from the early 80's giving the limit of this constant for k tending to infinity.