On the longest common increasing binary subsequence

Houdré, Christian; Lember, Jüri; Matzinger, Heinrich

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

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

¹ 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, Tome 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 :

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

¹ 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 = {Houdr\'e, Christian and Lember, J\"uri and Matzinger, Heinrich},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2006.10.004/}
}

TY  - JOUR
AU  - Houdré, Christian
AU  - Lember, Jüri
AU  - Matzinger, Heinrich
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2006.10.004/
DO  - 10.1016/j.crma.2006.10.004
LA  - en
ID  - CRMATH_2006__343_9_589_0
ER  -

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

Houdré, Christian; Lember, Jüri; Matzinger, Heinrich. On the longest common increasing binary subsequence. Comptes Rendus. Mathématique, Tome 343 (2006) no. 9, pp. 589-594. doi : 10.1016/j.crma.2006.10.004. http://www.numdam.org/articles/10.1016/j.crma.2006.10.004/

Bibliographie
Cité par

[1] Baik, J.; Deift, P.; Johansson, K. 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] Baryshnikov, Yu. GUEs and queues, Probab. Theory Related Fields, Volume 119 (2001), pp. 256-274

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

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

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

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

[8] Tracy, C.; Widom, H. 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] Waterman, M. Introduction to Computational Biology, Chapman & Hall, 1995

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

Cité par Sources :