Perfect Simulation
Perfect simulation is an extremely neat idea - or ideas - which allows one in favourable cases to sample exactly from the equilibrium distribution of a Markov chain (instead of doing it the old-fashioned approximate way by simulating for a long time and then ... hoping). The paper which got me started on this is the famous one by Propp and Wilson on CFTP, published in 1996, which shows just how new this area is. People seem to find the following graphic simulation on Dead Leaves both (a) useful and (b) pretty. See also the new page on perfect Ising models.
References relating to 2013-2014 Integrated Masters Projects:
Notes on Perfect Simulation
Here is a chapter giving an exposition of perfect simulation with illustrations.
Introduction to CFTP using R
A chapter on this is due shortly to appear in a Springer volume. From the abstract: "The purpose of this chapter is to exemplify construction of selected Coupling-from-the-Past algorithms, using simple examples and discussing code which can be run in the statistical scripting language \emph{R}. The simple examples are: symmetric random walk with two reflecting boundaries, a very basic continuous state-space Markov chain, the Ising model with external field, and random walk with negative drift and a reflecting boundary at the origin. In parallel with this, a discussion is given of the relationship between Coupling-from-the-Past algorithms on the one hand, and uniform and geometric ergodicity on the other."
The R programs (concatenated into one long script) can be found here. Since no non-trivial program can ever be guaranteed to be bug-free, I will maintain a list of errata in the following list.
Errata
Nothing reported yet.
Other papers
A Useful Bibliography
So you want to read more? You can look at my preprints (some examples below - or browse my preprints list). For other papers, start at the following on-line bibliography: http://dimacs.rutgers.edu/~dbwilson/exact.html.
Programs for Perfect Simulation
perfect/exclude: Perfect simulation algorithm for area-interaction and excluded-object disk processes perfect.tar.gz [Gzipped tarfile of C source: 13k] (one of the first two programs doing CFTP for point processes).
mh-cftp (joint with J. Møller): Perfect Metropolis-Hastings simulation algorithm for Strauss repulsion point processes MH.tar.gz [Gzipped tarfile of NuWeB source 74k]. NOTE: this algorithm is written in C and is found in the tarfile as NuWeB source for C programs. Briggs' Nuweb program is a small, free and portable C program based on Knuth's idea of literate programming. If you aren't familiar with the idea of literate programming then now is the time you should find out!
bl (joint with Y.Cai): Perfect simulation algorithm for correlated Poisson random variables conditioned to be positive bl.tar.gz [Gzipped tarfile of NuWeB source 24k]. NOTE: this algorithm is written in C and is found in the tarfile as NuWeB source for C programs.
[abstract] of research paper describing perfect (preprint 292);
[abstract] of research paper describing more work with perfect (preprint 295);
[abstract] of short invited paper on perfect simulation (preprint 308);
[abstract] of research paper (joint with E. Thönnes) on perfect simulation for conditional Boolean models (preprint 323);
[abstract] of research paper (joint with K. Burdzy) describing describing theory related to CFTP (preprint 331);
[abstract] of research paper (joint with J. Møller) describing mh-cftp (preprint 347);
[abstract] of nuweb source (joint with J. Møller) for mh-cftp. (preprint 348).
[abstract] of research paper (joint with Y. Cai) describing bl (preprint 349);
[abstract] of nuweb source (joint with Y. Cai) for bl. (preprint 350).
Also see the paper on Exact Simulation by my colleague Elke Thönnes: [Gzipped Postscript Paper: 90k]: notable for being the first application of Fill's method to point processes.
Last update: 15 February 2001