Exact sampling from non-attractive distributions using summary states

Ryan Patterson, Andrew Childs, and David MacKay

Propp and Wilson's method of coupling from the past allows one to efficiently generate exact samples from attractive statistical distributions (e.g., the ferromagnetic Ising model). This method may be generalized to non-attractive distributions by the use of summary states, as first described by Huber. Using this method, we present exact samples from a frustrated antiferromagnetic triangular Ising model and the antiferromagnetic q=3 Potts model. We discuss the advantages and limitations of the method of summary states for practical sampling, paying particular attention to the slowing down of the algorithm at low temperature. In particular, we show that such a slowing down can occur in the absence of a physical phase transition.


Additional data


Exact sample from the q=3 Potts model on a square lattice at T=1.2 with zero applied magnetic field.

David MacKay's Home Page
Last modified: Tue Jan 6 18:44:47 2004