## Annealed Importance Sampling

**Radford M. Neal,
Dept. of Statistics and Dept. of Computer Science,
University of Toronto**

Simulated annealing - moving from a tractable distribution to a
distribution of interest via a sequence of intermediate distributions
- has traditionally been used as an inexact method of handling
isolated modes in Markov chain samplers. Here, it is shown how one
can use the Markov chain transitions for such an annealing sequence to
define an importance sampler. The Markov chain aspect allows this
method to perform acceptably even for high-dimensional problems, where
finding good importance sampling distributions would otherwise be very
difficult, while the use of importance weights ensures that the
estimates found converge to the correct values as the number of
annealing runs increases. This annealed importance sampling procedure
resembles the second half of the previously-studied tempered
transitions, and can be seen as a generalization of a
recently-proposed variant of sequential importance sampling. It is
also related to thermodynamic integration methods for estimating
ratios of normalizing constants. Annealed importance sampling is most
attractive when isolated modes are present, or when estimates of
normalizing constants are required, but it may also be more generally
useful, since its independent sampling allows one to bypass some of
the problems of assessing convergence and autocorrelation in Markov
chain samplers.

Technical Report No. 9805 (revised), Dept. of Statistics (February/September
1998), 25 pages:
postscript,
pdf.

The above is the revised version of September 1998. The original version
of February 1998 is also available:
postscript,
pdf.

Also available
from arXiv.org.

**Associated references:**
A revised version of this technical report has been published as the
following paper:
Neal, R. M. (2001) ``Annealed importance sampling'', *Statistics and
Computing*, vol. 11, pp. 125-139:
abstract,
associated references.

Annealed importance sampling is related to the method of tempered transitions,
described in the following paper:
Neal, R. M. (1996) ``Sampling from multimodal distributions using
tempered transitions'', *Statistics and Computing*, vol. 6, pp. 353-366:
abstract,
associated references.