Hit-and-run for numerical integration

DOI10.1007/978-3-642-41095-6_31MaRDI QIDQ2926241zbMATH OpenOpenAlexFDO

Authors Daniel Rudolf

Publication date 31 October 2014

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.4486

zbMATH Keywords

algorithmerror boundintegrationMarkov chain Monte Carlo method

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

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 $R^d$ 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.

Recommendations

• General hit-and-run Monte Carlo sampling for evaluating multidimensional integrals
• Hit-and-Run Algorithms for Generating Multivariate Distributions
• Hit-and-run mixes fast
• Hit-and-Run from a Corner
• Convergence properties of hit–and–run samplers

Cites work

• Comparison of Swendsen-Wang and heat-Bath dynamics
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Explicit error bounds for Markov chain Monte Carlo
• General state space Markov chains and MCMC algorithms
• Geometric ergodicity and hybrid Markov chains
• Handbook of Markov Chain Monte Carlo
• Hit-and-Run Algorithms for Generating Multivariate Distributions
• Hit-and-Run from a Corner
• scientific article; zbMATH DE number 1124118 (Why is no real title available?)
• scientific article; zbMATH DE number 2042289 (Why is no real title available?)
• scientific article; zbMATH DE number 2117879 (Why is no real title available?)
• scientific article; zbMATH DE number 840151 (Why is no real title available?)
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Nonasymptotic bounds on the mean square error for MCMC estimates via renewal techniques
• On the computational complexity of MCMC-based estimators in large samples
• On the geometric ergodicity of hybrid samplers
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Random walks in a convex body and an improved volume algorithm
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Sharp estimates for the median of the (n+1,1) distribution
• Simple Monte Carlo and the Metropolis algorithm
• The geometry of logconcave functions and sampling algorithms
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators

Cited in

(3)

• Fast multivariate log-concave density estimation
• Comparison of hit-and-run, slice sampler and random walk Metropolis
• Computation of expectations by Markov chain Monte Carlo methods

This page was built for publication: Hit-and-run for numerical integration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2926241)