Explicit error bounds for lazy reversible Markov Chain Monte Carlo

Abstract

We prove explicit, i.e., non-asymptotic, error bounds for Markov Chain Monte Carlo methods, such as the Metropolis algorithm. The problem is to compute the expectation (or integral) of f with respect to a measure which can be given by a density with respect to another measure. A straight simulation of the desired distribution by a random number generator is in general not possible. Thus it is reasonable to use Markov chain sampling with a burn-in. We study such an algorithm and extend the analysis of Lovasz and Simonovits (1993) to obtain an explicit error bound.

References in corpus (1)

• Small-world MCMC and convergence to multi-modal distributions: From slow mixing to fast mixing

Cited by in corpus (15)

• Explicit error bounds for Markov chain Monte Carlo
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Information Geometry Approach to Parameter Estimation in Markov Chains
• Positivity of hit-and-run and related algorithms
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Complexity Results for MCMC derived from Quantitative Bounds
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Hit-and-run for numerical integration
• Error bounds of MCMC for functions with unbounded stationary variance
• On a Metropolis-Hastings importance sampling estimator
• Error bounds for computing the expectation by Markov chain Monte Carlo
• Nonasymptotic bounds on the estimation error for regenerative MCMC algorithms
• Exact Sampling for the Ising Model at all Temperatures
• Small World MCMC with Tempering: Ergodicity and Spectral Gap
• A weighted Discrepancy Bound of quasi-Monte Carlo Importance Sampling