A Caltech Library Service

On longest increasing subsequences in random permutations

Odlyzko, A. M. and Rains, E. M. (2000) On longest increasing subsequences in random permutations. In: Analysis, Geometry, Number Theory: The Mathematics of Leon Ehrenpreis. Contemporary Mathematics. No.251. American Mathematical Society , Providence, RI, pp. 439-451. ISBN 978-0-8218-1148-1.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The expected value of L_n, the length of the longest increasing subsequence of a random permutation of {1, ... , n}, has been studied extensively. This paper presents the results of both Monte Carlo and exact computations that explore the finer structure of the distribution of L_n. The results suggested that several of the conjectures that had been made about L_n were incorrect, and led to new conjectures, some of which have been proved recently by Jinho Baik, Percy Deift, and Kurt Johansson. In particular, the standard deviation of L_n is of order n^(1/6), contrary to earlier conjectures. This paper also explains some regular patterns in the distribution of L_n.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2000 American Mathematical Society. We thank Craig Tracy for providing the numerical data about asymptotic distribution of L_n that is used in Table 1 and Figure 1 and Jim Reeds for help with the random number generator programs. We also thank David Aldous, Harry Kesten, Anatoly Vershik, and Ofer Zeitouni for their comments.
Series Name:Contemporary Mathematics
Issue or Number:251
Record Number:CaltechAUTHORS:20171009-160133131
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:82239
Deposited By: Tony Diaz
Deposited On:09 Oct 2017 23:16
Last Modified:15 Nov 2021 19:49

Repository Staff Only: item control page