Bulletin of the American Mathematical Society

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

Author(s): David Aldous; Persi Diaconis
Journal: Bull. Amer. Math. Soc. 36 (1999), 413-432.
MSC (1991): Primary 60C05, 05E10, 15A52, 60F05
Posted: July 21, 1999
Retrieve article in: PDF DVI PostScript

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.

1.: D.J. Aldous and P. Diaconis. Hammersley's interacting particle process and longest increasing subsequences. Probab. Th. Rel. Fields, 103:199-213, 1995. MR 96k:60017
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.: P. Billingsley. Convergence of Probability Measures. Wiley, 1968. MR 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. In J.L. Lebowitz and E.W. Montrell, editors, Nonequilibrium Phenomena II: From Stochastics to Hydrodynamics, volume 11 of Studies in Statistical Mechanics, pages 123-294. North-Holland, Amsterdam, 1984. MR 86g:82003
12.: R. Durrett. Oriented percolation in two dimensions. The Annals of Probability, 12:999 - 1040, 1984. MR 86g:60117
13.: R. Durrett. Probability: Theory and Examples. Wadsworth, Pacific Grove, CA, 1991. MR 91m:60002
14.: R. Engelen, P. Tommassen, and W. Vervaat. Ignatov's theorem; a new and short proof. J. Appl. Probab., 25A:229-236, 1988. MR 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:411-419, 1996. MR 97j:60183
16.: M.L. Fredman. On computing the length of the longest increasing subsequence. Discrete Math., 11:29-35, 1975. MR 50:6865
17.: I.M. Gessel. Symmetric functions and $P$ -recursiveness. J. Combin. Theory Ser. A, 53:257-285, 1990. MR 91c:05190
18.: J.M. Hammersley. First-passage percolation. J. Roy. Statist. Soc. B, 28:491-496, 1966. MR 35:5014
19.: J.M. Hammersley. A few seedlings of research. In Proc. Sixth Berkeley Symp. Math. Statist. and Probability, Volume 1, pages 345-394. University of California Press, 1972. MR 53:9457
20.: G. James and A. Kerber. The Representation Theory of the Symmetric Group. Addison-Wesley, Reading, MA, 1981. MR 83k:20003
21.: T.A. Jenkyns and E.R. Muller. A probabilistic analysis of clock solitaire. Math. Magazine, 54:202-208, 1981. MR 83h:60015
22.: K. Johansson. Shape fluctuations and random matrices. Technical report, Royal Inst. Technology, Stockholm, 1999.
23.: N. L. Johnson and S. Kotz. Continuous Univariate Distributions, volume 2. Wiley, 1970. MR 96j:62029
24.: S.V. Kerov and A.M. Vershik. Asymptotic theory of the characters of the symmetric group. Functional Anal. Appl., 15:246-255, 1981. MR 84a:22016
25.: H. Kesten. On the speed of convergence in first-passage percolation. Ann. Appl. Probab., 3:296-338, 1993. MR 94m:60205
26.: J. H. Kim. On increasing subsequences of random permutations. J. Combin. Theory Ser. A, 76:148-155, 1996. MR 97f:60024
27.: C. Kuykendall. Analyzing solitaire. Science, 283(5403):794-795, Feb. 5, 1999.
28.: T.M. Liggett. Interacting Particle Systems. Springer-Verlag, 1985. MR 86e:60089
29.: B.F. Logan and L.A. Shepp. A variational problem for random Young tableaux. Advances in Math., 26:206-222, 1977. MR 98e:05108
30.: I. MacDonald. Symmetric Functions and Hall Polynomials. Oxford University Press, 1979. MR 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. D. Mauldin and S.M. Ulam. Mathematical problems and games. Adv. Appl. Math., 8:281-344, 1987. MR 89g:04005
34.: S.P. Meyn and R.L. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, 1993. MR 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.: S. Pilpel. Descending subsequences of random permutations. J. Combinatorial Th. A, 53:96-116, 1990. MR 91d:05001
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. Combinatorics, 5:R12, 1998. MR 98k:05146
43.: H. Rost. Nonequilibrium behavior of a many particle process: Density profile and local equilibrium. Z. Wahrsch. Verw. Gebiete, 58:41-53, 1981. MR 83a:60176
44.: B.E. Sagan. The Symmetric Group: Representations, Combinatorial Algorithms and Symmetric Functions. Wadsworth, 1991. MR 93f:05102
45.: C. Schensted. Longest increasing and decreasing subsequences. Canad. J. Math., 13:179-191, 1961. MR 22:12047
46.: T. Seppäläinen. Hydrodynamic scaling, convex duality and asymptotic shapes of growth models. Markov Process. Related Fields, 4:1-26, 1998. MR 99e:60221
47.: R. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge University Press, 1999. CMP 99:09
48.: R. P. Stanley. Enumerative Combinatorics, Vol I. Wadsworth & Brooks/Cole, Monterey, California, 1986. MR 87j:05003
49.: D. Stanton and D. White. Constructive Combinatorics. Undergraduate Texts in Mathematics. Springer-Verlag, 1986. MR 88a:05001
50.: C.A. Tracy and H. Widom. Level-spacing distributions and the Airy kernel. Comm. Math. Phys., 159:151-174, 1994. MR 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 . 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.: A.M. Vershik and S.V. Kerov. Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group. Functional Anal. Appl., 19:21-31, 1985. MR 85k:11051
57.: M.S. Waterman and M. Vingron. Sequence comparison significance and Poisson approximation. Statist. Science, 9:367-381, 1994. CMP 95:10

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

David Aldous
Affiliation: Department of Statistics, 367 Evans Hall, University of California, Berkeley, CA 94720
Email: aldous@stat.berkeley.edu

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

DOI: 10.1090/S0273-0979-99-00796-X
PII: S 0273-0979(99)00796-X
Received by editor(s): May 17, 1999
Posted: July 21, 1999
Additional Notes: Research supported by NSF Grant MCS 96-22859.
Copyright of article: Copyright 1999, American Mathematical Society

J. Baik, P. Deift and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999), 1119--1178. MR 2000e:05006

K. Johansson, Transversal fluctuations for inceasing subsequences on the plane, Probab. Theory Related Fields 116 (2000), 445--456. MR CMP 1 757 595

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS