\documentclass[11pt]{article} %\input amssym.def %\input amssym.tex \usepackage{epsfig,psfig,amsfonts,amssymb} \setlength{\textwidth}{6.2in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{.2in} \setlength{\topmargin}{-0.25in} \setlength{\headheight}{0in} %%%GREEK LETTERS \newcommand{\La}{\Lambda} \newcommand{\Ga}{\Gamma} \newcommand{\Dt}{\Delta} \newcommand{\bDt}{\mbox{\boldmath $\Delta$}} \newcommand{\la}{\lambda} \newcommand{\af}{\alpha} \newcommand{\be}{\beta} \newcommand{\ep}{\epsilon} \newcommand{\vp}{\varphi} \newcommand{\vt}{\vartheta} \newcommand{\om}{\omega} \newcommand{\Om}{\Omega} \newcommand{\Th}{\Theta} \newcommand{\tht}{\theta} \newcommand{\Sg}{\Sigma} \newcommand{\In}{\infty} \newcommand{\dr}{\Rightarrow} \newcommand{\dt}{\delta} \newcommand{\ga}{\gamma} \newcommand{\RR}{{\Bbb R}} \newcommand{\CC}{{\Bbb C}} \newcommand{\sig}{\sigma} \newcommand{\zt}{\zeta} \newcommand{\et}{\eta} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\lc}{\lceil} \newcommand{\rc}{\rceil} \newcommand{\lt}{\left(} \newcommand{\rt}{\right)} \newcommand{\dd}{\ldots} \newcommand{\ZZ}{{\Bbb Z}} \newcommand{\df}{\displaystyle\frac} \newcommand{\dis}{\displaystyle} \newcommand{\ds}{\displaystyle\sum} \newcommand{\bzero}{{\bf 0}} \newtheorem{coro}{Corollary}[section] \newtheorem{conj}{Conjecture}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{theorem}{Theorem}[section] \newtheorem{prop}{Proposition}[section] \newtheorem{remark}{\bf Remark}[section] \newtheorem{exam}{Example}[section] \newcommand{\eqn}[1]{(\ref{#1})} \newcommand{\hsp}{\hspace*{\parindent}} \newcommand{\vsp}{\vspace{.1in}} \newcommand{\pf}{\noindent{\bf Proof.~}} \newcommand{\eeq}{\end{equation}} \newcommand{\beql}[1]{\begin{equation}\label{#1}} \def\binom#1#2{{#1}\choose{#2}} \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \catcode`\@=11 \renewcommand{\section}{ \setcounter{equation}{0} \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\large\bf} } \catcode`@=12 \newcommand{\Bnu}{\mbox{\boldmath $\nu$}} \newcommand{\Bmu}{\mbox{\boldmath $\mu$}} %%%Filename is periodsec.sty%%% \makeatletter % put a period after section or subsection number in header \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} % put a period after theorem and theorem-like numbers \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \makeatother \makeatletter \def\eqalignno#1{\displ@y \tabskip\@centering \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip &$\@lign\displaystyle{{}##}$\hfil\tabskip\@centering &\llap{$\@lign##$}\tabskip\z@skip\crcr #1\crcr}} \makeatother \thispagestyle{empty} \begin{document} \begin{center} {\Large {\bf On longest increasing subsequences in random permutations}} \\ \vspace{\baselineskip} {\em A. M. Odlyzko} \\ {\em E. M. Rains} \\ \vspace{0.5\baselineskip} AT\&T Labs - Research \\ Florham Park, New Jersey 07932 \\ email: \{amo,rains\}@research.att.com \\ \vspace*{1.5\baselineskip} {\em Dedicated to Leon Ehrenpreis} \\ \vspace{\baselineskip} (Revised version, \today) \\ \vspace{1.5\baselineskip} {\bf ABSTRACT} \vspace{.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} The expected value of $L_n$, the length of the longest increasing subsequence of a random permutation of $\{1, \dd , 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$. \clearpage \large\normalsize \renewcommand{\baselinestretch}{1} \thispagestyle{empty} \setcounter{page}{1} \begin{center} {\Large {\bf On longest increasing subsequences in random permutations}} \\ \vspace{\baselineskip} {\em A. M. Odlyzko} \\ {\em E. M. Rains} \\ \vspace{0.5\baselineskip} AT\&T Labs - Research \\ Florham Park, New Jersey 07932 \\ email: \{amo,rains\}@research.att.com \\ \vspace*{1.5\baselineskip} {\em Dedicated to Leon Ehrenpreis} \\ \vspace{1.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \section{Introduction} \hsp Let $L_n$ denote the length of the longest increasing subsequence of a random permutation of $\{1, \dd , n \}$. There is extensive literature about this random variable. Ulam \cite{Ulam} was motivated to ask about the distribution of $L_n$ by the famous result of Erd\"{o}s and Szekeres that every permutation of $\{1, \dd , n \}$ has either an increasing or a decreasing subsequence of length $\ge \sqrt{n}$. Monte Carlo computations led Ulam to the conjecture that $L_n$ is usually on the order of $\sqrt{n}$. More extensive computations by Baer and Brock \cite{BaerB} led them to the conjecture that the expected value of $L_n$ is $\sim 2 \sqrt{n}$ as $n \to \infty$. (Ulam had conjectured a different value for the constant of proportionality.) Hammersley \cite{Ham} showed that $L_n$ is asymptotic to $c \sqrt{n}$ in probability for some constant $c$, that $EL_n \sim c \sqrt{n}$ also, and that $\pi /2 \le c \le e$. Kingman \cite{Kingman} (see also \cite{Kingman2}) proved $(8/ \pi)^{1/2} = 1.595 \dd \le c < 2.49$. Logan and Shepp \cite{LoganS} used calculus of variations methods to show that $c \ge 2$. Vershik and Kerov \cite{VershikK1} (see also \cite{KerovV}) used a method almost identical to that of Logan and Shepp to prove that $c \ge 2$, and a group theoretic and combinatorial argument to show that $c \le 2$. A more directly combinatorial proof that $c \le 2$ was obtained later by Pilpel \cite{Pilpel}. Other proofs that $c=2$ were recently obtained by Aldous and Diaconis \cite{AldousD}, Johansson \cite{Joh}, and Sepp\"al\"ainen \cite{Sep}. The Logan-Shepp and Vershik-Kerov results established that $c=2$, and thus answered the main question in this area. However, they left open many other problems, especially about the distribution of $L_n$. Frieze \cite{Frieze} was the first one to prove the conjecture that $L_n$ is very concentrated near its mean. His result was improved by Bollob\'{a}s and Brightwell \cite{BB}, who showed, among other things, that the variance of $L_n$ is $O(n^{1/2} ( \log n )^2 ( \log \log n)^{-2})$. (Bollob\'{a}s and Brightwell proved a more general result, and we quote only the special case that is relevant for our discussion.) An interesting feature of the Frieze and Bollob\'{a}s-Brightwell proofs is that they use martingale methods, and provide no information about $EL_n$ itself. Talagrand \cite{Tala} has recently sharpened the Bollob\'{a}s-Brightwell result, so that the variance of $L_n$ is known to be $O(n^{1/2})$. His methods are also indirect in that they prove only that the distribution of $L_n$ is very concentrated, but do not show where the mean is located. J.-H. Kim \cite{Kim} has shown that for every $\epsilon > 0$, \beql{AMO12} Pr \left( L_n > \sum_{k=1}^n k^{-1/2} + \theta n^{1/6} \right) \le \exp (-1.2 \theta^{3/2} ) \eeq for $n^{-2/3+ \epsilon} \le \theta \le 2n^{1/3}$ if $n \ge n_0 ( \epsilon )$, which provides a bound for one tail of the distribution, but without relating it to $EL_n$. Two-sided tail estimates have been provided more recently by Deuschel and Zeitouni \cite{DeuZ}. Steele (unpublished) had originally conjectured that the variance of $L_n$ is not only small, but is bounded. This was shown to be false by Bollob\'{a}s and Janson, who proved that this variance is $\ge n^{1/8} ( \log n)^{-3/4}$ for large $n$. Bollob\'{a}s and Brightwell conjectured that the variance of $L_n$ is $\ge n^{1/2}$. Since the Talagrand result \cite{Tala} gives an upper bound for the variance of $O(n^{1/2})$, their conjecture says that this upper bound is best possible. Vershik and Kerov \cite{VershikK2} showed that $2 \sqrt{n} - EL_n = O(n^{1/3})$. Pilpel's proof that $c \le 2$ \cite{Pilpel} shows that $EL_n \le 2 \sqrt{n}$ for all $n$. These results still left open the precise order of $2 \sqrt{n} - EL_n$. In 1992, Poonen, Widom, Wilf, and the first author \cite{OdlyzkoPWW} developed an analytic method for studying the distribution of $L_n$. This motivated our computations, which were designed to extend those of Baer and Brock \cite{BaerB}. The purpose was to obtain data to formulate more precise conjectures about the behavior of $L_n$, and hopefully to use it as a check on any asymptotic estimates that were to be made. Starting in 1993, we have intermittently done a series of computer calculations which are summarized in this note. More detailed data from our computations is available online at $\langle$http://www.research.att.com/$\sim$amo$\rangle$, and will be supplemented by additional data that we are collecting to provide insight into other features of random permutations, Young tableaux, and related topics. There have been no algorithmic advances since the time of Baer and Brock, and our methods are essentially the same as the ones they used. However, much faster computers have become available, and have allowed us to compute the distribution of $L_n$ exactly for $n \le 120$ (in contrast to $n \le 36$ for \cite{BaerB}) and to do Monte Carlo simulations for $n$ up to $10^{10}$ (in constrast to $10^4$ for \cite{BaerB}). Our computational methods are described briefly in Section~4. Table~1 summarizes the results of our Monte Carlo experiments. The scaled moments for each $n$ are the moments of $(L_n - m_n ) /s_n$, where $m_n$ is the observed mean of the sample, and $s_n$ the standard deviation (so that the 1-st and 2-nd moments are by definition 0 and 1). The Monte Carlo data of Table~1 showed that the mean of $L_n$ is about two standard deviations below $2n^{1/2}$. This was apparently first observed by H.~L. Montgomery (personal communication to the first author). However, contrary to Montgomery's guess (based on smaller runs than ours) our data showed clearly that the distribution of $L_n$ is not asymptotically normal, and is asymmetric. For a normal distribution, one would expect the odd-order scaled moments to be 0, and the $(2m)$-th order ones to be $(2m-1) (2m-3) \cdot \dd \cdot 3 \cdot 1$. While the even order moments are close to those of a normal distribution, the odd order ones are not. This difference is also visible in the data. For example, tables~2--4 as well as the tables in \cite{BaerB} and the Monte Carlo runs show that the distribution function of $L_n$ rises much faster to its peak than it falls afterwards. This impression is also confirmed by use of $qq$-plots. The standard deviation of $L_n$ appears to increase by a factor of about $5^{1/2}$ each time $n$ increases by a factor of 100. This suggests that it grows like $n^{0.17}$ $(( \log 5^{1/2}) ( \log 100)^{-1} = 0.1747 \dd )$, which is contrary to the Bollob\'{a}s-Brightwell \cite{BB} conjecture that it is $\ge n^{1/4}$. We conjectured back in 1993 that the standard deviation of $L_n$ is asymptotic to a constant times $n^{1/6}$, and that ${(2 \sqrt{n} - L_n)}/{n^{1/6}}$ converges to a nice distribution. This conjecture was presented in private conversations and public lectures, although was not published. (The same conjecture for the standard deviation of $L_n$ was made independently by Kim \cite{Kim}.) Although our and Kim's were the first explicit statements of the conjecture that the standard deviation of $L_n$ is $O(n^{1/6})$, this conjecture arises naturally from some bounds of Vershik and Kerov \cite{VershikK2}. Also, Kesten suggested around 1993 (unpublished) that $n^{1/6}$ might be the right order by analogy with some first-passage percolation results. \section{Asymptotic distribution of $L_n$} \hsp The approach of \cite{OdlyzkoPWW} started with a generating function of Gessel \cite{Gessel} and produced an explicit analytic formula for the distribution of $L_n$, a formula that was soon thereafter derived in a much more direct way by the second author \cite{Rains}. However, this formula involved a complicated multidimensional integral. It led to very precise large deviations estimates for $L_n$, but not to any useful results about the behavior of $L_n$ near its mode. It was also discovered (as a result of a conversation between the first author and Claude Itzykson) that the same multidimensional integral plays a crucial role in two-dimensional quantum gravity models \cite{GrossW,MyersP,Neub,PerSa,PerSb}. The physics papers do have asymptotic estimates for this generating function, but those estimates are neither precise enough to obtain the asymptotic distribution of $L_n$, nor rigorous. Interestingly enough, one half of the main result of Gross and Witten \cite{GrossW} can be deduced easily and rigorously from the estimates of Logan and Shepp \cite{LoganS} and of Vershik and Kerov \cite{VershikK1}, but this was not recognized at the time, since the connection between the longest increasing subsequence problem and quantum gravity was not known. Recently the problem of the distribution of $L_n$ near its mode was solved rigorously and essentially completely by Jinho Baik, Percy Deift, and Kurt Johansson \cite{BaikDJ}. Their work is a tour de force of mathematical analysis. It proceeds through the generating function of \cite{OdlyzkoPWW,Rains}, the theory of polynomials orthogonal on the unit circle (whose connection to the generating function was already known to the physicists \cite{Neub,PerSa,PerSb}), very powerful and sophisticated Riemann-Hilbert Problem techniques, and the work of Tracy and Widom on eigenvalues of random matrices \cite{TracyW}. Baik, Deift, and Johansson have completely determined the asymptotic distribution of ${(2 \sqrt{n} - L_n)}/{n^{1/6}}$. Their results are not simple to state, as they are given in terms of the solution to a Painlev\'{e}~II equation, and presumably are not expressible in elementary functions. A remarkable fact is that this asymptotic distribution is the same (aside from scale factors) as that which Tracy and Widom showed to hold for the gap between the largest eigenvalue of a random matrix from the Gaussian Unitary Ensemble and ${(2n)}^{1/2}$. No direct relation between the two problems is known, and the scaling factors make it unlikely there is one, so this is presumably an expression of the universality of the distribution. See \cite{TracyW2} for more details. Numerical computations by Craig Tracy show that the standard deviation of ${L_n}/{n^{1/6}}$ is asymptotic to 0.90177..., and the expected value of ${(2 \sqrt{n} - L_n)}/{n^{1/6}}$ is asymptotic to -1.77108..., values that agree well with the numbers in Table 1. Fig. 1 compares the asymptotic distribution of ${(2 \sqrt{n} - L_n)}/{n^{1/6}}$ to the Monte Carlo results for $n={10^6}$, and it can be seen that the agreement is excellent. \section{Numerology} \hsp Tables 2-4 give the exact values of $g_{n,k}$ for $n=15$, 30, and 60. It is interesting to note the patterns in the final digits of these numbers; these patterns can all be explained by the following fact: \beql{eqER1} \chi^\lambda_{\kappa(p\mu)}\equiv \chi^\lambda_{\kappa\mu^p} \pmod p~, \eeq where $p\mu$ is the partition produced from $\mu$ by multiplying each element by $p$, and similarly for $\mu^p$; $\kappa\mu$ is the (sorted) concatenation of the two partitions. This follows easily from the fact that $S_n$ has integral representations, and so for all permutations $\pi$, $$ \chi^\lambda(\pi^p) \equiv \chi^\lambda(\pi)^p \equiv \chi^\lambda(\pi) \pmod p~. $$ Consider, now, the special case $\kappa$ empty and $\mu=k$ of~\ref{eqER1}. By squaring both sides and summing over $\lambda$, we get, in the notation of~\cite{Rains}, $$ f_{(pn)k}\equiv f^{(p)}_{nk}\pmod p~; $$ as a special case, $$ f_{(p^r)k}-f_{(p^r)(k-1)}\equiv 1\pmod p~. $$ (By induction in $r$, we have $f_{(p^r)k}\equiv f^{(p^r)}_{1k}$; the latter is easily shown to be equal to $k$.) Similarly, one can fairly easily deduce other ``numerological'' results concerning the values $(\bmod p)$ of $f_{nk}$, for $n=ap^r+b$, $a,b$ small (In these cases, only a small, easily enumerated, set of shapes contributes $(\bmod p)$.) When $p=2$, everything actually works mod 4, since every term in the sum was squared. Thus, in particular, we have the following fact: $$ f_{nk}\equiv b_{nk}\pmod 4~. $$ \section{Computations} \hsp The exact computations were performed using the Schensted correspondence and the hook formula, as in \cite{BaerB}. Thus instead of computing all $n!$ permutations of n elements, it was only necessary to generate the $p(n)$ partitions of $n$. (Multiple precision arithmetic was required, which was performed using the GNU package.) The running time, on a Silicon Graphics computer with R10000 200 MHz chips, was about 10 seconds for $n = 60$, and 45,000 seconds for $n = 120$. Roughly speaking, the Monte Carlo computations proceeded by generating random permutations, and computing the length of their longest increasing subsequence using the Schensted correspondence again. One difficulty that arises is that the computation for $10^{10}$ requires the generation of around $10^{10}$ random 32-bit numbers per permutation (the exact number will be slightly greater, due to the times when two of the generated $\pi(i)$ agree in the first 32-bits, so more bits need be generated to distinguish them). For, say, 100 permutations, this means that $10^{12}$ random words need to be generated. This gives rise to two problems. The first, less serious, problem is that random number generation is frequently slow, causing the computation speed to be bound by the speed of random number generation. The more significant problem is that the readily available random number generators have periods of $2^{31}$ or $2^{48}$ (and the latter RNG is quite slow). Since we needed to generate over $2^{40}$ random numbers, there was a significant risk with such short periods that the results could be erroneous. This problem was fixed by combining a Marsaglia subtract-with-borrow generator (using code provided by Jim Reeds, who also provided helpful advice on random number generation in general) with the LCG routine lrand(), from v9 UNIX. The running time for the Monte Carlo code was around 10 hours for each permutation for $n = 10^{10}$. (These times are for the same R10000 chips as were mentioned above, although many runs were performed on slower machines, using their idle cycles.) Our programs have been adopted to produce further statistics, for example on the distribution of the length of the second row of a Young tableaux, which served as a check on the asymptotic estimates of \cite{BaikDJ2}. Data is available at $\langle$http://www.research.att.com/$\sim$amo/tables/index.html$\rangle$ and will be supplemented as more runs are carried out and more statistics are collected. \paragraph{Acknowledgements:} 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. \clearpage \begin{thebibliography}{SchenstedM} \bibitem[AldousD]{AldousD} D. Aldous and P. Diaconis, Hammersley's interacting particle process and longest increasing subsequences, {\em Th. Prob. Rel. Fields 103}, (1995), 199--213. \bibitem[AskeyR]{AskeyR} R. Askey and A. Regev, Maximal degrees for Young diagrams in a strip, {\em Europ. J. Comb. 5} (1984), 189--191. \bibitem[BaerB]{BaerB} R.~M. Baer and P. Brock, Natural sorting over permutation spaces, {\em Math. Comp. 22} (1968), 385--410. \bibitem[BaikDJ]{BaikDJ} J. Baik, P. Deift, and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations. Available as preprint math.CO/9810105 at $\langle$http://xxx.lanl.gov$\rangle$. \bibitem[BaikDJ2]{BaikDJ2} J. Baik, P. Deift, and K. Johansson, On the distribution of the length of the second row of Young diagrams under Plancherel measure, in preparation. \bibitem[Bars1]{Bars1} I. Bars, $U(N)$ integral for the generating functional in lattice gauge theory, {\em J. Math. Phys. 21} (1980), 2678--2681. \bibitem[Bars2]{Bars2} I. Bars, Exact evaluation of $U(N)$ group integrals in lattice QCD, {\em Physica Scr. 23} (1981), 983--986. \bibitem[BB]{BB} B. Bollob\'{a}s and G. Brightwell, The height of a random partial order: concentration of measure, {\em Ann. Appl. Prob. 2} (1992), 1009--1018. \bibitem[BJ]{BJ} B. Bollob\'{a}s and S. Janson, On the length of the longest increasing subsequence in a random permutation, to be published. \bibitem[DeuZ]{DeuZ} J.-D. Deuschel and O. Zeitouni, On increasing subsequences of i.i.d. samples. To be published. \bibitem[Frieze]{Frieze} A. Frieze, On the length of the longest monotone subsequence in a random permutation, {\em Ann. Appl. Prob. 1} (1991), 301--305. \bibitem[Gessel]{Gessel} I.~M. Gessel, Symmetric functions and $P$-recursiveness, {\em J. Comb. Theory (A) 53} (1990), 257--286. \bibitem[GrossW]{GrossW} D.~J. Gross and E. Witten, Possible third-order phase transition in the large-$N$ lattice gauge theory, {\em Phys. Rev. D 21} (1980), 446--453. \bibitem[Ham]{Ham} J.~M. Hammersley, A few seedlings of research, pp.~345--394 in {\em Proc. 6th Berkeley Symp. Math. Stat. Prob.}, Univ. California Press, 1972. \bibitem[Joh]{Joh} K. Johansson, The longest increasing subsequence in a random permutation and a unitary random matrix model, {\em Math. Res. Letters 5} (1998), 63-82. \bibitem[KerovV]{KerovV} S.~V. Kerov and A.~M. Vershik, The characters of the infinite symmetric group and probability properties of the Robinson-Schensted-Knuth algorithm, {\em SIAM J. Alg. Discr. Math. 7} (1986), 116--124. \bibitem[Kesten]{Kesten} H. Kesten, Comments in \cite{Kingman}. \bibitem[Kim]{Kim} J.-H. Kim, On the longest increasing subsequences of random permutations - a concentration result, {\em J. Comb. Theory A 76}, (1996), 148--155. \bibitem[Kingman]{Kingman} J.~F.~C. Kingman, Subadditive ergodic theory, {\em Ann. Prob. 1} (1973), 883--899. \bibitem[Kingman2]{Kingman2} J.~F.~C. Kingman, Some random collections of finite subsets, pp.~241--247 in {\em Disorder in Physical Systems}, G.~R. Grimmett and D.~J.~A. Welsh, eds., Oxford Univ. Press, 1990. \bibitem[LoganS]{LoganS} B.~F. Logan and L.~A. Shepp, A variational problem for random Young tableaux, {\em Advances Math. 26} (1977), 206--222. \bibitem[Mehta]{Mehta} M.~L. Mehta, {\em Random Matrices}, 2nd ed., Academic Press, 1991. \bibitem[MyersP]{MyersP} R.~C. Myers and V. Periwal, Exact solution of critical self-dual unitary-matrix models, {\em Phys. Rev. Lett. 65} (1990), 1088--1091. \bibitem[Neub]{Neub} H. Neuberger, Scaling regime at the large-$N$ phase transition of two-dimensional pure gauge theories, {\em Nuclear Phys. B340} (1990), 703--720. \bibitem[OdlyzkoPWW]{OdlyzkoPWW} A.~M. Odlyzko, B. Poonen, H. Widom, and H.~S. Wilf, On the distribution of longest increasing subsequences in random permutations, in preparation. \bibitem[PerSa]{PerSa} V. Periwal and D. Shevitz, Unitary-matrix models as exactly solvable string theories, {\em Phys. Rev. Lett. 64} (1990), 1326--1329. \bibitem[PerSb]{PerSb} V. Periwal and D. Shevitz, Exactly solvable unitary matrix models: Multicritical potentials and correlations, {\em Nuclear Phys. B344} (1990), 731--746. \bibitem[Pilpel]{Pilpel} S. Pilpel, Descending subsequences of random permutations, {\em J. Comb. Theory A 53} (1990), 96--116. \bibitem[Rains]{Rains} E.~M. Rains, Increasing subsequences and the classical groups, {\em Electr. J. Comb. 5(1)}, (1998), R12. $\langle$http://www.combinatorics.org$\rangle$. \bibitem[Schensted]{Schensted} C. Schensted, Longest increasing and decreasing subsequences, {\em Canad. J. Math. 31} (1961), 179--191. \bibitem[Sep]{Sep} T. Sepp\"al\"ainen, A microscopic model for the Burgers equation and longest increasing subsequences, {\em Electron. J. Prob.}, 1, no.5, (1996). \bibitem[Tala]{Tala} M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, {\em Publ. Math. Inst. Hautes Etud. Sci. 81} (1995), 73-205. \bibitem[TracyW]{TracyW} C. A. Tracy and H. Widom, Level-spacing distributions and the Airy kernel, {\em Comm. Math. Phys.}, 159 (1994) 151-174. \bibitem[TracyW2]{TracyW2} C. A. Tracy and H. Widom, Random unitary matrices, permutations and Painlev\'{e}, available as preprint math.CO/9811154 at $\langle$http://xxx.lanl.gov$\rangle$. \bibitem[Ulam]{Ulam} S.~M. Ulam, Monte Carlo calculations in problems of mathematical physics, pp.~261--281 in {\em Modern Mathematics for the Engineer}, E.~F. Beckenbach, ed., McGraw-Hill, 1961. \bibitem[VershikK1]{VershikK1} A.~M. Vershik and C.~V. Kerov, Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux, {\em Dokl. Akad. Nauk USSR, 233} (1977), 1024--1027. (In Russian.) \bibitem[VershikK2]{VershikK2} A.~M. Vershik and C.~V. Kerov, Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group, {\em Funkt. Anal. Prilozh. 19} (1985), 25--36, 96. (In Russian.) English translation in {\em Functional Anal. Appl. 19} (1985), 21--31. \end{thebibliography} \clearpage \begin{table} \caption{Monte Carlo simulation data on the distribution of $L_n$ and asymptotic values} {\footnotesize $$ \begin{array}{c|c|c|c|c|c|c|c|c} ~ & n = 10^4 & n = 10^5 & n= 10^6 & n = 10^7 & n= 10^8 & n= 10^9 & n= 10^{10} & asymptotic \\ \hline \mbox{no. permutations} & 10^7 & 6*10^5 & 10^5 & 10^5 & 10^4 & 2000 & 4000 \\ ~ &~ & ~ & ~ & ~ \\ \mbox{$2n^{1/2} -$ mean $(L_n)$} & 7.704 & 11.560 & 17.196 & 25.430 & 37.873 & 54.850 & 82.352 \\ ~ &~ & ~ & ~ & ~ \\ \mbox{($2n^{1/2} -$ mean $(L_n)$)$n^{-1/6}$} & 1.660 & 1.697 & 1.720 & 1.733 & 1.758 & 1.735 & 1.774 & 1.77109 \\ ~ &~ & ~ & ~ & ~ \\ \mbox{st. dev. $(L_n)$} & 4.043 & 6.032 & 8.959 & 13.209 & 19.342 & 28.538 & 41.545 \\ ~ &~ & ~ & ~ & ~ \\ \mbox{(st. dev. $(L_n))n^{-1/6}$} & 0.871 & 0.885 & 0.896 & 0.900 & 0.898 & 0.902 & 0.895 & 0.90177 \\ ~ &~ & ~ & ~ & ~ \\ ~ &~ & ~ & ~ & ~ \\ ~ &~ & ~ & ~ & ~ \\ \mbox{scaled} & ~ & ~ & ~ & ~ \\ \mbox{moments} & ~ & ~ & ~ & ~ \\ ~ &~ & ~ & ~ & ~ \\ [-.1in] 3 & 0.249 & 0.237 & 0.238 & 0.222 & 0.204 & 0.251 & 0.269 & 0.224 \\ 4 & 3.108 & 3.092 & 3.135 & 3.068 & 3.139 & 3.072 & 3.007 & 3.094 \\ 5 & 2.531 & 2.394 & 2.497 & 2.174 & 2.115 & 2.455 & 2.277 & 2.280 \\ 6 & 17.217 & 16.952 & 17.694 & 16.224 & 17.310 & 16.557 & 14.922 & 16.908 \\ 7 & 27.826 & 26.323 & 28.655 & 22.155 & 23.301 & 23.437 & 19.417 & 25.051 \\ 8 & 145.110 & 141.505 & 153.789 & 123.732 & 139.010 & 125.014 & 100.303 & 139.552 \end{array} $$ } \end{table} \clearpage \begin{table} \caption{Exact distribution of $L_n$ for $n=15$} {\footnotesize $$ \begin{array}{r|r} \multicolumn{1}{c}{k} & \multicolumn{1}{c}{g(15, k)} \\ \hline 1 & 1 \\ 2 & 9694844 \\ 3 & 8017098273 \\ 4 & 164161815768 \\ 5 & 485534447114 \\ 6 & 434119587475 \\ 7 & 172912977525 \\ 8 & 37558353900 \\ 9 & 4927007100 \\ 10 & 410474625 \\ 11 & 22128576 \\ 12 & 766221 \\ 13 & 16381 \\ 14 & 196 \\ 15 & 1 \end{array} $$ } \end{table} \clearpage \begin{table} \caption{Exact distribution of $L_n$ for $n=30$} {\footnotesize $$ \begin{array}{r|r} \multicolumn{1}{c}{k} & \multicolumn{1}{c}{g(30, k)} \\ \hline 1 & 1 \\ 2 & 3814986502092303 \\ 3 & 122238896672891001069665 \\ 4 & 1790036582998939530743648877 \\ 5 & 449044243619862872721423598179 \\ 6 & 10236819433951393776243660748875 \\ 7 & 50241067877038219983230124657600 \\ 8 & 86511371455863277882723853476200 \\ 9 & 70971582765623356071324810857700 \\ 10 & 33700117351593715495661064101700 \\ 11 & 10447178628714722178634866396630 \\ 12 & 2277900847905046253535807880680 \\ 13 & 366440157064983378222220318530 \\ 14 & 44912755712412555783652789980 \\ 15 & 4289203871330156652985437480 \\ 16 & 324301002215082697285357800 \\ 17 & 19633107355949074371195000 \\ 18 & 959064229546178387532600 \\ 19 & 37982369568044622191625 \\ 20 & 1222055891584247185425 \\ 21 & 31925927141978856309 \\ 22 & 675007128155925069 \\ 23 & 11475430101232224 \\ 24 & 155228816648544 \\ 25 & 1644397829384 \\ 26 & 13319151176 \\ 27 & 79490741 \\ 28 & 328861 \\ 29 & 841 \\ 30 & 1 \end{array} $$ } \end{table} \clearpage \begin{table} \caption{Exact distribution of $L_n$ for $n=60$} {\scriptsize $$ \begin{array}{r|r} \multicolumn{1}{c}{k} & \multicolumn{1}{c}{g(60, k)} \\ \hline 1 & 1 \\ 2 & 1583850964596120042686772779038895 \\ 3 & 353580101123476924257628603730083960324608410748129 \\ 4 & 17080691328825216538079811628828842602913045806045692424793199 \\ 5 & 175243028250079660905018843213615929860825569549681884867765690541701 \\ 6 & 9336151984930708021143911217956813677819162164640452787627883005534760901 \\ 7 & 15180807338873516832021030140438444665815147021460591742801378406314408952231 \\ 8 & 2233494474948495690243110568745222983262159502283551689273891105099703764639203 \\ 9 & 60002895752771099779779088462943847999099581712023250349374731986619450937660387 \\ 10 & 468104440722126644812839632177556187281953330916322512459026291795529190084140003 \\ 11 & 1455327054374385756982545351864306579536481867901002010423776062240740978062678405 \\ 12 & 2259251055120372007733214696091079754018818083465717757461536975882962682765500625 \\ 13 & 2062265432178679983886852088922462401452557170316484374161761008379074310593517320 \\ 14 & 1243711511999821270591207565082889798761871176715300197918122808539228337822802740 \\ 15 & 537394830317050100339379519887032754646946119740464857911956705681737098244483360 \\ 16 & 175923103423553571947761906278676245128973950100129233119563346326464104855276860 \\ 17 & 45368617608497201905530039854748875664926717869975676357175086535901817870722812 \\ 18 & 9479603856030503157955685146063700672586357866208188042547738509639642888641224 \\ 19 & 1638759009110121823982506004487303838241549550728662507775364230503063574975316 \\ 20 & 238188858817559653907757766891040131636069359492222134403147802254653854771728 \\ 21 & 29480487670047223803921747890109023556319166001013451281038912984170310753120 \\ 22 & 3139198038828528286203710931455906285276708940460977128156446860885650927310 \\ 23 & 290030563932022002118220602447753575011631132138930828877529635970794362700 \\ 24 & 23413655153323993212944806641432538187723487636946542215904509952446312690 \\ 25 & 1661393542805513071742417067989822659686364866756920591886636429663178680 \\ 26 & 104145900363220144830466866571023152418199800997341553230438935249107258 \\ 27 & 5792237419925383613451898590561388009628831263062366370911868157401964 \\ 28 & 286869467381919681822222469760492255054776533189183154318863752312230 \\ 29 & 12691871855481828626593458025125606857596131143782738903573825981796 \\ 30 & 502968058628572662277191566575373626415624915252154954972665008452 \\ 31 & 17894607700299703295952617215614009799494649283846631618530060276 \\ 32 & 572672495594979262825338794738392020356281425452234267523956756 \\ 33 & 16511387220795567604685869448544444896127174737028045397681196 \\ 34 & 429447776828374945008891956588902876262471997021459648212556 \\ 35 & 10085939380850856133146998090323665735800777575608380654076 \\ 36 & 214047059046253016288888877319022168888880344026378396380 \\ 37 & 4106553547655147341710844172909909933553257664495111405 \\ 38 & 71234520883705192260893127544474396900805731744717605 \\ 39 & 1117112951073704289164060302012753184712282502843905 \\ 40 & 15831468365324027218299523307120731328900971994505 \\ 41 & 202607444815864518792560988913570051638925224579 \\ 42 & 2339113811472688502277654778306794059853563499 \\ 43 & 24328028687991328153614089674352694270581559 \\ 44 & 227535457430697745412499435864265131254799 \\ 45 & 1909464678419065197802131758896939250754 \\ 46 & 14338575949172527832964867110076216498 \\ 47 & 96024776493391284512354802786801738 \\ 48 & 571194238941869175779849437632858 \\ 49 & 3003101053234619836243294988438 \\ 50 & 13871858035569655993122428198 \\ 51 & 55882289445190125856537982 \\ 52 & 194538945880191885164142 \\ 53 & 578499468416768375547 \\ 54 & 1447687482601462467 \\ 55 & 2988846947868807 \\ 56 & 4953109533951 \\ 57 & 6329639181 \\ 58 & 5851621 \\ 59 & 3481 \\ 60 & 1 \end{array} $$ } \end{table} \clearpage \begin{figure} \centerline{\psfig{file=P61,width=7in,height=7in}} \caption{Asymptotic density function for %$\frac{ 2 \sqrt{n} - L_n}{n^{1/6}}$, and Monte Carlo simulations for $n = {10^6}$. The smooth curve is the asymptotic density function for ${(2 \sqrt{n} - L_n)}/{n^{1/6}}$, based on theorem of Jinho Baik, Percy Deift, and Kurt Johansson. Data for the asymptotic distribution figure provided by Craig Tracy. Crosses represent the distribution of values of ${(2 \sqrt{n} - L_n)}/{n^{1/6}}$ for $n = {10^5}$ random permutations for $n = {10^6}$.} \end{figure} \end{document}