How to couple from the past using a read-once source of randomness
From MaRDI portal
Publication:4943355
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.
Recommendations
Cites work
- An interruptible algorithm for perfect sampling via Markov chains
- Characterization results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes
- Exact Sampling from a Continuous State Space
- Exact sampling from anti‐monotone systems
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Extensions of Fill's Algorithm for Perfect Simulation
- Fast convergence of the Glauber dynamics for sampling independent sets
- How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
- scientific article; zbMATH DE number 1188967 (Why is no real title available?)
- scientific article; zbMATH DE number 1261817 (Why is no real title available?)
- scientific article; zbMATH DE number 1559584 (Why is no real title available?)
- scientific article; zbMATH DE number 1775385 (Why is no real title available?)
- scientific article; zbMATH DE number 767429 (Why is no real title available?)
- scientific article; zbMATH DE number 795106 (Why is no real title available?)
- scientific article; zbMATH DE number 6472598 (Why is no real title available?)
- Iterated Random Functions
- On Arrivals That See Time Averages
- On Exact Simulation of Markov Random Fields Using Coupling from the Past
- Optimal speedup of Las Vegas algorithms
- Perfect simulation and backward coupling∗
- Perfect Simulation of Conditionally Specified Models
- Poisson Arrivals See Time Averages
- Shuffling biological sequences
- Stationarity detection in the initial transient problem
- The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
Cited in
(34)- Slice sampling. (With discussions and rejoinder)
- Computational issues for perfect simulation in spatial point patterns.
- Efficiency test of pseudorandom number generators using random walks
- A mixture representation of \(\pi\) with applications in Markov chain Monte Carlo and perfect sampling.
- Exact sampling for intractable probability distributions via a Bernoulli factory
- Parallel simulation of two-dimensional Ising models using probabilistic cellular automata
- Correlation decay for hard spheres via Markov chains
- Doeblin trees
- Criticality of measures on 2-d Ising configurations: from square to hexagonal graphs
- A kind of dual form for coupling from the past algorithm, to sample from Markov chain steady-state probability
- Multiprocess parallel antithetic coupling for backward and forward Markov chain Monte Carlo
- One-shot CFTP; application to a class of truncated Gaussian densities
- Exact Monte Carlo simulation for fork-join networks
- On the simulation of Markov chain steady-state distribution using CFTP algorithm
- Using a Markov Chain to Construct a Tractable Approximation of an Intractable Probability Distribution
- Relating Time and Customer Averages for Queues Using ‘forward’ Coupling from the Past
- Likelihood-based inference for Matérn type-III repulsive point processes
- scientific article; zbMATH DE number 1195782 (Why is no real title available?)
- scientific article; zbMATH DE number 1545677 (Why is no real title available?)
- scientific article; zbMATH DE number 1560256 (Why is no real title available?)
- Probability and algorithmics: a focus on some recent developments
- scientific article; zbMATH DE number 2163509 (Why is no real title available?)
- Monotonic multigamma coupling for perfect sampling
- Perfect simulation of processes with long memory: a ``coupling into and from the past algorithm
- Perfect simulation of steady-state Markov chain on mixed state space
- Nonasymptotic bounds on the mean square error for MCMC estimates via renewal techniques
- Perfect Simulation for Image Restoration
- Perfect Forward Simulation via Simulated Tempering
- Coupling from the past with randomized quasi-Monte Carlo
- Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
- On the sub-additivity of stochastic matching
- Coupling results and Markovian structures for number representations of continuous random variables
- Perfect sampling of stochastic matching models with reneging
- Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers
This page was built for publication: How to couple from the past using a read-once source of randomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943355)
