Random reversible Markov matrices with tunable extremal eigenvalues

DOI10.1214/15-AAP1146MaRDI QIDQ341612zbMATH OpenOpenAlexFDO

Authors Zhiyi Chi

Publication date 16 November 2016

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

Full work available at URL https://arxiv.org/abs/1505.02086, https://projecteuclid.org/euclid.aoap/1472745458

zbMATH Keywords

Markov matrixrandom graphrandom matrixreversible

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: Random sampling of large Markov matrices with a tunable spectral gap, a nonuniform stationary distribution, and a nondegenerate limiting empirical spectral distribution (ESD) is useful. Fix $c>0$ and $p>0$. Let $A_n$ be the adjacency matrix of a random graph following $mathrmG(n,p/n)$, known as the ErdH{o}s-R'enyi distribution. Add $c/n$ to each entry of $A_n$ and then normalize its rows. It is shown that the resulting Markov matrix has the desired properties. Its ESD weakly converges in probability to a symmetric nondegenerate distribution, and its extremal eigenvalues, other than 1, fall in $[-1/sqrt1+c/k,-b]cup[b,1/sqrt1+c/k]$ for any $0<b<1/sqrt1+c$, where $k=lfloorpfloor+1$. Thus, for $pin(0,1)$, the spectral gap tends to $1-1/sqrt1+c$.

Recommendations

• The smallest eigenvalue for reversible Markov chains
• Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains
• Interlacing eigenvalues in time reversible Markov chains
• Optimal spectral structure of reversible stochastic matrices, Monte Carlo methods and the simulation of Markov random fields
• On the Eigenvalues of Random Matrices
• Spectral theory for weakly reversible Markov chains
• Eigenvalues and Condition Numbers of Random Matrices
• Spectrum of large random reversible Markov chains: two examples

Cited in

(11)

• Optimal spectral structure of reversible stochastic matrices, Monte Carlo methods and the simulation of Markov random fields
• Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains
• The smallest eigenvalue for reversible Markov chains
• Spectral norm bounds for block Markov chain random matrices
• Singular value distribution of dense random matrices with block Markovian dependence
• Interlacing eigenvalues in time reversible Markov chains
• Time-inhomogeneous random Markov chains
• Spectral properties for the Laplacian of a generalized Wigner matrix
• Statistics of the non-zero eigenvalues and singular values of low-rank random matrices with non-negative entries
• Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
• The Dirichlet Markov ensemble

This page was built for publication: Random reversible Markov matrices with tunable extremal eigenvalues

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