×

zbMATH — the first resource for mathematics

A random walk approach to linear statistics in random tournament ensembles. (English) Zbl 1398.05094
Summary: We investigate the linear statistics of random matrices with purely imaginary Bernoulli entries of the form \(H_{pq} = \overline{H}_{qp} = \pm i\), that are either independently distributed or exhibit global correlations imposed by the condition \(\sum_{q} H_{pq} = 0\). These are related to ensembles of so-called random tournaments and random regular tournaments respectively. Specifically, we construct a random walk within the space of matrices and show that the induced motion of the first \(k\) traces in a Chebyshev basis converges to a suitable Ornstein-Uhlenbeck process. Coupling this with Stein’s method allows us to compute the rate of convergence to a Gaussian distribution in the limit of large matrix dimension.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C80 Random graphs (graph-theoretic aspects)
05C81 Random walks on graphs
15B52 Random matrices (algebraic aspects)
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni, An introduction to random matrices, Cambridge Studies in Advanced Mathematics, vol. 118, Cambridge University Press, Cambridge, 2010. · Zbl 1184.15023
[2] Greg W. Anderson and Ofer Zeitouni, A CLT for a band matrix model, Probab. Theory Related Fields 134 (2006), no. 2, 283–338.
[3] Z. D. Bai and J. Yao, On the convergence of the spectral empirical process of Wigner matrices, Bernoulli 11 (2005), no. 6, 1059–1092. · Zbl 1101.60012
[4] Andrew D. Barbour, Stein’s method for diffusion approximations, Probab. Theory Related Fields 84 (1990), no. 3, 297–322. · Zbl 0665.60008
[5] Roland Bauerschmidt, Jiaoyang Huang, Antti Knowles, and Horng-Tzer Yau, Bulk eigenvalue statistics for random regular graphs, Ann. Probab. 45 (2017), no. 6A, 3626–3663. · Zbl 1379.05098
[6] Roland Bauerschmidt, Jiaoyang Huang, and Horng-Tzer Yau, Local Kesten-McKay law for random regular graphs, Preprint (2017), https://arxiv.org/abs/1609.09052. · Zbl 1379.05098
[7] Roland Bauerschmidt, Antti Knowles, and Horng-Tzer Yau, Local semicircle law for random regular graphs, Comm. Pure Appl. Math. 70 (2017), no. 10, 1898–1960. · Zbl 1372.05194
[8] Thierry Cabanal-Duvillard, Fluctuations de la loi empirique de grandes matrices aléatoires, Ann. Inst. H. Poincaré Probab. Statist. 37 (2001), no. 3, 373–402. · Zbl 1016.15020
[9] Sourav Chatterjee, Fluctuations of eigenvalues and second order Poincaré inequalities, Probab. Theory Related Fields 143 (2009), no. 1-2, 1–40. · Zbl 1152.60024
[10] Sourav Chatterjee and Elizabeth Meckes, Multivariate normal approximation using exchangeable pairs, ALEA Lat. Am. J. Probab. Math. Stat. 4 (2008), 257–283. · Zbl 1162.60310
[11] Sandrine Dallaporta and Van Vu, A note on the central limit theorem for the eigen-value counting function of Wigner matrices, Electron. Commun. Probab. 16 (2011), 314–322. · Zbl 1226.60009
[12] Christian Döbler, New developments in steins method with applications, Ph.D. thesis, Fakultät für Mathematik der Ruhr-Universität Bochum, 7 2012, http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/DoeblerChristian/diss.pdf.
[13] Christian Döbler and Michael Stolz, Stein’s method and the multivariate CLT for traces of powers on the classical compact groups, Electron. J. Probab. 16 (2011), no. 86, 2375–2405. · Zbl 1243.15023
[14] Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette, Functional limit theorems for random regular graphs, Probab. Theory Related Fields 156 (2013), no. 3-4, 921–975. · Zbl 1271.05088
[15] Freeman J. Dyson, A Brownian-motion model for the eigenvalues of a random matrix, J. Mathematical Phys. 3 (1962), 1191–1198. · Zbl 0111.32703
[16] László Erdős and Horng-Tzer Yau, A dynamical approach to random matrix theory, Courant Lecture Notes in Mathematics, vol. 28, Courant Institute of Mathematical Sciences, New York; American Mathematical Society, Providence, RI, 2017. · Zbl 1379.15003
[17] Ohad N. Feldheim and Sasha Sodin, A universality result for the smallest eigenvalues of certain sample covariance matrices, Geom. Funct. Anal. 20 (2010), no. 1, 88–123. · Zbl 1198.60011
[18] P. J. Forrester, Log-gases and random matrices, London Mathematical Society Monographs Series, vol. 34, Princeton University Press, Princeton, NJ, 2010. · Zbl 1217.82003
[19] Zhicheng Gao, Brendan D. McKay, and Xiaoji Wang, Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph, Random Structures Algorithms 16 (2000), no. 1, 47–57. · Zbl 0972.05002
[20] S. V. Gervacio, Score sequences: lexicographic enumeration and tournament construction, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), vol. 72, 1988, pp. 151–155. · Zbl 0665.05019
[21] Friedrich Götze, On the rate of convergence in the multivariate CLT, Ann. Probab. 19 (1991), no. 2, 724–739. · Zbl 0729.62051
[22] Alice Guionnet, Large deviations upper bounds and central limit theorems for non-commutative functionals of Gaussian large random matrices, Ann. Inst. H. Poincaré Probab. Statist. 38 (2002), no. 3, 341–384. · Zbl 0995.60028
[23] Kurt Johansson, On fluctuations of eigenvalues of random Hermitian matrices, Duke Math. J. 91 (1998), no. 1, 151–204. · Zbl 1039.82504
[24] Tobias Johnson, Exchangeable pairs, switchings, and random regular graphs, Electron. J. Combin. 22 (2015), no. 1, Paper 1.33, 28. · Zbl 1307.05205
[25] Dag Jonsson, Some limit theorems for the eigenvalues of a sample covariance matrix, J. Multivariate Anal. 12 (1982), no. 1, 1–38. · Zbl 0491.62021
[26] Christopher H. Joyner and Uzy Smilansky, Spectral statistics of Bernoulli matrix ensembles—a random walk approach (I), J. Phys. A 48 (2015), no. 25, 255101, 30. · Zbl 1386.60026
[27] Christopher H. Joyner, Uzy Smilansky, and Hans A. Weidenmüller, Spectral statistics of the uni-modular ensemble, J. Phys. A 50 (2017), no. 38, 385101, 35. · Zbl 1407.60009
[28] Ravi Kannan, Prasad Tetali, and Santosh Vempala, Simple Markov-chain algorithms for generating bipartite graphs and tournaments, vol. 14, 1999, pp. 293–308. · Zbl 0933.05145
[29] Alexei M. Khorunzhy, Boris A. Khoruzhenko, and Leonid A. Pastur, Asymptotic properties of large random matrices with independent entries, J. Math. Phys. 37 (1996), no. 10, 5033–5060. · Zbl 0866.15014
[30] S. Kirkland, An upper bound on the Perron value of an almost regular tournament matrix, Linear Algebra Appl. 361 (2003), 7–22, Ninth Conference of the International Linear Algebra Society (Haifa, 2001). · Zbl 1019.15004
[31] Daniela Kühn and Deryk Osthus, A survey on Hamilton cycles in directed graphs, European J. Combin. 33 (2012), no. 5, 750–766. · Zbl 1239.05114
[32] Gaultier Lambert, Michel Ledoux, and Christian Webb, Stein’s method for normal approximation of linear statistics of beta-ensembles, Preprint (2017), https://arxiv.org/abs/1706.10251.
[33] A. Lytova and L. Pastur, Central limit theorem for linear eigenvalue statistics of random matrices with independent entries, Ann. Probab. 37 (2009), no. 5, 1778–1840. · Zbl 1180.15029
[34] Tomasz Maciążek, Christopher H. Joyner, and Uzy Smilansky, The probability distribution of spectral moments for the Gaussian \(β \)-ensembles, Acta Physica Polonica A 128 (2015), 983–989.
[35] Brendan D. McKay, The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs, Combinatorica 10 (1990), no. 4, 367–377. · Zbl 0729.05021
[36] Brendan D. McKay and Xiaoji Wang, Asymptotic enumeration of tournaments with a given score sequence, J. Combin. Theory Ser. A 73 (1996), no. 1, 77–90. · Zbl 0842.05042
[37] Elizabeth Meckes, On Stein’s method for multivariate normal approximation, High dimensional probability V: the Luminy volume, Inst. Math. Stat. (IMS) Collect., vol. 5, Inst. Math. Statist., Beachwood, OH, 2009, pp. 153–178. · Zbl 1243.60025
[38] Idan Oren, Amit Godel, and Uzy Smilansky, Trace formulae and spectral statistics for discrete Laplacians on regular graphs. I, J. Phys. A 42 (2009), no. 41, 415101, 20. · Zbl 1179.81083
[39] Gesine Reinert and Adrian Röllin, Multivariate normal approximation with Stein’s method of exchangeable pairs under a general linearity condition, Ann. Probab. 37 (2009), no. 6, 2150–2173. · Zbl 1200.62010
[40] Nathan Ross, Fundamentals of Stein’s method, Probab. Surv. 8 (2011), 210–293. · Zbl 1245.60033
[41] Jeffrey Schenker and Hermann Schulz-Baldes, Gaussian fluctuations for random matrices with correlated entries, Int. Math. Res. Not. IMRN (2007), no. 15, Art. ID rnm047, 36. · Zbl 1128.60026
[42] M. Shcherbina, Central limit theorem for linear eigenvalue statistics of the Wigner and sample covariance random matrices, Zh. Mat. Fiz. Anal. Geom. 7 (2011), no. 2, 176–192, 197, 199. · Zbl 1228.15016
[43] Ya. Sinai and A. Soshnikov, Central limit theorem for traces of large random symmetric matrices with independent matrix elements, Bol. Soc. Brasil. Mat. (N.S.) 29 (1998), no. 1, 1–24. · Zbl 0912.15027
[44] Sasha Sodin, Fluctuations of interlacing sequences, Zh. Mat. Fiz. Anal. Geom. 13 (2017), no. 4, 364–401. · Zbl 1386.60029
[45] Philippe Sosoe and Uzy Smilansky, On the spectrum of random anti-symmetric and tournament matrices, Random Matrices Theory Appl. 5 (2016), no. 3, 1650010, 33. · Zbl 1355.15028
[46] Philippe Sosoe and Percy Wong, Regularity conditions in the CLT for linear eigenvalue statistics of Wigner matrices, Adv. Math. 249 (2013), 37–87. · Zbl 1292.60008
[47] J. H. Spencer, Random regular tournaments, Period. Math. Hungar. 5 (1974), 105–120. · Zbl 0283.05010
[48] Charles Stein, A bound for the error in the normal approximation to the distribution of a sum of dependent random variables, Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability theory, Univ. California Press, Berkeley, Calif., 1972, pp. 583–602.
[49] Christian Webb, Linear statistics of the circular \(β \)-ensemble, Stein’s method, and circular Dyson Brownian motion, Electron. J. Probab. 21 (2016), Paper No. 25, 16. · Zbl 1375.15056
[50] Eugene P. Wigner, Characteristic vectors of bordered matrices with infinite dimensions, Ann. of Math. (2) 62 (1955), 548–564. · Zbl 0067.08403
[51] Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325–327. · Zbl 0085.13203
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.