On the rate of approximation in finite-alphabet longest increasing subsequence problems
Christian Houdré, Zsolt Talata · The Annals of Applied Probability · 2012
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.