Comparing eigenvalue bounds for Markov chains: when does Poincaré beat Cheeger?

Citation
Fulman, Jason et L. Wilmer, Elizabeth, Comparing eigenvalue bounds for Markov chains: when does Poincaré beat Cheeger?, Annals of applied probability , 9(1), 1999, pp. 1-13
ISSN journal
10505164
Volume
9
Issue
1
Year of publication
1999
Pages
1 - 13
Database
ACNP
SICI code
Abstract
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.