Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing

DOI10.1214/105051606000000772zbMATH Open1139.65001arXivmath/0703021OpenAlexW3103537158MaRDI QIDQ2467120FDOQ2467120

Yongtao Guan, Stephen M. Krone

Publication date: 18 January 2008

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: We compare convergence rates of Metropolis--Hastings chains to multi-modal target distributions when the proposal distributions can be of ``local and ``small world type. In particular, we show that by adding occasional long-range jumps to a given local proposal distribution, one can turn a chain that is ``slowly mixing (in the complexity of the problem) into a chain that is ``rapidly mixing. To do this, we obtain spectral gap estimates via a new state decomposition theorem and apply an isoperimetric inequality for log-concave probability measures. We discuss potential applicability of our result to Metropolis-coupled Markov chain Monte Carlo schemes.

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

zbMATH Keywords

distributionconvergenceisoperimetric inequalityspectral gapgeometric ergodicitysmall worldCheeger's inequalitystate decompositionMarkov chain Monte Carlo (MCMC) methodsMetropolis-Hastings chainsMetropolis-coupled MCMC

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Metric theory of other algorithms and expansions; measure and Hausdorff dimension (11K55) Pseudo-random numbers; Monte Carlo methods (11K45)

Cites Work

• Optimization by Simulated Annealing
• Monte Carlo sampling methods using Markov chains and their applications
• Geometric ergodicity and hybrid Markov chains
• Annealing Markov Chain Monte Carlo with Applications to Ancestral Inference
• Collective dynamics of ‘small-world’ networks
• Convex measures on locally convex spaces
• Isoperimetric and analytic inequalities for log-concave probability measures
• Isoperimetric problems for convex bodies and a localization lemma
• Random walks in a convex body and an improved volume algorithm
• Title not available (Why is that?)
• Markov chain decomposition for convergence rate analysis
• Geometric L² and ^{L1 convergence are equivalent for reversible Markov chains}
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Henselian closures of a P\(p\)C field
• Exclusion and Inclusion Intervals for the Real Eigenvalues of Positive Matrices
• Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces

Cited In (7)

• Markov chain Monte Carlo based on deterministic transformations
• On‐line partitioning of the sample space in the regional adaptive algorithm
• Transdimensional transformation based Markov chain Monte Carlo
• Fast model-fitting of Bayesian variable selection regression using the iterative complex factorization algorithm
• The use of a single pseudo-sample in approximate Bayesian computation
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Bayesian variable selection regression for genome-wide association studies and other large-scale problems

   Recommendations

• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions 👍 👎
• Fast mixing of Metropolis-Hastings with unimodal targets 👍 👎
• Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces 👍 👎
• Spectral gaps of random walk Metropolis chains 👍 👎
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions 👍 👎

This page was built for publication: Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing

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