On the longest common increasing binary subsequence
type: Item
instance of: scholarly article
title: On the longest common increasing binary subsequence
zbMATH Open document ID: 1106.60033
author: Christian Houdré
author: J. Lember
author: Heinrich Matzinger
published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris
publication date: 2006-12-14T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 60F05
zbMATH DE Number: 5080215
zbMATH Keywords: Binary sequence
zbMATH Keywords: Brownian functional
reviewed by: N. G. Gamkrelidze
MaRDI profile type: Publication
full work available at URL: j.crma.2006.10.004
OpenAlex ID: W1981481562
cites work: On the distribution of the length of the longest increasing subsequence of random permutations
cites work: GUEs and queues
cites work: Longest increasing subsequences of random colored permutations
cites work: Random words, Toeplitz determinants, and integrable systems. I
cites work: Random words, Toeplitz determinants and integrable systems. II
cites work: Discrete orthogonal polynomial ensembles and the Plancherel measure
cites work: Q4226355
cites work: On the distributions of the lengths of the longest monotone subsequences in random words
cites work: Q4315008
DOI: 10.1016/J.CRMA.2006.10.004
description: scientific article; zbMATH DE number 5080215