Spectrum of large random reversible Markov chains: Heavy-tailed weights on the complete graph

Abstract

We consider the random reversible Markov kernel K obtained by assigning i.i.d. nonnegative weights to the edges of the complete graph over n vertices and normalizing by the corresponding row sum. The weights are assumed to be in the domain of attraction of an $\alpha$-stable law, $\alpha \in (0,2)$. When $1\le \alpha <2$, we show that for a suitable regularly varying sequence ${\kappa }_n$ of index $1-1/\alpha$, the limiting spectral distribution ${\mu }_{\alpha }$ of ${\kappa }_{n}K$ coincides with the one of the random symmetric matrix of the un-normalized weights (Lévy matrix with i.i.d. entries). In contrast, when $0<\alpha <1$, we show that the empirical spectral distribution of K converges without rescaling to a nontrivial law ${\tilde{\mu }}_{\alpha }$ supported on [-1,1], whose moments are the return probabilities of the random walk on the Poisson weighted infinite tree (PWIT) introduced by Aldous. The limiting spectral distributions are given by the expected value of the random spectral measure at the root of suitable self-adjoint operators defined on the PWIT. This characterization is used together with recursive relations on the tree to derive some properties of ${\mu }_{\alpha }$ and ${\tilde{\mu }}_{\alpha }$. We also study the limiting behavior of the invariant probability measure of K.

Published in at http://dx.doi.org/10.1214/10-AOP587 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Spectral measure of heavy tailed band and covariance random matrices
• Spectrum of non-Hermitian heavy tailed random matrices
• The rank of diluted random graphs
• Spectral characterization of aging: the rem-like trap model
• K-processes, scaling limit and aging for the trap model in the complete graph
• Spectrum of large random reversible Markov chains: two examples

Cited by in corpus (21)

• Around the circular law
• Circular Law Theorem for Random Markov Matrices
• Spectrum of non-Hermitian heavy tailed random matrices
• Central limit theorems for linear statistics of heavy tailed random matrices
• A large deviation principle for Wigner matrices without Gaussian tails
• The Dirichlet Markov Ensemble
• Spectrum of Markov generators on sparse random graphs
• Delocalization at small energy for heavy-tailed random matrices
• Spectral properties of the trap model on sparse networks
• Spectrum of large random reversible Markov chains: two examples
• Spectrum of large random Markov chains: heavy-tailed weights on the oriented complete graph
• Physical Limitations of Work Extraction from Temporal Correlations
• Delocalization and Limiting Spectral Distribution of Erdős-Rényi Graphs with Constant Expected Degree
• Linear processes in high-dimension: phase space and critical properties
• Circular Law for Random Block Band Matrices with Genuinely Sublinear Bandwidth
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• Singular value distribution of dense random matrices with block Markovian dependence
• Explosion and linear transit times in infinite trees
• Spectral analysis of 1D nearest-neighbor random walks and applications to subdiffusive trap and barrier models
• Random reversible Markov matrices with tunable extremal eigenvalues
• Fluctuations of linear statistics of half-heavy-tailed random matrices