Markov chain decomposition for convergence rate analysis
Authors:
- Neal MadrasNMNeal Madras
- Dana RandallDRDana Randall
Open Access
- 1 May 2002
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 12 (2) , 581-606
Abstract
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.Keywords
This publication has 24 references indexed in Scilit:
- Geometric L2 and L1 convergence are equivalent for reversible Markov chainsJournal of Applied Probability, 2001
- Mixing properties of the Swendsen–Wang process on the complete graph and narrow gridsJournal of Mathematical Physics, 2000
- Importance sampling for families of distributionsThe Annals of Applied Probability, 1999
- A note on Metropolis-Hastings kernels for general state spacesThe Annals of Applied Probability, 1998
- Annealing Markov Chain Monte Carlo with Applications to Ancestral InferenceJournal of the American Statistical Association, 1995
- Comparison Techniques for Random Walk on Finite GroupsThe Annals of Probability, 1993
- Comparison Theorems for Reversible Markov ChainsThe Annals of Applied Probability, 1993
- Simulated Tempering: A New Monte Carlo SchemeEurophysics Letters, 1992
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Exponential convergence to equilibrium for a class of random-walk modelsJournal of Statistical Physics, 1989