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

DOI10.1016/J.SPA.2016.09.005zbMATH Open1361.05006arXiv1505.06164OpenAlexW2143972405MaRDI QIDQ529438FDOQ529438

Authors: Jean-Christophe Breton, Christian Houdré 

Publication date: 18 May 2017

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the distribution of the length of the longest increasing subsequence of random permutations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discrete orthogonal polynomial ensembles and the Plancherel measure
• GUEs and queues
• Limit theorems for height fluctuations in a class of discrete space and time growth models
• Departures from many queues in series
• The surprising mathematics of longest increasing subsequences
• On the longest common increasing binary subsequence
• A universality property for last-passage percolation paths close to the axis
• Algorithms and Computation
• A linear space algorithm for computing a longest common increasing subsequence
• Random words, Toeplitz determinants, and integrable systems. I
• On the longest increasing subsequence for finite and countable alphabets
• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity
• Random words, Toeplitz determinants and integrable systems. II
• On the distributions of the lengths of the longest monotone subsequences in random words
• A scaling limit for queues in series
• On the Limiting Shape of Young Diagrams Associated with Inhomogeneous Random Words
• GUE minors, maximal Brownian functionals and longest increasing subsequences in random words

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)