Thumbnail Image
Publication

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

Houdre, Christian
; 
Talata, Zsolt
Citations
Altmetric:
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 logn/n√ is obtained. The uniform binary case is further explored, and an improved 1/n√ rate obtained.
Description
This is the published version, also available here: http://dx.doi.org/10.1214/12-AAP853.
Date
2012-09-05
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Mathematical Statistics
Collections
Mathematics Scholarly Works
Show all metadata
Files
Thumbnail Image
TalataZ_AAP_22(6)2539.pdf
Adobe PDF, 232.56 KB
Research Projects
Organizational Units
Journal Issue
Keywords
Longest increasing subsequence, Brownian functional, approximation, rate of convergence
Citation
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.
URI
https://hdl.handle.net/1808/17225
DOI
10.1214/12-AAP853
Embedded videos