Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains

• 成果类型: Article
• 署名作者: Jerrum, M; Son, JB; Tetali, P; Vigoda, E
• 署名单位: University of Edinburgh; University System of Georgia; Georgia Institute of Technology; University of Chicago
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051604000000639
• 发表日期: 2004
• 页码: 1741-1765
• 关键词: INEQUALITIES

摘要

We consider finite-state Markov chains that can be naturally decomposed into smaller projection and restriction chains. Possibly this decomposition will be inductive, in that the restriction chains will be smaller copies of the initial chain. We provide expressions for Poincare (resp. log-Sobolev) constants of the initial Markov chain in terms of Poincare (resp. log-Sobolev) constants of the projection and restriction chains, together with further a parameter. In the case of the Poincare constant, our bound is always at least as good as existing ones and, depending on the value of the extra parameter, may be much better. There appears to be no previously published decomposition result for the log-Sobolev constant. Our proofs are elementary and self-contained.