The Poincaré and Cheeger bounds are two useful bounds for the second
largest eigenvalue of a reversible Markov chain. Diaconis and Stroock and
Jerrum and Sinclair develop versions of these bounds which involve choosing
paths. This paper studies these path-related bounds and shows that the
Poincaré bound is superior to the Cheeger bound for simple random walk on a
tree and random walk on a finite group with any symmetric generating set. This
partially resolves a question posed by Diaconis and Stroock.
Publié le : 1999-02-14
Classification:
Markov chains,
eigenvalues,
random walk,
Poincaré inequalities,
Cheeger inequalitites,
trees,
groups,
60J10,
60C05
@article{1029962594,
author = {Fulman, Jason and Wilmer, Elizabeth L.},
title = {Comparing eigenvalue bounds for Markov chains: when does Poincar\'e
beat Cheeger?},
journal = {Ann. Appl. Probab.},
volume = {9},
number = {1},
year = {1999},
pages = { 1-13},
language = {en},
url = {http://dml.mathdoc.fr/item/1029962594}
}
Fulman, Jason; Wilmer, Elizabeth L. Comparing eigenvalue bounds for Markov chains: when does Poincaré
beat Cheeger?. Ann. Appl. Probab., Tome 9 (1999) no. 1, pp. 1-13. http://gdmltest.u-ga.fr/item/1029962594/