Renewal theory and computable convergence rates for geometrically ergodic Markov chains

Abstract

We give computable bounds on the rate of convergence of the transition probabilities to the stationary distribution for a certain class of geometrically ergodic Markov chains. Our results are different from earlier estimates of Meyn and Tweedie, and from estimates using coupling, although we start from essentially the same assumptions of a drift condition toward a ``small set.'' The estimates show a noticeable improvement on existing results if the Markov chain is reversible with respect to its stationary distribution, and especially so if the chain is also positive. The method of proof uses the first-entrance-last-exit decomposition, together with new quantitative versions of a result of Kendall from discrete renewal theory.

Published at http://dx.doi.org/10.1214/105051604000000710 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Quantitative bounds on convergence of time-inhomogeneous Markov chains

Cited by in corpus (52)

• General state space Markov chains and MCMC algorithms
• On the ergodicity properties of some adaptive MCMC algorithms
• On the Geometric Ergodicity of Hamiltonian Monte Carlo
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• Explicit error bounds for Markov chain Monte Carlo
• On the ergodicity of the adaptive Metropolis algorithm on unbounded domains
• Nonparametric Bayesian posterior contraction rates for discretely observed scalar diffusions
• Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms
• Diffusion models and steady-state approximations for exponentially ergodic Markovian queues
• Variance bounding and geometric ergodicity of Markov chain Monte Carlo kernels for approximate Bayesian computation
• Markov Chain Monte Carlo Estimation of Quantiles
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Approximating Markov chains and V-geometric ergodicity via weak perturbation theory
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Complexity Results for MCMC derived from Quantitative Bounds
• Kernel estimators of asymptotic variance for adaptive Markov chain Monte Carlo
• Limit theorems for sequential MCMC methods
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• A cautionary tale on the efficiency of some adaptive Monte Carlo schemes
• Approximations of Geometrically Ergodic Reversible Markov Chains
• Convergence of hybrid slice sampling via spectral gap
• Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance
• Some remarks on MCMC estimation of spectra of integral operators
• Quasi-compactness of Markov kernels on weighted-supremum spaces and geometrical ergodicity
• Efficient implementation of Markov chain Monte Carlo when using an unbiased likelihood estimator
• Comment: Gibbs Sampling, Exponential Families, and Orthogonal Polynomials
• Comparison of hit-and-run, slice sampling and random walk Metropolis
• Exponential Concentration Inequalities for Additive Functionals of Markov Chains
• Computable Convergence Rates for Subgeometrically Ergodic Markov Chains
• T. E. Harris's contributions to recurrent Markov processes and stochastic flows
• Nonasymptotic bounds on the estimation error for regenerative MCMC algorithms
• On estimation of expectation of simultaneous renewal time of time-inhomogeneous Markov chains using dominating sequence
• Dimension-free Mixing for High-dimensional Bayesian Variable Selection
• On the limitations of single-step drift and minorization in Markov chain convergence analysis
• Optimal Scaling of Random-Walk Metropolis Algorithms on General Target Distributions
• Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo
• Gibbs Sampling, Exponential Families and Orthogonal Polynomials
• Statistical estimation of jump rates for a specific class of Piecewise Deterministic Markov Processes
• On the Stationary Distribution of Iterative Imputations
• CLTs and asymptotic variance of time-sampled Markov chains
• Perturbation theory and uniform ergodicity for discrete-time Markov chains
• Return Probabilities for the Reflected Random Walk on ${\mathbb{N}}_0$
• Exponential Convergence Rates for Stochastically Ordered Markov Processes with Random Initial Conditions
• A Fluid Limit for an Overloaded X Model Via a Stochastic Averaging Principle
• Computable bounds of ${\ell }^2$-spectral gap for discrete Markov chains with band transition matrices
• A convergent numerical algorithm for the stochastic growth-fragmentation problem
• Orthogonality and probability: mixing times
• A tail inequality for suprema of unbounded empirical processes with applications to Markov chains
• A computable bound of the essential spectral radius of finite range Metropolis--Hastings kernels
• Optimal scaling for the pseudo-marginal random walk Metropolis: insensitivity to the noise generating mechanism
• Hitting Time and Convergence Rate Bounds for Symmetric Langevin Diffusions
• The Kendall's Theorem and its Application to the Geometric Ergodicity of Markov Chains