Tracy–Widom distribution

From HandWiki
Short description: Probability distribution
Densities of Tracy–Widom distributions for β = 1, 2, 4

The Tracy–Widom distribution is a probability distribution from random matrix theory introduced by Craig Tracy and Harold Widom (1993, 1994). 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,[2] as large-scale statistics in the Kardar-Parisi-Zhang equation,[3] in current fluctuations of the asymmetric simple exclusion process (ASEP) with step initial condition,[4] and in simplified mathematical models of the behavior of the longest common subsequence problem on random inputs.[5] See (Takeuchi Sano) and (Takeuchi Sano) for experimental testing (and verifying) that the interface fluctuations of a growing droplet (or substrate) are described by the TW distribution [math]\displaystyle{ F_2 }[/math] (or [math]\displaystyle{ F_1 }[/math]) as predicted by (Prähofer Spohn).

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

Definition as a law of large numbers

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

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

In general, consider a gaussian ensemble with beta value [math]\displaystyle{ \beta }[/math], with its diagonal entries having variance 1, and off-diagonal entries having variance [math]\displaystyle{ \sigma^2 }[/math], and let [math]\displaystyle{ F_{N, \beta}(s) }[/math] be probability that an [math]\displaystyle{ N\times N }[/math] matrix sampled from the ensemble have maximal eigenvalue [math]\displaystyle{ \leq s }[/math], then define[8][math]\displaystyle{ F_\beta(x) = \lim_{N\to \infty} F_{N, \beta}(\sigma(2N^{1/2} + N^{-1/6} x)) =\lim_{N \to \infty} Pr(N^{1/6}(\lambda_{max}/\sigma - 2N^{1/2}) \leq x) }[/math]where [math]\displaystyle{ \lambda_{\max} }[/math] denotes the largest eigenvalue of the random matrix. The shift by [math]\displaystyle{ 2\sigma N^{1/2} }[/math] centers the distribution, since at the limit, the eigenvalue distribution converges to the semicircular distribution with radius [math]\displaystyle{ 2\sigma N^{1/2} }[/math]. The multiplication by [math]\displaystyle{ N^{1/6} }[/math] is used because the standard deviation of the distribution scales as [math]\displaystyle{ N^{-1/6} }[/math] (first derived in [9]).

For example:[10]

[math]\displaystyle{ F_2(x) = \lim_{N\to \infty} \operatorname{Prob}\left( (\lambda_{\max}-\sqrt{4N})N^{1/6}\leq x\right), }[/math]

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

The definition of the Tracy–Widom distributions [math]\displaystyle{ F_\beta }[/math] may be extended to all [math]\displaystyle{ \beta \gt 0 }[/math] (Slide 56 in (Edelman 2003), (Ramírez Rider)).

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

[math]\displaystyle{ F_2 }[/math] can be given as the Fredholm determinant

[math]\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 }[/math]

of the kernel [math]\displaystyle{ A_s }[/math] ("Airy kernel") on square integrable functions on the half line [math]\displaystyle{ (s,\infty) }[/math], given in terms of Airy functions Ai by

[math]\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} }[/math]

Painlevé transcendents

[math]\displaystyle{ F_2 }[/math] can also be given as an integral

[math]\displaystyle{ F_2(s) = \exp\left(-\int_s^\infty (x-s)q^2(x)\,dx\right) }[/math]

in terms of a solution[note 1] of a Painlevé equation of type II

[math]\displaystyle{ q^{\prime\prime}(s) = sq(s)+2q(s)^3\, }[/math]

with boundary condition [math]\displaystyle{ \displaystyle q(s) \sim \textrm{Ai}(s), s\to\infty. }[/math] This function [math]\displaystyle{ q }[/math] is a Painlevé transcendent.

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

[math]\displaystyle{ \begin{align} 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{align} }[/math]

Functional equations

Define [math]\displaystyle{ \begin{align} F(x) &= \exp\left(-\frac{1}{2}\int_{x}^{\infty}(y-x)q(y)^{2}\,d y\right) \\ E(x) &= \exp\left(-\frac{1}{2}\int_{x}^{\infty}q(y)\,d y\right) \end{align} }[/math]then[8][math]\displaystyle{ F_1(x) = E(x)F(x), \quad F_2(x) = F(x)^2, \quad \quad F_4\left(\frac{x}{\sqrt{2}}\right) = \frac{1}{2}\left(E(x) + \frac{1}{E(x)}\right)F(x) }[/math]

Occurrences

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

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

Asymptotics

Probability density function

Let [math]\displaystyle{ f_\beta(x) = F_\beta'(x) }[/math] be the probability density function for the distribution, then[12][math]\displaystyle{ f_{\beta}(x) \sim \begin{cases} e^{-\frac{\beta}{24}|x|^3}, \quad x \to -\infty\\ e^{-\frac{2\beta}{3}|x|^{3/2}},\quad x \to +\infty \end{cases} }[/math]In particular, we see that it is severely skewed to the right: it is much more likely for [math]\displaystyle{ \lambda_{max} }[/math] to be much larger than [math]\displaystyle{ 2\sigma\sqrt{N} }[/math] 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 [math]\displaystyle{ \lambda_{max} }[/math] to be not much smaller than [math]\displaystyle{ 2\sigma\sqrt{N} }[/math].

At the [math]\displaystyle{ x\to -\infty }[/math] limit, a more precise expression is (equation 49 [12])[math]\displaystyle{ f_{\beta}(x) \sim \tau_{\beta}|x|^{(\beta^{2}+4-6\beta)/16\beta}\exp\left[-\beta\frac{|x|^{3}}{24}+\sqrt{2}\frac{\beta-2}{6}|x|^{3/2}\right] }[/math]for some positive number [math]\displaystyle{ \tau_\beta }[/math] that depends on [math]\displaystyle{ \beta }[/math].

Cumulative distribution function

At the [math]\displaystyle{ x\to +\infty }[/math] limit,[14][math]\displaystyle{ \begin{align} F(x)&=1-\frac{e^{-\frac{4}{3}x^{3/2}}}{32\pi x^{3/2}}\biggl(1-\frac{35}{24x^{3/2}}+{\cal O}(x^{-3})\biggr), \\ E(x) &=1-\frac{e^{-\frac{2}{3}x^{3/2}}}{4\sqrt{\pi}x^{3/2}}\biggl(1-\frac{41}{48x^{3/2}}+{\cal O}(x^{-3})\biggr) \end{align} }[/math]and at the [math]\displaystyle{ x\to -\infty }[/math] limit,[math]\displaystyle{ \begin{align} F(x)&=2^{1/48}e^{\frac{1}{2}\zeta^{\prime}(-1)}\frac{e^{-\frac{1}{24}|x|^{3}}}{|x|^{1/16}} \left(1+\frac{3}{2^{7}|x|^{3}}+O(|x|^{-6})\right) \\ E(x)&=\frac{1}{2^{1/4}}e^{-\frac{1}{3\sqrt{2}}|x|^{3/2}} \Biggl(1-\frac{1}{24\sqrt{2}|x|^{3/2}}+{\cal O}(|x|^{-3})\Biggr). \end{align} }[/math]where [math]\displaystyle{ \zeta }[/math] is the Riemann zeta function, and [math]\displaystyle{ \zeta' (-1) = -0.1654211437 }[/math].

This allows derivation of [math]\displaystyle{ x\to \pm\infty }[/math] behavior of [math]\displaystyle{ F_\beta }[/math]. For example,[math]\displaystyle{ \begin{align} 1-F_{2}(x)&=\frac{1}{32\pi x^{3/2}}e^{-4x^{3/2}/3}(1+O(x^{-3/2})), \\ F_{2}(-x)&=\frac{2^{1/24}e^{\zeta^{\prime}(-1)}}{x^{1/8}}e^{-x^{3}/12}\biggl(1+\frac{3}{2^{6}x^{3}}+O(x^{-6})\biggr). \end{align} }[/math]

Painlevé transcendent

The Painlevé transcendent has asymptotic expansion at [math]\displaystyle{ x \to -\infty }[/math] (equation 4.1 of [15])[math]\displaystyle{ q(x) = \sqrt{-\frac{x}{2}} \left(1 + \frac 18 x^{-3} - \frac{73}{128} x^{-6} + \frac{10657}{1024}x^{-9} + O(x^{-12})\right) }[/math]This is necessary for numerical computations, as the [math]\displaystyle{ q\sim \sqrt{-x/2} }[/math] solution is unstable: any deviation from it tends to drop it to the [math]\displaystyle{ q \sim -\sqrt{-x/2} }[/math] 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) 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 [math]\displaystyle{ \beta=1,2,4 }[/math]) 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 [math]\displaystyle{ F_\beta }[/math] and the density functions [math]\displaystyle{ f_\beta(s)=dF_\beta/ds }[/math] for [math]\displaystyle{ \beta=1,2,4 }[/math]. These algorithms can be used to compute numerically the mean, variance, skewness and excess kurtosis of the distributions [math]\displaystyle{ F_\beta }[/math].[17]

[math]\displaystyle{ \beta }[/math] 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 Ma) and MATLAB package 'RMLab' by (Dieng 2006).

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

(Shen Serkh) developed a spectral algorithm for the eigendecomposition of the integral operator [math]\displaystyle{ A_s }[/math], which can be used to rapidly evaluate Tracy–Widom distributions, or, more generally, the distributions of the [math]\displaystyle{ k }[/math]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 [math]\displaystyle{ t^{1/3} }[/math] scaling of the one-dimensional KPZ equation with fixed time.[18]

See also

Footnotes

  1. Mysterious Statistical Law May Finally Have an Explanation, wired.com 2014-10-27
  2. Baik, Deift & Johansson (1999).
  3. (Sasamoto Spohn)
  4. (Johansson 2000); (Tracy Widom)).
  5. Majumdar & Nechaev (2005).
  6. Johnstone (2007, 2008, 2009).
  7. Domínguez-Molina (2017).
  8. 8.0 8.1 8.2 Tracy, Craig A.; Widom, Harold (2009b). "The Distributions of Random Matrix Theory and their Applications". in Sidoravičius, Vladas (in en). New Trends in Mathematical Physics. Dordrecht: Springer Netherlands. pp. 753–765. doi:10.1007/978-90-481-2810-5_48. ISBN 978-90-481-2810-5. https://link.springer.com/chapter/10.1007/978-90-481-2810-5_48. 
  9. Forrester, P. J. (1993-08-09). "The spectrum edge of random matrix ensembles" (in en). Nuclear Physics B 402 (3): 709–728. doi:10.1016/0550-3213(93)90126-A. ISSN 0550-3213. Bibcode1993NuPhB.402..709F. https://dx.doi.org/10.1016/0550-3213%2893%2990126-A. 
  10. 10.0 10.1 Tracy & Widom (1996).
  11. Dieng, Momar (2005). "Distribution functions for edge eigenvalues in orthogonal and symplectic ensembles: Painlevé representations". International Mathematics Research Notices 2005 (37): 2263–2287. doi:10.1155/IMRN.2005.2263. ISSN 1687-0247. 
  12. 12.0 12.1 12.2 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): P01012. doi:10.1088/1742-5468/2014/01/p01012. ISSN 1742-5468. Bibcode2014JSMTE..01..012M. http://dx.doi.org/10.1088/1742-5468/2014/01/p01012. 
  13. Baik, Deift & Johansson 1999
  14. 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. doi:10.1007/s00220-008-0433-5. ISSN 0010-3616. Bibcode2008CMaPh.280..463B. http://dx.doi.org/10.1007/s00220-008-0433-5. 
  15. Tracy, Craig A.; Widom, Harold (May 1993). "Level-spacing distributions and the Airy kernel". Physics Letters B 305 (1–2): 115–118. doi:10.1016/0370-2693(93)91114-3. ISSN 0370-2693. Bibcode1993PhLB..305..115T. http://dx.doi.org/10.1016/0370-2693(93)91114-3. 
  16. Bender, Carl M.; Orszag, Steven A. (1999-10-29) (in en). Advanced Mathematical Methods for Scientists and Engineers I: Asymptotic Methods and Perturbation Theory. Springer Science & Business Media. pp. 163–165. ISBN 978-0-387-98931-0. https://books.google.com/books?id=-yQXwhE6iWMC&dq=Advanced+Mathematical+Methods+for+Scientists+and+Engineers&pg=PR13. 
  17. Su, Zhong-gen; Lei, Yu-huan; Shen, Tian (2021-03-01). "Tracy-Widom distribution, Airy2 process and its sample path properties" (in en). Applied Mathematics-A Journal of Chinese Universities 36 (1): 128–158. doi:10.1007/s11766-021-4251-2. ISSN 1993-0445. 
  18. Amir, Gideon; Corwin, Ivan; Quastel, Jeremy (2010). "Probability distribution of the free energy of the continuum directed random polymer in 1 + 1 dimensions". Communications on Pure and Applied Mathematics (Wiley) 64 (4): 466--537. doi:10.1002/cpa.20347. 
  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

Further reading

External links