Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(online) ISSN 0273-0979(print)

 

Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem


Authors: David Aldous and Persi Diaconis
Journal: Bull. Amer. Math. Soc. 36 (1999), 413-432
MSC (1991): Primary 60C05, 05E10, 15A52, 60F05
Published electronically: July 21, 1999
MathSciNet review: 1694204
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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. MR 1355056 (96k:60017), http://dx.doi.org/10.1007/BF01204214
  • 2. B.C. Arnold, N. Balakrishnan, and H.N. Nagarajo. Records. Wiley, 1998. CMP 98:15
  • 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.
  • 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.
  • 5. J. Baik and E.M. Rains. Algebraic aspects of increasing subsequences. Technical Report math.CO/9905083, XXX Math Archive, 1999.
  • 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. MR 0233396 (38 #1718)
  • 8. A. Borodin. Longest increasing subsequences of random colored permutations. Technical Report math.CO/9902001, XXX Math Archive, 1999.
  • 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.
  • 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. MR 757003 (86g:82003)
  • 12. Richard Durrett, Oriented percolation in two dimensions, Ann. Probab. 12 (1984), no. 4, 999–1040. MR 757768 (86g:60117)
  • 13. 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 (91m: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. MR 974584 (90a:60094)
  • 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. MR 1385350 (97j:60183)
  • 16. Michael L. Fredman, On computing the length of longest increasing subsequences, Discrete Math. 11 (1975), 29–35. MR 0354386 (50 #6865)
  • 17. Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257–285. MR 1041448 (91c:05190), http://dx.doi.org/10.1016/0097-3165(90)90060-A
  • 18. J. M. Hammersley, First-passage percolation, J. Roy. Statist. Soc. Ser. B 28 (1966), 491–496. MR 0214163 (35 #5014)
  • 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. MR 0405665 (53 #9457)
  • 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. MR 644144 (83k:20003)
  • 21. T. A. Jenkyns and E. R. Muller, A probabilistic analysis of clock solitaire, Math. Mag. 54 (1981), no. 4, 202–208. MR 627454 (83h:60015), http://dx.doi.org/10.2307/2689633
  • 22. K. Johansson. Shape fluctuations and random matrices. Technical report, Royal Inst. Technology, Stockholm, 1999.
  • 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. MR 1326603 (96j:62029)
  • 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). MR 639197 (84a:22016)
  • 25. Harry Kesten, On the speed of convergence in first-passage percolation, Ann. Appl. Probab. 3 (1993), no. 2, 296–338. MR 1221154 (94m:60205)
  • 26. Jeong Han Kim, On increasing subsequences of random permutations, J. Combin. Theory Ser. A 76 (1996), no. 1, 148–155. MR 1405997 (97f:60024), http://dx.doi.org/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. MR 776231 (86e:60089)
  • 29. 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 (98e:05108), http://dx.doi.org/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. MR 553598 (84g:05003)
  • 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. MR 898709 (89g:04005), http://dx.doi.org/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. MR 1287609 (95j:60103)
  • 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.
  • 38. A. Okounkov. Random matrices and random permutations. Technical Report math.CO/9903176, XXX Math Archive, 1999.
  • 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. MR 1031615 (91d:05001), http://dx.doi.org/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 pp. (electronic). MR 1600095 (98k:05146)
  • 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. MR 635270 (83a:60176), http://dx.doi.org/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. MR 1093239 (93f:05102)
  • 45. C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191. MR 0121305 (22 #12047)
  • 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. MR 1625007 (99e:60221)
  • 47. R. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge University Press, 1999. CMP 99:09
  • 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. MR 847717 (87j:05003)
  • 49. Dennis Stanton and Dennis White, Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986. MR 843332 (88a:05001)
  • 50. Craig A. Tracy and Harold Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), no. 1, 151–174. MR 1257246 (95e:82003)
  • 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.
  • 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.
  • 56. Pascual Llorente, Some problems in the theory of algebraic numbers, Publ. Sec. Mat. Univ. Autònoma Barcelona 23 (1981), 101–132 (Spanish). MR 766674 (85k:11051)
  • 57. M.S. Waterman and M. Vingron. Sequence comparison significance and Poisson approximation. Statist. Science, 9:367-381, 1994. CMP 95:10

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1991): 60C05, 05E10, 15A52, 60F05

Retrieve articles in all journals with MSC (1991): 60C05, 05E10, 15A52, 60F05


Additional Information

David Aldous
Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305
Email: aldous@stat.berkeley.edu

Persi Diaconis
Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, CA 94305

DOI: http://dx.doi.org/10.1090/S0273-0979-99-00796-X
PII: S 0273-0979(99)00796-X
Received by editor(s): May 17, 1999
Published electronically: July 21, 1999
Additional Notes: Research supported by NSF Grant MCS 96-22859.
Article copyright: © Copyright 1999 American Mathematical Society