Improving Perfect Simulation

                
                             Xiao-Li Meng
                         Department of Statistics
                         The University of Chicago
           



      The Monte Carlo community recently has had a pleasant surprise. 
Based on their ingenious idea of running coupled Markov chains with
negative time, Propp and Wilson (1996, Random Structures and
Algorithms) proposed a Markov chain Monte Carlo (MCMC) algorithm
that will, with probability one, terminate itself in a finite number of steps
and yet deliver draws that are exactly from the limiting (i.e., stationary)
distribution.  By applying the algorithm to a variety of problems, including
sampling exactly from the Ising model at the critical temperature with a
4200 by 4200 toroidal grid, they demonstrated the practicality and
efficiency of the algorithm.  Their findings are perhaps particularly
exciting for statisticians/probabilists/applied mathematicians, since this
appears to be the first time that a major Monte Carlo method is developed
solely by non-physicists, yet the method is applicable to non-trivial
computational problems in physics and other scientific studies.  Built upon
their method of coupling from the past or backward coupling, a new class
of MCMC algorithms has emerged.  This class of algorithms has been
labeled perfect simulation or exact simulation, because for this class of
stochastic iterative algorithms the challenging issue of accessing
convergence as well as errors in approximation completely vanishes.

      After a brief review of the Propp-Wilson algorithm, in this talk I will
propose two methods, multi-stage backward coupling and parallel antithetic
coupling, for improving the computational or equivalently statistical
efficiency of the current perfect simulation schemes.  The first method
borrows ideas from survey sampling where it is a common knowledge that
multi-stage sampling is typically more cost effective than single-stage
sampling.  The second method explores the use of antithetic variates with
backward coupling, and it relies critically on the theory of negative
association, which studies the preservation of negative correlation under
monotone transformations.  Limited empirical and theoretical evidence
suggests the possibility of significant improvement (e.g., 30%-50%
reduction in time/variance) with either method over the Propp-Wilson
algorithm in certain applications.

      While the theory and implementation of the proposed methods is not
completely trivial, the talk should be accessible to both the pessimists
(nothing is perfect) and the optimists (things can always be better).