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 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.

Keywords

• Expected
• length
• longest
• common
• subsequence
• large
• alphabets