Expected length of the longest common subsequence for large alphabets

2003/08/25 by Marcos Kiwi, Kiwi, Marcos, Martin Loebl +4 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Random Matrices and Applications #math.CO #math.PR #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0308234

14 pages, 1 figure, LaTex

arxiv created 2003/08/25 · openalex publication_date 2003/08/25 · arxiv updated 2009/12/01 · openalex created_date 2017/02/10 · openalex updated_date 2026/07/28

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 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√(k) goes to 2 as k goes to infinity.

Cited by

• Incorporating indel channels into average-case analysis of seed-chain-extend

Related

• Expected Length of the Longest Common Subsequence of Multiple Strings
• Longest common subsequences between words of very unequal length
• Improved Lower Bounds on the Expected Length of Longest Common Subsequences
• Longest common subsequences in sets of words
• Improved Approximation for Longest Common Subsequence over Small Alphabets