Explicit error bounds for Markov chain Monte Carlo

Details Explicit error bounds for Markov chain Monte Carlo Explicit error bounds for Markov chain Monte Carlo

2011-08-16

arxiv.org/abs/1108.3201v1

Mathematics

Probability

PhD thesis

Scientific paper

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 {\pi}. 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 the L2 -norm of f . If there exists an L2 -spectral gap, which is a weaker convergence property than uniform ergodicity, then we show an upper error bound with respect to the Lp -norm of f 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 the integration with respect to a possibly unnormalized density. More precise, we consider the integration with respect to log-concave densities and the 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.

Affiliated with

Also associated with

No associations

Rating

Explicit error bounds for Markov chain Monte Carlo does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Explicit error bounds for Markov chain Monte Carlo, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explicit error bounds for Markov chain Monte Carlo will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-195241