## Layered Multishift Coupling

for use in Perfect Sampling Algorithms

### (with a primer on CFTP)

In this article we describe a new coupling technique which is useful
in a variety of perfect sampling algorithms. A multishift coupler
generates a random function *f()* so that for each real *x*,
*f(x)-x* is governed by the same fixed probability distribution, such
as a normal distribution. We develop the class of layered multishift
couplers, which are simple and have several useful properties. For
the standard normal distribution, for instance, the layered multishift
coupler generates an *f()* which (surprisingly) maps an interval of
length *l* to fewer than *2+l/2.35* points --- useful in
applications which perform computations on each such image point. The
layered multishift coupler improves and simplifies algorithms for
generating perfectly random samples from several distributions,
including and autogamma distribution, posterior
distributions for Bayesian inference, and the steady state
distribution for certain storage systems. We also use the layered
multishift coupler to develop a Markov-chain based perfect sampling
algorithm for the autonormal distribution.
At the request of the organizers, we begin by giving a primer on CFTP
(coupling from the past); CFTP and Fill's algorithm are the two
predominant techniques for generating perfectly random samples using
coupled Markov chains.

Code for the autonormal. Uses read-once CFTP, the layered multishift coupler for the normal, and Murdoch's method for dealing with unbounded state spaces.

Jesper Møller's code for measuring coalescence times for the autogamma.

Modified version of Møller's code which uses the layered multishift coupler for the gamma distribution.

PostScript version

In Neil Madras, editor, *Monte Carlo Methods*, volume 26 of
*Fields Institute Communications*, pages 141--176.
American Mathematical Society, 2000.
To appear.
Copyright © 2000 American Mathematical Society.