Simple Monte Carlo and the Metropolis algorithm

DOI10.1016/j.jco.2007.05.002zbMath1132.65004arXivmath/0611285OpenAlexW2069659232MaRDI QIDQ2465298

Peter Mathé, Erich Novak

Publication date: 9 January 2008

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

complexityMonte Carlo methodsadaptivityworst-case erroroptimal algorithmsrapidly mixing Markov chainlog-concave densityMetropolis-Hastings methodball-walk-step method

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)

Related Items

Hit-and-Run for Numerical Integration, On a Metropolis-Hastings importance sampling estimator, Rigorous confidence bounds for MCMC under a geometric drift condition, Nonasymptotic bounds on the estimation error of MCMC algorithms, Comparison of hit-and-run, slice sampler and random walk Metropolis, Explicit error bounds for lazy reversible Markov chain Monte Carlo, A weighted discrepancy bound of quasi-Monte Carlo importance sampling, Computation of Expectations by Markov Chain Monte Carlo Methods

Cites Work

• Markov chains and stochastic stability
• On adaptive Markov chain Monte Carlo algorithms
• On the ergodicity properties of some adaptive MCMC algorithms
• Ergodic theorems. With a supplement by Antoine Brunel
• Deterministic and stochastic error bounds in numerical analysis
• Sampling from log-concave distributions
• The real number model in numerical analysis
• Isoperimetric problems for convex bodies and a localization lemma
• The optimal error of Monte Carlo integration
• Examples comparing importance sampling and the Metropolis algorithm
• On the power of adaption
• Ausfüllung und Überdeckung konvexer Körper durch konvexe Körper
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Approximating the Permanent
• Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms
• Random walks in a convex body and an improved volume algorithm
• Numerical Integration using Markov Chains
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item