Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. (English) Zbl 0937.60001
Summary: We describe a simple one-person card game, patience sorting. Its analysis leads to a broad circle of ideas linking Young tableaux with the longest increasing subsequence of a random permutation via the Schensted correspondence. A recent highlight of this area is the work of J. Baik, P. A. Deift and K. Johansson [J. Am. Math. Soc. 12, No. 4, 1119-1178 (1999; Zbl 0932.05001)] which yields limiting probability laws via hard analysis of Toeplitz determinants.
MSC:
| 60C05 | Combinatorial probability |
| 05E10 | Combinatorial aspects of representation theory |
| 15B52 | Random matrices (algebraic aspects) |
| 60F05 | Central limit and other weak theorems |
| 82C22 | Interacting particle systems in time-dependent statistical mechanics |
| 60H15 | Stochastic partial differential equations (aspects of stochastic analysis) |
Citations:
Zbl 0932.05001Online Encyclopedia of Integer Sequences:
Number of block permutations on an n-set which are uniform, i.e., corresponding blocks have same size.Triangle of generalized Stirling numbers.
References:
| [1] | D. Aldous and P. Diaconis, Hammersley’s interacting particle process and longest increasing subsequences, Probab. Theory Related Fields 103 (1995), no. 2, 199 – 213. · Zbl 0836.60107 · doi:10.1007/BF01204214 |
| [2] | B.C. Arnold, N. Balakrishnan, and H.N. Nagarajo. Records. Wiley, 1998. CMP 98:15 · Zbl 0914.60007 |
| [3] | J. Baik, P.A. Deift, and K. Johansson. On the distribution of the length of the longest increasing subsequence of random permutations. Technical Report math.CO/9810105, XXX Math Archive, J. Amer. Math. Soc., 12:1119-1178, 1999. · Zbl 0932.05001 |
| [4] | J. Baik, P.A. Deift, and K. Johansson. On the distribution of the length of the second row of a Young diagram under Plancherel measure. Technical Report math.CO/9901118, XXX Math Archive, 1999. · Zbl 0963.05133 |
| [5] | J. Baik and E.M. Rains. Algebraic aspects of increasing subsequences. Technical Report math.CO/9905083, XXX Math Archive, 1999. · Zbl 1007.05096 |
| [6] | J. Baik and E.M. Rains. Generalized increasing subsequence problems II. Asymptotic results. Technical report, Courant Institute, 1999. |
| [7] | Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, Inc., New York-London-Sydney, 1968. · Zbl 0944.60003 |
| [8] | A. Borodin. Longest increasing subsequences of random colored permutations. Technical Report math.CO/9902001, XXX Math Archive, 1999. · Zbl 0923.05001 |
| [9] | A. Borodin, A. Okounkov, and G. Olshanski. On asymptotics of Plancherel measures for symmetric groups. Technical Report math.CO/9905032, XXX Math Archive, 1999. · Zbl 0938.05061 |
| [10] | D. Critchlow. Ulam’s metric. In Encyclopedia of Statistical Sciences, volume 9, pages 379-380. Wiley, 1988. |
| [11] | A. De Masi, N. Ianiro, A. Pellegrinotti, and E. Presutti, A survey of the hydrodynamical behavior of many-particle systems, Nonequilibrium phenomena, II, Stud. Statist. Mech., XI, North-Holland, Amsterdam, 1984, pp. 123 – 294. · Zbl 0567.76006 |
| [12] | Richard Durrett, Oriented percolation in two dimensions, Ann. Probab. 12 (1984), no. 4, 999 – 1040. · Zbl 0567.60095 |
| [13] | Richard Durrett, Probability, The Wadsworth & Brooks/Cole Statistics/Probability Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Theory and examples. · Zbl 0709.60002 |
| [14] | Ron Engelen, Paul Tommassen, and Wim Vervaat, Ignatov’s theorem: a new and short proof, J. Appl. Probab. Special Vol. 25A (1988), 229 – 236. A celebration of applied probability. · Zbl 0661.60062 |
| [15] | P. A. Ferrari and L. R. G. Fontes, Poissonian approximation for the tagged particle in asymmetric simple exclusion, J. Appl. Probab. 33 (1996), no. 2, 411 – 419. · Zbl 0855.60097 |
| [16] | Michael L. Fredman, On computing the length of longest increasing subsequences, Discrete Math. 11 (1975), 29 – 35. · Zbl 0312.68027 · doi:10.1016/0012-365X(75)90103-X |
| [17] | Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257 – 285. · Zbl 0704.05001 · doi:10.1016/0097-3165(90)90060-A |
| [18] | J. M. Hammersley, First-passage percolation, J. Roy. Statist. Soc. Ser. B 28 (1966), 491 – 496. · Zbl 0158.35506 |
| [19] | J. M. Hammersley, A few seedlings of research, Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971) Univ. California Press, Berkeley, Calif., 1972, pp. 345 – 394. |
| [20] | Gordon James and Adalbert Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn; With an introduction by Gilbert de B. Robinson. · Zbl 0491.20010 |
| [21] | T. A. Jenkyns and E. R. Muller, A probabilistic analysis of clock solitaire, Math. Mag. 54 (1981), no. 4, 202 – 208. · doi:10.2307/2689633 |
| [22] | K. Johansson. Shape fluctuations and random matrices. Technical report, Royal Inst. Technology, Stockholm, 1999. · Zbl 0969.15008 |
| [23] | Norman L. Johnson, Samuel Kotz, and N. Balakrishnan, Continuous univariate distributions. Vol. 2, 2nd ed., Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. · Zbl 0821.62001 |
| [24] | A. M. Vershik and S. V. Kerov, Asymptotic theory of the characters of a symmetric group, Funktsional. Anal. i Prilozhen. 15 (1981), no. 4, 15 – 27, 96 (Russian). · Zbl 0534.20008 |
| [25] | Harry Kesten, On the speed of convergence in first-passage percolation, Ann. Appl. Probab. 3 (1993), no. 2, 296 – 338. · Zbl 0783.60103 |
| [26] | Jeong Han Kim, On increasing subsequences of random permutations, J. Combin. Theory Ser. A 76 (1996), no. 1, 148 – 155. · Zbl 0859.05002 · doi:10.1006/jcta.1996.0095 |
| [27] | C. Kuykendall. Analyzing solitaire. Science, 283(5403):794-795, Feb. 5, 1999. |
| [28] | Thomas M. Liggett, Interacting particle systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. · Zbl 0559.60078 |
| [29] | B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206 – 222. · Zbl 0363.62068 · doi:10.1016/0001-8708(77)90030-5 |
| [30] | I. G. Macdonald, Symmetric functions and Hall polynomials, The Clarendon Press, Oxford University Press, New York, 1979. Oxford Mathematical Monographs. · Zbl 0487.20007 |
| [31] | C.L. Mallows. Problem 62-2, patience sorting. SIAM Review, 5:375-376, 1963. |
| [32] | C.L. Mallows. Patience sorting. Bull. Inst. Math. Appl., 9:216-224, 1973. |
| [33] | R. Daniel Mauldin and S. M. Ulam, Mathematical problems and games, Adv. in Appl. Math. 8 (1987), no. 3, 281 – 344. · Zbl 0642.00001 · doi:10.1016/0196-8858(87)90026-1 |
| [34] | S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability, Communications and Control Engineering Series, Springer-Verlag London, Ltd., London, 1993. · Zbl 0925.60001 |
| [35] | Albert H. Morehead and Geoffrey Mott-Smith. The Complete Book of Solitaire and Patience Games. Bantam, 1973. |
| [36] | A.M. Odlyzko, B. Poonen, H. Widom, and H. Wilf. On the distribution of longest increasing subsequences in random permutations. In Preparation, 1998. |
| [37] | A.M. Odlyzko and E.M. Rains. On longest increasing subsequences in random permutations. Technical report, AT&T Labs, 1998. · Zbl 0966.60010 |
| [38] | A. Okounkov. Random matrices and random permutations. Technical Report math.CO/9903176, XXX Math Archive, 1999. · Zbl 1018.15020 |
| [39] | David Partlett. Solitaire: Aces Up and 399 Other Card Games. Pantheon, 1979. |
| [40] | Shaiy Pilpel, Descending subsequences of random permutations, J. Combin. Theory Ser. A 53 (1990), no. 1, 96 – 116. · Zbl 0694.05004 · doi:10.1016/0097-3165(90)90022-O |
| [41] | A. Rabb. A probabilistic analysis of the game of solitaire, 1989. Undergraduate Honors Thesis, Harvard. |
| [42] | E. M. Rains, Increasing subsequences and the classical groups, Electron. J. Combin. 5 (1998), Research Paper 12, 9. · Zbl 0885.05112 |
| [43] | H. Rost, Nonequilibrium behaviour of a many particle process: density profile and local equilibria, Z. Wahrsch. Verw. Gebiete 58 (1981), no. 1, 41 – 53. · Zbl 0451.60097 · doi:10.1007/BF00536194 |
| [44] | Bruce E. Sagan, The symmetric group, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Representations, combinatorial algorithms, and symmetric functions. · Zbl 0823.05061 |
| [45] | C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179 – 191. · Zbl 0097.25202 · doi:10.4153/CJM-1961-015-3 |
| [46] | T. Seppäläinen, Hydrodynamic scaling, convex duality and asymptotic shapes of growth models, Markov Process. Related Fields 4 (1998), no. 1, 1 – 26. · Zbl 0906.60082 |
| [47] | R. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge University Press, 1999. CMP 99:09 · Zbl 0928.05001 |
| [48] | Richard P. Stanley, Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. With a foreword by Gian-Carlo Rota. · Zbl 0608.05001 |
| [49] | Dennis Stanton and Dennis White, Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986. · Zbl 0595.05002 |
| [50] | Craig A. Tracy and Harold Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), no. 1, 151 – 174. · Zbl 0789.35152 |
| [51] | C.A. Tracy and H. Widom. Random unitary matrices, permutations and Painlevé. Technical Report math.CO/9811154, XXX Math Archive, 1998. |
| [52] | C.A. Tracy and H. Widom. On the distribution of the lengths of the longest monotone subsequences in random words. Technical Report math.CO/9904042, XXX Math Archive, 1999. · Zbl 0989.60012 |
| [53] | S.M. Ulam. Some ideas and prospects in biomathematics. Ann. Rev. Biophys. Bioeng., 1:277-292, 1972. |
| [54] | R. Venkatsubramani. Hydrodynamic Limit for the Asymmetric Exclusion Process with Deterministic Initial Data and the Hammersley Process on \(S^1\). Ph.D. thesis, New York University, 1995. |
| [55] | A.M. Vershik and S.V. Kerov. Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tables. Soviet Math. Dokl., 18:527-531, 1977. Translation of Dokl. Acad. Nauk. SSSR 233 (1977) 1024-1027. · Zbl 0406.05008 |
| [56] | Pascual Llorente, Some problems in the theory of algebraic numbers, Publ. Sec. Mat. Univ. Autònoma Barcelona 23 (1981), 101 – 132 (Spanish). |
| [57] | M.S. Waterman and M. Vingron. Sequence comparison significance and Poisson approximation. Statist. Science, 9:367-381, 1994. CMP 95:10 · Zbl 0955.92501 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
