On the longest increasing subsequence for finite and countable alphabets

DOI10.1214/09-IMSCOLL513MaRDI QIDQ2900956zbMATH OpenOpenAlexFDO

Authors Trevis J. Litherland, Christian Houdré

Publication date 26 July 2012

Published in Institute of Mathematical Statistics Collections (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0612364, https://projecteuclid.org/euclid.imsc/1265119269

zbMATH Keywords

Brownian functionalfunctional central limit theoremlongest increasing subsequencetracy-widom distribution

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Central limit and other weak theorems (60F05) Functional limit theorems; invariance principles (60F17) Gaussian processes (60G15) Sample path properties (60G17)

Abstract: Let $X_1,X_2,\mathrm{...},X_n,\mathrm{...}$ be a sequence of iid random variables with values in a finite alphabet $1,\mathrm{...},m$. Let $L{I}_n$ be the length of the longest increasing subsequence of $X_1,X_2,\mathrm{...},X_n.$ We express the limiting distribution of $L{I}_n$ as functionals of $m$ and $(m-1)$-dimensional Brownian motions. These expressions are then related to similar functionals appearing in queueing theory, allowing us to further establish asymptotic behaviors as $m$ grows. The finite alphabet results are then used to treat the countable (infinite) alphabet.

Recommendations

• scientific article; zbMATH DE number 3860389
• The longest almost-increasing subsequence
• The Longest Almost-Increasing Subsequence
• scientific article; zbMATH DE number 7732144
• On the rate of approximation in finite-alphabet longest increasing subsequence problems
• scientific article; zbMATH DE number 1515819
• scientific article; zbMATH DE number 1047715
• Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Longest increasing subsequences and log concavity

Cited in

(10)

• On the rate of approximation in finite-alphabet longest increasing subsequence problems
• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution
• Multi-state asymmetric simple exclusion processes
• Simultaneous large deviations for the shape of Young diagrams associated with random words
• On the Limiting Shape of Young Diagrams Associated with Inhomogeneous Random Words
• Asymptotics for the length of the longest increasing subsequence of a binary Markov random word
• The Longest Almost-Increasing Subsequence
• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity
• On the limiting law of the length of the longest common and increasing subsequences in random words
• Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm

This page was built for publication: On the longest increasing subsequence for finite and countable alphabets

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