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

By Charles Bordenave, Pietro Caputo, Djalil CHAFAÏ. 2009

59 citations recorded by the source corpus.

We consider the random reversible Markov kernel K obtained by assigning i.i.d. non negative 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, with alpha in (0,2). When 1<= \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 (Levy 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 non trivial law wmu_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 wmu_alpha. We also study the limiting behavior of the invariant probability measure of K.

Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/6f64cd0d7550c9340f0ad2e7ff34049824cacbd2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Around the circular law (2011, background): “It does not have a known explicit closed form but has been studied in [16, 25, 15].”
Circular law theorem for random Markov matrices (2008, unknown): “X1,1 = V −β with 2β > 1 and where V is a uniform random variable on [0, 1], see for instance [11] for the reversible case.”
Spectrum of Markov Generators on Sparse Random Graphs (2012, background): “entries and to [10] for the case of reversible Markov transition matrices.”
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain (2018, unknown): “We consider here the case of random reversible Markov chains, as studied by Bordenave et al. (2010, 2011).”
Localization and delocalization of eigenvectors for heavy-tailed random matrices (2012, background): “From (23), T (z) ∈ L β and E[|T (z)|β] ≤ cn− β α + c ( Mn n )β 2 ≤ c ( η 4 2+αn(log n)− 2+α 4 )−β 2 , where we have finally assumed that n− 2+α 4 ≤ η ≤ 1 and used (17).”