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

DOI10.1214/10-AOP587zbMATH Open1245.60008arXiv0903.3528MaRDI QIDQ717890FDOQ717890

Djalil Chafaï, Pietro Caputo, Charles Bordenave

Publication date: 10 October 2011

Published in: The Annals of Probability (Search for Journal in Brave)

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, $alphain(0,2)$. When $1leqalpha<2$, we show that for a suitable regularly varying sequence $kapp{a}_n$ of index $1-1/alpha$, the limiting spectral distribution $m{u}_{alpha}$ of $kapp{a}_{n}K$ coincides with the one of the random symmetric matrix of the un-normalized weights (L'{e}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 $widetilde{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 $m{u}_{alpha}$ and $widetilde{mu}_{alpha}$. We also study the limiting behavior of the invariant probability measure of K.

Full work available at URL: https://arxiv.org/abs/0903.3528

zbMATH Keywords

heavy-tailed distributionempirical spectral measurerandom stochastic matrix

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Spectrum, resolvent (47A10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recurrence of distributional limits of finite planar graphs
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
• Heavy-Tail Phenomena
• Size-biased sampling of Poisson point processes and excursions
• Processes on unimodular random networks
• The arcsine law as a universal aging scheme for trap models
• Random Fragmentation and Coagulation Processes
• Matrix inequalities
• Convergence to a stable distribution via order statistics
• Poisson statistics for the largest eigenvalues of Wigner random matrices with heavy tails
• Spectrum of non-Hermitian heavy tailed random matrices
• Poisson convergence for the largest eigenvalues of heavy tailed random matrices
• The spectrum of heavy tailed random matrices
• Spectral measure of heavy tailed band and covariance random matrices
• The rank of diluted random graphs
• A generalization of Wigner's law
• Spectrum of large random reversible Markov chains: two examples
• Extended states in the Anderson model on the Bethe lattice
• Asymptotics in the random assignment problem
• K-processes, scaling limit and aging for the trap model in the complete graph
• Spectral characterization of aging: the REM-like trap model

Cited In (34)

• The spectral gap of sparse random digraphs
• GOE statistics for Lévy matrices
• Resolvent of large random graphs
• Spectrum of large random reversible Markov chains: two examples
• Bernoulli random matrices
• Spectral norm bounds for block Markov chain random matrices
• Limit theory for the largest eigenvalues of sample covariance matrices with heavy-tails
• Upper escape rate of Markov chains on weighted graphs
• Eigenvector statistics of Lévy matrices
• Around the circular law
• Aspects of large random Markov kernels
• Circular law theorem for random Markov matrices
• Lévy-Khintchine random matrices and the Poisson weighted infinite skeleton tree
• Clustering in block Markov chains
• Fluctuations of linear statistics of half-heavy-tailed random matrices
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• Circular law for random block band matrices with genuinely sublinear bandwidth
• The limiting distributions of large heavy Wigner and arbitrary random matrices
• Spectrum of non-Hermitian heavy tailed random matrices
• A random walk on the Rado graph
• Spectrum of Lévy-Khintchine random Laplacian matrices
• On the speed and spectrum of mean-field random walks among random conductances
• Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree
• Singular value distribution of dense random matrices with block Markovian dependence
• Delocalization at small energy for heavy-tailed random matrices
• Central limit theorems for linear statistics of heavy tailed random matrices
• Spectrum of large random Markov chains: Heavy-tailed weights on the oriented complete graph
• Extreme eigenvalue statistics of \(m\)-dependent heavy-tailed matrices
• Spectrum of heavy-tailed elliptic random matrices
• Explosion and linear transit times in infinite trees
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• A coupling of the spectral measures at a vertex
• Spectral properties of the trap model on sparse networks
• Spectrum of Markov Generators on Sparse Random Graphs

This page was built for publication: Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q717890)