How to Couple from the Past
Using a Read-Once Source of Randomness
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.
Random Structures and Algorithms volume 16 number 1, pp. 85--113, 2000. Copyright © 1996 by John Wiley & Sons.
Code for the Strauss process pictures in the article.
DVI version
PostScript version