A guide to exact simulation

Markov Chain Monte Carlo (MCMC) methods are used to sample from complicated multivariate distributions with normalizing constants that may not be comp utable in practice and from which direct sampling is not feasible. A fundam ental problem is to determine convergence of the chains. Propp & Wilson (19 96) devised a Markov chain algorithm called Coupling From The Past (CFTP) t hat solves this problem, as it produces exact samples from the target distr ibution and determines automatically how long it needs to run. Exact sampli ng by CFTP and other methods is currently a thriving research topic, This p aper gives a review of some of these ideas,with emphasis on the CFTP algori thm. The concepts of coupling and monotone CFTP are introduced, and results on the running time of the algorithm presented. The interruptible method o f Fill (1998) and the method of Murdoch & Green (1998) for exact sampling f or continuous distributions are presented. Novel simulation experiments are reported for exact sampling from the Ising model in the setting of Bayesia n image restoration, and the results are compared to standard MCMC, The res ults show that CFTP works at least as well as standard MCMC, with convergen ce monitored by the method of Raftery & Lewis (1992, 1996).