Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph. (English) Zbl 1245.60008

The main object of study is the asymptotic behaviour of the spectral distribution of certain random matrices. The model under consideration depends on a single probability measure \(U\) supported on the non-negative real numbers. The authors consider first a Wigner (i.e., with i.i.d. entries) \(N\times N\) matrix with elements distributed according to \(U\) and then normalize the rows so that the sum along each row is \(1\). The resulting random matrix \(K\) can be also viewed as a (random) Markov kernel of a random walk on the complete graph with \(N\) vertices.
The authors consider the empirical spectral distribution \(\mu_K\) of the matrix \(K\) (i.e., the measure with atoms at eigenvalues of \(K\)) and its limit behavior (perhaps, after some rescaling) as \(N\to\infty\). If the second moment of \(U\) exists, then in the limit one uncovers the familiar Wigner semi-circle law, but the situation changes dramatically when \(U\) has heavy tails. In the paper the case when \(U\) has a tail of index \(\alpha\), that is, when \(U([t,+\infty))\) decays like \(t^{-\alpha}\) up to some slowly changing function, is studied. The authors prove that when \(\alpha\in(1,2)\), then \(\mu_K\) converges to a non-random limit law which turns out to be the same as for Wigner (i.e., not normalized) random matrices with \(U\)-distributed entries. The intuitive reason for this fact is the law of large numbers for the sums of \(U\)-distributed random variables which means that the normalization constant in each row is approximately the same and does not change the shape of the limit distribution. This is no longer true when \(\alpha<1\) and, indeed, the authors prove that there is a phase transition at \(\alpha=1\). For \(\alpha\in(0,1)\), the limit of \(\mu_K\) still exists but no longer coincides with the one appearing in Wigner matrices.
The relation of the limiting law with Poisson weighted infinite trees and the Poisson-Dirichlet distribution is also explained in the article.


60B20 Random matrices (probabilistic aspects)
15B52 Random matrices (algebraic aspects)
47A10 Spectrum, resolvent
Full Text: DOI arXiv


[1] Aldous, D. (1992). Asymptotics in the random assignment problem. Probab. Theory Related Fields 93 507-534. · Zbl 0767.60006
[2] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508. · Zbl 1131.60003
[3] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia of Mathematical Sciences 110 1-72. Springer, Berlin. · Zbl 1037.60008
[4] Auffinger, A., Ben Arous, G. and Péché, S. (2009). Poisson convergence for the largest eigenvalues of heavy tailed random matrices. Ann. Inst. H. Poincaré Probab. Statist. 45 589-610. · Zbl 1177.15037
[5] Belinschi, S., Dembo, A. and Guionnet, A. (2009). Spectral measure of heavy tailed band and covariance random matrices. Comm. Math. Phys. 289 1023-1055. · Zbl 1221.15050
[6] Ben Arous, G. and Černý, J. (2008). The arcsine law as a universal aging scheme for trap models. Comm. Pure Appl. Math. 61 289-329. · Zbl 1141.60075
[7] Ben Arous, G. and Guionnet, A. (2008). The spectrum of heavy tailed random matrices. Comm. Math. Phys. 278 715-751. · Zbl 1157.60005
[8] Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 13 pp. (electronic). · Zbl 1010.82021
[9] Bertoin, J. (2006). Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics 102 . Cambridge Univ. Press, Cambridge. · Zbl 1107.60002
[10] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1989). Regular Variation. Encyclopedia of Mathematics and Its Applications 27 . Cambridge Univ. Press, Cambridge. · Zbl 0667.26003
[11] Bordenave, C., Caputo, P. and Chafaï, D. (2010). Spectrum of large random reversible Markov chains: Two examples. ALEA Lat. Am. J. Probab. Math. Stat. 7 41-64. · Zbl 1276.15016
[12] Bordenave, C., Caputo, P. and Chafaï, D. (2010). Spectrum of non-Hermitian heavy tailed random matrices. Preprint. Available at . · Zbl 1235.60008
[13] Bordenave, C., Lelarge, M. and Salez, J. (2011). The rank of diluted random graphs. Ann. Probab. 39 1097-1121. · Zbl 1298.05283
[14] Bouchaud, J. P. (1992). Weak ergodicity breaking and aging in disordered systems. J. Phys. I France 2 1705-1713.
[15] Bouchaud, J. P. and Cizeau, P. (1994). Theory of Lévy matrices. Phys. Rev. E 3 1810-1822.
[16] Bovier, A. and Faggionato, A. (2005). Spectral characterization of aging: The REM-like trap model. Ann. Appl. Probab. 15 1997-2037. · Zbl 1086.60064
[17] Feller, W. (1971). An Introduction to Probability Theory and Its Applications. Vol. II , 2nd ed. Wiley, New York. · Zbl 0219.60003
[18] Fontes, L. R. G. and Mathieu, P. (2008). K -processes, scaling limit and aging for the trap model in the complete graph. Ann. Probab. 36 1322-1358. · Zbl 1154.60073
[19] Klein, A. (1998). Extended states in the Anderson model on the Bethe lattice. Adv. Math. 133 163-184. · Zbl 0899.60088
[20] LePage, R., Woodroofe, M. and Zinn, J. (1981). Convergence to a stable distribution via order statistics. Ann. Probab. 9 624-632. · Zbl 0465.60031
[21] Perman, M., Pitman, J. and Yor, M. (1992). Size-biased sampling of Poisson point processes and excursions. Probab. Theory Related Fields 92 21-39. · Zbl 0741.60037
[22] Pitman, J. and Yor, M. (1997). The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator. Ann. Probab. 25 855-900. · Zbl 0880.60076
[23] Reed, M. and Simon, B. (1980). Methods of Modern Mathematical Physics. I : Functional Analysis , 2nd ed. Academic Press, New York. · Zbl 0459.46001
[24] Resnick, S. I. (2007). Heavy-tail Phenomena : Probabilistic and Statistical Modeling . Springer, New York. · Zbl 1152.62029
[25] Simon, B. (2005). Trace Ideals and Their Applications , 2nd ed. Mathematical Surveys and Monographs 120 . Amer. Math. Soc., Providence, RI. · Zbl 1074.47001
[26] Soshnikov, A. (2004). Poisson statistics for the largest eigenvalues of Wigner random matrices with heavy tails. Electron. Comm. Probab. 9 82-91 (electronic). · Zbl 1060.60013
[27] Talagrand, M. (2003). Spin Glasses : A Challenge for Mathematicians : Cavity and Mean Field Models. Ergebnisse der Mathematik und Ihrer Grenzgebiete . 3. Folge. A Series of Modern Surveys in Mathematics [ Results in Mathematics and Related Areas . 3 rd Series. A Series of Modern Surveys in Mathematics ] 46 . Springer, Berlin. · Zbl 1033.82002
[28] Zakharevich, I. (2006). A generalization of Wigner’s law. Comm. Math. Phys. 268 403-414. · Zbl 1147.82334
[29] Zhan, X. (2002). Matrix Inequalities. Lecture Notes in Math. 1790 . Springer, Berlin. · Zbl 1018.15016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.