On the limiting law of the length of the longest common and increasing subsequences in random words

DOI10.1016/J.SPA.2016.09.005MaRDI QIDQ529438zbMATH OpenOpenAlexFDO

Authors Jean-Christophe Breton, Christian Houdré

Publication date 18 May 2017

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.06164

zbMATH Keywords

random matriceslongest common subsequencelast passage percolationlongest increasing subsequencerandom wordsDonsker's theoremoptimal alignment

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Central limit and other weak theorems (60F05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)

Abstract: Let $X=(X_i{)}_{ige1}$ and $Y=(Y_i{)}_{ige1}$ be two sequences of independent and identically distributed (iid) random variables taking their values, uniformly, in a common totally ordered finite alphabet. Let LCI${}_n$ be the length of the longest common and (weakly) increasing subsequence of $X_{1}cdots{X}_n$ and $Y_{1}cdots{Y}_n$. As $n$ grows without bound, and when properly centered and normalized, LCI${}_n$ is shown to converge, in distribution, towards a Brownian functional that we identify.

Recommendations

• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution
• On the longest common increasing binary subsequence
• On the longest increasing subsequence for finite and countable alphabets
• Maximal length of common words among random letter sequences
• On the order of the central moments of the length of the longest common subsequences in random words

Cites work

• scientific article; zbMATH DE number 3630761 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1957500 (Why is no real title available?)
• A linear space algorithm for computing a longest common increasing subsequence
• A scaling limit for queues in series
• A universality property for last-passage percolation paths close to the axis
• Algorithms and Computation
• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity
• Departures from many queues in series
• Discrete orthogonal polynomial ensembles and the Plancherel measure
• GUE minors, maximal Brownian functionals and longest increasing subsequences in random words
• GUEs and queues
• Limit theorems for height fluctuations in a class of discrete space and time growth models
• On the Limiting Shape of Young Diagrams Associated with Inhomogeneous Random Words
• 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
• On the longest common increasing binary subsequence
• On the longest increasing subsequence for finite and countable alphabets
• Random words, Toeplitz determinants and integrable systems. II
• Random words, Toeplitz determinants, and integrable systems. I
• The surprising mathematics of longest increasing subsequences

Cited in

(11)

• Staircase patterns in words: subsequences, subwords, and separation number
• A central limit theorem for the length of the longest common subsequences in random words
• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution
• Asymptotic results on weakly increasing subsequences in random words
• Maximal length of common words among random letter sequences
• On the longest common increasing binary subsequence
• Asymptotics for the length of the longest increasing subsequence of a binary Markov random word
• Longest common substring for random subshifts of finite type
• On the longest common subsequence of conjugation invariant random permutations
• On the order of the central moments of the length of the longest common subsequences in random words
• On the asymptotic average length of a maximum common subsequence for words over a finite alphabet

This page was built for publication: On the limiting law of the length of the longest common and increasing subsequences in random words

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