General state space Markov chains and MCMC algorithms

Abstract

This paper surveys various results about Markov chains on general (non-countable) state spaces. It begins with an introduction to Markov chain Monte Carlo (MCMC) algorithms, which provide the motivation and context for the theory which follows. Then, sufficient conditions for geometric and uniform ergodicity are presented, along with quantitative bounds on the rate of convergence to stationarity. Many of these results are proved using direct coupling constructions based on minorisation and drift conditions. Necessary and sufficient conditions for Central Limit Theorems (CLTs) are also presented, in some cases proved via the Poisson Equation or direct regeneration constructions. Finally, optimal scaling and weak convergence results for Metropolis-Hastings algorithms are discussed. None of the results presented is new, though many of the proofs are. We also describe some Open Problems.

Published at http://dx.doi.org/10.1214/154957804100000024 in the Probability Surveys (http://www.i-journals.org/ps/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Renewal theory and computable convergence rates for geometrically ergodic Markov chains
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• Sufficient burn-in for Gibbs samplers for a hierarchical random effects model
• Improving Asymptotic Variance of MCMC Estimators: Non-reversible Chains are Better

Cited by in corpus (209)

• A Conceptual Introduction to Hamiltonian Monte Carlo
• Markov Chain Monte Carlo: Can We Trust the Third Significant Figure?
• Batch means and spectral variance estimators in Markov chain Monte Carlo
• Bayesian Analysis of Hot Jupiter Radius Anomalies: Evidence for Ohmic Dissipation?
• Calibrate, Emulate, Sample
• Accelerating diffusions
• On the Geometric Ergodicity of Hamiltonian Monte Carlo
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Calibration and Uncertainty Quantification of Convective Parameters in an Idealized GCM
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Transport map accelerated Markov chain Monte Carlo
• Accelerating Asymptotically Exact MCMC for Computationally Intensive Models via Local Approximations
• Harris recurrence of Metropolis-within-Gibbs and trans-dimensional Markov chains
• Explicit error bounds for Markov chain Monte Carlo
• A theoretical comparison of the data augmentation, marginal augmentation and PX-DA algorithms
• Non-reversible Metropolis-Hastings
• Irreversible Langevin samplers and variance reduction: a large deviation approach
• Weak convergence of Metropolis algorithms for non-i.i.d. target distributions
• On particle Gibbs sampling
• Component-Wise Markov Chain Monte Carlo: Uniform and Geometric Ergodicity under Mixing and Composition
• Improving the convergence of reversible samplers
• Parameter Estimation of Heavy-Tailed AR Model with Missing Data via Stochastic EM
• Quantitative bounds for Markov chain convergence: Wasserstein and total variation distances
• Sample Selection with Uncertainty of Losses for Learning with Noisy Labels
• Adaptive sampling of large deviations
• Adaptive Gibbs samplers and related MCMC methods
• Variance bounding and geometric ergodicity of Markov chain Monte Carlo kernels for approximate Bayesian computation
• On the stability and ergodicity of adaptive scaling Metropolis algorithms
• Variable transformation to obtain geometric ergodicity in the random-walk Metropolis algorithm
• Implicitly Adaptive Importance Sampling
• Ensemble Kalman Sampler: mean-field limit and convergence analysis
• Explicit error bounds for lazy reversible Markov Chain Monte Carlo
• Unbiased Markov chain Monte Carlo with couplings
• Bayesian neural networks via MCMC: a Python-based tutorial
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Global Sensitivity Analysis and Estimation of Model Error, Toward Uncertainty Quantification in Scramjet Computations
• Multilevel rejection sampling for approximate Bayesian computation
• Stabilizing Invertible Neural Networks Using Mixture Models
• Stochastic optimization on continuous domains with finite-time guarantees by Markov chain Monte Carlo methods
• Convergence analysis of the Gibbs sampler for Bayesian general linear mixed models with improper priors
• Stochastic Normalizing Flows for Inverse Problems: a Markov Chains Viewpoint
• Positivity of hit-and-run and related algorithms
• Limit theorems for stationary Markov processes with L2-spectral gap
• Exact sampling for intractable probability distributions via a Bernoulli factory
• A method to challenge symmetries in data with self-supervised learning
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Comparison of asymptotic variances of inhomogeneous Markov chains with application to Markov chain Monte Carlo methods
• A Kushner-Stratonovich Monte Carlo Filter Applied to Nonlinear Dynamical System Identification
• The seven sisters DANCe IV. Bayesian hierarchical model
• Efficient Learning of the Parameters of Non-Linear Models using Differentiable Resampling in Particle Filters
• A practical guide to pseudo-marginal methods for computational inference in systems biology
• Simulated Annealing: Rigorous finite-time guarantees for optimization on continuous domains
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
• Hit-and-run for numerical integration
• Bayesian computation: a perspective on the current state, and sampling backwards and forwards
• Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling
• Convergence rate and concentration inequalities for Gibbs sampling in high dimension
• Variational Inference with Hamiltonian Monte Carlo
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• On the Scalability and Message Count of Trickle-based Broadcasting Schemes
• Approximations of Geometrically Ergodic Reversible Markov Chains
• Modeling collision probability for Earth-impactor 2008 TC3
• Convergence rate of Markov chain methods for genomic motif discovery
• An approximation scheme for quasi-stationary distributions of killed diffusions
• Hamiltonian Monte Carlo with Energy Conserving Subsampling
• WPPNets and WPPFlows: The Power of Wasserstein Patch Priors for Superresolution
• Relative fixed-width stopping rules for Markov chain Monte Carlo simulations
• Metropolis-Hastings reversiblizations of non-reversible Markov chains
• On automating Markov chain Monte Carlo for a class of spatial models
• Estimating Convergence of Markov chains with L-Lag Couplings
• Stability of adversarial Markov chains, with an application to adaptive MCMC algorithms
• Individual adaptation: an adaptive MCMC scheme for variable selection problems
• Markov Chain Monte Carlo confidence intervals
• Computation of expectations by Markov chain Monte Carlo methods
• Time-invariant Prefix Coding for LQG Control
• Some remarks on MCMC estimation of spectra of integral operators
• On the Markov chain central limit theorem
• Multiplicative random walk Metropolis-Hastings on the real line
• Comment: Gibbs Sampling, Exponential Families, and Orthogonal Polynomials
• Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo
• Convergence of Markov chain transition probabilities
• An asymptotic Peskun ordering and its application to lifted samplers
• Neuronized Priors for Bayesian Sparse Linear Regression
• Strong Consistency of Multivariate Spectral Variance Estimators
• Local Consistency of Markov Chain Monte Carlo Methods
• Computable Convergence Rates for Subgeometrically Ergodic Markov Chains
• Complexity Bounds for MCMC via Diffusion Limits
• Random Walk Sampling in Social Networks Involving Private Nodes
• Mixing of Metropolis-Adjusted Markov Chains via Couplings: The High Acceptance Regime
• Non-asymptotic confidence intervals for MCMC in practice
• Generalizations of Fano's Inequality for Conditional Information Measures via Majorization Theory
• MCMC-Net: Accelerating Markov Chain Monte Carlo with Neural Networks for Inverse Problems
• Path integral Monte Carlo method for the quantum anharmonic oscillator
• Nonasymptotic bounds on the estimation error for regenerative MCMC algorithms
• Neural parameter calibration and uncertainty quantification for epidemic forecasting
• Error bounds for computing the expectation by Markov chain Monte Carlo
• Hypothesis testing for Markov chain Monte Carlo
• Adaptive Gibbs samplers
• Moving Target Monte Carlo
• Estimating accuracy of the MCMC variance estimator: a central limit theorem for batch means estimators
• On the occupancy problem for a regime switching model
• Behavior near the extinction time in self-similar fragmentations II: Finite dislocation measures
• Markov Random Geometric Graph (MRGG): A Growth Model for Temporal Dynamic Networks
• Convergence of Griddy Gibbs Sampling and other perturbed Markov chains
• Control Variates for Reversible MCMC Samplers
• On the limitations of single-step drift and minorization in Markov chain convergence analysis
• Statistical models and probabilistic methods on Riemannian manifolds
• Convergence Analysis of the Data Augmentation Algorithm for Bayesian Linear Regression with Non-Gaussian Errors
• Control variates and Rao-Blackwellization for deterministic sweep Markov chains
• On Exact and $\infty$-Rényi Common Informations
• Bayesian Classification and Regression with High Dimensional Features
• Note on the computation of the Metropolis-Hastings ratio for Birth-or-Death moves in trans-dimensional MCMC algorithms for signal decomposition problems
• Limit Theorems for quadratic forms of Markov Chains
• Local degeneracy of Markov chain Monte Carlo methods
• Particle Gibbs algorithms for Markov jump processes
• Multivariate strong invariance principles in Markov chain Monte Carlo
• Asymptotics for Strassen's Optimal Transport Problem
• Sparse estimation in Ising Model via penalized Monte Carlo methods
• Random Coordinate Langevin Monte Carlo
• A Metropolized adaptive subspace algorithm for high-dimensional Bayesian variable selection
• Stability of Noisy Metropolis-Hastings
• Measuring Performance of Continuous-Time Stochastic Processes using Timed Automata
• Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
• On hitting time, mixing time and geometric interpretations of Metropolis-Hastings reversiblizations
• AdvNF: Reducing Mode Collapse in Conditional Normalising Flows using Adversarial Learning
• Adapting The Gibbs Sampler
• Exact Channel Synthesis
• A Common Derivation for Markov Chain Monte Carlo Algorithms with Tractable and Intractable Targets
• Metropolis Monte Carlo sampling: convergence, localization transition and optimality
• Metropolising forward particle filtering backward sampling and Rao-Blackwellisation of Metropolised particle smoothers
• Bayesian Probabilistic Numerical Integration with Tree-Based Models
• Spatial populations with seed-banks in random environment: III. Convergence towards mono-type equilibrium
• Universality of the Langevin diffusion as scaling limit of a family of Metropolis-Hastings processes I: fixed dimension
• Constrained Ensemble Langevin Monte Carlo
• A micro-macro Markov chain Monte Carlo method for molecular dynamics using reaction coordinate proposals I: direct reconstruction
• Parallel MCMC with Generalized Elliptical Slice Sampling
• Singular relaxation of a random walk in a box with a Metropolis Monte Carlo dynamics
• A Bayesian Nonparametric Meta-Analysis Model
• On the convergence of the Metropolis-Hastings Markov chains
• Precision annealing Monte Carlo methods for statistical data assimilation and machine learning
• Analyzing MCMC Output
• Large Deviations of Irreversible Processes
• Fixed-delay Events in Generalized Semi-Markov Processes Revisited
• Involutive MCMC: a Unifying Framework
• In Search of Lost (Mixing) Time: Adaptive Markov chain Monte Carlo schemes for Bayesian variable selection with very large p
• Sampling nodes and hyperedges via random walks on large hypergraphs
• Multilevel Delayed Acceptance MCMC with an Adaptive Error Model in PyMC3
• Rademacher complexity for Markov chains : Applications to kernel smoothing and Metropolis-Hasting
• Can the Adaptive Metropolis Algorithm Collapse Without the Covariance Lower Bound?
• CLTs and asymptotic variance of time-sampled Markov chains
• A splitting Hamiltonian Monte Carlo method for efficient sampling
• An Improved Composite Hypothesis Test for Markov Models with Applications in Network Anomaly Detection
• On Rates of Convergence for Markov Chains under Random Time State Dependent Drift Criteria
• Monte Carlo Quantum Computing
• Convergence Rates of Attractive-Repulsive MCMC Algorithms
• MCMC Confidence Intervals and Biases
• Exact Convergence Rate Analysis of the Independent Metropolis-Hastings Algorithms
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo
• The devil's staircase for chip-firing on random graphs and on graphons
• Estimating MCMC convergence rates using common random number simulation
• Optimally adaptive Bayesian spectral density estimation for stationary and nonstationary processes
• $L^q$-spectra of box-like graph-directed self-affine measures: closed forms, with rotation
• On the Riemannian barycentre of a Markov chain
• Theoretical guarantees for lifted samplers
• Algorithmic Bayesian Group Gibbs Selection
• Simple Confidence Intervals for MCMC Without CLTs
• Population-Based Reversible Jump Markov Chain Monte Carlo
• Quantum Markov chain Monte Carlo method with programmable quantum simulators
• MatBYIB: A Matlab-based code for Bayesian inference of extreme mass-ratio inspiral binary with arbitrary eccentricity
• FLARE MCMC: Fidelity-based Layer-Adaptive REcursive proposals for MCMC
• Almost sure convergence of the accelerated weight histogram algorithm
• A Short Review of Ergodicity and Convergence of Markov chain Monte Carlo Estimators
• Augmented truncation approximations to the solution of Poisson's equation for Markov chains
• Few-shot time series segmentation using prototype-defined infinite hidden Markov models
• MEXIT: Maximal un-coupling times for stochastic processes
• Optimization Based Methods for Partially Observed Chaotic Systems
• Stratified Splitting for Efficient Monte Carlo Integration
• Convergence of Contrastive Divergence with Annealed Learning Rate in Exponential Family
• Adaptive Component-wise Multiple-Try Metropolis Sampling
• Geometric ergodicity of Rao and Teh's algorithm for Markov jump processes
• Variance reduction for Markov chains with application to MCMC
• Bayesian sequential parameter estimation with a Laplace type approximation
• Fixed-width output analysis for Markov chain Monte Carlo
• Software Framework for Tribotronic Systems
• Convergence bound in total variation for an image restoration model
• The Riemannian barycentre as a proxy for global optimisation
• The Implicit Metropolis-Hastings Algorithm
• Monte Carlo methods for light propagation in biological tissues
• Compositional Inference Metaprogramming with Convergence Guarantees
• Efficiently Estimating Motif Statistics of Large Networks
• Multivariate initial sequence estimators in Markov chain Monte Carlo
• Statistical tests for MIXMAX pseudorandom number generator
• Analysis of the Polya-Gamma block Gibbs sampler for Bayesian logistic linear mixed models
• Air Markov Chain Monte Carlo
• Hitting Time and Convergence Rate Bounds for Symmetric Langevin Diffusions
• A computable bound of the essential spectral radius of finite range Metropolis--Hastings kernels
• A practical sequential stopping rule for high-dimensional MCMC and its application to spatial-temporal Bayesian models
• Bayesian complementary clustering, MCMC and Anglo-Saxon placenames
• A Bayesian Nonparametric IRT Model
• Principle of detailed balance and convergence assessment of Markov Chain Monte Carlo methods and simulated annealing
• Small World MCMC with Tempering: Ergodicity and Spectral Gap
• Derivatives of the Stochastic Growth Rate
• Robust adaptive Metropolis algorithm with coerced acceptance rate
• Improved annealing for sampling from multimodal distributions via landscape modification
• On Mixing Times of Metropolized Algorithm With Optimization Step (MAO) : A New Framework
• hIPPYlib-MUQ: A Bayesian Inference Software Framework for Integration of Data with Complex Predictive Models under Uncertainty