Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
HTML articles powered by AMS MathViewer
- by David Aldous and Persi Diaconis PDF
- Bull. Amer. Math. Soc. 36 (1999), 413-432 Request permission
Abstract:
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 Baik-Deift-Johansson which yields limiting probability laws via hard analysis of Toeplitz determinants.References
- D. Aldous and P. Diaconis, Hammersley’s interacting particle process and longest increasing subsequences, Probab. Theory Related Fields 103 (1995), no. 2, 199–213. MR 1355056, DOI 10.1007/BF01204214
- B.C. Arnold, N. Balakrishnan, and H.N. Nagarajo. Records. Wiley, 1998.
- 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.
- 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.
- J. Baik and E.M. Rains. Algebraic aspects of increasing subsequences. Technical Report math.CO/9905083, XXX Math Archive, 1999.
- J. Baik and E.M. Rains. Generalized increasing subsequence problems II. Asymptotic results. Technical report, Courant Institute, 1999.
- Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0233396
- A. Borodin. Longest increasing subsequences of random colored permutations. Technical Report math.CO/9902001, XXX Math Archive, 1999.
- A. Borodin, A. Okounkov, and G. Olshanski. On asymptotics of Plancherel measures for symmetric groups. Technical Report math.CO/9905032, XXX Math Archive, 1999.
- D. Critchlow. Ulam’s metric. In Encyclopedia of Statistical Sciences, volume 9, pages 379–380. Wiley, 1988.
- 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. MR 757003
- Richard Durrett, Oriented percolation in two dimensions, Ann. Probab. 12 (1984), no. 4, 999–1040. MR 757768
- Richard Durrett, Probability, The Wadsworth & Brooks/Cole Statistics/Probability Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Theory and examples. MR 1068527
- 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. MR 974584, DOI 10.1017/s0021900200040389
- 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. MR 1385350, DOI 10.1017/s0021900200099824
- Michael L. Fredman, On computing the length of longest increasing subsequences, Discrete Math. 11 (1975), 29–35. MR 354386, DOI 10.1016/0012-365X(75)90103-X
- Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257–285. MR 1041448, DOI 10.1016/0097-3165(90)90060-A
- J. M. Hammersley, First-passage percolation, J. Roy. Statist. Soc. Ser. B 28 (1966), 491–496. MR 214163, DOI 10.1111/j.2517-6161.1966.tb00661.x
- 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. MR 0405665
- 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. MR 644144
- T. A. Jenkyns and E. R. Muller, A probabilistic analysis of clock solitaire, Math. Mag. 54 (1981), no. 4, 202–208. MR 627454, DOI 10.2307/2689633
- K. Johansson. Shape fluctuations and random matrices. Technical report, Royal Inst. Technology, Stockholm, 1999.
- 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. MR 1326603
- 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). MR 639197
- Harry Kesten, On the speed of convergence in first-passage percolation, Ann. Appl. Probab. 3 (1993), no. 2, 296–338. MR 1221154
- Jeong Han Kim, On increasing subsequences of random permutations, J. Combin. Theory Ser. A 76 (1996), no. 1, 148–155. MR 1405997, DOI 10.1006/jcta.1996.0095
- C. Kuykendall. Analyzing solitaire. Science, 283(5403):794–795, Feb. 5, 1999.
- Thomas M. Liggett, Interacting particle systems, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231, DOI 10.1007/978-1-4613-8542-4
- B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222. MR 1417317, DOI 10.1016/0001-8708(77)90030-5
- I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979. MR 553598
- C.L. Mallows. Problem 62-2, patience sorting. SIAM Review, 5:375–376, 1963.
- C.L. Mallows. Patience sorting. Bull. Inst. Math. Appl., 9:216–224, 1973.
- R. Daniel Mauldin and S. M. Ulam, Mathematical problems and games, Adv. in Appl. Math. 8 (1987), no. 3, 281–344. MR 898709, DOI 10.1016/0196-8858(87)90026-1
- S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability, Communications and Control Engineering Series, Springer-Verlag London, Ltd., London, 1993. MR 1287609, DOI 10.1007/978-1-4471-3267-7
- Albert H. Morehead and Geoffrey Mott-Smith. The Complete Book of Solitaire and Patience Games. Bantam, 1973.
- A.M. Odlyzko, B. Poonen, H. Widom, and H. Wilf. On the distribution of longest increasing subsequences in random permutations. In Preparation, 1998.
- A.M. Odlyzko and E.M. Rains. On longest increasing subsequences in random permutations. Technical report, AT&T Labs, 1998.
- A. Okounkov. Random matrices and random permutations. Technical Report math.CO/9903176, XXX Math Archive, 1999.
- David Partlett. Solitaire: Aces Up and 399 Other Card Games. Pantheon, 1979.
- Shaiy Pilpel, Descending subsequences of random permutations, J. Combin. Theory Ser. A 53 (1990), no. 1, 96–116. MR 1031615, DOI 10.1016/0097-3165(90)90022-O
- A. Rabb. A probabilistic analysis of the game of solitaire, 1989. Undergraduate Honors Thesis, Harvard.
- E. M. Rains, Increasing subsequences and the classical groups, Electron. J. Combin. 5 (1998), Research Paper 12, 9. MR 1600095, DOI 10.37236/1350
- H. Rost, Nonequilibrium behaviour of a many particle process: density profile and local equilibria, Z. Wahrsch. Verw. Gebiete 58 (1981), no. 1, 41–53. MR 635270, DOI 10.1007/BF00536194
- 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. MR 1093239
- C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179–191. MR 121305, DOI 10.4153/CJM-1961-015-3
- T. Seppäläinen, Hydrodynamic scaling, convex duality and asymptotic shapes of growth models, Markov Process. Related Fields 4 (1998), no. 1, 1–26. MR 1625007
- R. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge University Press, 1999.
- 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. MR 847717, DOI 10.1007/978-1-4615-9763-6
- Dennis Stanton and Dennis White, Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986. MR 843332, DOI 10.1007/978-1-4612-4968-9
- Craig A. Tracy and Harold Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), no. 1, 151–174. MR 1257246, DOI 10.1007/BF02100489
- C.A. Tracy and H. Widom. Random unitary matrices, permutations and Painlevé. Technical Report math.CO/9811154, XXX Math Archive, 1998.
- 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.
- S.M. Ulam. Some ideas and prospects in biomathematics. Ann. Rev. Biophys. Bioeng., 1:277–292, 1972.
- 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.
- 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.
- Pascual Llorente, Some problems in the theory of algebraic numbers, Publ. Sec. Mat. Univ. Autònoma Barcelona 23 (1981), 101–132 (Spanish). MR 766674
- M.S. Waterman and M. Vingron. Sequence comparison significance and Poisson approximation. Statist. Science, 9:367–381, 1994.
Additional Information
- David Aldous
- Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305
- MR Author ID: 24555
- Email: aldous@stat.berkeley.edu
- Persi Diaconis
- Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305
- MR Author ID: 57595
- Received by editor(s): May 17, 1999
- Published electronically: July 21, 1999
- Additional Notes: Research supported by NSF Grant MCS 96-22859.
- © Copyright 1999 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 36 (1999), 413-432
- MSC (1991): Primary 60C05, 05E10, 15A52, 60F05
- DOI: https://doi.org/10.1090/S0273-0979-99-00796-X
- MathSciNet review: 1694204