Perfect simulation using atomic regeneration with application to Sequential Monte Carlo
arXiv:1407.5770
Abstract
Consider an irreducible, Harris recurrent Markov chain of transition kernel Π and invariant probability measure π. If Π satisfies a minorization condition, then the split chain allows the identification of regeneration times which may be exploited to obtain perfect samples from π. Unfortunately, many transition kernels associated with complex Markov chain Monte Carlo algorithms are analytically intractable, so establishing a minorization condition and simulating the split chain is challenging, if not impossible. For uniformly ergodic Markov chains with intractable transition kernels, we propose two efficient perfect simulation procedures of similar expected running time which are instances of the multigamma coupler and an imputation scheme. These algorithms overcome the intractability of the kernel by introducing an artificial atom and using a Bernoulli factory. We detail an application of these procedures when Π is the recently introduced iterated conditional Sequential Monte Carlo kernel. We additionally provide results on the general applicability of the methodology, and how Sequential Monte Carlo methods may be used to facilitate perfect simulation and/or unbiased estimation of expectations with respect to the stationary distribution of a non-uniformly ergodic Markov chain.
References in corpus (10)
- The pseudo-marginal approach for efficient Monte Carlo computations
- Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference
- Fast simulation of new coins from old
- Uniform ergodicity of the Particle Gibbs sampler
- Variance bounding and geometric ergodicity of Markov chain Monte Carlo kernels for approximate Bayesian computation
- A mixture representation of πwith applications in Markov chain Monte Carlo and perfect sampling
- Exact sampling for intractable probability distributions via a Bernoulli factory
- Nearly optimal Bernoulli factories for linear functions
- A Practical Implementation of the Bernoulli Factory
- Perfect simulation for the Feynman-Kac law on the path space