Preface
Suppose a new deck of cards is shuffled. Then as the number of shuffles grows,
the distribution of the deck becomes closer an d closer to uniform over th e set of
permutations of the cards. On the other hand, no matter how long you shufflethe
deck, it will never be perfectly uniform over the set of permutations.
This technique—of making small changes to a state in order to move it closer to
some target distribution—is known today as Markov chain Monte Carlo, or MCMC.
Each step brings the chain closer to its target, but it never quite reaches it. With roots
in The Manhattan Project, by the early 1990s this idea had become a cornerstone of
simulation. For statistical physicists it was the only way to get approximately correct
samples in a reasonable amount of time, especially for high d imensional examples
such as the Ising model. For frequentist statisticians, it was the only way to calculate
p-values for complex statistical models. For Bayesian statisticians, it allowed the use
of a d izzying array of non-conjugate priors and models.
For almost half a century MCMC had been used, and still only a finite number
of steps could be taken. No one realized that it might be possible to somehow jump
to an infinite number of steps in a finite number o f time. That changed when James
Propp and David Wilson introduced coupling from the past (CFTP) in 1996. Their
elegant idea allowed users for the first time to sample exactly from the station ary
distribution o f a Markov chain. That paper, “Exact sampling with coupled Markov
chains and applications to statistical mechanics,” gave the first exact sample from the
Ising model at the cr itical temperature on an over 16 million dimensional problem.
The list of applications started to grow. Spatial statistics models, domino tilings,
linear extensions, random spanning trees...the first few years after publication saw
enormous growth in the field. Along the way exact sampling changed to perfect simu-
lation. The term was introduced by Wilfred Kendall in 1998, and immediately caught
on as a way to differentiate the CFTP protocol from o ther Monte Carlo algorithms
that returned samples exactly from the distribution, but without using the peculiar
ideas central to CFTP.
David Wilson created a website entitled, “Perfectly Random Sampling with
Markov Chains” at http://d imacs.rutgers.edu/ dbwilson/exact/ to infor m the nascent
community about developments. As of July 2015 the site still exists; a snapshot of
the early days of the field.
As time went on, variants of the CFTP method were developed. Read-once cou-
pling from the past allowed samples to be taken using less memory, Fill’s method
and FMMR connected CFTP to the much older (and less widely applicable) method
of acceptance/rejection.
xxi
xxii PREFACE
Then around 2000 something interesting happened. Protocols that were very dif-
ferent from CFTP, such as the Randomness Recycler, were developed. CFTP was
now not the only way to draw from the stationary distribution of a Markov chain!
New life was breathed into acceptance/rejection through the use of retrospective
sampling and sequential acceptance/rejection, allowing for the first time perfect
simulation from some diffusions and perfect matchings. Partially recursive accep-
tance/rejection even allowed for simu lation from the classic problem of the Ising
model.
CFTP was no longer unique, but fit within a larger framework of perfect simula-
tion ideas. The connections between CFTP and acceptance/rejection became clearer,
as each employs a recursive structure that could conceivably go on forever, but with
prob ability 1 does not.
Today the set of perfect simulation algorithms continues to grow, albeit more
slowly than in the early days. In researching and writing this text, I was astounded
at the wide range of problems to which perfect simulation ideas had been applied.
Coupling from the past was not just a protocol; it was the first to show that high
dimensional simulation from interacting distributions was even possible, opening up
areas of simulation that have yet to be fully explored.
Acknowledgments: My study of perfect simulation began with a special topics
course taught by Persi Diaconis when I was a graduate student at Cornell. Persi later
became my postdoc advisor as well, and his unflagging enthusiasm for new ideas
was an inspiration to me.
I would also like to thank my Ph.D. advisor David Shmoys who took a chance in
letting me change research directions in the middle of my graduate work to dive into
this newly forming field.
Jim Fill introduced me to several intriguing problems in the area, and later be-
came my first p erfect simulation collaborator. Together we added the Randomness
Recycler to the world of perfect simu lation.
Thanks also to my many colleagues and collaborators who brought me up to
speed on Bayesian statistics and patiently sat through the many talks I gave on per-
fect simulation while I was in the midst of figuring problems out. A great academic
environment stimulates the mind in unexpected ways, and I have been privileged to
belong to several.
Mark L. Huber
23 July, 2015
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.