Premium
On Exact Simulation of Markov Random Fields Using Coupling from the Past
Author(s) -
Haggstrom Olle,
Nelander Karin
Publication year - 1999
Publication title -
scandinavian journal of statistics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.359
H-Index - 65
eISSN - 1467-9469
pISSN - 0303-6898
DOI - 10.1111/1467-9469.00156
Subject(s) - mathematics , markov chain , monotonic function , random field , statistical physics , convergence (economics) , coupling (piping) , lattice (music) , markov process , markov model , discrete mathematics , algorithm , statistics , mathematical analysis , physics , mechanical engineering , acoustics , engineering , economics , economic growth
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.