ON THE RATE OF APPROXIMATION IN FINITE-ALPHABET LONGEST INCREASING SUBSEQUENCE PROBLEMS

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 logn/ p n is obtained. The uniform binary case is further explored, and an improved 1/ p n rate obtained.