Tracy–Widom distribution explained

The Tracy–Widom distribution is a probability distribution from random matrix theory introduced by . It is the distribution of the normalized largest eigenvalue of a random Hermitian matrix. The distribution is defined as a Fredholm determinant.

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 longest increasing subsequence of random permutations, as large-scale statistics in the Kardar-Parisi-Zhang equation, in current fluctuations of the asymmetric simple exclusion process (ASEP) with step initial condition,^[2] and in simplified mathematical models of the behavior of the longest common subsequence problem on random inputs. See and for experimental testing (and verifying) that the interface fluctuations of a growing droplet (or substrate) are described by the TW distribution

F _{2} (or F _{1} ) as predicted by .

The distribution

F _{1} is of particular interest in multivariate statistics.^[3] For a discussion of the universality of F _{\beta} , \beta =1 , 2 , 4 , see . For an application of F _{1} to inferring population structure from genetic data see .In 2017 it was proved that the distribution F is not infinitely divisible.

Definition as a law of large numbers

Let

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

There are typically three Tracy–Widom distributions,

F _{\beta} , with \beta \in \{ 1 , 2 , 4 \} . They correspond to the three gaussian ensembles: orthogonal (\beta =1 ), unitary (\beta =2 ), and symplectic (\beta =4 ).

In general, consider a gaussian ensemble with beta value

\beta , with its diagonal entries having variance 1, and off-diagonal entries having variance \sigma ^{2} , and let F _{N,} (s) be probability that an N x N matrix sampled from the ensemble have maximal eigenvalue \leq s , then define^[4] $$F\_\backslash beta(x)\; =\; \backslash lim\_\; F\_(\backslash sigma(2N^\; +\; N^\; x))\; =\backslash lim\_\; Pr(N^(\backslash lambda\_/\backslash sigma\; -\; 2N^)\; \backslash leq\; x)$$where λ _{max} denotes the largest eigenvalue of the random matrix. The shift by 2 \sigma N ^{1/2} centers the distribution, since at the limit, the eigenvalue distribution converges to the semicircular distribution with radius 2 \sigma N ^{1/2} . The multiplication by N ^{1/6} is used because the standard deviation of the distribution scales as N ^{-1/6} (first derived in ^[5]).

For example:

F _{2(x)} = \lim _{N\to} \operatorname{Prob}\left( ( λ _{max} - \sqrt{ 4 N})N ^{1/6} \leq x\right),

where the matrix is sampled from the gaussian unitary ensemble with off-diagonal variance

1 .

The definition of the Tracy–Widom distributions

F _{\beta} may be extended to all \beta > 0 (Slide 56 in,).

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

Functional forms

Fredholm determinant

F _{2} can be given as the Fredholm determinantF _{2(s)} = \det(I - A _{s)} = 1 + \sum ^{inf ty} _{n =1} (( -1 ) ^{n})/(n!) \int _{(s, inf ty) ^{n}} \det _{i,} [A _{s(x} _{i,} x _{j)]dx} _{1 …} dx _{n} A _{s} ("Airy kernel") on square integrable functions on the half line (s, inf ty) , given in terms of Airy functions Ai byA _{s(x,} y) = \begin{cases} (Ai (x) Ai '(y) - Ai '(x) Ai (y))/(x - y) if x ≠ y \\ Ai' (x) ^{2-} x (Ai(x)) ^{2} if x = y \end{cases}

Painlevé transcendents

F _{2} can also be given as an integralF _{2(s)} = \exp\left( - \int ^{inf ty} _{s} (x - s)q ^{2(x)dx\right)}

in terms of a solution^[7] of a Painlevé equation of type II

q ^{\prime\prime} (s) = sq(s) +2 q(s) ^{3} with boundary condition $\backslash displaystyle\; q(s)\; \backslash sim\; \backslash textrm(s),\; s\backslash to\backslash infty.$ This function q is a Painlevé transcendent.

Other distributions are also expressible in terms of the same

q :\begin{align} F _{1(s)} & = \exp\left( - (1)/(2) \int ^{inf ty} _{s} q(x)dx\right) \left(F ^{1 / 2} _{2 (s)\right)} \\ F _{4(s/\sqrt{2})} & = \cosh\left( (1)/(2) \int ^{inf ty} _{s} q(x) dx\right) \left(F ^{1 / 2} _{2 (s)\right)} . \end{align}

Functional equations

Define

then$$F\_1(x)\; =\; E(x)F(x),\; \backslash quad\; F\_2(x)\; =\; F(x)^2,\; \backslash quad\; \backslash quad\; F\_4\backslash left(\backslash frac\backslash right)\; =\; \backslash frac\backslash left(E(x)\; +\; \backslash frac\backslash right)F(x)$$

Occurrences

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

Let

l _{n} be the length of the longest increasing subsequence in a random permutation sampled uniformly from S _{n} , the permutation group on n elements. Then the cumulative distribution function of (l _{n} -2 N ^{1/2})/(N ^{1/6}) converges to F _{2} .

Asymptotics

Probability density function

Let

f _{\beta(x)} = F _{\beta'(x)} be the probability density function for the distribution, then$$f\_(x)\; \backslash sim\; \backslash begine^,\; \backslash quad\; x\; \backslash to\; -\backslash infty\backslash \backslash e^,\backslash quad\; x\; \backslash to\; +\backslash infty\backslash end$$In particular, we see that it is severely skewed to the right: it is much more likely for λ _{max} to be much larger than 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 λ _{max} to be not much smaller than 2 \sigma\sqrt{N} .

At the

x\to -inf ty limit, a more precise expression is (equation 49)$$f\_(x)\; \backslash sim\; \backslash tau\_|x|^\backslash exp\backslash left[-\backslash beta\backslash frac\{|x|^\{3\}\}\{24\}+\backslash sqrt\{2\}\backslash frac\{\backslash beta-2\}\{6\}|x|^\{3/2\}\backslash right]$$for some positive number \tau _{\beta} that depends on \beta .

Cumulative distribution function

At the

x\to +inf ty limit,^[9] $$\backslash begin$$

F(x)&=1-\frac\biggl(1-\frac+(x^)\biggr), \\

E(x) &=1-\frac\biggl(1-\frac+(x^)\biggr)\endand at the

x\to -inf ty limit,

^

\left(1+\frac+O(|x|^)\right) \\E(x)&=\frace^ \Biggl(1-\frac+(|x|^)\Biggr).\endwhere \zeta is the Riemann zeta function, and \zeta' ( -1 ) = -0 . 1654211437 .

This allows derivation of

x\to \pm inf ty behavior of F _{\beta} . For example,$$\backslash begin$$

1-F_(x)&=\frace^(1+O(x^)),\\F_(-x)&=\frace^\biggl(1+\frac+O(x^)\biggr).

\end

Painlevé transcendent

The Painlevé transcendent has asymptotic expansion at

x \to -inf ty (equation 4.1 of ^[10])$$q(x)\; =\; \backslash sqrt\; \backslash left(1\; +\; \backslash frac\; 18\; x^\; -\; \backslash frac\; x^\; +\; \backslash fracx^\; +\; O(x^)\backslash right)$$This is necessary for numerical computations, as the q\sim \sqrt{ - x/ 2 } solution is unstable: any deviation from it tends to drop it to the q \sim - \sqrt{ - x/ 2 } branch instead.^[11]

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 using MATLAB. These approximation techniques were further analytically justified in and used to provide numerical evaluation of Painlevé II and Tracy–Widom distributions (for

\beta =1 , 2 , 4 ) in S-PLUS. These distributions have been tabulated in 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. gave accurate and fast algorithms for the numerical evaluation of F _{\beta} and the density functions f _{\beta(s)=dF} _{\beta/ds} for \beta =1 , 2 , 4 . These algorithms can be used to compute numerically the mean, variance, skewness and excess kurtosis of the distributions F _{\beta} .^[12]

\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 and MATLAB package 'RMLab' by .

For a simple approximation based on a shifted gamma distribution see .

developed a spectral algorithm for the eigendecomposition of the integral operator

A _{s} , which can be used to rapidly evaluate Tracy–Widom distributions, or, more generally, the distributions of the 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 KPZ equation. For example it appears under

t ^{1/3} scaling of the one-dimensional KPZ equation with fixed time.^[13]

See also

• Wigner semicircle distribution
• Marchenko–Pastur distribution

References

• .
• .
• .
  • .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
  • • .
• .
  • .
• .

Further reading

• .
• .
• .
• .

External links

• .
• .
• .
• At the Far Ends of a New Universal Law, Quanta Magazine

Notes and References

1. https://www.wired.com/2014/10/tracy-widom-mysterious-statistical-law/ Mysterious Statistical Law May Finally Have an Explanation

2. ).

3. .
4. Book: Tracy . Craig A. . Widom . Harold . New Trends in Mathematical Physics . The Distributions of Random Matrix Theory and their Applications . 2009b . Sidoravičius . Vladas . https://link.springer.com/chapter/10.1007/978-90-481-2810-5_48 . en . Dordrecht . Springer Netherlands . 753–765 . 10.1007/978-90-481-2810-5_48 . 978-90-481-2810-5.
5. Forrester . P. J. . 1993-08-09 . The spectrum edge of random matrix ensembles . Nuclear Physics B . en . 402 . 3 . 709–728 . 10.1016/0550-3213(93)90126-A . 1993NuPhB.402..709F . 0550-3213.
6. Dieng . Momar . 2005 . Distribution functions for edge eigenvalues in orthogonal and symplectic ensembles: Painlevé representations . International Mathematics Research Notices . 2005 . 37 . 2263–2287 . 10.1155/IMRN.2005.2263 . 1687-0247 . free.
7. 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)

8. Majumdar . Satya N . Schehr . Grégory . 2014-01-31 . Top eigenvalue of a random matrix: large deviations and third order phase transition . Journal of Statistical Mechanics: Theory and Experiment . 2014 . 1 . 01012 . 10.1088/1742-5468/2014/01/p01012 . 1311.0580 . 2014JSMTE..01..012M . 119122520 . 1742-5468.
9. Baik . Jinho . Buckingham . Robert . DiFranco . Jeffery . 2008-02-26 . Asymptotics of Tracy-Widom Distributions and the Total Integral of a Painlevé II Function . Communications in Mathematical Physics . 280 . 2 . 463–497 . 10.1007/s00220-008-0433-5 . 0704.3636 . 2008CMaPh.280..463B . 16324715 . 0010-3616.
10. Tracy . Craig A. . Widom . Harold . May 1993 . Level-spacing distributions and the Airy kernel . Physics Letters B . 305 . 1–2 . 115–118 . 10.1016/0370-2693(93)91114-3 . hep-th/9210074 . 1993PhLB..305..115T . 13912236 . 0370-2693.
11. Book: Bender . Carl M. . Advanced Mathematical Methods for Scientists and Engineers I: Asymptotic Methods and Perturbation Theory . Orszag . Steven A. . 1999-10-29 . Springer Science & Business Media . 978-0-387-98931-0 . 163–165 . en.
12. Su . Zhong-gen . Lei . Yu-huan . Shen . Tian . 2021-03-01 . Tracy-Widom distribution, Airy2 process and its sample path properties . Applied Mathematics-A Journal of Chinese Universities . en . 36 . 1 . 128–158 . 10.1007/s11766-021-4251-2 . 237903590 . 1993-0445. free .
13. Gideon . Amir . Ivan . Corwin . Jeremy . Quastel . Wiley . Probability distribution of the free energy of the continuum directed random polymer in 1 + 1 dimensions . Communications on Pure and Applied Mathematics . 64 . 4 . 2010 . 466–537 . 10.1002/cpa.20347. 1003.0443 .