Coupled MCMC with a randomized acceptance probability

Abstract

We consider Metropolis Hastings MCMC in cases where the log of the ratio of target distributions is replaced by an estimator. The estimator is based on m samples from an independent online Monte Carlo simulation. Under some conditions on the distribution of the estimator the process resembles Metropolis Hastings MCMC with a randomized transition kernel. When this is the case there is a correction to the estimated acceptance probability which ensures that the target distribution remains the equilibrium distribution. The simplest versions of the Penalty Method of Ceperley and Dewing (1999), the Universal Algorithm of Ball et al. (2003) and the Single Variable Exchange algorithm of Murray et al. (2006) are special cases. In many applications of interest the correction terms cannot be computed. We consider approximate versions of the algorithms. We show that on average O(m) of the samples realized by a simulation approximating a randomized chain of length n are exactly the same as those of a coupled (exact) randomized chain. Approximation biases Monte Carlo estimates with terms O(1/m) or smaller. This should be compared to the Monte Carlo error which is O(1/sqrt(n)).

20 pages, 5 graphs in 3 figures

References in corpus (5)

• The pseudo-marginal approach for efficient Monte Carlo computations
• MCMC for doubly-intractable distributions
• The Penalty Method for Random Walks with Uncertain Energies
• A Noisy Monte Carlo Algorithm
• Stochastic Annealing

Cited by in corpus (16)

• On the efficiency of pseudo-marginal random walk Metropolis algorithms
• Speeding Up MCMC by Efficient Data Subsampling
• GPS-ABC: Gaussian Process Surrogate Approximate Bayesian Computation
• Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms
• Speeding Up MCMC by Delayed Acceptance and Data Subsampling
• On nonnegative unbiased estimators
• Comparison of asymptotic variances of inhomogeneous Markov chains with application to Markov chain Monte Carlo methods
• On the utility of Metropolis-Hastings with asymmetric acceptance ratio
• Hamiltonian Monte Carlo with Energy Conserving Subsampling
• Establishing some order amongst exact approximations of MCMCs
• Scalable iterative methods for sampling from massive Gaussian random vectors
• Error bounds for some approximate posterior measures in Bayesian inference
• A Multi-armed Bandit MCMC, with applications in sampling from doubly intractable posterior
• On the Use of Penalty MCMC for Differential Privacy
• Probabilistic Programs with Stochastic Conditioning
• MEXIT: Maximal un-coupling times for stochastic processes