Comparing eigenvalue bounds for Markov chains: When does Poincare beat Cheeger?

• 成果类型: Article
• 署名作者: Fulman, J; Wilmer, EL
• 署名单位: Harvard University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1999
• 页码: 1-13
• 关键词: finite-groups; random-walk; graphs

摘要

The Poincare 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 Poincare 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.