Extension of Fill's perfect rejection sampling algorithm to general chains
Random Structures and AlgorithmsPublished 1 January 2000Open access
James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal
Citations81
SJR quartileQ1
SJR score1.05
SNIP1.22
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work provides an extension of the perfect sampling algorithm of Fill (1998) to general chains, and describes how use of bounding processes can ease computational burden.
Abstract
By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998a) to general chains on quite general state spaces, and describe how use of bounding processes can ease computational burden. Along the way, we unearth a simple connection between the coupling from the past (CFTP) algorithm originated by Propp and Wilson (1996) and our extension of Fill's algorithm. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 290–316, 2000
Keywords
Computer ScienceMathematics
Markov Chain Monte Carlo in Practice
7,730 Citations1995Walter R. Gilks, Sylvia Richardson +1 more
Journal of the American Statistical AssociationSampling-Based Approaches to Calculating Marginal Densities
6,616 Citations1990Alan E. Gelfand, A. F. M. Smith
Stochastic substitution, the Gibbs sampler, and the sampling-importance-resampling algorithm can be viewed as three alternative sampling- (or Monte Carlo-) based approaches to the calculation of numerical estimates of marginal probability distributions.
The Annals of StatisticsMarkov Chains for Exploring Posterior Distributions
3,472 Citations1994Luke Tierney
This paper outlines some of the basic methods and strategies of Markov chain methods and discusses some related theoretical and practical issues.
Journal of the American Statistical AssociationMarkov Chain Monte Carlo Convergence Diagnostics: A Comparative Review
1,977 Citations1996Mary Kathryn Cowles, Bradley P. Carlin
Journal of the Royal Statistical Society Series B (Statistical Methodology)Bayesian Computation Via the Gibbs Sampler and Related Markov Chain Monte Carlo Methods
1,727 Citations1993A. F. M. Smith, Gareth O. Roberts
The use of the Gibbs sampler for Bayesian computation and other Markov chain Monte Carlo simulation methods are reviewed and illustrated in the context of some canonical examples.
Random Structures and AlgorithmsExact sampling with coupled Markov chains and applications to statistical mechanics
1,146 Citations1996James Propp, David Bruce Wilson
This work describes a simple variant of this method that determines on its own when to stop and that outputs samples in exact accordance with the desired distribution, and uses couplings which have also played a role in other sampling schemes.
The Annals of ProbabilityStochastic Inequalities on Partially Ordered Spaces
525 Citations1977Teturo Kamae, Ulrich Krengel +1 more
Iterated random functions
474 Citations2017Persi Diaconis, David Freedman
SIAM ReviewIterated Random Functions
472 Citations1999Persi Diaconis, David A. Freedman
Survey of iterated random functions offers a method for studying the steady state distribution of a Markov chain, and presents useful bounds on rates of convergence in a variety of examples.
Journal of the American Statistical AssociationMinorization Conditions and Convergence Rates for Markov Chain Monte Carlo
463 Citations1995Jeffrey S. Rosenthal
The Annals of Applied ProbabilityComputable Bounds for Geometric Convergence Rates of Markov Chains
299 Citations1994Sean Meyn, Richard L. Tweedie
The Annals of ProbabilityStrong Stationary Times Via a New Form of Duality
268 Citations1990Persi Diaconis, James Allen Fill
Journal of AlgorithmsHow to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
211 Citations1998James Propp, David B. Wilson
Algorithms for generating a random sample from the state space of a Markov chain in accordance with the steady-state probability law of the chain are given, improving on earlier results and exploiting the duality between the two problems.
The Annals of Applied ProbabilityAn interruptible algorithm for perfect sampling via Markov chains
176 Citations1998James Allen Fill
Scandinavian Journal of StatisticsExact Sampling from a Continuous State Space
167 Citations1998D. Murdoch, P. J. Green
The Annals of ProbabilityRandom walks and hyperplane arrangements
157 Citations1998Kenneth S. Brown, Persi Diaconis
Lecture notes in statisticsPerfect Simulation for the Area-Interaction Point Process
151 Citations1998Wilfrid S. Kendall
A coupling method is proposed which delivers exact simulation of equilibrium distributions of (finite-state-space) Markov chains of attractive area-interaction point processes in bounded windows and which provides perfect simulation of the repulsive case as well.
Communications in Statistics Stochastic ModelsPerfect simulation and backward coupling
107 Citations1998Sergey Foss, Richard L. Tweedie
It is shown that although general backward couplings can be constructed for chains with finite mean forward coupling times, and can even be thought of as extending the classical “Loynes schemes” from queueing theory, successful “vertical” CFTP algorithms such as those of Propp and Wilson can only be constructed if and only if the chain is uniformly geometric ergodic.
Random Structures and AlgorithmsHow to couple from the past using a read-once source of randomness
96 Citations2000David B. Wilson
A new method for generating perfectly random samples from the stationary distribution of a Markov chain that can be run using a read-once stream of randomness is given, related to coupling from the past (CFTP), but only runs the MarkovChain forwards in time, and never restarts it at previous times in the past.
Pattern RecognitionPerfect simulation in stochastic geometry
93 Citations1999Wilfrid S. Kendall, Elke Thönnes
This paper introduces the new idea of perfect simulation and illustrates it using two common models in stochastic geometry: the dead leaves model and a Boolean model conditioned to cover a finite set of points.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Perfect Simulation of Conditionally Specified Models
76 Citations1999Jesper Møller
Statistica NeerlandicaExact sampling from anti‐monotone systems
65 Citations1998Olle Häggström, Karin Nelander
Exact sampling and approximate counting techniques
54 Citations1998Mark Huber
This work presents two algorithms for uniformly sampling from the proper colorings of a graph using colors using the Potts model, and presents the first polynomial time exact sampling algorithm for this problem, which is the first to run in polynometric time.
Scandinavian Journal of StatisticsOn Exact Simulation of Markov Random Fields Using Coupling from the Past
44 Citations1999Olle Häggström, Karin Nelander
A general framework for exact simulation of Markov random fields using the Propp–Wilson coupling from the past approach is proposed, with emphasis is on situations lacking the monotonicity properties that have been exploited in previous studies.
Advances in Applied ProbabilityPerfect simulation of some point processes for the impatient user
43 Citations1999Elke Thönnes
An algorithm is constructed which protects against bias caused by user impatience and which delivers samples not only of the mixture model but also of the attractive area-interaction and the continuum random-cluster process.
Perfect Metropolis-Hastings simulation of locally stable point processes
29 Citations1999Wilfred S. Kendall, Jesper Möller
Journal of Computational and Graphical StatisticsAn Approach to Diagnosing Total Variation Convergence of MCMC Algorithms
27 Citations1997Stephen P. Brooks, Πέτρος Δελλαπόρτας +1 more
A convergence diagnostic procedure for MCMC that operates by estimating total variation distances for the distribution of the algorithm after certain numbers of iterations, and it is shown how lower dimensional analogues of the full-dimensional method are available at a lower computational cost.
Statistics and ComputingOn perfect simulation for some mixtures of distributions
26 Citations1999James P. Hobert, Christian P. Robert +1 more
This paper studies the implementation of the coupling from the past (CFTP) method in the set-up of two and three component mixtures with known components and unknown weights to show that monotonicity structures can be exhibited in both cases.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Extensions of Fill's Algorithm for Perfect Simulation
23 Citations1999Jesper Møller, Katja Schladitz
The Annals of Applied ProbabilityOn the Markov Chain for the Move-to-Root Rule for Binary Search Trees
18 Citations1995Robert P. Dobrow, James Allen Fill
It is shown that the MTR chain can be derived by lumping the MTF chain and given exact formulas for the transition probabilities and stationary distribution for MTR, and the eigenvalues and their multiplicities for M TR are derived.
Statistics and ComputingEfficient use of exact samples
16 Citations2000Duncan J. Murdoch, Jeffrey S. Rosenthal
This paper considers using the CFTP and related algorithms to create tours so as to combine the precision of exact sampling with the efficiency of using entire tours.
Efficient exact sampling from the Ising model using Swendsen-Wang
12 Citations1999Mark Huber
This work gives the first method for running Swendsen-Wang as a completely coupling chain, thereby giving a procedure for taking exact samples from the ferromagnetic Ising model using Swendeden-wang.
The Annals of Applied ProbabilityRates of Convergence for the Move-to-Root Markov Chain for Binary Search Trees
11 Citations1995Robert P. Dobrow, James Allen Fill
Probability in the Engineering and Informational SciencesThe Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms
10 Citations1998James Allen Fill
The elementary problem of exhaustively sampling a finite population without replacement is used as a nonreversible test case for comparing two recently proposed MCMC algorithms for perfect sampling, one based on backward coupling and the other on strong stationary duality.
arXiv (Cornell University)Stochastic monotonicity and realizable monotonicity
6 Citations2000James Allen Fill, Motoya Machida
arXiv (Cornell University)Extension of Fill's perfect rejection sampling algorithm to general chains (Extended abstract)
4 Citations2001James Allen Fill, Motoya Machida +2 more
Advances in Applied ProbabilityPerfect simulation of some point processes for the impatient user
3 Citations1999Elke Thönnes