Explicit error bounds for lazy reversible Markov chain Monte Carlo |
| |
Authors: | Daniel Rudolf |
| |
Institution: | Friedrich Schiller University Jena, Mathem. Institute, Ernst-Abbe-Platz 2, D-07743 Jena, Germany |
| |
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 L. Lovász, 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. |
| |
Keywords: | Markov chain Monte Carlo Metropolis algorithm Conductance Explicit error bounds Burn-in Ball walk Reversible Lazy |
本文献已被 ScienceDirect 等数据库收录! |
|