On the longest common increasing binary subsequence

Christian Houdré; Jüri Lember; Heinrich Matzinger

doi:10.1016/j.crma.2006.10.004

Probability Theory

On the longest common increasing binary subsequence
[Sur la plus longue sous-suite binaire croissante commune]

Présenté par : Marc Yor

Christian Houdré ¹ ; Jüri Lember ² ; Heinrich Matzinger ¹

¹ School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
² Institute of Mathematical Statistics, Tartu University, Liivi 2-513 50409 Tartu, Estonia

Comptes Rendus. Mathématique, Volume 343 (2006) no. 9, pp. 589-594.

Résumé
Abstract

Soient $X_{1}, X_{2}, \dots$ et $Y_{1}, Y_{2}, \dots$ deux suites mutuellement indépendantes de variables aléatoires de Bernoulli indépendantes, équidistribuées de paramètre 1/2. Soit ${LCI}_{n}$ la longueur de la plus longue sous-suite croissante et commune aux deux sous-suites finies $X_{1}, \dots, X_{n}$ and $Y_{1}, \dots, Y_{n}$ . Nous démontrons que, lorsque n tend vers l'infini, $n^{- 1 / 2} ({LCI}_{n} - n / 2)$ converge en loi vers une fonctionnelle brownienne que nous identifions.

Let $X_{1}, X_{2}, \dots$ and $Y_{1}, Y_{2}, \dots$ be two independent sequences of iid Bernoulli random variables with parameter 1/2. Let ${LCI}_{n}$ be the length of the longest increasing sequence which is a subsequence of both finite sequences $X_{1}, \dots, X_{n}$ and $Y_{1}, \dots, Y_{n}$ . We prove that, as n goes to infinity, $n^{- 1 / 2} ({LCI}_{n} - n / 2)$ converges in law to a Brownian functional that we identify.

Reçu le : 2006-01-03
Accepté le : 2006-09-26
Publié le : 2006-10-31

DOI : 10.1016/j.crma.2006.10.004

Affiliations des auteurs :

Christian Houdré ¹ ; Jüri Lember ² ; Heinrich Matzinger ¹

¹ School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
² Institute of Mathematical Statistics, Tartu University, Liivi 2-513 50409 Tartu, Estonia

@article{CRMATH_2006__343_9_589_0,
     author = {Christian Houdr\'e and J\"uri Lember and Heinrich Matzinger},
     title = {On the longest common increasing binary subsequence},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {589--594},
     publisher = {Elsevier},
     volume = {343},
     number = {9},
     year = {2006},
     doi = {10.1016/j.crma.2006.10.004},
     language = {en},
}

TY  - JOUR
AU  - Christian Houdré
AU  - Jüri Lember
AU  - Heinrich Matzinger
TI  - On the longest common increasing binary subsequence
JO  - Comptes Rendus. Mathématique
PY  - 2006
SP  - 589
EP  - 594
VL  - 343
IS  - 9
PB  - Elsevier
DO  - 10.1016/j.crma.2006.10.004
LA  - en
ID  - CRMATH_2006__343_9_589_0
ER  -

%0 Journal Article
%A Christian Houdré
%A Jüri Lember
%A Heinrich Matzinger
%T On the longest common increasing binary subsequence
%J Comptes Rendus. Mathématique
%D 2006
%P 589-594
%V 343
%N 9
%I Elsevier
%R 10.1016/j.crma.2006.10.004
%G en
%F CRMATH_2006__343_9_589_0

Christian Houdré; Jüri Lember; Heinrich Matzinger. On the longest common increasing binary subsequence. Comptes Rendus. Mathématique, Volume 343 (2006) no. 9, pp. 589-594. doi : 10.1016/j.crma.2006.10.004. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2006.10.004/

Bibliographie
Cité par

[1] J. Baik; P. Deift; K. Johansson On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc., Volume 12 (1999), pp. 1119-1178

[2] Yu. Baryshnikov GUEs and queues, Probab. Theory Related Fields, Volume 119 (2001), pp. 256-274

[3] A. Borodin Longest increasing subsequences of random colored permutations, Electron. J. Combin., Volume 6 (1999) (Research Paper 13, 12 pp)

[4] A. Its; C. Tracy; H. Widom Random words, Toeplitz determinants, and integrable systems. I. Random matrix models and their applications, Math. Sci. Res. Inst. Publ., vol. 40, Cambridge Univ. Press, Cambridge, 2001, pp. 245-258

[5] A. Its; C. Tracy; H. Widom Random words, Toeplitz determinants and integrable systems. II. Advances in nonlinear mathematics and science, Physica D, Volume 152/153 (2001), pp. 199-224

[6] K. Johansson Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math., Volume 153 (2001), pp. 259-296

[7] D. Revuz; M. Yor Continuous Martingales and Brownian Motion, Grundlehren der Mathematischen Wissenschaften, Fundamental Principles of Mathematical Sciences, vol. 293, Springer-Verlag, Berlin, 1999

[8] C. Tracy; H. Widom On the distributions of the lengths of the longest monotone subsequences in random words, Probab. Theory Related Fields, Volume 119 (2001), pp. 350-380

[9] M. Waterman Introduction to Computational Biology, Chapman & Hall, 1995

[10] H. Zhang Alignment of BLAST high-scoring segment pairs based on the longest increasing subsequence algorithm, Bioinformatics, Volume 19 (2003), pp. 1391-1396

Christian Houdré; Ümit Işlak A central limit theorem for the length of the longest common subsequences in random words, Electronic Journal of Probability, Volume 28 (2023), p. 24 (Id/No 3) | DOI:10.1214/22-ejp894 | Zbl:7644433
Clément Deslandes; Christian Houdré On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution, Electronic Journal of Probability, Volume 26 (2021), p. 27 (Id/No 69) | DOI:10.1214/21-ejp612 | Zbl:1511.68212
Jüri Lember; Heinrich Matzinger; Joonas Sova; Fabio Zucca Lower bounds for moments of global scores of pairwise Markov chains, Stochastic Processes and their Applications, Volume 128 (2018) no. 5, pp. 1678-1710 | DOI:10.1016/j.spa.2017.08.009 | Zbl:1390.60354
Jun Tao Duan; Heinrich Matzinger; Ionel Popescu Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets, Journal of Statistical Physics, Volume 168 (2017) no. 5, pp. 1056-1084 | DOI:10.1007/s10955-017-1835-6 | Zbl:1373.92094
Jean-Christophe Breton; Christian Houdré On the limiting law of the length of the longest common and increasing subsequences in random words, Stochastic Processes and their Applications, Volume 127 (2017) no. 5, pp. 1676-1720 | DOI:10.1016/j.spa.2016.09.005 | Zbl:1361.05006
Christian Houdré; Heinrich Matzinger Closeness to the diagonal for longest common subsequences in random words, Electronic Communications in Probability, Volume 21 (2016) no. none | DOI:10.1214/16-ecp4029
Christian Houdré; Jinyong Ma On the order of the central moments of the length of the longest common subsequences in random words, High dimensional probability VII. The Cargèse volume. Selected papers based on the presentations at the 7th conference, HDP VII, Institut d'Études Scientifiques de Cargèse, IESC, Fance, May 26–30, 2014, Basel: Birkhäuser/Springer, 2016, pp. 105-136 | DOI:10.1007/978-3-319-40519-3_5 | Zbl:1382.60020
Christian Houdré; Heinrich Matzinger On the variance of the optimal alignments score for binary random words and an asymmetric scoring function, Journal of Statistical Physics, Volume 164 (2016) no. 3, pp. 693-734 | DOI:10.1007/s10955-016-1549-1 | Zbl:1350.60102
Chihiro Matsui Multi-state asymmetric simple exclusion processes, Journal of Statistical Physics, Volume 158 (2015) no. 1, pp. 158-191 | DOI:10.1007/s10955-014-1121-9 | Zbl:1317.82032
Jüri Lember; Heinrich Matzinger; Anna Vollmer Optimal alignments of longest common subsequences and their path properties, Bernoulli, Volume 20 (2014) no. 3, pp. 1292-1343 | DOI:10.3150/13-bej522 | Zbl:1312.60004
Raphael Hauser; Heinrich Matzinger Letter change bias and local uniqueness in optimal sequence alignments, Journal of Statistical Physics, Volume 153 (2013) no. 3, pp. 512-529 | DOI:10.1007/s10955-013-0819-4 | Zbl:1315.60011
Christian Houdré; Trevis J. Litherland Asymptotics for the Length of the Longest Increasing Subsequence of a Binary Markov Random Word, Malliavin Calculus and Stochastic Analysis, Volume 34 (2013), p. 511 | DOI:10.1007/978-1-4614-5906-4_23
Jüri Lember; Heinrich Matzinger Standard deviation of the longest common subsequence, The Annals of Probability, Volume 37 (2009) no. 3, pp. 1192-1235 | DOI:10.1214/08-aop436 | Zbl:1182.60004
Saba Amsalu; Heinrich Matzinger; Marina Vachkovskaia Thermodynamical approach to the longest common subsequence problem, Journal of Statistical Physics, Volume 131 (2008) no. 6, pp. 1103-1120 | DOI:10.1007/s10955-008-9533-z | Zbl:1214.82066

Cité par 14 documents. Sources : Crossref, zbMATH

Commentaires - Politique