Mark Jerrum

Perfect sampling, old and new

The possibility of obtaining perfect samples efficiently from a complex probability distribution entered the consciousness of the community in the mid-nineties with the invention of `coupling from the past' by Propp and Wilson.  The study of perfect samplers of course has considerable theoretical appeal.  But, in addition, their `self clocking' aspect may have practical advantages.  For example, to obtain (imperfect) samples by direct Markov chain simulation we need an a priori analytic bound on the mixing time of the Markov chain, which even now may be very weak;  in contrast, a simulation by coupling from the past halts as soon as a perfect sample has been computed.  Coupling may occur much earlier than the analytic mixing time bound might suggest.

In the last decade or so, a remarkable variety of perfect samplers have come to light, too many to survey in one talk.  To cut down the scope to something reasonable, I'll focus on perfect samplers that have the additional property that they are able to sample perfectly (a finite window onto) a random configuration of infinite spatial extent, such as one finds in statistical mechanics.  Coupling from the past has this property, as does an approach that Konrad Anand (a PhD student at QMUL) and I have been investigating, and which we are calling `lazy depth-first sampling'.  I feel this approach gives a particularly concrete account of what it means for an infinite system to have a unique Gibbs measure.