Published 2000
| public
Book Section - Chapter
On longest increasing subsequences in random permutations
- Creators
- Odlyzko, A. M.
-
Rains, E. M.
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.
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.Additional details
- Eprint ID
- 82239
- Resolver ID
- CaltechAUTHORS:20171009-160133131
- Created
-
2017-10-09Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field
- Series Name
- Contemporary Mathematics
- Series Volume or Issue Number
- 251