The technique of Markov chain Monte Carlo lies at the crossroads between several domains of mathematical science: statistical physics, where one can define random fields as equilibrium distributions of random processes; computer science, where methods for approximate counting make use of the convergence to equilibrium of random walks; statistics, where one investigates posterior distributions using Gibbs' or Metropolis-Hastings samplers; and stochastic geometry, where one borrows from statistical physics to define processes of interacting objects as equilibrium distributions of Markov chains.
The seminal works of Propp and Wilson [4] and of Fill [1] show how in favourable circumstances one can modify the Markov chain Monte Carlo simulation algorithm to draw not just approximately but actually exactly from the equilibrium distribution of a Markov chain. This is the technique of exact or perfect simulation. The articles [2,3] mark the start of a vigorously developing programme seeking to extend this idea to many areas of stochastic geometry, applied probability and Bayesian statistics. In this talk I will survey the rapid development of the subject over the last three years, describe some illuminating simple examples, and discuss recent work.
For various preprints of mine, and an animation, see the relevant research reports in http://www.warwick.ac.uk/statsdept/Staff/WSK/abstracts.html.
A useful bibliography is to be found in http://dimacs.rutgers.edu/~dbwilson/exact.html.
[1] J.A. Fill "An Interruptible Algorithm for Perfect Sampling via Markov Chains", The Annals of Applied Probability (1998) 8, 131-162.
[2] O. Haggstrom, M.N.M. van Lieshout, and J. Moeller, "Characterisation results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes", Aalborg Mathematics Department Research Report R-96-2040: To appear in Bernoulli (1998).
[3] W.S. Kendall, "Perfect simulation for the area-interaction point process", in "Probability Towards 2000", edited by L. Accardi and C.C. Heyde, Springer New York (1998) 218-234.
[4] J.G. Propp and D.B. Wilson, "Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics", Random Structures and Algorithms, (1996) 9, 1&2, 223-252.
This was last updated on 22 February 1999.