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.
Publié le : 1991-02-14
Classification:
Markov chains,
eigenvalues,
random walk,
60J10,
60C05
@article{1177005980,
author = {Diaconis, Persi and Stroock, Daniel},
title = {Geometric Bounds for Eigenvalues of Markov Chains},
journal = {Ann. Appl. Probab.},
volume = {1},
number = {4},
year = {1991},
pages = { 36-61},
language = {en},
url = {http://dml.mathdoc.fr/item/1177005980}
}
Diaconis, Persi; Stroock, Daniel. Geometric Bounds for Eigenvalues of Markov Chains. Ann. Appl. Probab., Tome 1 (1991) no. 4, pp. 36-61. http://gdmltest.u-ga.fr/item/1177005980/