Geodesic
A formula for the mean length of the longest common subsequence
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 10 (2017) no. 1, pp. 71-74.

Voir la notice de l'article provenant de la source Math-Net.Ru

The expected value $E$ of the longest common subsequence of letters in two random words is considered as a function of the $\alpha=|A|$ 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(\alpha, m, n)$ and its empirical proof are presented for fixed $ \alpha $ and $ m + n $. High accuracy of the formula in a wide range of values is confirmed by numerical simulations.
Keywords: longest common subsequence, expected value, LCS length, asymptotic formula.
Mots-clés : simulation 
@article{JSFU_2017_10_1_a10,
     author = {Sergej V. Znamenskij},
     title = {A formula for the mean length of the longest common subsequence},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {71--74},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/}
}
TY  - JOUR
AU  - Sergej V. Znamenskij
TI  - A formula for the mean length of the longest common subsequence
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2017
SP  - 71
EP  - 74
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/
LA  - en
ID  - JSFU_2017_10_1_a10
ER  - 
%0 Journal Article
%A Sergej V. Znamenskij
%T A formula for the mean length of the longest common subsequence
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2017
%P 71-74
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/
%G en
%F JSFU_2017_10_1_a10
Sergej V. Znamenskij. A formula for the mean length of the longest common subsequence. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 10 (2017) no. 1, pp. 71-74. http://geodesic.mathdoc.fr/item/JSFU_2017_10_1_a10/

[1] V. Chvátal, D. Sankoff, “Longest common subsequences of two random sequences”, J. Appl. Prob., 12 (1975), 306–315 | DOI | MR | Zbl

[2] M. A. Kiwi, M. Loebl, J. Matousek, “Expected length of the longest common subsequence for large alphabets”, Advances in Mathematics, 197:2 (2005), 480–498 | DOI | MR | Zbl

[3] G. S. Lueker, “Improved bounds on the average length of longest common subsequences”, Journal of the ACM, 56:3 (2009), 17 | DOI | MR | Zbl

[4] R. Bundschuh, “High precision simulations of the longest common subsequence problem”, The European Physical Journal B – Condensed Matter and Complex Systems, 22:4 (2001), 533–541 | DOI

[5] J. Boutet de Monvel, “Extensive simulations for longest common subsequences”, The European Physical Journal B – Condensed Matter and Complex Systems, 7:2 (1999), 293–308 | DOI

[6] R. Baeza-Yates, G. Navarro, R. Gavaldá, R. Schehing, “Bounding the expected length of the longest common subsequences and forests”, Theory of Computing Systems, 32:4 (1999), 435–452 | DOI | MR | Zbl

[7] Kang Ning, Kwok Pui Choi, Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences, 2013, arXiv: 1306.4253

[8] J. D. Dixon, Longest common subsequences in binary sequences, 2013, arXiv: 1307.2796

[9] S. V. Znamenskij, “A picture of common subsequence length for two random strings over an alphabet of 4 symbols”, Program systems: theory and applications, 7:1(28) (2016), 201–208