Explicit error bounds for Markov chain Monte Carlo
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...