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.
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
