On the longest common increasing binary subsequence

DOI10.1016/J.CRMA.2006.10.004MaRDI QIDQ857117zbMATH OpenOpenAlexFDO

Authors Christian Houdré, J. Lember, Heinrich Matzinger

Publication date 14 December 2006

Published in Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.crma.2006.10.004

zbMATH Keywords

Binary sequenceBrownian functional

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05)

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.

Recommendations

• On the limiting law of the length of the longest common and increasing subsequences in random words
• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution
• Asymptotics for the length of the longest increasing subsequence of a binary Markov random word
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Standard deviation of the longest common subsequence

Cites work

• Discrete orthogonal polynomial ensembles and the Plancherel measure
• GUEs and queues
• scientific article; zbMATH DE number 1245556 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• Longest increasing subsequences of random colored permutations
• On the distribution of the length of the longest increasing subsequence of random permutations
• On the distributions of the lengths of the longest monotone subsequences in random words
• Random words, Toeplitz determinants and integrable systems. II
• Random words, Toeplitz determinants, and integrable systems. I

Cited in

(17)

• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
• Longest increasing subsequences and log concavity
• Lower bounds for moments of global scores of pairwise Markov chains
• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution
• Standard deviation of the longest common subsequence
• Multi-state asymmetric simple exclusion processes
• Letter change bias and local uniqueness in optimal sequence alignments
• A central limit theorem for the length of the longest common subsequences in random words
• Compound Poisson approximation for long increasing sequences
• Asymptotics for the length of the longest increasing subsequence of a binary Markov random word
• On the order of the central moments of the length of the longest common subsequences in random words
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
• Optimal alignments of longest common subsequences and their path properties
• scientific article; zbMATH DE number 806867 (Why is no real title available?)
• On longest matching consecutive subsequence
• On the limiting law of the length of the longest common and increasing subsequences in random words
• Thermodynamical approach to the longest common subsequence problem

This page was built for publication: On the longest common increasing binary subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q857117)