# Universality of the Distribution Functions of Random Matrix Theory

## 1 Random Matrix Models

In probability theory and statistics a common first approximation to many random processes is a sequence $`X_1,X_2,X_3,\mathrm{}`$ of independent and identically distributed (iid) random variables. Let $`F`$ denote their common distribution. To motivate the material below, we take these random variables and construct a particularly simple $`N\times N`$ random matrix,

$$\text{diag}(X_1(\omega ),X_2(\omega ),\mathrm{},X_N(\omega )).$$

The order statistics are the eigenvalues ordered

$$\lambda _1\lambda _2\mathrm{}\lambda _N,$$

and the distribution of the largest eigenvalue, $`\lambda _{\text{max}}(N)=\lambda _N`$, is

$`\text{Prob}\left(\lambda _{\text{max}}(N)x\right)`$ $`=`$ $`\text{Prob}\left(X_1x,\mathrm{},X_Nx\right)`$   
$`=`$ $`F(x)^N.`$   
Since the distribution $`F`$ is arbitrary, we observe that so too is the distribution of the largest eigenvalue of a $`N\times N`$ random matrix. However, one is really interested in limiting laws as $`N\mathrm{}`$. That is, we ask if there exist constants $`a_N`$ and $`b_N`$ such that

$$\frac{\lambda _{\text{max}}(N)a_N}{b_N}$$
(1.1)   
converges in distribution to a nontrivial limiting distribution function $`G`$. In the present situation a complete answer is provided by

Theorem: If (1.1) converges in distribution to some nontrivial distribution function $`G`$, then $`G`$ belongs to one of the following forms:

1. $`e^{e^x}`$ with support R.
2. $`e^{1/x^\alpha }`$ with support $`[0,\mathrm{})`$ and $`\alpha >0`$.
3. $`e^{(x)^\alpha }`$ with support $`(\mathrm{},0]`$ and $`\alpha >0`$.

This theorem is a model for the type of results we want for nondiagonal random matrices.

A random matrix model is a probability space $`(\mathrm{\Omega },𝒫,)`$ where $`\mathrm{\Omega }`$ is a set of matrices. Here are some examples

* Circular Unitary Ensemble (CUE, $`\beta =2`$)

+ $`\mathrm{\Omega }=𝒰(N)=N\times N`$ unitary matrices.
    + $`𝒫`$= Haar measure.
* Gaussian Orthogonal Ensemble (GOE, $`\beta =1`$)

+ $`\mathrm{\Omega }=N\times N`$ real symmetric matrices.
    + $`𝒫`$ = unique<sup>1</sup><sup>1</sup>1Uniqueness is up to centering and a normalization of the variance. measure that is invariant under orthogonal transformations and the matrix elements (say on and above the diagonal) are iid random variables.
* Gaussian Unitary Ensemble (GUE, $`\beta =2`$)

+ $`\mathrm{\Omega }=N\times N`$ hermitian matrices.
    + $`𝒫`$= unique measure that is invariant under unitary transformations and the real and imaginary matrix elements (say on and above the diagonal) are iid random variables.
* Gaussian Symplectic Ensemble (GSE, $`\beta =4`$)

+ $`\mathrm{\Omega }=2N\times 2N`$ Hermitian self-dual matrices.<sup>2</sup><sup>2</sup>2Identify the $`2N\times 2N`$ matrix with the $`N\times N`$ matrix whose entries are quaternions. If the quaternion matrix elements satisfy $`\overline{M}_{ji}=M_{ij}`$ where the bar is quaternion conjugation, then the $`2N\times 2N`$ matrix is called Hermitian self-dual. Each eigenvalue of a Hermitian self-dual matrix has multiplicity two.
    + $`𝒫`$= unique measure that is invariant under symplectic transformations and the real and imaginary matrix elements (say on and above the diagonal) are iid random variables.

Expected values of random variables $`f:\mathrm{\Omega }\text{C}`$ are computed from the usual formula

$$E_\mathrm{\Omega }(f)=_\mathrm{\Omega }f(M)𝑑𝒫(M).$$

If $`f(M)`$ depends only on the eigenvalues of $`M\mathrm{\Omega }`$, then one can be more explicit:

* CUE (Weyl’s Formula)

$$E_{𝒰(N)}(f)=\frac{1}{N!(2\pi )^N}_\pi ^\pi \mathrm{}_\pi ^\pi f(\theta _1,\mathrm{},\theta _N)\underset{1\mu <\nu N}{}\left|\mathrm{\Delta }(e^{i\theta _1},\mathrm{},e^{i\theta _N})\right|^2d\theta _1\mathrm{}d\theta _N,$$
* Gaussian Ensembles ($`\beta =1,2,4`$):

$$E_{N\beta }(f)=c_{N\beta }_{\mathrm{}}^{\mathrm{}}\mathrm{}_{\mathrm{}}^{\mathrm{}}f(x_1,\mathrm{},x_N)\left|\mathrm{\Delta }(x_1,\mathrm{},x_N)\right|^\beta e^{\frac{\beta }{2}{\scriptscriptstyle x_j^2}}𝑑x_1\mathrm{}𝑑x_N,$$

where $`c_{N\beta }`$ is chosen so that $`E_{N\beta }(1)=1`$ and $`\mathrm{\Delta }(x_1,\mathrm{},x_N)=_{1i<jN}(x_ix_j)`$. The factor $`e^{\frac{\beta }{2}{\scriptscriptstyle x_j^2}}`$ explains the choice of the word “gaussian” in the names of these ensembles. A commonly studied generalization of these gaussian measures is to replace the sum of quadratic terms appearing in the exponential with $`V(x_i)`$ where $`V`$ is, say, a polynomial (with the obvious restrictions to make the measure well-defined).

Choosing $`f=_i\left(1\chi _J(x_i)\right)`$, $`\chi _J`$ the characteristic function of a set $`J\text{R}`$, we get the important quantity<sup>3</sup><sup>3</sup>3This quantity has an obvious extension to other random matrix models.

$$E_{N\beta }(f)=E_{N\beta }(0;J):=\text{probability no eigenvalues lie in}J,$$

and in the particular case $`J=(t,\mathrm{})`$

$$F_{N\beta }(t):=\text{Prob}\left(\lambda _{\text{max}}t\right)=E_{N\beta }(0,J).$$

The level spacing distribution<sup>4</sup><sup>4</sup>4Let the eigenvalues be ordered. The conditional probability that given an eigenvalue at $`a`$, the next one lies between $`s`$ and $`s+ds`$ is called the level spacing density. is expressible in terms of the mixed second partial derivative of $`E_{N\beta }(0;(a,b))`$ with respect to the endpoints $`a`$ and $`b`$.

## 2 Fredholm Determinant Representations

Though $`E_{N\beta }(0;J)`$ are explicit $`N`$-dimensional integrals, these expressions are not so useful in establishing limiting laws as $`N\mathrm{}`$. What turned out to be very useful are Fredholm determinant representations for $`E_{N\beta }(0;J)`$. In 1961 M. Gaudin proved for $`\beta =2`$ (using the newly developed orthogonal polynomial method of M. L. Mehta) that $`E_{N2}(0;J)=det(IK_{N2})`$ where $`K_{N2}`$ is an integral operator acting on $`J`$ whose kernel is of the form

$$\frac{\phi (x)\psi (y)\psi (x)\phi (y)}{xy},$$
(2.1)   
with $`\phi (x)=c_Ne^{x^2/2}H_N(x)`$, $`\psi (x)=c_Ne^{x^2/2}H_{N1}(x)`$, and $`H_j(x)`$ are the Hermite polynomials.<sup>5</sup><sup>5</sup>5For the random matrix models corresponding to general potential $`V`$, $`\phi (x)=c_Ne^{V(x)/2}p_N(x)`$ and $`\psi (x)=c_Ne^{V(x)/2}p_{N1}(x)`$ where $`p_j(x)`$ are the orthogonal polynomials associated with weight function $`w(x)=e^{V(x)}`$. It is in this generalization that we see the close relation between the general theory of orthogonal polynomials and random matrix theory. For $`\beta =1\text{or}\mathrm{\hspace{0.25em}4}`$, generalizing F. J. Dyson’s 1970 analysis of the $`n`$-point correlations for the circular ensembles, it follows from work by Mehta the following year that the square of $`E_{N\beta }(0;J)`$ again equals a Fredholm determinant, $`det(IK_{N\beta })`$, but now the kernel of $`K_{N\beta }`$ is a $`2\times 2`$ matrix.<sup>6</sup><sup>6</sup>6 See  for elementary proofs of these facts.

## 3 Scaling Limits (Limiting Laws)

### 3.1 Bulk Scaling Limit

Let $`\rho _N(x)`$ denote the density of eigenvalues at $`x`$ and pick a point $`x_0`$, independent of $`N`$ with $`\rho _N(x_0)>0`$. We scale distances so that resulting density is one at $`x_0`$, $`\xi :=\rho _N(x_0)\left(xx_0\right)`$, and we call the limit

$$N\mathrm{},xx_0,\text{such that}\xi \text{is fixed},$$

the bulk scaling limit. For $`\beta =2`$,

$$E_{N2}(0;J)E_2(0;J)=det\left(IK_2\right)$$

where the integral operator $`K_2`$ (acting on $`L^2(J)`$) has as its kernel (the sine kernel)

$$\frac{1}{\pi }\frac{\mathrm{sin}\pi (\xi \xi ^{})}{\xi \xi ^{}}.$$

(We use the same symbol $`J`$ to denote the scaled set $`J`$.) Furthermore,

$$p_2(s)=\frac{d^2}{ds^2}E_2(0;(0,s))$$

is the (limiting) level-spacing density for GUE; known as the Gaudin distribution.<sup>7</sup><sup>7</sup>7For the analogous $`\beta =1,4`$ results, see, e.g.,  or . We observe that the limiting kernel is translationally invariant and independent of $`x_0`$.

### 3.2 Edge Scaling Limit

In the gaussian ensembles, the density decays exponentially fast around $`2\sigma \sqrt{N}`$; perhaps surprisingly, it is also the case that

$$\underset{N\mathrm{}}{lim}\frac{\lambda _{\text{max}}(N)}{\sqrt{N}}=2\sigma ,a.s.$$
(3.1)   
where $`\sigma `$ is the standard deviation of the off-diagonal matrix elements. (In the normalization we’ve adopted, $`\sigma =1/\sqrt{2}`$.) If we introduce the scaled random variable $`\widehat{\lambda }`$ through

$$\lambda _{\text{max}}=2\sigma \sqrt{N}+\frac{\sigma \widehat{\lambda }}{N^{1/6}},$$

then

$$\text{Prob}\left(\lambda _{\text{max}}t\right)=\text{Prob}\left(\widehat{\lambda }s\right)F_\beta (s)\text{as}N\mathrm{},$$

where $`t=2\sigma \sqrt{N}+\sigma s/N^{1/6}`$. For $`\beta =2`$,

$$F_2(s)=det(IK_{\text{Airy}}),$$

where $`K_{\text{Airy}}`$ has kernel of the form (2.1) with $`\phi (x)=\text{Ai}(x)`$, $`\psi (x)=\text{Ai}^{}(x)`$ and $`J=(s,\mathrm{})`$. (See, e.g.,  for the $`\beta =1,4`$ results.)

## 4 Connections with Integrable Systems

### 4.1 Bulk Scaling Limit

In 1980 M. Jimbo, T. Miwa, Y. Môri, and M. Sato  expressed the Fredholm determinant of the sine kernel in terms of a solution to a certain system of integrable differential equations.<sup>8</sup><sup>8</sup>8A simplified proof of their results can be found in . In the simplest case of a single interval, $`J=(0,s)`$, the differential equation is a particular case of Painlevé V ($`P_V`$)<sup>9</sup><sup>9</sup>9The differential equation below is the sigma representation of $`P_V`$. and the Fredholm determinant is given by

$$det\left(I\lambda K_2\right)=\mathrm{exp}\left(_0^{\pi s}\frac{\sigma (x;\lambda )}{x}𝑑x\right),$$

$$\left(x\sigma ^{\prime \prime }\right)^2+4\left(x\sigma ^{}\sigma \right)\left(x\sigma ^{}\sigma +(\sigma ^{})^2\right)=0,$$

$$\sigma (x;\lambda )\frac{\lambda }{\pi }x,\text{as}x0.$$

For $`\beta =1,4`$ and $`J=(0,s)`$, $`E_\beta (0;(0,s))`$ can also be expressed in terms of the same function $`\sigma (x;1)`$. A down-to-earth application of these Painlevé representations (and using the known asymtptotics of $`\sigma (x;1)`$) is that one can easily produce graphs of the level spacing densities $`p_\beta (s)`$.<sup>10</sup><sup>10</sup>10Without the Painlevé representations, the numerical evaluation of the Fredholm determinants is quite involved.

### 4.2 Edge Scaling Limit

The limiting distributions (edge scaling) of the largest eigenvalue, $`F_\beta (s)`$, can also be expressed in terms of Painlevé functions—this time $`P_{II}`$ :

$`F_1(s)^2`$ $`=`$ $`\mathrm{exp}\left({\displaystyle _s^{\mathrm{}}}q(x)𝑑x\right)F_2(s),`$ (4.1)   
$`F_2(s)`$ $`=`$ $`\mathrm{exp}\left({\displaystyle _s^{\mathrm{}}}(xs)q(x)^2𝑑x\right),`$ (4.2)   
$`F_4(s/\sqrt{2})^2`$ $`=`$ $`\mathrm{cosh}^2\left({\displaystyle \frac{1}{2}}{\displaystyle _s^{\mathrm{}}}q(x)𝑑x\right)F_2(s),`$ (4.3)   
where $`q`$ satisfies the Painlevé II equation

$$q^{\prime \prime }=xq+2q^3$$

with boundary condition $`q(x)\text{Ai}(x)`$ as $`x\mathrm{}`$.<sup>11</sup><sup>11</sup>11That a solution $`q`$ exists and is unique follows from the representation of the Fredholm determinant in terms of it. Independent proofs of this, as well as the asymptotics as $`x\mathrm{}`$, were given by S. Hastings and J. McLeod, P. Clarkson and McLeod and by P. Deift and X. Zhou. The graphs of the densities $`f_\beta (s)=dF_\beta (s)/ds`$ are in Figure 1.

### 4.3 Generalizations

Both the sine kernel and the Airy kernel are of the form (2.1). Kernels of this form arise in many problems in integrable systems; indeed, so much so that A. Its, A. Izergin, V. Korepin and V. Slavnov  in 1990 initiated a general analysis of these kernels. The following theorem , which applies to a wide class of $`\beta =2`$ random matrix ensembles, gives the general situation:

Theorem: Let $`J=_{j=1}^m(a_{2j1}a_{2j})`$ be a union of open intervals. Define $`\tau (a)=det\left(IK\right)`$ where $`K`$ is an integral operator acting on $`L^2(J)`$ whose kernel is of the form (2.1) where $`\phi `$ and $`\psi `$ are assumed to satisfy

$$\frac{d}{dx}\left(\begin{array}{c}\phi \\ \psi \end{array}\right)=\mathrm{\Omega }(x)\left(\begin{array}{c}\phi \\ \psi \end{array}\right)$$

with $`\mathrm{\Omega }(x)`$ a $`2\times 2`$ matrix with zero trace and rational entries in $`x`$, then $`\frac{}{a_j}\mathrm{log}det(IK)`$ are expressible polynomially in terms of solutions to a total system of partial differential equations ($`a_j`$ are the independent variables). The differential equations are given explicitly in terms of the coefficients of the rational functions appearing in $`\mathrm{\Omega }(x)`$.

### 4.4 Historical Comments

The first connection between Toeplitz/Fredholm determinants and Painlevé functions was established in 1973–77 in work of T. T. Wu, B. M. McCoy, E. Barouch and the first author concerning the scaling limit of the 2-point functions of the 2D Ising model of statistical mechanics. The Painlevé function that arose was $`P_{III}`$. This work was subsequently generalized by Sato, Miwa and Jimbo to $`n`$-point functions and, more generally, holonomic quantum fields. The Kyoto School then took up the problem of the density matrix of the impenetrable Bose gas and it was in this context that they discovered that the Fredholm determinant of the sine kernel is related to $`P_V`$.

A crucial simplification of the Kyoto School work, as it applies to random matrix theory, was made by Mehta in 1992 . This last work inspired the commutator methods introduced by the present authors in the period 1993–96. Since then both Riemann-Hilbert methods of Deift, Its, Zhou and others (see, e.g. ); and Virasoro methods of M. Adler, T. Shiota, P. van Moerbeke, and others (see, e.g. ), have played an increasingly important role in the development of random matrix theory. The connection of these methods with the isomonodromy method has been clarified by J. Palmer  and J. Harnad .

Space does not permit us to discuss the interesting connections between random matrices and Szegö type limit theorems. See E. Basor  for connections with linear statistics and the review papers  for some related historical comments.

## 5 Universality

### 5.1 Universality of Gaussian Ensembles in Random Matrix Models

#### 5.1.1 Invariant Measures, $`\beta =2`$

As briefly mentioned above, a widely studied class of random matrix models is defined by the replacement of the gaussian potential, $`x^2`$, by the general potential $`V(x)`$. For the weight functions most studied, the parameter $`N`$ is put into the exponent so that the weight function becomes $`e^{NV(x)}`$. For different $`V`$’s, the limiting density $`\rho _V(x)`$ can be quite different. It may be supported on many distinct intervals, and it may vanish at interior points of its support. In the gaussian case, the limiting density is the Wigner semicircle law: $`\rho _W(x)=\frac{2}{\pi }\sqrt{1x^2}`$. Heuristic arguments suggest that the behavior exhibited by the Wigner law—that $`\rho `$ is positive on the interior of its support and vanishes like a square root at endpoints—is the typical behavior for $`\rho _V`$. The bulk scaling limit and edge scaling limit are defined in analogous ways to the gaussian cases. To establish universality of these scaling limits, one must show (for $`\beta =2`$ ensembles) that the scaled kernels approach the sine kernel and the Airy kernel, respectively. The potential $`V(x)=\frac{t}{2}x^2+\frac{g}{4}x^4`$ ($`g>0`$, $`t<0`$) is an example of a “two interval” potential. Indeed, for this important example P. Bleher and A. Its  proved precisely this statement of universality. (See their paper for related work in the orthogonal polynomial literature as well as the physics literature.) Recently, building on work of , A. Kuijlaars and K. McLaughlin  have shown this behavior is generic for real analytic $`V`$ satisfying $`lim_x\mathrm{}V(x)/\mathrm{log}|x|=+\mathrm{}`$.

In the physics literature, M. Bowick, E. Brézin  and others have argued (for $`\beta =2`$ ensembles) that if $`\rho _V`$ vanishes faster than a square root, then the corresponding edge scaling limit will result in nonAiry universality classes. The resulting new kernels will have form (2.1) and the theory developed in  will apply, but there remains much to be understood in these cases.

For $`\beta =1,4`$, the situation is more complicated due to the structure of $`K_V`$ , and the “universality” theorems are not so general.

### 5.2 Noninvariant Measures: Wigner Ensemble

The Wigner ensembles are defined by requiring that the matrix elements on and above the diagonal in either the real symmetric case or the complex hermitian case are independent and identically distributed random variables. It is only in the case when the distribution is gaussian is the measure invariant. One usually assumes, as we do here, that all moments of the common distribution function exist. It was Wigner himself who showed that the limiting density of states is the Wigner semicircle. Subsequently several authors—culminating in a theorem by Z. Bai and Y. Lin clarifying which moments need exist—showed (3.1) continues to hold for the Wigner ensembles.

It should be noted that because the measure is noninvariant, the nongaussian Wigner ensembles do not, as far as we understand, have Fredholm determinant representation for their distribution functions. This means, for one, that the methods of integrable systems are not directly applicable to Wigner ensembles. It is therefore particularly important, as A. Soshnikov  recently proved, that in the edge scaling limit the Wigner ensembles are in the same universality class as the gaussian models. In particular, the limiting distribution of the scaled largest eigenvalue is given by $`F_1(s)`$ for real symmetric Wigner matrices and by $`F_2(s)`$ for complex hermitian Wigner matrices.

### 5.3 Examples from Physics

A second type of universality, and the one first envisioned by Wigner in the context of nuclear physics, asserts in Wigner’s words 

> Let me say only one more word. It is very likely that the curve in Figure I \[an approximate graph of $`p_1(s)`$\] is a universal function. In other words, it doesn’t depend on the details of the model with which you are working.

The modern version of this asserts that for a classical, “fully” chaotic Hamiltonian the corresponding quantum system has a level spacing distribution equal to $`p_\beta (s)`$ in the bulk. (The symmetry class determines which ensemble.) This quantum chaos conjecture, due to O. Bohigas, M. Giannoni and C. Schmit , has been a guiding principle for much subsequent work, though it is the authors’ understanding that it remains a conjecture. A particularly nice numerical example supporting this conjecture is M. Robnik’s work  on chaotic billards. The reader is referred to the recent review article  for further numerical examples that support this conjecture. It should be noted that there are examples from number theory where the conjecture fails. Thus, as it has been said, the conjecture is undoubtedly true except where it is demonstratively false.

#### 5.3.1 Aperiodic Tiling Adjacency Matrix

The discovery of quasicrystals has made the study of statistical mechanical models whose underlying lattice is quasiperiodic of considerable interest to physicists. In particular, in order to understand transport properties, tight binding models have been defined on various quasiperiodic lattices. One such study by Zhong et al.  defined a simplified tight binding model for the octagonal tiling of Ammann and Beenker. This quasiperiodic tiling consists of squares and rhombi with all edges of equal lengths (see Figure 2) and has a $`D_8`$ symmetry around the central vertex. On this tiling the authors take as their Hamiltonian the adjacency matrix for the graph with free boundary conditions. The largest lattice they consider has 157,369 vertices. The matrix splits into ten blocks according to the irreducible representations of the dihedral group $`D_8`$. For each of these ten independent subspectra, they compare the empirical distribution of the normalized spacings of the consecutive eigenvalues with the GOE level spacing density $`p_1(s)`$. In Figure 2 we have reproduced a portion of their data for one such subspectrum together with $`p_1`$.

### 5.4 Spacings of the Consecutive Zeros of Zeta Functions

Perhaps the most surprising appearance of the distributions of random matrix theory is in number theory. Analytical work by H. Montgomery and extensive numerical calculations by A. Odlyzko on the zeros of the Riemann zeta function have given convincing evidence that the normalized consecutive spacings follow the Gaudin distribution, see Figure 3. Recent results of Z. Rudnick and P. Sarnak are also compatible with the belief that the distribution of the spacings between zeros, not only of the Riemann zeta function, but also of quite general automorphic $`L`$-functions over Q, are all given by this Montgomery-Odlyzko Law. In their landmark book , N. Katz and P. Sarnak establish the Montgomery-Odlyzko Law for wide classes of zeta and $`L`$-functions over finite fields.

### 5.5 Random Matrix Theory and Combinatorics

The last decade has seen a flurry of activity centering around connections between combinatorial probability of the Robinson-Schensted-Knuth (RSK) type on the one hand and random matrices and integrable systems on the other. From the point of view of probability theory, the quite surprising feature of these developments is that the methods came from Toeplitz determinants, integrable differential equations of the Painlevé type and the closely related Riemann-Hilbert techniques as they were applied and refined in random matrix theory. Using these techniques new, and apparently quite universal, limiting laws have been discovered. The earliest signs of these connections can be found in the work of A. Regev  and I. Gessel . Here, however, we introduce this subject by examining a certain card game of D. Aldous and P. Diaconis , called patience sorting.

#### 5.5.1 Patience Sorting and Random Permutations

Our deck of cards is labeled $`\{1,2,\mathrm{},N\}`$ and we order the cards with their natural ordering. Shuffle the deck of cards and

* Turn over the first card.
* Turn over the second card. If it is of higher rank, start a new pile to the right of the first card. Otherwise place the second card on top of the first card.
* Turn over the third card. If it is of higher rank than either the first or the second card, start a new pile to the right of the second card. Otherwise place the third card on top of the card of higher rank. If both first and second are of higher rank, place the third card on the smaller ranked card. (That is, play cards as far as possible to the left.)
* Continue playing the game, playing cards as far left as possible, until all the cards are turned over.

The object of the game is to end with a small number of piles. Let $`\mathrm{}_N(\sigma )`$ equal the number of piles at the end of the game where we started with deck $`\sigma =\{i_1,i_2,\mathrm{},i_N\}`$. Clearly, $`1\mathrm{}_N(\sigma )N`$, but what are some typical values for a shuffled deck? Starting each time with a newly shuffled deck of $`N=52`$ cards, the computer played patience sorting 100,000 times. Here are the statistics for $`\mathrm{}_{52}`$:

* Mean=11.56 (11.00).
* Standard Deviation=1.37 (1.74)
* Skewness=0.33 (0.22)
* Kurtosis Excess =0.16 (0.09)
* Sample Range = 7 to 19 (Probability 0.993)

where the numbers in parentheses are the asymptotic predictions (as the number of cards tends to infinity) of the theory of J. Baik, P. Deift and K. Johansson  to be described below.

A shuffled deck of cards, $`\sigma =\{i_1,i_2,\mathrm{},i_N\}`$, is a permutation of $`\{1,2,\mathrm{},n\}`$, and so we think of the shuffled deck as a random permutation. A moment’s reflection will convince the reader that $`\mathrm{}_N(\sigma )`$ is equal to the length of the longest increasing subsequence in the permutation $`\sigma `$. As a problem in random permutations, determining the asymptotics of $`E(\mathrm{}_N)`$ as $`N\mathrm{}`$ is called Ulam’s Problem. In the 1970’s A. Vershik and S. Kerov and independently B. Logan and L. Shepp showed $`E(\mathrm{}_N)2\sqrt{N}`$ with important earlier work by J. Hammersley. Hammersley’s analysis introduced a certain interacting particle system interpretation. This was developed by Aldous and Diaconis  who in 1995 gave a “soft” proof of this result using hydrodynamic scaling arguments from interacting particle theory.

Introducing the exponential generating function

$$\underset{N0}{}\text{Prob}(\mathrm{}_Nn)\frac{t^N}{N!},$$

Gessel showed that it is equal to $`D_n(t)`$, the determinant of the $`n\times n`$ Toeplitz determinant with symbol $`e^{\sqrt{t}(z+z^1)}`$. (Recall that the $`i,j`$ entry of a Toeplitz matrix equals the $`ij`$ Fourier coefficient of its symbol.) It is in this work of Gessel and subsequent work of Odlyzko et al.  and E. Rains , that the methods of random matrix theory first appear in RSK type problems.<sup>12</sup><sup>12</sup>12Gessel  does not mention random matrices, but in light of well-known formulas in random matrix theory relating Toeplitz determinants to expectations over the unitary group, we believe it is fair to say that the connection with random matrix theory begins with this discovery. See, however, Regev .

Starting with this Toeplitz determinant representation, Baik, Deift and Johansson , using the steepest descent method for Riemann-Hilbert problems , derived a delicate asymptotic formula for $`D_n(t)`$ which we now describe. Introduce another parameter $`s`$ and suppose that $`n`$ and $`t`$ are related by $`n=[2t^{1/2}+st^{1/6}]`$. Then as $`t\mathrm{}`$ with $`s`$ fixed one has

$$\underset{t\mathrm{}}{lim}e^tD_n(t)=F_2(s)$$

where $`F_2(s)`$ is the distribution function (4.2). Using a dePoissonization lemma due to Johansson , these asymptotics led Baik, Deift and Johansson to the limiting law

$$\underset{N\mathrm{}}{lim}\text{Prob}\left(\frac{\mathrm{}_N2\sqrt{N}}{N^{1/6}}<s\right)=F_2(s).$$

Since the work of Baik, Deift and Johansson, several groups have extended this connection between RSK type combinatorics and the distribution functions of random matrix theory. The aforementioned result is equivalent to the determination of the limiting distribution of the number of boxes in the first row in the RSK correspondence $`\sigma (P,Q)`$. In  the same authors show that the limiting distribution of the number of boxes in the second row is (when centered and normalized) distributed as the second largest scaled eigenvalue in GUE . They then conjectured that this correspondence extends to all rows. This conjecture was recently proved by A. Okounkov  using topological methods and by A. Borodin, A. Okounkov and G. Olshanski  and Johansson  using analytical methods.

Placing restrictions on the permutations $`\sigma `$ (that they be fixed point free and involutions), Baik and Rains  have shown that the limiting laws for the length of the longest increasing/decreasing subsequence are now the limiting distributions $`F_1`$ and $`F_4`$ for the scaled largest eigenvalue in GOE and GSE, see (4.1) and (4.3). Generalizing to signed permutations and colored permutations the present authors and Borodin  showed that the distribution functions of the length of the longest increasing subsequence involve the same $`F_2`$.

Johansson  showed that the shape fluctuations of a certain random growth model, again appropriately scaled, converges in distribution to $`F_2`$. (This random growth model is intimately related to certain randomly growing Young diagrams.) In subsequent work, Johansson  showed that the fluctuations in certain random tiling problems (related to the Artic Circle Theorem) are again described by $`F_2`$. Finally, Johansson  and the present authors  have considered analogous problems for random words and have discovered various random matrix theory connections.

Acknowledgments The authors have benefited from conversations with A. Its and it is a pleasure to acknowledge this. The first author thanks J. Harnad and P. Winternitz for their invitation to speak at the workshop Integrable Systems: From Classical to Quantum. This work was supported, in part, by the National Science Foundation through grants DMS–9802122 and DMS–9732687.