On the rate of approximation in finite-alphabet longest increasing subsequence problems

Abstract

The rate of convergence of the distribution of the length of the longest increasing subsequence, toward the maximal eigenvalue of certain matrix ensembles, is investigated. For finite-alphabet uniform and nonuniform i.i.d. sources, a rate of $\log n/\sqrt{n}$ is obtained. The uniform binary case is further explored, and an improved $1/\sqrt{n}$ rate obtained.

Published in at http://dx.doi.org/10.1214/12-AAP853 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity

Cited by in corpus (1)

• Multi-state asymmetric simple exclusion processes