Perfect simulation in stochastic geometry

Simulation plays an important role in stochastic geometry and related field s, because all but the simplest random set models tend to be intractable to analysis. Many simulation algorithms deliver (approximate) samples of such random set models, for example by simulating the equilibrium distribution of a Markov chain such as a spatial birth-and-death process. The samples us ually fail to be exact because the algorithm simulates the Markov chain for a long but finite time, and thus convergence to equilibrium is only approx imate. The seminal work by Propp and Wilson made an important contribution to simulation by proposing a coupling method, coupling from the past (CFTP) , which delivers perfect, that is to say exact, simulations of Markov chain s. In this paper we introduce this new idea of perfect simulation and illus trate it using two common models in stochastic geometry: the dead leaves mo del and a Boolean model conditioned to cover a finite set of points. (C) 19 99 Pattern Recognition Society. Published by Elsevier Science Ltd. All righ ts reserved.