On the rate of approximation in finite-alphabet longest increasing subsequence problems. (English) Zbl 1261.60012

Summary: 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.


60C05 Combinatorial probability
60G15 Gaussian processes
60G17 Sample path properties
05A16 Asymptotic enumeration
60F05 Central limit and other weak theorems
Full Text: DOI arXiv Euclid


[1] Baryshnikov, Y. (2001). GUEs and queues. Probab. Theory Related Fields 119 256-274. · Zbl 0980.60042
[2] Breton, J.-C. and Houdré, C. (2010). Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity. Bernoulli 16 471-492. · Zbl 1248.60009
[3] Etienne, M. P. and Vallois, P. (2004). Approximation of the distribution of the supremum of a centered random walk. Application to the local score. Methodol. Comput. Appl. Probab. 6 255-275. · Zbl 1045.60021
[4] Feller, W. (1968). An Introduction to Probability Theory and Its Applications , Vol. 1, 3rd ed. Wiley, New York. · Zbl 0155.23101
[5] Glynn, P. W. and Whitt, W. (1991). Departures from many queues in series. Ann. Appl. Probab. 1 546-572. · Zbl 0749.60090
[6] Gravner, J., Tracy, C. A. and Widom, H. (2001). Limit theorems for height fluctuations in a class of discrete space and time growth models. J. Stat. Phys. 102 1085-1132. · Zbl 0989.82030
[7] Houdré, C. and Litherland, T. On the limiting shape of young diagrams associated with Markov random words. Preprint. Available at . 1110.4570
[8] Houdré, C. and Litherland, T. J. (2009). On the longest increasing subsequence for finite and countable alphabets. In High Dimensional Probability V : The Luminy Volume. Inst. Math. Stat. Collect. 5 185-212. IMS, Beachwood, OH. · Zbl 1243.60022
[9] Its, A. R., Tracy, C. A. and Widom, H. (2001). Random words, Toeplitz determinants, and integrable systems. I. In Random Matrix Models and Their Applications. Math. Sci. Res. Inst. Publ. 40 245-258. Cambridge Univ. Press, Cambridge. · Zbl 0986.68104
[10] Its, A. R., Tracy, C. A. and Widom, H. (2001). Random words, Toeplitz determinants and integrable systems. II. Phys. D 152/153 199-224. · Zbl 0977.35103
[11] Johansson, K. (2001). Discrete orthogonal polynomial ensembles and the Plancherel measure. Ann. of Math. (2) 153 259-296. · Zbl 0984.15020
[12] Komlós, J., Major, P. and Tusnády, G. (1975). An approximation of partial sums of independent RV’s and the sample DF. I. Z. Wahrsch. Verw. Gebiete 32 111-131. · Zbl 0308.60029
[13] Komlós, J., Major, P. and Tusnády, G. (1976). An approximation of partial sums of independent RV’s, and the sample DF. II. Z. Wahrsch. Verw. Gebiete 34 33-58. · Zbl 0307.60045
[14] Lifshits, M. (2000). Lecture notes on strong approximation. Pub. IRMA Lille 53 No. 13, 25 pp.
[15] Mehta, M. L. (2004). Random Matrices , 3rd ed. Pure and Applied Mathematics ( Amsterdam ) 142 . Elsevier/Academic Press, Amsterdam. · Zbl 1107.15019
[16] Sakhanenko, A. I. (1984). Rate of convergence in the invariance principle for variables with exponential moments that are not identically distributed. In Limit Theorems for Sums of Random Variables. Trudy Inst. Mat. 3 4-49. “Nauka” Sibirsk. Otdel., Novosibirsk. · Zbl 0541.60024
[17] Tracy, C. A. and Widom, H. (2001). On the distributions of the lengths of the longest monotone subsequences in random words. Probab. Theory Related Fields 119 350-380. · Zbl 0989.60012
[18] van Beek, P. (1972). An application of Fourier methods to the problem of sharpening the Berry-Esseen inequality. Z. Wahrsch. Verw. Gebiete 23 187-196. · Zbl 0238.60020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.