Tracy–Widom distribution

The Tracy–Widom distribution is a

.

In practical terms, Tracy–Widom is the crossover function between the two phases of weakly versus strongly coupled components in a system.[1] It also appears in the distribution of the length of the

for experimental testing (and verifying) that the interface fluctuations of a growing droplet (or substrate) are described by the TW distribution ${\displaystyle F_{2}}$ (or ${\displaystyle F_{1}}$) as predicted by Prähofer & Spohn (2000).

The distribution ${\displaystyle F_{1}}$ is of particular interest in multivariate statistics.^[6] For a discussion of the universality of ${\displaystyle F_{\beta }}$, ${\displaystyle \beta =1,2,4}$, see Deift (2007). For an application of ${\displaystyle F_{1}}$ to inferring population structure from genetic data see Patterson, Price & Reich (2006). In 2017 it was proved that the distribution F is not infinitely divisible.^[7]

Definition as a law of large numbers

Let ${\displaystyle F_{\beta }}$ denote the cumulative distribution function of the Tracy–Widom distribution with given ${\displaystyle \beta }$. It can be defined as a law of large numbers, similar to the central limit theorem.

There are typically three Tracy–Widom distributions, ${\displaystyle F_{\beta }}$, with ${\displaystyle \beta \in \{1,2,4\}}$. They correspond to the three gaussian ensembles: orthogonal (${\displaystyle \beta =1}$), unitary (${\displaystyle \beta =2}$), and symplectic (${\displaystyle \beta =4}$).

In general, consider a gaussian ensemble with beta value ${\displaystyle \beta }$, with its diagonal entries having variance 1, and off-diagonal entries having variance ${\displaystyle \sigma ^{2}}$, and let ${\displaystyle F_{N,\beta }(s)}$ be probability that an ${\displaystyle N\times N}$ matrix sampled from the ensemble have maximal eigenvalue ${\displaystyle \leq s}$, then define^[8]

where ${\displaystyle \lambda _{\max }}$ denotes the largest eigenvalue of the random matrix. The shift by ${\displaystyle 2\sigma N^{1/2}}$ centers the distribution, since at the limit, the eigenvalue distribution converges to the semicircular distribution with radius ${\displaystyle 2\sigma N^{1/2}}$. The multiplication by ${\displaystyle N^{1/6}}$ is used because the standard deviation of the distribution scales as ${\displaystyle N^{-1/6}}$ (first derived in ^[9]).

For example:^[10]

${\displaystyle F_{2}(x)=\lim _{N\to \infty }\operatorname {Prob} \left((\lambda _{\max }-{\sqrt {4N}})N^{1/6}\leq x\right),}$

where the matrix is sampled from the gaussian unitary ensemble with off-diagonal variance ${\displaystyle 1}$.

The definition of the Tracy–Widom distributions ${\displaystyle F_{\beta }}$ may be extended to all ${\displaystyle \beta >0}$ (Slide 56 in Edelman (2003), Ramírez, Rider & Virág (2006)).

One may naturally ask for the limit distribution of second-largest eigenvalues, third-largest eigenvalues, etc. They are known.^[11][8]

Functional forms

Fredholm determinant

${\displaystyle F_{2}}$ can be given as the Fredholm determinant

${\displaystyle F_{2}(s)=\det(I-A_{s})=1+\sum _{n=1}^{\infty }{\frac {(-1)^{n}}{n!}}\int _{(s,\infty )^{n}}\det _{i,j=1,...,n}[A_{s}(x_{i},x_{j})]dx_{1}\cdots dx_{n}}$

of the kernel ${\displaystyle A_{s}}$ ("Airy kernel") on square integrable functions on the half line ${\displaystyle (s,\infty )}$, given in terms of Airy functions Ai by

${\displaystyle A_{s}(x,y)={\begin{cases}{\frac {\mathrm {Ai} (x)\mathrm {Ai} '(y)-\mathrm {Ai} '(x)\mathrm {Ai} (y)}{x-y}}\quad {\text{if }}x\neq y\\Ai'(x)^{2}-x(Ai(x))^{2}\quad {\text{if }}x=y\end{cases}}}$

Painlevé transcendents

${\displaystyle F_{2}}$ can also be given as an integral

${\displaystyle F_{2}(s)=\exp \left(-\int _{s}^{\infty }(x-s)q^{2}(x)\,dx\right)}$

in terms of a solution

of type II

${\displaystyle q^{\prime \prime }(s)=sq(s)+2q(s)^{3}\,}$

with boundary condition ${\textstyle \displaystyle q(s)\sim {\textrm {Ai}}(s),s\to \infty .}$ This function ${\displaystyle q}$ is a

.

Other distributions are also expressible in terms of the same ${\displaystyle q}$:^[10]

${\displaystyle {\begin{aligned}F_{1}(s)&=\exp \left(-{\frac {1}{2}}\int _{s}^{\infty }q(x)\,dx\right)\,\left(F_{2}(s)\right)^{1/2}\\F_{4}(s/{\sqrt {2}})&=\cosh \left({\frac {1}{2}}\int _{s}^{\infty }q(x)\,dx\right)\,\left(F_{2}(s)\right)^{1/2}.\end{aligned}}}$

Functional equations

Define

then^[8]

Occurrences

Other than in random matrix theory, the Tracy–Widom distributions occur in many other probability problems.^[12]

Let ${\displaystyle l_{n}}$ be the length of the longest increasing subsequence in a random permutation sampled uniformly from ${\displaystyle S_{n}}$, the permutation group on n elements. Then the cumulative distribution function of ${\displaystyle {\frac {l_{n}-2N^{1/2}}{N^{1/6}}}}$ converges to ${\displaystyle F_{2}}$.^[13]

Asymptotics

Probability density function

Let ${\displaystyle f_{\beta }(x)=F_{\beta }'(x)}$ be the probability density function for the distribution, then^[12]

In particular, we see that it is severely skewed to the right: it is much more likely for ${\displaystyle \lambda _{max}}$ to be much larger than ${\displaystyle 2\sigma {\sqrt {N}}}$ than to be much smaller. This could be intuited by seeing that the limit distribution is the semicircle law, so there is "repulsion" from the bulk of the distribution, forcing ${\displaystyle \lambda _{max}}$ to be not much smaller than ${\displaystyle 2\sigma {\sqrt {N}}}$.

At the ${\displaystyle x\to -\infty }$ limit, a more precise expression is (equation 49 ^[12])

for some positive number ${\displaystyle \tau _{\beta }}$ that depends on ${\displaystyle \beta }$.

Cumulative distribution function

At the ${\displaystyle x\to +\infty }$ limit,^[14]

and at the ${\displaystyle x\to -\infty }$ limit,where ${\displaystyle \zeta }$ is the Riemann zeta function, and ${\displaystyle \zeta '(-1)=-0.1654211437}$.

This allows derivation of ${\displaystyle x\to \pm \infty }$ behavior of ${\displaystyle F_{\beta }}$. For example,

Painlevé transcendent

The Painlevé transcendent has asymptotic expansion at ${\displaystyle x\to -\infty }$ (equation 4.1 of ^[15])

This is necessary for numerical computations, as the ${\displaystyle q\sim {\sqrt {-x/2}}}$ solution is unstable: any deviation from it tends to drop it to the ${\displaystyle q\sim -{\sqrt {-x/2}}}$ branch instead.^[16]

Numerics

Numerical techniques for obtaining numerical solutions to the Painlevé equations of the types II and V, and numerically evaluating eigenvalue distributions of random matrices in the beta-ensembles were first presented by Edelman & Persson (2005) using MATLAB. These approximation techniques were further analytically justified in Bejan (2005) and used to provide numerical evaluation of Painlevé II and Tracy–Widom distributions (for ${\displaystyle \beta =1,2,4}$) in S-PLUS. These distributions have been tabulated in Bejan (2005) to four significant digits for values of the argument in increments of 0.01; a statistical table for p-values was also given in this work. Bornemann (2010) gave accurate and fast algorithms for the numerical evaluation of ${\displaystyle F_{\beta }}$ and the density functions ${\displaystyle f_{\beta }(s)=dF_{\beta }/ds}$ for ${\displaystyle \beta =1,2,4}$. These algorithms can be used to compute numerically the

of the distributions ${\displaystyle F_{\beta }}$.^[17]

${\displaystyle \beta }$	Mean	Variance	Skewness	Excess kurtosis
1	−1.2065335745820	1.607781034581	0.29346452408	0.1652429384
2	−1.771086807411	0.8131947928329	0.224084203610	0.0934480876
4	−2.306884893241	0.5177237207726	0.16550949435	0.0491951565

Functions for working with the Tracy–Widom laws are also presented in the R package 'RMTstat' by Johnstone et al. (2009) and MATLAB package 'RMLab' by Dieng (2006).

For a simple approximation based on a shifted gamma distribution see Chiani (2014).

Shen & Serkh (2022) developed a spectral algorithm for the eigendecomposition of the integral operator ${\displaystyle A_{s}}$, which can be used to rapidly evaluate Tracy–Widom distributions, or, more generally, the distributions of the ${\displaystyle k}$th largest level at the soft edge scaling limit of Gaussian ensembles, to machine accuracy.

Tracy-Widom and KPZ universality

The Tracy-Widom distribution appears as a limit distribution in the universality class of the

. For example it appears under ${\displaystyle t^{1/3}}$ scaling of the one-dimensional

See also

• Wigner semicircle distribution
• Marchenko–Pastur distribution

Footnotes

1. ^ called "Hastings–McLeod solution". Published by Hastings, S.P., McLeod, J.B.: A boundary value problem associated with the second Painlevé transcendent and the Korteweg-de Vries equation. Arch. Ration. Mech. Anal. 73, 31–51 (1980)

References

• Baik, J.; Deift, P.; Johansson, K. (1999), "On the distribution of the length of the longest increasing subsequence of random permutations",
  MR 1682248
  .
• Bornemann, F. (2010), "On the numerical evaluation of distributions in random matrix theory: A review with an invitation to experimental mathematics", Markov Processes and Related Fields, 16 (4): 803–866,
  Bibcode:2009arXiv0904.1581B
  .
• Chiani, M. (2014), "Distribution of the largest eigenvalue for real Wishart and Gaussian random matrices and a simple approximation for the Tracy–Widom distribution",
  S2CID 15889291
  .
• Sasamoto, Tomohiro; Spohn, Herbert (2010), "One-Dimensional Kardar-Parisi-Zhang Equation: An Exact Solution and its Universality", Physical Review Letters, 104 (23): 230602,
  S2CID 34945972
• Deift, P. (2007), "Universality for mathematical and physical systems" (PDF),
  S2CID 14133017
  .
• Dieng, Momar (2006), RMLab, a MATLAB package for computing Tracy-Widom distributions and simulating random matrices.
• Domínguez-Molina, J.Armando (2017), "The Tracy-Widom distribution is not infinitely divisible", Statistics & Probability Letters, 213 (1): 56–60,
  S2CID 119676736
  .
• Johansson, K. (2000), "Shape fluctuations and random matrices",
  S2CID 16291076
  .
• Johansson, K. (2002), "Toeplitz determinants, random growth and determinantal processes" (PDF), Proc.
  MR 1957518
  .
• Johnstone, I. M. (2007), "High dimensional statistical inference and random matrices" (PDF),
  S2CID 88524958
  .
• Johnstone, I. M. (2008), "Multivariate analysis and Jacobi ensembles: largest eigenvalue, Tracy–Widom limits and rates of convergence",
  PMID 20157626
  .
• Johnstone, I. M. (2009), "Approximate null distribution of the largest root in multivariate analysis",
  PMID 20526465
  .
• Majumdar, Satya N.; Nechaev, Sergei (2005), "Exact asymptotic results for the Bernoulli matching model of sequence alignment", Physical Review E, 72 (2): 020901, 4,
  S2CID 11390762
  .
• Patterson, N.; Price, A. L.;
  PMID 17194218
  .
• Prähofer, M.; Spohn, H. (2000), "Universal distributions for growing processes in 1+1 dimensions and random matrices",
  S2CID 20814566
  .
• Shen, Z.; Serkh, K. (2022), "On the evaluation of the eigendecomposition of the Airy integral operator",
  S2CID 233407802
  .
• Takeuchi, K. A.; Sano, M. (2010), "Universal fluctuations of growing interfaces: Evidence in turbulent liquid crystals",
  S2CID 19315093
• Takeuchi, K. A.; Sano, M.; Sasamoto, T.; Spohn, H. (2011), "Growing interfaces uncover universal fluctuations behind scale invariance",
  PMID 22355553
• S2CID 119690132
  .
• S2CID 13912236
  .
• S2CID 17398688
• MR 1989209
  .
• S2CID 14730756
  .

Further reading

• Bejan, Andrei Iu. (2005), Largest eigenvalues and sample covariance matrices. Tracy–Widom and Painleve II: Computational aspects and realization in S-Plus with applications (PDF), M.Sc. dissertation, Department of Statistics, The University of Warwick.
• Edelman, A.; Persson, P.-O. (2005), Numerical Methods for Eigenvalue Distributions of Random Matrices,
  Bibcode:2005math.ph...1068E
  .
• Edelman, A. (2003), Stochastic Differential Equations and Random Matrices, SIAM Applied Linear Algebra.
• Ramírez, J. A.; Rider, B.; Virág, B. (2006), "Beta ensembles, stochastic Airy spectrum, and a diffusion", Journal of the American Mathematical Society, 24 (4): 919–944,
  S2CID 10226881
  .

External links

• Kuijlaars, Universality of distribution functions in random matrix theory (PDF).
• Tracy, C. A.; Widom, H., The distributions of random matrix theory and their applications (PDF).
• Johnstone, Iain; Ma, Zongming; Perry, Patrick; Shahram, Morteza (2009), Package 'RMTstat' (PDF).
• At the Far Ends of a New Universal Law, Quanta Magazine