On the longest common increasing binary subsequence (Q857117): Difference between revisions

This paper deals with the problem of the longest common and increasing subsequence of two random binary sequences. 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\). The authors prove that, as \(n\) goes to infinity, \(n^{-1/2}(\text{LCI}_n-n/2)\) converges in law to a Brownian functional that they identify.