Explicit error bounds for lazy reversible Markov chain Monte Carlo
From MaRDI portal
Publication:998975
DOI10.1016/J.JCO.2008.05.005zbMATH Open1160.65004arXiv0805.3587OpenAlexW2118757220MaRDI QIDQ998975FDOQ998975
Publication date: 30 January 2009
Published in: Journal of Complexity (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0805.3587
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
lazyMetropolis algorithmMarkov chain Monte Carlo methodconductancereversibleburn-inexplicit error boundsball walk
Cites Work
- Markov chains and stochastic stability
- General state space Markov chains and MCMC algorithms
- Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing
- General Irreducible Markov Chains and Non-Negative Operators
- Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
- Random walks in a convex body and an improved volume algorithm
- Geometric bounds for eigenvalues of Markov chains
- Markov chain decomposition for convergence rate analysis
- Approximating the Permanent
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Title not available (Why is that?)
- Simple Monte Carlo and the Metropolis algorithm
- Numerical integration using V-uniformly ergodic Markov chains
- Numerical Integration using Markov Chains
Cited In (15)
- A weighted discrepancy bound of quasi-Monte Carlo importance sampling
- On a Metropolis-Hastings importance sampling estimator
- Error bounds of MCMC for functions with unbounded stationary variance
- Hit-and-Run for Numerical Integration
- Information geometry approach to parameter estimation in Markov chains
- Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
- Curvature, concentration and error estimates for Markov chain Monte Carlo
- Mixing and concentration by Ricci curvature
- Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
- Complexity results for MCMC derived from quantitative bounds
- Rapid mixing of Swendsen–Wang dynamics in two dimensions
- Nonasymptotic bounds on the estimation error of MCMC algorithms
- Nonasymptotic Bounds on the Mean Square Error for MCMC Estimates via Renewal Techniques
- Rigorous confidence bounds for MCMC under a geometric drift condition
- Error bounds for computing the expectation by Markov chain Monte Carlo
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)
