Comparison of asymptotic variances of inhomogeneous Markov chains with application to Markov chain Monte Carlo methods

Abstract

In this paper, we study the asymptotic variance of sample path averages for inhomogeneous Markov chains that evolve alternatingly according to two different $\pi$-reversible Markov transition kernels $P$ and $Q$. More specifically, our main result allows us to compare directly the asymptotic variances of two inhomogeneous Markov chains associated with different kernels $P_i$ and $Q_i$, $i\in \{0,1\}$, as soon as the kernels of each pair $(P_0,P_1)$ and $(Q_0,Q_1)$ can be ordered in the sense of lag-one autocovariance. As an important application, we use this result for comparing different data-augmentation-type Metropolis-Hastings algorithms. In particular, we compare some pseudo-marginal algorithms and propose a novel exact algorithm, referred to as the random refreshment algorithm, which is more efficient, in terms of asymptotic variance, than the Grouped Independence Metropolis-Hastings algorithm and has a computational complexity that does not exceed that of the Monte Carlo Within Metropolis algorithm.

Published in at http://dx.doi.org/10.1214/14-AOS1209 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• The pseudo-marginal approach for efficient Monte Carlo computations
• Coupled MCMC with a randomized acceptance probability

Cited by in corpus (9)

• A general perspective on the Metropolis-Hastings kernel
• Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance
• Establishing some order amongst exact approximations of MCMCs
• Peskun-Tierney ordering for Markov chain and process Monte Carlo: beyond the reversible scenario
• Bayesian learning of weakly structural Markov graph laws using sequential Monte Carlo methods
• Sets of Stochastic Matrices with Converging Products: Bounds and Complexity
• Variational Formulas of Asymptotic Variance for General Discrete-time Markov Chains
• Stability of Noisy Metropolis-Hastings
• On the use of Markov chain Monte Carlo methods for the sampling of mixture models