On longest increasing subsequences in random permutations
A. M. Odlyzko
E. M. Rains
AT&T Labs - Research
Florham Park, New Jersey 07932
{amo,rains}@research.att.com
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.