Explicit error bounds for Markov chain Monte Carlo

Daniel Rudolf. Explicit error bounds for Markov chain Monte Carlo. 2012. <http://eudml.org/doc/286007>.

@book{DanielRudolf2012,
abstract = {We prove explicit, i.e. non-asymptotic, error bounds for Markov chain Monte Carlo methods. The problem is to compute the expectation of a function f with respect to a measure π. Different convergence properties of Markov chains imply different error bounds. For uniformly ergodic and reversible Markov chains we prove a lower and an upper error bound with respect to ||f||₂. If there exists an L₂-spectral gap, which is a weaker convergence property than uniform ergodicity, then we show an upper error bound with respect to $||f||_\{p\}$ for p > 2. Usually a burn-in period is an efficient way to tune the algorithm. We provide and justify a recipe how to choose the burn-in period. The error bounds are applied to the problem of integration with respect to a possibly unnormalized density. More precise, we consider integration with respect to log-concave densities and integration over convex bodies. By the use of the Metropolis algorithm based on a ball walk and the hit-and-run algorithm it is shown that both problems are polynomial tractable.},
author = {Daniel Rudolf},
keywords = {Markov chain Monte Carlo; spectral gap; uniform ergodicity; geometric ergodicity; burn-in; error bounds; metropolis algorithm; ball walk; mean square error; log-concave density; hit-and-run algorithm},
language = {eng},
title = {Explicit error bounds for Markov chain Monte Carlo},
url = {http://eudml.org/doc/286007},
year = {2012},
}

TY - BOOK
AU - Daniel Rudolf
TI - Explicit error bounds for Markov chain Monte Carlo
PY - 2012
AB - We prove explicit, i.e. non-asymptotic, error bounds for Markov chain Monte Carlo methods. The problem is to compute the expectation of a function f with respect to a measure π. Different convergence properties of Markov chains imply different error bounds. For uniformly ergodic and reversible Markov chains we prove a lower and an upper error bound with respect to ||f||₂. If there exists an L₂-spectral gap, which is a weaker convergence property than uniform ergodicity, then we show an upper error bound with respect to $||f||_{p}$ for p > 2. Usually a burn-in period is an efficient way to tune the algorithm. We provide and justify a recipe how to choose the burn-in period. The error bounds are applied to the problem of integration with respect to a possibly unnormalized density. More precise, we consider integration with respect to log-concave densities and integration over convex bodies. By the use of the Metropolis algorithm based on a ball walk and the hit-and-run algorithm it is shown that both problems are polynomial tractable.
LA - eng
KW - Markov chain Monte Carlo; spectral gap; uniform ergodicity; geometric ergodicity; burn-in; error bounds; metropolis algorithm; ball walk; mean square error; log-concave density; hit-and-run algorithm
UR - http://eudml.org/doc/286007
ER -