On the longest common increasing binary subsequence

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. To cite this article: C. Houdré et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).

Résumé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. Pour citer cet article : C. Houdré et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).