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. http://resolver.caltech.edu/CaltechAUTHORS:20171009-160133131
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20171009-160133131
Abstract
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: |
| |||||||||
| 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. | |||||||||
| Record Number: | CaltechAUTHORS:20171009-160133131 | |||||||||
| Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20171009-160133131 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 82239 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 09 Oct 2017 23:16 | |||||||||
| Last Modified: | 09 Oct 2017 23:16 |
Repository Staff Only: item control page
