SAMPLING FROM MULTIMODAL DISTRIBUTIONS USING TEMPERED TRANSITIONS
Radford M. Neal
Dept. of Statistics and Dept. of Computer Science
University of Toronto
29 October 1994
I present a new Markov chain sampling method appropriate for
distributions with isolated modes. Like the recently-developed method
of ``simulated tempering'', the ``tempered transition'' method uses a
series of distributions that interpolate between the distribution of
interest and a distribution for which sampling is easier. The new
method has the advantage that it does not require approximate values
for the normalizing constants of these distributions, which are needed
for simulated tempering, and can be tedious to estimate. Simulated
tempering performs a random walk along the series of distributions
used. In contrast, the tempered transitions of the new method move
systematically from the desired distribution, to the easily-sampled
distribution, and back to the desired distribution. This systematic
movement avoids the inefficiency of a random walk, an advantage that
unfortunately is cancelled by an increase in the number of
interpolating distributions required. Because of this, the sampling
efficiency of the tempered transition method in simple problems is
similar to that of simulated tempering. On more complex
distributions, however, simulated tempering and tempered transitions
may perform differently. Which is better depends on the ways in which
the interpolating distributions are ``deceptive''.