On longest increasing subsequences in random permutations
A. M. Odlyzko, E. M. Rains · Contemporary mathematics - American Mathematical Society · 2000
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.