Mark L. Huber
Chapman and Hall/CRC
Published November 19, 2015
Reference - 228 Pages - 18 B/W Illustrations
ISBN 9781482232448 - CAT# K22899
Series: Chapman & Hall/CRC Monographs on Statistics and Applied Probability
For Instructors Request Inspection Copy
For Librarians Available on Taylor & Francis eBooks >>
SAVE ~$18.79 on each
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.
What is a perfect simulation algorithm?
The Fundamental Theorem of perfect simulation
A little bit of measure theory
A few applications
Markov chains and approximate simulation
Designing Markov chains
Uniform random variables
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
Drawbacks to CFTP
What is a bounding chain?
The hard-core gas model
Swendsen-Wang bounding chain
Linear extensions of a partial order
Using simple coupling with bounding chains
Advanced Techniques Using Coalescence
Read-once coupling from the past
Fill, Machida, Murdoch, and Rosenthal’s method
Dealing with infinite graphs
Clan of ancestors
Deciding the length of time to run
Coalescence on Continuous and Unbounded State Spaces
Metropolis–Hastings for continuous state spaces
Discrete auxiliary variables
Dominated coupling from the past
Using continuous state spaces for permutations
Spatial Point Processes
Dominated coupling from the past for point processes
Continuous-time Markov chains
The Randomness Recycler
Strong stationary stopping time
Example: RR for the Ising model
The general randomness recycler
Application: sink-free orientations of a graph
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
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
"… Today perfect simulation is a flourishing area with many quite distinct protocols and algorithms. This monograph reviews many of these. It assumes no prior knowledge (other than the very basics of probability), and is replete with illustrative examples and discussion. It has no exercises. It would be very suitable as a text with which to introduce a graduate student to perfect simulation; it would also be an ideal entrée to this research area for any mathematician, engineer or computer scientist with some basic knowledge of probability. It is very well written, and manages to be simultaneously approachable and precise."
—David J. Galvin in Mathematical Reviews, March 2017
"… The author himself was at the center of this …, being the author of a number of important articles on perfect simulation. This places him ideally to write the first book fully dedicated to the development of the field. Moreover, he is known as a speaker who has the ability to convey complex mathematical ideas in a clear manner. The writing here follows suit; I found it crisp and concise. … The book has no conventional exercises. Going through its theoretical derivations, however, can be a useful, yet nontrivial exercise. The notions are clearly defined and illustrated by examples that start simple and grow more complex as the readers’ understanding grows."
—Radu V. Craiu, University of Toronto, in Journal of the American Statistical Association, January 2017
"This book offers the first comprehensive description of many fascinating perfect simulation techniques, which mainly have emerged within the last twenty years. It is enjoyable reading."
—Jesper Møller, Professor of Statistics, Department of Mathematical Science, Aalborg University
"… a close to perfect entry to a decade of work on perfect sampling. If you have not heard of the concept before, consider yourself lucky to be offered such gentle guidance into it. If you have dabbled with perfect sampling before, reading the book will be like meeting old friends and hearing about their latest deeds: Mark Huber’s book should bring you a new perspective on the topic."
—Christian Robert, Université Paris Dauphine and University of Warwick