Geometric Bounds for Eigenvalues of Markov Chains
Open Access
- 1 February 1991
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 1 (1) , 36-61
- https://doi.org/10.1214/aoap/1177005980
Abstract
We develop bounds for the second largest eigenvalue and spectral gap of a reversible Markov chain. The bounds depend on geometric quantities such as the maximum degree, diameter and covering number of associated graphs. The bounds compare well with exact answers for a variety of simple chains and seem better than bounds derived through Cheeger-like inequalities. They offer improved rates of convergence for the random walk associated to approximate computation of the permanent.Keywords
This publication has 0 references indexed in Scilit: