On Exact Simulation of Markov Random Fields Using Coupling from the Past

A general framework for exact simulation of Markov random fields using the Propp–Wilson coupling from the past approach is proposed. Our emphasis is on situations lacking the monotonicity properties that have been exploited in previous studies. A critical aspect is the convergence time of the algorithm; this we study both theoretically and experimentically. Our main theoretical result in this direction says, roughly, that if interactions are sufficiently weak, then the expected running time of a carefully designed implementation is O ( N log N ), where N is the number of interacting components of the system. Computer experiments are carried out for random q -colourings and for the Widom–Rowlinson lattice gas model.