Explicit error bounds for lazy reversible Markov chain Monte Carlo
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) off with respect to a measure pi which can be given by a density rho 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 burnin. We study such an algorithm and extend the analysis of Lovasz and Simonovits [L Lovasz, M. Simonovits, Random walks in a convex body and an improved Volume algorithm, Random Structures Algorithms 4 (4) (1993) 359-412] to obtain an explicit error bound. (C) 2008 Elsevier Inc. All rights reserved.
explicit error bounds lazy reversible markov chain monte carlo metropolis algorithm conductance burn-in ball walk