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.