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/n√ is obtained. The uniform binary case is further explored, and an improved 1/n√ rate obtained.
This is the published version, also available here: http://dx.doi.org/10.1214/12-AAP853.
Houdré, Christian; Talata, Zsolt. On the rate of approximation in finite-alphabet longest increasing subsequence problems. Ann. Appl. Probab. 22 (2012), no. 6, 2539--2559. http://dx.doi.org/10.1214/12-AAP853.
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please
share your stories
about how Open Access to this item benefits YOU.
The University of Kansas prohibits discrimination on the basis of race, color, ethnicity, religion, sex, national origin, age, ancestry, disability, status as a veteran, sexual orientation, marital status, parental status, gender identity, gender expression and genetic information in the University’s programs and activities. The following person has been designated to handle inquiries regarding the non-discrimination policies: Director of the Office of Institutional Opportunity and Access, IOA@ku.edu, 1246 W. Campus Road, Room 153A, Lawrence, KS, 66045, (785)864-6414, 711 TTY.