For a large class of examples arising in statistical physics known
as attractive spin systems (e.g., the Ising model), one seeks to sample
from a probability distribution $\pi$ on an enormously large state space, but
elementary sampling is ruled out by the infeasibility of calculating an
appropriate normalizing constant. The same difficulty arises in computer
science problems where one seeks to sample randomly from a large finite
distributive lattice whose precise size cannot be ascertained in any reasonable
amount of time.
¶ The Markov chain Monte Carlo (MCMC) approximate sampling approach to
such a problem is to construct and run "for a long time" a Markov chain
with long-run distribution $\pi$. But determining how long is long enough to
get a good approximation can be both analytically and empirically difficult.
¶ Recently, Propp and Wilson have devised an ingenious and efficient
algorithm to use the same Markov chains to produce perfect (i.e., exact)
samples from $\pi$. However, the running time of their algorithm is an
unbounded random variable whose order of magnitude is typically unknown a
priori and which is not independent of the state sampled, so a naive user with
limited patience who aborts a long run of the algorithm will introduce bias.
¶ We present a new algorithm which (1) again uses the same Markov
chains to produce perfect samples from $\pi$, but is based on a different idea
(namely, acceptance/rejection sampling); and (2) eliminates user-impatience
bias. Like the Propp-Wilson algorithm, the new algorithm applies to a general
class of suitably monotone chains, and also (with modification) to
"anti-monotone" chains. When the chain is reversible, naive implementation
of the algorithm uses fewer transitions but more space than Propp-Wilson.
When fine-tuned and applied with the aid of a typical pseudorandom number
generator to an attractive spin system on n sites using a random site
updating Gibbs sampler whose mixing time $\tau$ is polynomial in n, the
algorithm runs in time of the same order (bound) as Propp-Wilson [expectation
$O(\tau \log n)$] and uses only logarithmically more space [expectation $O(n
\log n)$, vs.$O9n)$ for Propp-Wilson].