Comptes Rendus
Probability Theory
On the longest common increasing binary subsequence
[Sur la plus longue sous-suite binaire croissante commune]
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, n1/2(LCInn/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, n1/2(LCInn/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

  • 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