Markov chain decomposition for convergence rate analysis

DOI10.1214/aoap/1026915617zbMath1017.60080OpenAlexW2161269121MaRDI QIDQ1872401

Neal Madras, Dana Randall

Publication date: 6 May 2003

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

Full work available at URL: https://doi.org/10.1214/aoap/1026915617

zbMATH Keywords

decompositionMonte CarloMarkov chainspectral gapMetropolis-Hastings algorithmsimulated tempering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete-time Markov processes on general state spaces (60J05) Numerical analysis or methods applied to Markov chains (65C40)

Related Items

Universality of cutoff for graphs with an added random matching ⋮ Spectral gap for open Jackson networks ⋮ Markov Kernels Local Aggregation for Noise Vanishing Distribution Sampling ⋮ Simulated tempering and swapping on mean-field models ⋮ Spectral gap of replica exchange Langevin diffusion on mixture distributions ⋮ Some drawbacks of finite modified logarithmic Sobolev inequalities ⋮ Elementary bounds on mixing times for decomposable Markov chains ⋮ Optimal Variance Reduction for Markov Chain Monte Carlo ⋮ Finite sample complexity of sequential Monte Carlo estimators on multimodal target distributions ⋮ Rapid Mixing of \({\boldsymbol{k}}\)-Class Biased Permutations ⋮ Convergence rate of Markov chain methods for genomic motif discovery ⋮ Unnamed Item ⋮ A bound for the convergence rate of parallel tempering for sampling restricted Boltzmann machines ⋮ Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing ⋮ New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling ⋮ Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions ⋮ Partial differential equations and stochastic methods in molecular dynamics ⋮ Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains ⋮ On fine properties of mixtures with respect to concentration of measure and Sobolev type inequalities ⋮ Eigenvalue bounds on restrictions of reversible nearly uncoupled Markov chains ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ Explicit error bounds for lazy reversible Markov chain Monte Carlo ⋮ Error bounds for computing the expectation by Markov chain Monte Carlo ⋮ Simple conditions for metastability of continuous Markov chains ⋮ Generalized parallel tempering on Bayesian inverse problems ⋮ Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions ⋮ Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces ⋮ Mixing and hitting times for Gibbs samplers and other non-Feller processes ⋮ Importance sampling for families of distributions ⋮ A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities ⋮ A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix ⋮ Mixing times for a constrained Ising process on the two-dimensional torus at low density ⋮ On swapping and simulated tempering algorithms.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric bounds for eigenvalues of Markov chains
• Exponential convergence to equilibrium for a class of random-walk models
• A note on Metropolis-Hastings kernels for general state spaces
• Comparison theorems for reversible Markov chains
• Comparison techniques for random walk on finite groups
• Geometric ergodicity and hybrid Markov chains
• Importance sampling for families of distributions
• Mixing properties of the Swendsen–Wang process on the complete graph and narrow grids
• Markov Chain Algorithms for Planar Lattice Structures
• Geometric L² and ^{L1 convergence are equivalent for reversible Markov chains}
• Approximating the Permanent
• Fast convergence of the Glauber dynamics for sampling independent sets
• Annealing Markov Chain Monte Carlo with Applications to Ancestral Inference