Comptes Rendus
no. 9
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é1 ; Jüri Lember2 ; Heinrich Matzinger1
1 School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
2 Institute of Mathematical Statistics, Tartu University, Liivi 2-513 50409 Tartu, Estonia
Comptes Rendus. Mathématique, Volume 343 (2006) no. 9, pp. 589-594.

Soient X1,X2,… et Y1,Y2,… deux suites mutuellement indépendantes de variables aléatoires de Bernoulli indépendantes, équidistribuées de paramètre 1/2. Soit LCIn la longueur de la plus longue sous-suite croissante et commune aux deux sous-suites finies X1,…,Xn and Y1,…,Yn. Nous démontrons que, lorsque n tend vers l'infini, n−1/2(LCIn−n/2) converge en loi vers une fonctionnelle brownienne que nous identifions.

Let X1,X2,… and Y1,Y2,… be two independent sequences of iid Bernoulli random variables with parameter 1/2. Let LCIn be the length of the longest increasing sequence which is a subsequence of both finite sequences X1,…,Xn and Y1,…,Yn. We prove that, as n goes to infinity, n−1/2(LCIn−n/2) converges in law to a Brownian functional that we identify.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2006.10.004

Christian Houdré 1 ; Jüri Lember 2 ; Heinrich Matzinger 1

1 School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
2 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/

[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

Cité par Sources :

Commentaires - Politique