Expected length of the longest common subsequence for large alphabets

Kiwi, Marcos; Loebl, Martin; Matousek, Jiri

Expected length of the longest common subsequence for large alphabets

Authors

Kiwi, Marcos

Loebl, Martin

Matousek, Jiri

Description

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 expected value of L, when normalized by n, converges to a constant C_k. We prove a conjecture of Sankoff and Mainville from the early 80's claiming that C_k\sqrt{k} goes to 2 as k goes to infinity.
14 pages, 1 figure, LaTex