Expected length of the longest common subsequence for large alphabets

Abstract

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 E[L]/n converges to a constant gamma(k). We prove a conjecture of Sankoff and Mainville from the early 1980s claiming that gamma(k)root k -> 2 as k -> infinity.