Exact sampling for intractable probability distributions via a Bernoulli factory

Abstract

Many applications in the field of statistics require Markov chain Monte Carlo methods. Determining appropriate starting values and run lengths can be both analytically and empirically challenging. A desire to overcome these problems has led to the development of exact, or perfect, sampling algorithms which convert a Markov chain into an algorithm that produces i.i.d. samples from the stationary distribution. Unfortunately, very few of these algorithms have been developed for the distributions that arise in statistical applications, which typically have uncountable support. Here we study an exact sampling algorithm using a geometrically ergodic Markov chain on a general state space. Our work provides a significant reduction to the number of input draws necessary for the Bernoulli factory, which enables exact sampling via a rejection sampling approach. We illustrate the algorithm on a univariate Metropolis-Hastings sampler and a bivariate Gibbs sampler, which provide a proof of concept and insight into hyper-parameter selection. Finally, we illustrate the algorithm on a Bayesian version of the one-way random effects model with data from a styrene exposure study.

28 pages, 2 figures

References in corpus (6)

• MCMC using Hamiltonian dynamics
• Markov Chain Monte Carlo: Can We Trust the Third Significant Figure?
• Batch means and spectral variance estimators in Markov chain Monte Carlo
• Perfect Sampling Using Bounding Chains
• Fast simulation of new coins from old
• A mixture representation of πwith applications in Markov chain Monte Carlo and perfect sampling

Cited by in corpus (11)

• On nonnegative unbiased estimators
• Unbiased Markov chain Monte Carlo with couplings
• Nearly optimal Bernoulli factories for linear functions
• An Experimental Quantum Bernoulli Factory
• Polarization-encoded photonic quantum-to-quantum Bernoulli factory based on a quantum dot source
• Perfect simulation using atomic regeneration with application to Sequential Monte Carlo
• General Quantum Bernoulli Factory: Framework Analysis and Experiments
• A Practical Implementation of the Bernoulli Factory
• Analyzing MCMC Output
• Couplings of the Random-Walk Metropolis algorithm
• Complexity and multi-functional variants of the Quantum-to-Quantum Bernoulli Factories