Probability Theory
On the longest common increasing binary subsequence
Comptes Rendus. Mathématique, Volume 343 (2006) no. 9, pp. 589-594.

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, n1/2(LCInn/2) converges in law to a Brownian functional that we identify.

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, n1/2(LCInn/2) converge en loi vers une fonctionnelle brownienne que nous identifions.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2006.10.004
Houdré, Christian 1; Lember, Jüri 2; Matzinger, Heinrich 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 = {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, Volume 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/

[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

Cited by Sources: