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

Houdré, Christian; Talata, Zsolt

Ann. Appl. Probab. 22, No. 6, 2539-2559 (2012).

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.

MSC:

60C05	Combinatorial probability
60G15	Gaussian processes
60G17	Sample path properties
05A16	Asymptotic enumeration
60F05	Central limit and other weak theorems

Keywords:

longest increasing subsequence; Brownian functional; approximation; rate of convergence

References:

[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