Markov chain decomposition for convergence rate analysis

• 成果类型: Article
• 署名作者: Madras, N; Randall, D
• 署名单位: York University - Canada; University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2002
• 页码: 581-606
• 关键词: planar lattice structures; monte-carlo; glauber dynamics; random-walk; distributions; algorithms

摘要

In this paper we develop tools for analyzing the rate at which a reversible Markov chain converges to stationarity. Our techniques are useful when the Markov chain can be decomposed into pieces which are themselves easier to analyze. The main theorems relate the spectral gap of the original Markov chains to the spectral gaps of the pieces. In the first case the pieces are restrictions of the Markov chain to subsets of the state space; the second case treats a Metropolis-Hastings chain whose equilibrium distribution is a weighted average of equilibrium distributions of other Metropolis-Hastings chains on the same state space.