Hit-and-run for numerical integration
arXiv:1212.4486 · doi:10.1007/978-3-642-41095-6_31
Abstract
We study the numerical computation of an expectation of a bounded function with respect to a measure given by a non-normalized density on a convex body. We assume that the density is log-concave, satisfies a variability condition and is not too narrow. We consider general convex bodies or even the whole and show that the integration problem satisfies a refined form of tractability. The main tools are the hit-and-run algorithm and an error bound of a multi run Markov chain Monte Carlo method.
References in corpus (9)
- MCMC using Hamiltonian dynamics
- General state space Markov chains and MCMC algorithms
- Curvature, concentration and error estimates for Markov chain Monte Carlo
- Explicit error bounds for Markov chain Monte Carlo
- On the Computational Complexity of MCMC-based Estimators in Large Samples
- Explicit error bounds for lazy reversible Markov Chain Monte Carlo
- Swendsen-Wang is faster than single-bond dynamics
- Rigorous confidence bounds for MCMC under a geometric drift condition
- Rapid mixing of Swendsen-Wang and single-bond dynamics in two dimensions