PERFECT SIMULATION. MONOGRAPHS ON STATISTICS & APPLIED PROBABILITY 148

• Introduction
Two examples
What is a perfect simulation algorithm?
The Fundamental Theorem of perfect simulation
A little bit of measure theory
Notation
A few applications
Markov chains and approximate simulation
Designing Markov chains
Uniform random variables
Computational complexity
• Acceptance/Rejection
The method
Dealing with densities
Union of sets
Randomized approximation for #P complete problems
Gamma Bernoulli approximation scheme
Approximate densities for perfect simulation
Simulation using Markov and Chernoff inequalities
Where AR fails
• Coupling from the Past
What is a coupling?
From the past
Monotonic CFTP
Slice samplers
Drawbacks to CFTP
• Bounding Chains
What is a bounding chain?
The hard-core gas model
Swendsen-Wang bounding chain
Linear extensions of a partial order
Self-organizing lists
Using simple coupling with bounding chains
• Advanced Techniques Using Coalescence
Read-once coupling from the past
Fill, Machida, Murdoch, and Rosenthal’s method
Variable chains
Dealing with infinite graphs
Clan of ancestors
Deciding the length of time to run
• Coalescence on Continuous and Unbounded State Spaces
Splitting chains
Multigamma coupling
Multishift coupling
Auto models
Metropolis–Hastings for continuous state spaces
Discrete auxiliary variables
Dominated coupling from the past
Using continuous state spaces for permutations
• Spatial Point Processes
Acceptance/rejection
Thinning
Jump processes
Dominated coupling from the past for point processes
Shift moves
Cluster processes
Continuous-time Markov chains
• The Randomness Recycler
Strong stationary stopping time
Example: RR for the Ising model
The general randomness recycler
Edge-based RR
Dimension building
Application: sink-free orientations of a graph
• Advanced Acceptance/Rejection
Sequential acceptance/rejection
Application: approximating permanents
Partially recursive acceptance/rejection
Rooted spanning trees by popping
• Stochastic Differential Equations
Brownian motion and the Brownian bridge
An exponential Bernoulli factory
Retrospective exact simulation
• Applications and Limitations of Perfect Simulation
Doubly intractable distributions
Approximating integrals and sums
Omnithermal approximation
Running time of TPA
The paired product estimator
Concentration of the running time
Relationship between sampling and approximation
Limits on perfect simulation
The future of perfect simulation

Exact sampling, specifically coupling from the past (CFTP), allows users to sample exactly from the stationary distribution of a Markov chain. During its nearly 20 years of existence, exact sampling has evolved into perfect simulation, which enables high-dimensional simulation from interacting distributions.
Perfect Simulation illustrates the application of perfect simulation ideas and algorithms to a wide range of problems. The book is one of the first to bring together research on simulation from statistics, physics, finance, computer science, and other areas into a unified framework. You will discover the mechanisms behind creating perfect simulation algorithms for solving an array of problems.
The author describes numerous protocol methodologies for designing algorithms for specific problems. He first examines the commonly used acceptance/rejection (AR) protocol for creating perfect simulation algorithms. He then covers other major protocols, including CFTP; the Fill, Machida, Murdoch, and Rosenthal (FMMR) method; the randomness recycler; retrospective sampling; and partially recursive AR, along with multiple variants of these protocols. The book also shows how perfect simulation methods have been successfully applied to a variety of problems, such as Markov random fields, permutations, stochastic differential equations, spatial point processes, Bayesian posteriors, combinatorial objects, and Markov processes.

Features
• Explains the building blocks of perfect simulation algorithms
• Provides detailed descriptions and examples of how sampling works
• Describes the two most important protocols for creating perfect simulation algorithms: AR and CFTP
• Presents algorithms for each application discussed
• Reviews the necessary concepts from measure theory and probability
• Covers a variety of Markov chains, including Gibbs, Metropolis–Hastings, auxiliary random variables, and the shift move

Author(s) Bio
Mark L. Huber is the Fletcher Jones Associate Professor of Mathematics and Statistics and George R. Roberts Fellow at Claremont McKenna College. Dr. Huber works in the area of computational probability, designing Monte Carlo methods for applications in statistics and computer science. His research interests include applied mathematics, calculus, computers, probability, and statistics. He earned a PhD from Cornell University.