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

Presented by: 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.

Abstract (Original language)
Résumé

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.

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.

Received: 2006-01-03
Accepted: 2006-09-26
Published online: 2006-10-31

DOI: 10.1016/j.crma.2006.10.004

Author's affiliations:

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/

References
Cited by

[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

Cited by Sources:

Comments - Policy