Explicit error bounds for lazy reversible Markov chain Monte Carlo

DOI10.1016/J.JCO.2008.05.005MaRDI QIDQ998975zbMATHOpenAlexFDO

Authors Daniel Rudolf

Publication date 30 January 2009

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

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

zbMATH Keywords

lazyMetropolis algorithmMarkov chain Monte Carlo methodconductancereversibleburn-inexplicit error boundsball walk

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: We prove explicit, i.e., non-asymptotic, error bounds for Markov Chain Monte Carlo methods, such as the Metropolis algorithm. The problem is to compute the expectation (or integral) of f with respect to a measure which can be given by a density with respect to another measure. A straight simulation of the desired distribution by a random number generator is in general not possible. Thus it is reasonable to use Markov chain sampling with a burn-in. We study such an algorithm and extend the analysis of Lovasz and Simonovits (1993) to obtain an explicit error bound.

Recommendations

• Explicit error bounds for Markov chain Monte Carlo
• Error bounds for computing the expectation by Markov chain Monte Carlo
• scientific article; zbMATH DE number 1246228
• Error bounds of MCMC for functions with unbounded stationary variance
• Computation of expectations by Markov chain Monte Carlo methods

Cites work

• scientific article; zbMATH DE number 3519673 (Why is no real title available?)
• Approximating the Permanent
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• General Irreducible Markov Chains and Non-Negative Operators
• General state space Markov chains and MCMC algorithms
• Geometric bounds for eigenvalues of Markov chains
• Markov chain decomposition for convergence rate analysis
• Markov chains and stochastic stability
• Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
• Numerical Integration using Markov Chains
• Numerical integration using V-uniformly ergodic Markov chains
• Random walks in a convex body and an improved volume algorithm
• Simple Monte Carlo and the Metropolis algorithm
• Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing

Cited in

(18)

• On a Metropolis-Hastings importance sampling estimator
• Error bounds of MCMC for functions with unbounded stationary variance
• A weighted discrepancy bound of quasi-Monte Carlo importance sampling
• Mixing and concentration by Ricci curvature
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Computation of expectations by Markov chain Monte Carlo methods
• Complexity results for MCMC derived from quantitative bounds
• Hit-and-run for numerical integration
• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
• Information geometry approach to parameter estimation in Markov chains
• The Monte Carlo computation error of transition probabilities
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Error bounds for computing the expectation by Markov chain Monte Carlo
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Explicit error bounds for Markov chain Monte Carlo
• Nonasymptotic bounds on the mean square error for MCMC estimates via renewal techniques
• Rigorous confidence bounds for MCMC under a geometric drift condition

This page was built for publication: Explicit error bounds for lazy reversible Markov chain Monte Carlo

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