Expected length of the longest common subsequence for large alphabets
classification
🧮 math.CO
math.PR
keywords
commonexpectedgoeslengthlongestsubsequencealphabetalphabets
read the original 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\sqrt{k} goes to 2 as k goes to infinity.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
High-Rate Public-Key Pseudorandom Codes for Edit Errors
First high-rate public-key binary PRCs for edit channels via reduction from Hamming-robust PRCs and alphabet-size constructions attaining near-Singleton rates.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.