A Formula for the Mean Length of the Longest Common Subsequence

Abstract

The expected value E of the longest common subsequence of letters in two random words is considered as a function of the = jAj of alphabet and of words lengths m and n. It is assumed that each letter independently appears at any position with equal probability. A simple expression for E( ; m; n) and its empirical proof are presented for fixed and m + n. High accuracy of the formula in a wide range of values is confirmed by numerical simulations

Математическое ожидание E длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от мощности алфавита jAj и длин m и n этих слов. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Предъявлено простое выражение для E( ; m; n) при фиксированных и m + n