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 o n situations tacking the monotonicity properties that have been exploited i n previous studies. A critical aspect is the convergence time of the algori thm; this,ve study both theoretically and experimentically. Our main theore tical result in this direction says, roughly, that if interactions are suff iciently weak, then the expected running time of a carefully designed imple mentation is O(N log N)?, where N is the number of interacting components o f the system. Computer experiments are carried out for random q-colourings and for the Widom-Rowlinson lattice gas model.