An interruptible algorithm for perfect sampling via Markov chains

Abstract

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