Importance Sampling for Families of DistributionsNeal Madras; Mauro PiccioniThe Annals of Applied Probability, Vol. 9, No. 4. (Nov., 1999), pp. 1202-1225.Stable URL:http://links.jstor.org/sici?sici=1050-5164%28199911%299%3A4%3C1202%3AISFFOD%3E2.0.CO%3B2-CThe Annals of Applied Probability is currently published by Institute of Mathematical Statistics.Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available athttp://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtainedprior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content inthe JSTOR archive only for your personal, non-commercial use.Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained athttp://www.jstor.org/journals/ims.html.Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printedpage of such transmission.JSTOR is an independent not-for-profit organization dedicated to and preserving a digital archive of scholarly journals. Formore information regarding JSTOR, please contact [email protected]://www.jstor.orgThu Mar 29 09:47:24 2007The Anilals ofApplied Probability 1999. Thl. 9. KO.4, 1202-1228 IMPORTANCE SAMPLING FOR FAMILIES OF DISTRIBUTIONS York University and Universita di L'Aquila This paper analyzes the performance of importance sampling distribu- tions for computing expectations with respect to a whole family of probabil- ity laws in the context of Marlrov chain Monte Carlo simulation methods. Motivations for such a study arise in statistics as well as in statistical physics. Two choices of importance sampling distributions are considered in detail: mixtures of the distributions of interest and distributions that are "uniform over energy levels" (motivated by physical applications). We an- alyze two examples, a "witch's hat" distribution and the mean field Ising model, to illustrate the advantages that such simulation procedures are expected to offer in a greater generality. The connection with the recently proposed simulated tempering method is also examined. 1. Introduction. Monte Carlo methods have long been an indispensable tool in the field of statistical physics [see Metropolis, Rosenbluth, Rosenbluth, Teller and Teller (1953), Sokal (1989), Binder and Heerman (199211. More recently, a similar view has been developing among statisticians [see, e.g., Smith and Roberts (1993), Besag and Green (1993), Tanner (1993), Gilks, Richardson and Spigelhalter (1996), Robert (1996), Gamerman (199711. This paper will discuss some procedures that attempt to alleviate two common problems that arise in many Monte Carlo studies: (i) The need to perform many Monte Carlo runs that differ only in the value of some input parameter(s); and (ii) A very slow approach to equilibrium of dynamic sampling schemes, which are usually known in statistics as Markov chain Monte Carlo methods. Many practitioners, in statistics as well as in physics, have observed that suitable variations on the classical technique of importance sampling can of- ten help to overcome both of these problems. For the most part, however, these observations have been largely empirical, based upon experience with a partic- ular set of models. Our main contribution in this paper is to perform a rigorous asymptotic analysis of the behavior of such procedures in two model examples: the mean field Ising model from statistical physics, and the "witch's hat" dis- tribution of Geyer and Thompson (1995). To this end, we establish some basic general results about the efficiency of such implementations of importance sampling, which are valid in general state spaces. Received July 1997; revised February 1999. lSupported in part by the Natural Science and Engineering Research Council of Canada. 2Supported in part by the Ministry of University and Research of Italy. AMS 1991 subject classifications. Primary 60505; secondary 65C05, 82B80. Key words and phruses. Marlrov chain Monte Carlo, importance sampling, simulated temper- ing, Metropolis algorithm, spectral gap, Ising model. 12021203 IMPORTANCE SAMPLING FOR FAMILIES The essential idea of importance sampling is the following. Suppose that p is a known probability measure on some measurable state space (a.&) (usually a subset of R~),and let f be a real-valued integrable function on 0. We want to compute the expected value but we are unable to evaluate it either exactly or by standard numerical ap- proximations, typically because either d is large or p is very complicated. The crude Monte Carlo solution is to generate a vector Xi of i.i.d. p-distributed random variables Xy, . . .:XE and to estimate E'f by the empirical average which is unbiased (its expectation is E' f) and strongly consistent (it converges to E'f almost surely as n + m).Moreover if the variance of f (Xy), denoted by aE(f), is finite, then the central limit theorem holds, making it possible to evaluate the error of the estimate (the variance being likewise consistently estimated). One can try to find an estimator with a smaller variance by sampling from a different probability distribution v on (0..%), such that p is absolutely con- tinuous with respect to v (otherwise the sampling process will always miss some nonnegligible part of 0).If we can generate X:; = (X';. . . . ,Xx) i.i.d. with distribution v, then the empirical average g(XK), where g = f dpldv is the product off with the importance sampling weights dpldv, is again an un- biased and strongly consistent estimator of E'f. Moreover, the central limit theorem still holds, provided the variance a;(g) exists. It is clear that such a variance depends on v; a good choice of v can make it dramatically smaller than aE(f). The classical guideline for a good choice is that v should put weight where p is concentrated and simultaneously f is large, hence the name im- portance sampling. However, in this paper our choice of v is determined only by the measure(s1 p, and we adopt a "worst case" approach with respect to the variation of f. A quite different approach to importance sampling is used in rare event simulation, where the choice of v is heavily determined by the event or function being estimated; see Bucklew