An interruptible algorithm for perfect sampling via Markov chains
James Allen Fill · 1997
For a large class of examples arising in statistical ph~ics known as attnxtiue spin @ems (e.g., the Ising model), one seeks to sample from a probability distribution T on an enormously large state space, but elementary sampling is ruled out by the infeaaibility 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 r.But determining how long is long enough to get a good approximation can be both analytically and empirically difncult.Recently, Jim Propp and David Wilson have devised an ingenious and efficient algorithm to use the same Markov chains to produce per$xt(i.e., exact) samples from T. However, the nmning time of their algorithm is an unbounded random wuiable whoee 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 n, but is baaed 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 uaw fewer transitions but more epaoe than Propp-Wilson.When finetuned and applied with the aid of a typical peeudorandom number generator to an attractive spin system on n sits "Waearch supported by NSF grants DMS-93-11367 and DMS-9626756.Mailing addIees James Allen Fti, The Johns Hop kins Univemity, Department of Mathematical Sciences, Whitahead Hall, 34th and Charles Stm%s, Baltimore, MD 2121S-26S2.Email addr~jirn6110jhu.edu.using a random site updating Gibbs sampler whose mixing time T is polynomial in n, the algorithm runs in time of the same order (bound) as Propp-WMm [expectation O(T log n)] and uaee only logarithmically more space [expectation O(n log n), VS.O(n) fir Propp-Whn].If truly random bits are used instead, then the time and space bounda for a fine-tuned implementation of the new algorithm are no worse than those for Propp-Wilson.The full paper is available on the author's web PEW% at the Um http: //WU .mts.jhu.edul-f ill/