How to Couple from the Past Using a Read-Once Source of Randomness

Abstract

We give a new method for generating perfectly random samples from the stationary distribution of a Markov chain. The method is related to coupling from the past (CFTP), but only runs the Markov chain forwards in time, and never restarts it at previous times in the past. The method is also related to an idea known as PASTA (Poisson arrivals see time averages) in the operations research literature. Because the new algorithm can be run using a read-once stream of randomness, we call it read-once CFTP. The memory and time requirements of read-once CFTP are on par with the requirements of the usual form of CFTP, and for a variety of applications the requirements may be noticeably less. Some perfect sampling algorithms for point processes are based on an extension of CFTP known as coupling into and from the past; for completeness, we give a read-once version of coupling into and from the past, but it remains unpractical. For these point process applications, we give an alternative coupling method with which read-once CFTP may be efficiently used.

28 pages, 2 figures

Cited by in corpus (17)

• Multiprocess parallel antithetic coupling for backward and forward Markov Chain Monte Carlo
• A mixture representation of πwith applications in Markov chain Monte Carlo and perfect sampling
• Exact sampling for intractable probability distributions via a Bernoulli factory
• Sampling from a polytope and hard-disk Monte Carlo
• Mixing and perfect sampling in one-dimensional particle systems
• Renormalization group approach to exact sampling
• Damage spreading and coupling in Markov chains
• Criticality of measures on 2-d Ising configurations: from square to hexagonal graphs
• The Randomness Recycler: A new technique for perfect sampling
• Extension of Fill's perfect rejection sampling algorithm to general chains (Extended abstract)
• Convergence and coupling for spin glasses and hard spheres
• Perfect sampling of stochastic matching models with reneging
• Exact sampling of corrugated surfaces
• Coupling results and Markovian structures for number representations of continuous random variables
• Extension of Fill's perfect rejection sampling algorithm to general chains
• Designing Perfect Simulation Algorithms using Local Correctness
• Geometric Ergodicity and Perfect Simulation