INTRODUCTION TO EXACT MARKOV CHAIN MONTE CARLO

                    Olle Häggström

             CTH och Göteborgs Universitet
  

The basic idea of the Markov chain Monte Carlo (MCMC)
method for simulation of a random object with a complicated
distribution pi (say), is to define an ergodic Markov chain
whose unique stationary distribution  is pi. Starting from
an arbitrary initial state and running the chain for long
enough produces a sample whose distribution is close to pi. 
A serious problem with this approach is that useful bounds on
how long  ``long enough'' is seldom are available. In the
1990's, several authors have proposed algorithms that
circumvent this problem by running the chain for some random
amount of time in such a way that the distribution of the
output automatically becomes exactly pi. The breakthrough
came in a 1996 paper of Propp and Wilson, who gave an
algorithm, based on couplings of several Markov chains, that
produces exact samples from pi and moreover is fast enough
to be useful  in many situations of practical interest. In
this talk, I will describe the Propp--Wilson algorithm and
some of the subsequent work that has been done (by Kendall,
Fill, Van Lieshout, Møller, Nelander, myself and many others)
to improve and to extend the applicability of the Propp-Wilson
approach.