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

• 成果类型: Article
• 署名作者: Houdre, Christian; Talata, Zsolt
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Kansas
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/12-AAP853
• 发表日期: 2012
• 页码: 2539-2559
• 关键词: partial sums

摘要

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