arXiv:1511.01437v3 [math.PR] 21 Jun 2017

THE SAMPLE SIZE REQUIRED IN IMPORTANCE
SAMPLING
SOURAV CHATTERJEE AND PERSI DIACONIS
Abstract. The goal of importance sampling is to estimate the expected
value of a given function with respect to a probability measure ν using
a random sample of size n drawn from a different probability measure
µ. If the two measures µ and ν are nearly singular with respect to each
other, which is often the case in practice, the sample size required for
accurate estimation is large. In this article it is shown that in a fairly
general setting, a sample of size approximately exp(D(ν||µ)) is necessary
and sufficient for accurate estimation by importance sampling, where
D(ν||µ) is the Kullback–Leibler divergence of µ from ν. In particular,
the required sample size exhibits a kind of cut-off in the logarithmic
scale. The theory is applied to obtain a general formula for the sample size required in importance sampling for one-parameter exponential
families (Gibbs measures).

1. Theory
Let µ and ν be two probability measures on a set X equipped with some
sigma-algebra. Suppose that ν is absolutely continuous with respect to µ.
Let ρ be the probability density of ν with respect to µ. Let X1 , X2 , . . . be
a sequence of X -valued random variables with law µ. Let f : X → R be a
measurable function. Suppose that our goal is to evaluate the integral
Z
I(f ) :=
f (y)dν(y) .
X

The importance sampling estimate of this quantity based on the sample
X1 , . . . , Xn is given by
n

In (f ) :=

1X
f (Xi )ρ(Xi ) .
n
i=1

Sometimes, when the probability density ρ is known only up to a normalizing
constant — that is, ρ(x) = Cτ (x) where τ is explicit but C is hard to
2010 Mathematics Subject Classification. 65C05, 65C60, 60F05, 82B80.
Key words and phrases. Importance sampling, Monte Carlo methods, Gibbs measure,
phase transition.
Sourav Chatterjee’s research was partially supported by NSF grant DMS-1441513.
Persi Diaconis’s research was partially supported by NSF grant DMS-1208775.
1

2

SOURAV CHATTERJEE AND PERSI DIACONIS

calculate — the following alternative estimate is used:
Pn
f (Xi )τ (Xi )
Pn
Jn (f ) := i=1
.
i=1 τ (Xi )

(1.1)

It is easy to see that
Z

Z

f (y)dν(y) .

f (x)ρ(x)dµ(x) =

E(In (f )) =
X

X

Therefore, the expected value of In (f ) is the quantity I(f ) that we are trying
to estimate. However, In (f ) may have large fluctuations. The two main
problems in importance sampling are: (a) given µ, ν and f , to determine
the sample size required for getting a reliable estimate, and (b) given ν
and f , to find a sampling measure µ that minimizes the required sample
size among a given class of measures. We address the first problem in this
paper.
A straightforward approach for computing an upper bound on the required sample size is to compute the variance of In (f ). Indeed, this is easy
to compute:
Z

1
2
2
2
Var(In (f )) =
f (x) ρ(x) dµ(x) − I(f )
n X

Z
1
2
2
f (y) ρ(y)dν(y) − I(f ) .
(1.2)
=
n X
The formula for the variance can be used, at least in theory, to calculate a
sample size that is sufficient for guaranteeing any desired degree of accuracy
for the importance sampling estimate. In practice, however, this number is
often much larger than what is actually required for good performance.
Sometimes the variance formula (1.2) is estimated using the simulated
data X1 , . . . , Xn . This estimate is known as the empirical variance. There
is an inherent unreliability in using the empirical variance to determine
convergence of importance sampling. We will elaborate on this in Section 2.
We begin by stating our main theorems. Proofs are collected together in
Section 4. A literature review on importance sampling is given at the end
of this introduction.
There are three main results in this article. The first theorem, stated
below, says that under a certain condition that often holds in practice,
the sample size n required for |In (f ) − I(f )| to be close to zero with high
probability is roughly exp(D(ν||µ)) where D(ν||µ) is the Kullback–Leibler
divergence of µ from ν. More precisely, it says that if s is the typical order
of fluctuations of log ρ(Y ) around its expected value, then a sample of size
exp(D(ν||µ) + O(s)) is sufficient and a sample of size exp(D(ν||µ) − O(s))
is necessary for |In (f ) − I(f )| to be close to zero with high probability. The
necessity is proved by considering the worst possible f — which, as it turns
out, is the function that is identically equal to 1.

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

3

An immediate concern that the reader may have is that |In (f ) − I(f )| ≈ 0
may not always be the desired criterion for convergence. If I(f ) is very
small, then one may want to have In (f )/I(f ) ≈ 1 instead. A necessary and
sufficient condition for this, when f is the indicator of a rare event, is given
in Theorem 1.3 later in this section.
Theorem 1.1. Let X , µ, ν, ρ, f , I(f ) and In (f ) be as above. Let Y be
an X -valued random variable with law ν. Let L = D(ν||µ) be the Kullback–
Leibler divergence of µ from ν, that is,
Z
Z
log ρ(y)dν(y) = E(log ρ(Y )) .
ρ(x) log ρ(x)dµ(x) =
L = D(ν||µ) =
X

X

Let kf kL2 (ν) := (E(f (Y

)2 ))1/2 .

If n = exp(L + t) for some t ≥ 0, then
p

E|In (f ) − I(f )| ≤ kf kL2 (ν) e−t/4 + 2 P(log ρ(Y ) > L + t/2) .

Conversely, let 1 denote the function from X into R that is identically equal
to 1. If n = exp(L − t) for some t ≥ 0, then for any δ ∈ (0, 1),
P(In (1) ≥ 1 − δ) ≤ e−t/2 +

P(log ρ(Y ) ≤ L − t/2)
.
1−δ

Note that Theorem 1.1 does not just give the sample size required to
ensure that In (f ) is close to I(f ) in the L1 sense; the second part of the
theorem implies that if we are below the sample size prescribed by Theorem 1.1, then for f ≡ 1, there is a substantial chance that In (f ) is actually
not close to I(f ). Such lower bounds cannot be given merely by moment
estimates. For example, lower bounds on moments like E|In (f ) − I(f )| and
Var(In (f )) imply nothing; In (f ) may be close to I(f ) with high probability
and yet E|In (f ) − I(f )| and Var(In (f )) may be large. The second part of
Theorem 1.1 gives an actual lower bound on the sample size required to
ensure that In (f ) is close to I(f ) with high probability, and the first part
shows that this lower bound matches a corresponding upper bound. It is
interesting that the sample size required for small L1 error turns out to be
the actual correct sample size for good performance.
As shown later in this section, it is fairly common that log ρ(Y ) is concentrated around its expected value in large systems. In this situation, a
sample of size roughly exp(D(ν||µ)) is both necessary and sufficient.
The second main result of this article, stated below, gives the analogous
result for the estimate Jn (f ). The conclusion is essentially the same.
Theorem 1.2. Let all notation be as in Theorem 1.1 and let Jn (f ) be the
estimate defined in (1.1). Suppose that n = exp(L + t) for some t ≥ 0. Let
p
1/2
 := e−t/4 + 2 P(log ρ(Y ) > L + t/2)
.
Then


2kf kL2 (ν) 
P |Jn (f ) − I(f )| ≥
≤ 2 .
1−

4

SOURAV CHATTERJEE AND PERSI DIACONIS

Conversely, suppose that n = exp(L − t) for some t ≥ 0. Let f (x) denote
the function from X into R that is equal to 1 when log ρ(x) ≤ L − t/2 and
0 otherwise. Then I(f ) = P(log ρ(Y ) ≤ L − t/2) but P(Jn (f ) 6= 1) ≤ e−t/2 .
Sometimes, importance sampling is used to estimate the probabilities of
rare events under the target measure ν. Typically, the quantity of interest
is ν(A), where A is a rare event under ν but is not a rare event under
µ. The method of estimation is the same as before, that is, let 1A (x) be
the function that is 1 if x ∈ A and 0 otherwise, and let In (1A ) be the
importance sampling estimate of ν(A). The difference with the previous
setting is that when estimating ν(A), we are not satisfied if |In (1A ) − ν(A)|
is small because ν(A) itself is a small number. Rather, it is satisfactory
if the ratio In (1A )/ν(A) is close to 1. It turns out that the sample size
that is necessary and sufficient for this purpose is not exp(D(ν||µ)), but
exp(D(νA ||µ)), where νA is the probability measure ν conditioned on the
event A. This is quantified by the following theorem, which is the third
main result of this paper.
Theorem 1.3. Let all notation be as in Theorem 1.1. Let A be any event
such that ν(A) > 0 and let 1A be the indicator function of A, defined above.
Let νA be the measure ν conditioned on the event A, that is, for any event B,
ν(A ∩ B)
.
νA (B) :=
ν(A)
Let ρA (x) := ρ(x)1A (x)/ν(A) be the probability density function of νA with
respect to µ. Let LA := D(νA ||µ). If n = exp(LA + t) for some t ≥ 0, then
p
In (1A )
E
− 1 ≤ e−t/4 + 2 P(log ρA (Y ) > LA + t/2 | Y ∈ A) .
ν(A)
Conversely, suppose that n = exp(LA − t) for some t ≥ 0. Then for any
δ ∈ (0, 1),


In (1A )
P(log ρA (Y ) ≤ LA − t/2 | Y ∈ A)
P
≥ 1 − δ ≤ e−t/2 +
.
ν(A)
1−δ
We would like to remark here that the upper bounds in Theorems 1.1,
1.2 and 1.3 may not be tight. The only purpose of these theorems is to
give matching upper and lower bounds on the sample size required for good
performance of importance sampling. No attempt was made to get optimal
error bounds, especially of the type that is relevant to practitioners.
Another remark is that in practice, µ is chosen depending on ν, to minimize the required sample size. One potential use for our theorems is that
they may be used to choose µ by minimizing the Kullback–Leibler divergence of µ from ν among some class of candidate measures. This point is
elaborated in the literature review at the end of this section.
Sometimes, however, µ is chosen depending on both ν and f . Since
Theorems 1.1 and 1.2 give bounds that depend only on the L2 (ν) norm
of f , they will not be useful for choosing µ using fine properties of f . This is

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

5

particularly problematic if f is something like the indicator of a rare event.
This issue is partially addressed in Theorem 1.3, where f = 1A for some
rare event A, and the required sample size depends on µ, ν and the event A.
Therefore Theorem 1.3 can be used for choosing µ depending on properties
of both ν and f .
Let us now investigate the implications of our theorems in a few simple
examples. More complex examples are given in later sections.
Example 1.4 (Binomial distributions). Let µ = Binomial(N, p) and ν =
Binomial(N, r), where r > p. Then
r
1−r
log ρ(x) = x log + (N − x) log
.
p
1−p
Let Y ∼ ν. Then L = E(log ρ(Y )) = N H(r, p), where
1−r
r
.
H(r, p) = r log + (1 − r) log
p
1−p
√
Moreover, the standard deviation of log ρ(Y√) is of order N . Thus, the
required sample size is exp(N H(r, p) + O( N )). On the other hand, a
simple calculation shows that if variance is used to determine sample size,
the required size would be exp(N V (r, p)), where

 2
(1 − r)2
r
+
.
V (r, p) = log
p
1−p
By Jensen’s inequality, V (r, p) ≥ H(r, p). Figure 1 shows that graph of
H(r, p) versus the graph of V (r, p), as r varies and p is fixed at 1/2. This
elementary example demonstrates how using the variance can lead to unnecessarily large sample sizes.
Example 1.5 (Directed paths). Let X be the set of all monotone paths from
(0, 0) to (n, n) in the two dimensional lattice. Here, paths are only allowed
to go up and to the right. The target measure is the uniform distribution
on all such paths. Clearly, |X | = 2n
n . The sampling measure µ in this
example constructs a random path γ as follows (this is known as sequential
importance sampling): Choose one of the two directions ‘up’ or ‘right’ with
probability 1/2 until the walk hits the top or right side of the n × n ‘box’,
when the remainder of the walk is forced. If T (γ) is the first time the path
hits the top or right side then
µ(γ) = 2−T (γ) .

Both the uniform distribution ν(γ) = 1/ 2n
n and µ(γ) have the property
that, conditional on T (γ) = j, the paths are uniformly distributed. Thus
distributional questions are determined by the distribution of T (γ).
The following proposition from Bassetti and Diaconis
√ [4] shows that under
the sampling distribution µ, T (γ) is usually about O( n) from the maximum
possible 2n − 1, but under the uniform distribution ν, T (γ) is usually about
O(1) away from 2n − 1.

SOURAV CHATTERJEE AND PERSI DIACONIS

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

6

0.5

0.6

0.7

0.8

0.9

1.0

r

Figure 1. Let H and V be as in Example 1.4. The dotted
line represents V (r, p) and the solid line represents H(r, p).
Here p = 0.5 and r goes from 0.5 to 1 on the x-axis.

Proposition 1.6. With the notation above,
(a) Under the importance sampling distribution µ,
1−j

µ{T (γ) = j} = 2




j−1
, n ≤ j ≤ 2n − 1 .
n−1

(b) For n large and fixed positive x,

Z
2n − 1 − T (γ)
1 x −y2 /4
√
µ
≤x ∼
e
dy .
π 0
n


(c) Under the uniform distribution ν,
ν{T (γ) = j} =

2

j−1
n−1

2n
n


, n ≤ j ≤ 2n − 1 .

2
Further Eν (T (γ)) = (2 − n+1
)n.
(d) For n large and any fixed k,

ν{T (γ) = 2n − 1 − k} ∼

1
2k+1

, 0 ≤ k < ∞.

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

7

The quantity L of Theorem 1.1 is determined from ρ(γ) = ν(γ)/µ(γ) as
L=

X

ν(γ) log

γ

ν(γ)
µ(γ)

 
2n
log 2 X
T (γ)
= − log
+ 2n
n
n
γ
  

2n
2
= − log
+ 2−
n log 2
n
n+1
 
√
1
= log πn − 2 log 2 + O
.
n
√
Thus, eL ∼ πn/4, and moreover, log ρ(γ)√has fluctuations of order 1 around
its mean. Thus, a sample size of order n is necessary and sufficient for
accuracy of importance sampling in this example. The sufficiency was already observed using variance computations in Bassetti and Diaconis [4];
the necessity is a new result. Similar computations can be carried out for
paths allowed to go left or right or up (staying self avoiding) using results
of Bousquet-Mélou [12].
Example 1.7 (Estimating the probability of a rare event). As an example
for Theorem 1.3, fix N and p > 1/2 and let A = {j : N p ≤ j ≤ N }. Take ν
to be the Binomial(N, 1/2) distribution. Let b(A; N, 1/2) be the probability
of A under ν. Estimating b(A; N, 1/2) by simple sampling from ν would
be a crazy task; for example when N = 100 and p = .9, b(A; 100, 1/2) ≈
0.676049 × 10−45 , which means that we would need roughly 1045 samples
to directly estimate this probability. A standard importance sampling approach (Siegmund [54]) is to sample X1 , X2 , . . . , Xn from µ = Binomial(N, θ)
for some θ and use
n

In (A) =

1 X ν(Xi )
1A (Xi ) .
n
µ(Xi )
i=1

Theorem 1.3 shows that this will be accurate in ratio for n of order eLA . The
following proposition shows that when µ is Binomial(N, θ), θ = p minimizes
eLA , agreeing with the variance minimization in Siegmund [54]. When N =
100 and p = .9, eLA ≈ 1.723 × 1028 (still an impossible sample size, but
much smaller than 1045 ).
Proposition 1.8. Fix N and p > 1/2 such that N p is an integer. Let µ
be the Binomial(N, θ) distribution, ν be the Binomial(N, 1/2) distribution
and A = {j : N p ≤ j ≤ N }. Then the quantity LA of Theorem 1.3 is
asymptotically minimized when θ = p, and with this choice of θ, LA is
aymptotic to −2N log(pp (1 − p)1−p ) as N → ∞.

8

SOURAV CHATTERJEE AND PERSI DIACONIS

Review of the literature. Our interest in this topic started with a question from our colleague Don Knuth in Knuth [37]. He used sequential importance sampling to generate random self-avoiding paths starting at (0, 0)
and ending at (N, N ) in a two dimensional N × N grid. For N = 10 he
calculated the number of paths (about 1.6 × 1024 ), the average path length
(92 ± 5) and the proportion of paths passing through (5, 5) (81% ± 10%).
He noticed huge fluctuations along the way and wanted to know about the
accuracy of his estimates. In the follow up work Knuth [38], exact computation showed surprising accuracy for his example. Bassetti and Diaconis
[4] and Bousquet-Mélou [12] studied toy versions of Knuth’s problem where
exact calculations can be done; they confirm the extreme variability and
make the accuracy observed mysterious.
In our work, the choice of the proposal measure µ is considered fixed. A
good deal of the art of successful implementation of importance sampling
consists in a careful choice of µ, adapted to the problem under study. This
is often done to minimize the variance of the resulting estimate. Our work,
especially the main result of Section 2, suggests that the variance is a poor
measure of accuracy for these long tailed problems. Thus, there is work to
be done, exploring ways of adapting the many good ideas below, based on
the variance, to minimizing the Kullback–Leibler divergence.
Any book on simulation will treat importance sampling. We recommend Hammersley and Handscomb [29], Srinivasan [55], Cappé, Moulines
and Rydén [13] and Liu [40]. To begin our review of the research literature,
R
a classical choice of the sampling measure µ for estimating I(f ) = f dν is
to take dµ(x) proportional to |f (x)|dν(x) (Kahn and Marshall [33]). Hesterberg [30] suggests using a mixture of measures for µ with one component
proportional to |f (x)| near its maximum. This is closely related to the
widely used method of umbrella sampling (Torrie and Valleau [57]; nicely
developed in Madras [42]). Owen and Zhou [50] combine Hesterberg’s idea
with control variates to give an attractive, practical approach. In later work,
Owen and Zhou [49] suggest an adaptive version, attempting to improve the
proposed µ using previous sampling. This is based on the empirical variance
which means that our laments in Section 2 apply.
The idea of using L1 distance to measure performance of importance
sampling has appeared in a few prior instances. Two notable examples are
Owen [47] and Owen [48], where L1 error was used to compare the Monte
Carlo and quasi-Monte Carlo approaches to estimating singular integrands
via importance sampling.
Importance sampling is often used to do rare event simulation. Then,
it is natural to tilt the sampling distribution µ towards to the region of
interest. Siegmund [54] gives an asymptotically principled approach to doing
this, which has given rise to much follow-up work, some of it quite deep
mathematically. A unifying account of a variety of importance sampling
algorithms for simulating the maxima of Gaussian fields appears in Shi,
Siegmund and Yakir [53]. A host of novel ways of building importance

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

9

sampling estimates for problems such as estimating the size of the union of
a collection of sets when the size of each is known is in Naiman and Wynn
[46]. The work of Paul Dupuis with many coauthors is notable here. Dupuis
and Wang [25] and Dupuis, Spiliopoulos and Wang [24] are representative
papers with useful pointers to an extensive literature. Asmussen and Glynn
[2] give a textbook account of this part of the subject.
An important part of the literature adapts importance sampling from the
case of independent proposals considered here to use with a Markov chain
generating proposals. Madras and Piccioni [43] give a clear development as
do the textbook accounts of Robert and Casella [51] or Liu [40].
An important class of techniques for building proposal distributions is
known as sequential importance sampling. An early appearance of this to
sampling self-avoiding paths occurs in Rosenbluth and Rosenbluth [52]. For
contingency table examples see Chen, Diaconis, Holmes and Liu [17]. For
degree sequences of graphs, see Blitzstein and Diaconis [11]. For time series
and a general review see the textbook by Doucet, de Freitas and Gordon
[23] or the survey of Chen and Liu [18].
A relatively recent technique choosing the proposal distribution, which
has been particularly successful in the heavy-tailed setting, is a method
based on Lyapunov functions developed by Blanchet and Liu [9, 10], Blanchet
and Glynn [7] and Blanchet, Glynn and Leder [8].
One large related topic is the connection between importance sampling
and particle filters. Roughly, when building a proposal µ sequentially, one
begins with a number N of starts. As the proposals are independently built
up, some weights may be much larger than others. One can generate N
new proposals from the present ones (say with probability proportional to
weights). This will replicate some proposals and kill of those with smaller
weights. This resampling can be repeated several times. The final weighted
samples are used, in the usual way, to form importance sampling estimates.
This large enterprise can be surveyed in the textbooks of Del Moral [19, 20]
and Doucet, de Freitas and Gordon [23]. Work of Chan and Lai [14, 15]
harnesses martingale central limit theorems to get the limiting distribution
of these importance sampling methods in a variety of complex stochastic
models. The web page of Arnaud Doucet is extremely useful. A very clear
recent paper is: Del Moral, Kohn and Patras [21].
Besides the broad classifications outlined above, importance sampling has
a variety of other applications that are harder to categorize. A recent example is the paper by Efron [26] that suggests the use of importance sampling
for generating from Bayesian posterior distributions. In this context, an
interesting note is that simulating from a Bayesian posterior by rejection
sampling was investigated by Freer, Mansinghka and Roy [27], who found a
connection with the Kullback–Leibler divergence that bears some similarities
with the results of this paper.

10

SOURAV CHATTERJEE AND PERSI DIACONIS

Two other recent papers have similarities with our work. One is that of
Hult and Nyquist [32], who analyze the performance of importance sampling in the estimation of probabilities of rare events using large deviation
techniques. The Kullback–Leibler divergence arises naturally in this work,
due to its appearance in large deviation rate functions. The other is a paper
of Agapiou, Papaspiliopoulos, Sanz-Alonso and Stuart [1], who prove that
|In (f ) − I(f )| is small if n ≥ E(ρ(Y )) ≥ eL , in the notation of our Theorem 1.1. This result is applied to a class of problems that don’t overlap
with our set of examples, making [1] and this paper complementary to each
other.
2. Testing for convergence
The theory developed in Section 1, while theoretically interesting, is possibly not very useful from a practical point of view. Determining D(ν||µ)
requires in-depth knowledge of not only the measure µ, but also the usually
much more complicated measure ν. It is precisely the lack of understanding
about ν that motivates importance sampling, so it seems pointless to ask a
practitioner to compute the required sample size by using properties of ν.
To determine whether the importance sampling estimate has converged,
a common practice is to estimate Var(In (f )) by estimating the variance
formula (1.2) using the data from µ. One natural estimate is
n
In (f )2
1 X
f (Xi )2 ρ(Xi )2 −
.
vn (f ) := 2
n
n
i=1

If this estimate is used, then importance sampling is declared to have converged if for some n, vn (f ) turns out to be smaller than some pre-specified
tolerance threshold  (see Robert and Casella [51]).
The following theorem shows that using vn (f ) as a diagnostic for convergence of importance sampling is problematic, because for any given tolerance level , there is high probability that the test declares convergence at
or before a sample size that depends only on  and not on µ, ν or f . This
is absurd, since convergence may take arbitrarily long, depending on the
problem.
−3

Theorem 2.1. Given any  > 0, there exists n ≤ −2 21+ such that the
following is true. Take any µ and ν as in Theorem 1.1, and any f : X → R
such that kf kL2 (ν) ≤ 1. Let vn (f ) be defined as above. Then P(vn (f ) < ) ≥
1 − 4.
Although the upper bound on n is very large — for example, for  = .1
the upper bound is roughly 2.14 × 10303 — Theorem 2.1 gives a conceptual
proof that using vn (f ) for testing convergence of importance sampling is
fundamentally flawed. As the measures µ and ν get more and more singular
with respect to each other (which often happens as system size gets larger),
importance sampling should take longer to converge. A test that does not

1.0

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

11

0.0

0.2

0.4

0.6

0.8

Actual error
Estimated standard deviation

2

4

6

8

10

12

14

log(Sample size)

p
Figure 2. Estimated standard deviation vn (f ) of In (f ),
as n ranges from 1 to 106 , and the actual error |In (f ) − I(f )|.
Here µ = Binomial(100, .5), ν = Binomial(100, .7) and f ≡ 1.
respect this feature cannot be a plausible test for convergence. Incidentally,
it is not clear whether the upper bound on n in Theorem 2.1 can be improved
to something more reasonable.
The ineffectiveness of the variance diagnostic is not hard to demonstrate
in examples. One such examples are given below.
Example 2.2. In Example 1.4 with large N , vn (f ) stays extremely close
to zero for any realistic value of n because ρ(Xi ) is very close to zero with
high probability. But here we know that the actual convergence takes place
at a sample size that is exponentially large in N . For instance, consider µ =
Binomial(100, .5) and ν = Binomial(100, .7). Let f be the function that is
identicallyp
equal to 1. Figure 2 shows the plot of the estimated standard
deviation vn (f ) against n, as n ranges from 1 to 106 . The estimated
standard deviation remains fairly small throughout. However, since we know
the actual value of I(f ) in this case (which is 1), it is easy to compute the
actual error |In (f ) − I(f )| and check that the variance diagnostic is giving
a false conclusion.
There are results in the literature that claim to show that the variance
estimation method gives a valid criterion for the convergence of importance
sampling. However, what these results actually show is that if n is so large

12

SOURAV CHATTERJEE AND PERSI DIACONIS

that the importance sampling estimates are accurate, then vn (f ) is small. In
other words, the smallness of vn (f ) is a necessary condition for convergence
of importance sampling, but not a sufficient condition. For a diagnostic
criterion to be useful, it needs to be both necessary and sufficient for convergence.
In practice, vn (f ) is not usually the preferred diagnostic. Various selfnormalized versions of vn (f ) are used. It is possible that these more complicated estimates are also problematic in the same way, but we do not
have a proof. It would be interesting to prove analogs of Theorem 2.1 for
self-normalized diagnostic statistics.
In view of Theorem 1.1, it is natural to consider estimates of the Kullback–
Leibler divergence as possible diagnostic tools for convergence. However, an
inspection of the proof of Theorem 2.1 indicates that such estimates are
likely to suffer from similar problems. The issue is that any diagnostic
criterion that is itself dependent on the accuracy of an estimate obtained by
importance sampling, is unlikely to be effective as a measure of the efficacy
of importance sampling.
We suggest the following alternative diagnostic that is not itself an importance sampling estimate of any quantity. As usual, let µ be the sampling measure, ν be the target measure, and ρ = dν/dµ. Let X1 , X2 , . . . be
i.i.d. random variables with law µ. Define qn := E(Qn ), where
Qn :=

max1≤i≤n ρ(Xi )
Pn
.
i=1 ρ(Xi )

The size of qn is our criterion for diagnosing convergence of importance
sampling. The general prescription is that if for some value of n the quantity
qn is smaller than some pre-specified threshold (say, 0.01), declare that n
is large enough for importance sampling to work. Note that the random
variable Qn always lies between 0 and 1, and therefore qn ∈ [0, 1]. Moreover,
given any n, it is possible to estimate qn up to any desired degree of accuracy
by repeatedly simulating Qn and taking an average, since qn = E(Qn ) and
Qn always lies between 0 and 1. Lastly, note that for estimating qn using
simulations in the above manner, it suffices to know the density ρ up to an
unspecified normalizing constant. Repeatedly calculating Qn , however, may
be computationally expensive if either n is too large or ρ is too complex.
Why should one expect the smallness of the quantity qn to be a valid
diagnostic criterion for convergence of importance sampling? First, let us
hasten to add the caveat that one can produce examples where it does not
work. One such example is the following: Take a large number N . Let µ be
the uniform distribution on {1, 2, . . . , N }. Let ν be the distribution that puts
mass 1/2N on the points 1, 2, . . . , N − 1, and mass (N + 1)/2N on the point
N . Then ρ(x) = 1/2 for x = 1, 2, . . . , N − 1 and ρ(N ) = (N + 1)/2. Under
the sampling measure µ, ρ = 1/2 with probability 1 − 1/N . Therefore when
1  n  N , the quantity qn will be small; but convergence of importance
sampling will not happen until n  N .

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

13

In spite of the above counterexample, we expect that qn is a valid diagnostic for many natural examples. This is made precise to a certain extent in
the setting of Gibbs measures by Theorem 3.5 in the next section. A general
heuristic argument for the effectiveness of the qn diagnostic, on which the
proof of Theorem 3.5 is based, can be described as follows.
Suppose that log ρ is concentrated under ν, so that Theorem 1.1 applies, and the sample size required for convergence of importance sampling
is roughly eL , where L = Eν (log ρ). Take any n below this threshold. Let
Mn := max1≤i≤n ρ(Xi ). Since ρ(X1 ), ρ(X2 ), . . . are i.i.d. random variables,
it is easy to see that under mild conditions, Mn ≈ a with high probability,
where a solves
nP(ρ(X1 ) ≥ a) = 1 .
Next, let Sn :=

Pn

i=1 ρ(Xi ).

(2.1)

Since Mn ≈ a, therefore

Sn ≈

n
X

ρ(Xi )1{ρ(Xi )≤a} .

i=1

Therefore
E(Sn ) ≈ nE(ρ(X1 )1{ρ(X1 )≤a} ) = nPν (ρ ≤ a) = nPν (log ρ ≤ log a) .

(2.2)

Now, Eν (log ρ) = L > log a. Thus, Pν (log ρ ≤ log a) is a large deviation
probability. Therefore under mild conditions, one may expect that
Pν (log ρ ≤ log a) ≈ Pν (log ρ ≈ log a) .
Plugging this into (2.2), we get
E(Sn ) ≈ nPν (log ρ ≈ log a)
= nE(ρ(X1 )1{ρ(X1 )≈a} )
= naP(ρ(X1 ) ≈ a) ≤ naP(ρ(X1 ) ≥ a) .
Using the equation (2.1) to evaluate the last term, we get E(Sn ) . a, and
therefore Sn = O(a) by Markov’s inequality. Since Mn ≈ a, this shows that


Mn
qn = E
= Ω(1) ,
Sn
where Ω(1) means a quantity that is uniformly bounded away from zero as
n → ∞. The above heuristic shows that if n  eL and some appropriate
conditions hold, then qn = Ω(1). In other words, smallness of qn should be
a sufficient condition for convergence of importance sampling. This sketch
can be made rigorous under certain circumstances. An instance of this is
illustrated by Theorem 3.5 in the next section.
The smallness of qn is also a necessary condition for convergence of importance sampling. Unlike sufficiency, the necessity can be rigorously proved in
full generality.

14

SOURAV CHATTERJEE AND PERSI DIACONIS

0.0

0.2

0.4

0.6

0.8

Estimated standard deviation
Proposed statistic q

2

4

6

8

10

12

14

log(Sample size)

Figure 3. Performance of qn in Example 2.2, plotted
against the natural logarithm of the sample size.
Theorem 2.3. Let all notation be as in Theorem 1.1. Let qn be defined as
above. Let n := E|In (1) − 1|. Then


1 log log(1/n )
qn ≤ C max
,
,
n
log(1/n )
where C is a universal constant.
As mentioned above, this theorem shows that the smallness of qn is a necessary condition for convergence of importance sampling (recalling that by
Theorem 1.1, convergence in L1 is equivalent to actual good performance);
if n is small, then qn is forced to be small. This is, however, a conceptual
theorem. The bound is too poor to be applicable in practice, and the unspecified universal constant C can also be too large for the theorem to have
any practical relevance.
The performance of qn in Example 2.2
pis depicted in Figure 3. The figure
plots the estimated standard deviation vn (f ) and the statistic qn , against
log n as n ranges from 1 to 106 . As in Figure 2, we see that the estimated
standard error is generally quite misleading and unstable. On the other
hand the statistic qn detects the non-convergence in small samples and is
very stable. The estimation of qn was based on a sample of size 500 for
each n.

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

15

Figure 4. Performance of qn for Knuth’s self-avoiding walks
on a 10×10 grid. The values of qn , denoted by the thick dots,
were estimated from 31 simulations of Qn , which are depicted
by the solid lines. Picture courtesy of Marc Coram.

Another illustration is given in Figure 4, which investigates the performance of qn for Knuth’s self-avoiding walks on a 10 × 10 grid, that was
described in the literature review part of Section 1. The plot shows the
behavior of qn as n ranges from 1 to 105 . We see that qn is not too small
(greater than 0.2) when n = 103 , but starts getting appreciably small around
n = 104 . When n = 105 , qn is minuscule.
The random quantity Qn is closely related to some existing diagnostics
in the literature on sequential Monte Carlo (particle filters). It has the
same form as the ∞-ESS statistic proposed by Huggins and Roy [31] in the
context of sequential Monte Carlo. Here ESS stands for ‘Effective Sample
Size’, a familiar concept in the sequential Monte Carlo literature. There is
a substantial body of work on the efficacy of the effective sample size as a
diagnostic tool, possibly beginning with Liu and Chen [41] and Doucet, de
Freitas and Gordon [23]. See Whiteley, Lee and Heine [58] for some latest
results. Huggins and Roy [31] established similar properties for the ∞-ESS.
It would be interesting to see whether analogs of these results can be proved
for the Qn and qn statistics proposed in this section.

16

SOURAV CHATTERJEE AND PERSI DIACONIS

3. Importance sampling for exponential families (Gibbs
measures)
As in Section 1, let X be a set equipped with some sigma-algebra. Let λ be
a finite measure on X that we shall call the ‘base measure’. Let H : X → R
be a measurable function, called the Hamiltonian, and let β ∈ R be a parameter, called the inverse temperature. The exponential family distribution
(Gibbs measure) Gβ on X defined by the sufficient statistic (Hamiltonian)
H at a parameter value (inverse temperature) β is the probability measure
on X that has probability density
Z(β)−1 exp(−βH(x))
with respect to the base measure λ, where
Z
Z(β) =
exp(−βH(x))dλ(x)
X

is the normalizing constant, which is assumed to be finite. Let
F (β) := log Z(β) .
In physics parlance, the quantity −F (β)/β is known as the free energy of
the system at inverse temperature β.
Often, the normalizing constant Z(β) is hard to calculate theoretically.
Importance sampling is used to estimate Z(β) in a variety of ways. See
Gelman and Meng [28] for a useful review. Lelièvre, Rousset and Stoltz
[39] show the breadth of this problem. One simple technique: Let β0 be an
inverse temperature at which we know how to generate a sample from the
Gibbs measure. For example β0 = 0 is often a good choice, because G0 is
nothing but the base measure λ normalized to have total mass one. The
goal is to estimate Z(β) using a sample from Gβ0 . Let X1 , . . . , Xn be an
i.i.d. sample of size n from Gβ0 . The importance sampling estimate of Z(β)
based on this sample is the following:
n

Z(β0 ) X
exp(−(β − β0 )H(Xi )) .
Ẑn (β) :=
n
i=1

It is easy to see that E(Ẑn (β)) = Z(β). The question is, how large does n
need to be, so that the ratio Ẑn (β)/Z(β) is close to 1 with high probability?
The following theorem shows that under favorable conditions, a sample
of size approximately exp(F (β0 ) − F (β) − (β0 − β)F 0 (β)) is necessary and
sufficient. The proof, given in Section 4, is a simple consequence of Theorem
1.1 since F (β0 ) − F (β) − (β0 − β)F 0 (β) is actually the Kullback–Leibler
divergence of Gβ0 from Gβ . This theorem is a result for finite systems. A
more general version of this result that applies in the thermodynamic limit
is given later in this section.

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

17

Theorem 3.1. Let all notation be as above. Suppose that the Hamiltonian
H satisfies the condition that for some β 0 > |β|,
Z
exp(β 0 |H(x)|)dλ(x) < ∞ .
X

Then F is infinitely differentiable at β. Let
L := F (β0 ) − F (β) − (β0 − β)F 0 (β)
and
p
σ := |β0 − β| F 00 (β) .
If n = exp(L + rσ) for some r ≥ 0, then
E

Ẑn (β)
4
− 1 ≤ e−rσ/4 + .
Z(β)
r

Conversely, if n = exp(L − rσ) for some r ≥ 0, then for any δ ∈ (0, 1),


Ẑn (β)
4
≥ 1 − δ ≤ e−rσ/2 +
.
P
Z(β)
(1 − δ)r2
It is not difficult to verify by direct calculation that F 00 is always nonnegative. This implies, in particular, that F is convex. As a consequence of
this feature, L and σ are also nonnegative.
In standard examples, F , F 0 and F 00 are all of the same order of magni√
tude, and the magnitudes are large. Therefore L is large and σ = O( L),
which implies that the required
sample size is concentrated in the loga√
rithmic scale at exp(L + O( L)). The situation is illustrated through the
following examples.
Example 3.2 (Independent spins). Take some N ≥ 1 and let X = {−1, 1}N .
Let λ be the counting measure on this set, and for x = (x1 , . . . , xN ) ∈ X ,
let
N
X
H(x) = −
xi .
i=1

The Gβ is nothing but the joint law of N i.i.d. random variables that take
value 1 with probability eβ /(eβ + e−β ) and −1 with probability e−β /(eβ +
e−β ). A simple computation gives Z(β) = 2N (cosh β)N . Therefore
F (β) = N log cosh β + N log 2 .
Thus, for any given β0 and β,
L = N log
and

cosh β0
− N (β0 − β) tanh β ,
cosh β

√
σ = 4 N |β0 − β| sech β .

Therefore, L is typically of order N and σ is typically of order

√

N.

18

SOURAV CHATTERJEE AND PERSI DIACONIS

Example 3.3 (1D Ising model with periodic boundary). As in the previous
example, let X = {−1, 1}N and let λ be the counting measure on this set.
For x = (x1 , . . . , xN ) ∈ {−1, 1}N , let
H(x) = −J

N
X
i=1

xi xi+1 − h

N
X

xi ,

i=1

where J ≥ 0, h ∈ R, and xN +1 in the first sum stands for x1 . This is the
Hamiltonian for the one dimensional Ising model for a system of N spins
with periodic boundary. The parameters J and h are traditionally known as
the coupling constant and the strength of the external magnetic field. The
partition function of this model is easily computed by the transfer matrix
method (see Baxter [5]): Z(β) = Tr(V (β)N ), where V (β) is the 2 × 2 matrix
 β(h+J)

e
e−βJ
.
e−βJ
e−β(h−J)
In other words, if λ1 (β) and λ2 (β) are the two eigenvalues of this matrix
(arranged such that |λ1 | ≥ |λ2 |), then
Z(β) = λ1 (β)N + λ2 (β)N .
Consequently,
F (β) = log(λ1 (β)N + λ2 (β)N ) .
It is not hard to verify that
λ1 (β) = eβJ cosh βh +

q
e2βJ (sinh βh)2 + e−2βJ

and
λ2 (β) = eβJ cosh βh −

q
e2βJ (sinh βh)2 + e−2βJ .

Using these formulas it is easy to write down explicit formulas for L and
σ for any given β and β0 , and compute
a(β0 , β) and b(β0 , β) such that as
√
N → ∞, L ∼ N a(β0 , β) and σ ∼ N b(β0 , β).
Examples 3.2 and 3.3 demonstrate how Theorem 3.1 can be applied to
calculate the sample size required for importance sampling in statistical
mechanical models. However, these examples required exact computations
in finite systems, which is rarely possible in complex models. Our next
theorem deals with a generic sequence of models that converge to a limit.
Exact computations are assumed to be possible only in the limit.
Let {XN }N ≥1 be a sequence of spaces equipped with sigma-algebras and
finite measures {λN }N ≥1 . For each N let HN : X → R be a measurable
function, and for each β ∈ R let GN,β be the probability measure that has
probability density proportional to exp(−βHN (x)) with respect to λN . Let
Z
ZN (β) :=
exp(−βHN (x))dλN (x)
XN

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

19

be the normalizing constant of GN,β , and assume that these quantities are
finite. Let
FN (β) := log ZN (β) .
Let {LN }N ≥1 be a sequence of numbers tending to infinity, and let
FN (β)
N →∞ LN
whenever the limit exists and is finite. For a suitable choice of LN depending
on the situation, the function p(β) is sometimes referred to as the thermodynamic limit (or the thermodynamic free energy) of the sequence of systems
described above. The thermodynamic limit is said to have a k th order phase
transition at an inverse temperature β if the first k − 1 derivatives of p are
continuous at β but the k th derivative is discontinuous at β.
Fix two inverse temperatures β0 and β such that β0 < β. The goal is to
estimate FN (β) using importance sampling with a sample of size n from the
Gibbs measure GN,β0 , and determine how fast n needs to grow with N such
that the ratio of this estimate and the true value tends to one as N → ∞.
Recall that the importance sampling estimate of ZN (β) is
p(β) := lim

n

Ẑn,N (β) =

ZN (β0 ) X
exp(−(β − β0 )HN (Xi )) ,
n
i=1

where X1 , . . . , Xn are i.i.d. draws from GN,β0 . The following theorem identifies the sample size required for good performance of the above estimate
as long as the system does not exhibit a first-order phase transition at β in
the thermodynamic limit.
Theorem 3.4. Let all notation be as above. Let {LN }N ≥1 be a sequence of
constants such that the thermodynamic free energy p exists and is differentiable in a neighborhood of β, and exists at β0 . Assume that the derivative p0
is continuous at β, and that there exists a finite constant C such that for all
N and all x ∈ XN , |HN (x)| ≤ CLN . Suppose that the sample size n = n(N )
grows with N in such a way that L−1
N log n converges to a limit b ∈ [0, ∞],
and let
q(β) := p(β0 ) − p(β) − (β0 − β)p0 (β) .
Then the following conclusions hold:
(i) If b > q(β), then Ẑn,N (β)/ZN (β) → 1 in probability as N → ∞.
(ii) If b < q(β), then Ẑn,N (β)/ZN (β) 6→ 1 in probability as N → ∞.
(iii) If b = q(β) and p0 is not constant in any neighborhood of β, then
L−1
N log Ẑn,N (β) → p(β) in probability as N → ∞. Note that this is
a weaker version of the conclusion of part (i).
Theorem 3.4 has potentially much wider applicability than Theorem 3.1,
since thermodynamic limits are known in many important statistical mechanical systems. Classical examples from statistical physics include the 2D
Ising model, the six and eight vertex models, and many others (see Baxter

20

SOURAV CHATTERJEE AND PERSI DIACONIS

[5] and McCoy [44]). Recently, a variety of exponential random graph models have been explicitly ‘solved’ (see Chatterjee and Diaconis [16], Kenyon,
Radin, Ren and Sadun [35], Kenyon and Yin [36] and Bhattacharya, Ganguly, Lubetzky and Zhao [6]). Similar progress has been made for nonuniform distributions on permutations (see Starr [56], Mukherjee [45] and
Kenyon, Kral, Radin and Winkler [34]). All of these models provide examples for our theory.
The main strength of Theorem 3.4 is also its main weakness: While it
gives a definitive answer for exactly solvable models, the theorem is not
useful for systems that are not exactly solvable in a thermodynamic limit.
As discussed in Section 2, what a practitioner really wants is a diagnostic
test that will confirm whether importance sampling has converged. Interestingly, it turns out that the use of the alternative diagnostic test proposed
in Section 2 can be partially justified in the setting of Theorem 3.4, under
one additional assumption. The extra assumption is that the system has
no first-order phase transition at any point between β0 and β, strengthening the assumption made in Theorem 3.4 that there is no first-order phase
transition at β.
Take β0 and β such that β0 < β. Recall the quantities Qn and qn defined
in Section 2. Since there are two parameters n and N involved here, we will
write qn,N and Qn,N instead of qn and Qn . Then note that
Qn,N =

max1≤i≤n exp(−(β − β0 )HN (Xi ))
Pn
.
i=1 exp(−(β − β0 )HN (Xi ))

and qn,N = E(Qn,N ). (Note that qn,N has nothing to do with q(β).) The
following theorem shows that if n is large enough (depending on N ) for
the importance sampling to work, then qn,N is exponentially small in LN .
Otherwise, it is not exponentially small.
Theorem 3.5. Let all notation and assumptions be as in Theorem 3.4.
Additionally, assume that there is an open interval I ⊇ [β0 , β] such that the
thermodynamic free energy p is well-defined and continuously differentiable
in I, and that p0 is not constant in any nonempty open subinterval of I.
Then:
(i) If b ≤ q(β), then
lim

N →∞

log qn,N
= 0.
LN

Moreover, L−1
N log Qn,N → 0 in probability as N → ∞.
(ii) If b > q(β), then
lim sup
N →∞

log qn,N
< 0.
LN

Moreover, there exists c < 0 such that P(L−1
N log Qn,N ≤ c) → 1 as
N → ∞.

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

21

In particular, if n grows with N so fast that qn,N decays to zero like a negative
power of LN , then the estimated free energy L−1
N log Ẑn,N (β) converges to the
correct limit p(β) in probability.
Incidentally, the binomial distribution, as well as more complicated systems like Knuth’s self-avoiding paths, can be put into the framework of
Theorem 3.5 by an appropriate choice of the Hamiltonian and the inverse
temperatures β0 and β, so that the system at inverse temperature β0 gives
the sampling distribution and the system at inverse temperature β gives the
target distribution. The main theoretical question would be to prove the
absence of a phase transition between β0 and β.
4. Proofs
Proof of Theorem 1.1. Suppose that n = eL+t and let a := eL+t/2 . Let
h(x) = f (x) if ρ(x) ≤ a and 0 otherwise. Then
|In (f ) − I(f )| ≤ |In (f ) − In (h)| + |In (h) − I(h)| + |I(h) − I(f )| .
First, note that by the Cauchy–Schwarz inequality,
|I(h) − I(f )| ≤ E(|f (Y )|; ρ(Y ) > a) ≤ kf kL2 (ν)

p
P(ρ(Y ) > a) .

Similarly,
E|In (f ) − In (h)| ≤ E|ρ(X1 )f (X1 ) − ρ(X1 )h(X1 )|
= E(|f (Y )|; ρ(Y ) > a) ≤ kf kL2 (ν)

p
P(ρ(Y ) > a) .

Finally, note that
p
Var(In (h))
r
Var(ρ(X1 )h(X1 ))
=
n
r
E(ρ(X1 )2 h(X1 )2 )
≤
n
r
a E(ρ(X1 )f (X1 )2 )
≤
n
r
a
= kf kL2 (ν)
.
n
Combining the upper bounds obtained above, we get the first inequality in
the statement of the theorem.
Next, suppose that n = eL−t and let a = eL−t/2 . Markov’s inequality
gives
E(ρ(X1 ))
1
P(ρ(X1 ) > a) ≤
= .
(4.1)
a
a
Also,
E|In (h) − I(h)| ≤

E(ρ(X1 ); ρ(X1 ) ≤ a) = P(ρ(Y ) ≤ a) .

22

SOURAV CHATTERJEE AND PERSI DIACONIS

Thus,
P(In (1) ≥ 1 − δ)
 X

n

1
≤ P max ρ(Xi ) > a + P
ρ(Xi )1{ρ(Xi )≤a} ≥ 1 − δ
1≤i≤n
n
i=1
 X

n
n
X
1
1
E
ρ(Xi )1{ρ(Xi )≤a}
≤
P(ρ(Xi ) > a) +
1−δ
n
i=1

i=1

n P(ρ(Y ) ≤ a)
.
≤ +
a
1−δ
This completes the proof of the second inequality in the statement of the
theorem.

Proof of Theorem 1.2. Suppose that n = eL+t and let a = eL+t/2 . Let
r
p
a
b :=
+ 2 P(ρ(Y ) > a) .
n
Then by Theorem 1.1, for any , δ ∈ (0, 1),
P(|In (1) − 1| ≥ ) ≤

b


and

kf kL2 (ν) b
.
δ
Now, if |In (f ) − I(f )| < δ and |In (1) − 1| < , then
P(|In (f ) − I(f )| ≥ δ) ≤

In (f )
− I(f )
In (1)
|In (f ) − I(f )| + |I(f )||1 − In (1)|
≤
In (1)
δ + |I(f )|
<
.
1−

|Jn (f ) − I(f )| =

√
Taking  = b and δ = kf kL2 (ν)  completes the proof of the first inequality
in the statement of the theorem. Note that if  turns out to be bigger than
1, then the bound is true anyway.
Next, suppose that n = eL−t and let a = eL−t/2 . Let f (x) = 1 if ρ(x) ≤ a
and 0 otherwise. Then I(f ) = P(ρ(Y ) ≤ a) and by (4.1),
P(Jn (f ) 6= 1) ≤

n
X

P(ρ(Xi ) > a) ≤

i=1

This completes the proof of the theorem.



Proof of Theorem 1.3. Let
n

Kn :=

n
.
a

1X
In (1A )
=
ρA (Xi ) .
ν(A)
n
i=1

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

23

Suppose that n = eL+t and let a = eL+t/2 . Applying Theorem 1.1 with ρ
replaced by ρA , this gives
r
p
a
E|Kn − 1| ≤
+ 2 P(ρA (Y ) > a | Y ∈ A) ,
n
which is the first assertion of the theorem. The second claim follows similarly.

Proof of Proposition 1.8. Let
1
Z= N
2

X
N p≤j≤N

 
N
,
j

so that
N
j
1A (j) .
2N Z



νA (j) =

To explore the choice of sampling distribution let µ be the Binomial(N, θ)
distribution for fixed 1/2 < θ < 1. Then
X
LA = D(νA kµ) =
log(νA (j)/µ(j))νA (j)
j

1
=− N
2 Z

X

N

j

N −j

log(2 Zθ (1 − θ)

N p≤j≤N

 
N
)
j

log(θ/(1 − θ))
= − log(2 Z(1 − θ) ) −
2N Z
N

N

X
N p≤j≤N

 
N
j
.
j

An identity of de Moivre (see Diaconis and Zabell [22]) shows that for any
k, 0 ≤ k ≤ N ,
 

1 X
N
N
k
j−
= b(k; N, 1/2) .
N
j
2
2
2
k≤j≤N

Thus, since N p is an integer,


Np
N
LA = − log(2 Z(1 − θ) ) − log(θ/(1 − θ))
b(N p; N, 1/2) +
.
2Z
2
N

N

To approximate Z, use an inequality of Bahadur [3], specialized here: Let
1
Np + 1
R = b(N p; N, 1/2)
.
2
N p + 1 − (N + 1)/2
Then
1≤

R
≤ 1 + x−2 ,
Z

where
x=

N p − N/2
p
.
N/4

24

SOURAV CHATTERJEE AND PERSI DIACONIS

For large N and p fixed, this gives
Z ∼ b(N p; N, 1/2)

p
.
2p − 1

Stirling’s formula gives
(pp (1 − p)1−p )N
2N b(N p; N, 1/2) ∼ p
.
2πN p(1 − p)
Putting these approximations into LA , we get
LA ∼ −N log(pp (1 − p)1−p (1 − θ)(θ/(1 − θ))p ) .
The right side, as a function of θ, is minimized when θ = p. Plugging this
in gives the claim.

Proof of Theorem 2.1. Let X be a random variable with law µ. Then note
that
Z ∞
1 = E(ρ(X)) =
P(ρ(X) ≥ t)dt
0

≥

∞ Z
X
k=0

2k+1

2k

Therefore, for any l ≥ 0,
Z 2k+1
min
P(ρ(X) ≥ t)dt ≤
0≤k≤l

2k

P(ρ(X) ≥ t)dt .

l

1 X
l+1
k=0

Z

2k+1

2k

Thus, there exists k ≤ l such that
Z 2k+1
P(ρ(X) ≥ t)dt ≤
2k

P(ρ(X) ≥ t)dt ≤

1
.
l+1

1
.
l+1

Fixing l, take any such k. The above inequality implies that there exists
t ∈ [2k , 2k+1 ] such that
P(ρ(X) ≥ t) ≤

1
.
(l + 1)2k

Now take any  > 0. Let l = [1/3 ], where [1/3 ] is the integer part of 1/3 .
Then there exists k ≤ l and t ∈ [2k , 2k+1 ] such that the above inequality is
satisfied. Let n = [t/2 ] + 1. Then
P( max ρ(Xi ) ≥ 2 n) ≤ nP(ρ(X) ≥ 2 n)
1≤i≤n

≤ nP(ρ(X) ≥ t)
≤

n
3 n
(t + 1)
(2k+1 + 1)
≤ k ≤
≤
≤ 3 .
k
k
(l + 1)2
2
2
2k

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

25

Consequently, for this n,
 X

n
1
2
2
P(vn (f ) ≥ ) ≤ P 2
f (Xi ) ρ(Xi ) ≥ 
n
i=1
 X

n
1
1
2
2
≤ P( max ρ(Xi ) ≥  n) + P
f (Xi ) ρ(Xi ) ≥
1≤i≤n
n

i=1
 X

n
1
≤ 3 +  E
f (Xi )2 ρ(Xi )
n
i=1

= 3 +  E(f (X)2 ρ(X)) = 3 + kf k2L2 (ν) .
−3

To complete the proof, note that n ≤ −2 t ≤ −2 2k+1 ≤ −2 2l+1 ≤ −2 21+ .

Proof of Theorem 2.3. Since 0 ≤ Qn ≤ 1, therefore


qn
qn
+ P Qn ≥
qn = E(Qn ) ≤
2
2


qn
qn Sn
=
+ P Mn ≥
2
2




qn
n
qn n
≤
+ P Sn <
+ P Mn ≥
2
2
4


qn n
qn
+ 2n + P Mn ≥
.
≤
2
4
Suppose that
n ≤

qn
.
8

(4.2)

Then by the previous display,


qn n
qn
P Mn ≥
≥
.
4
4
Let k := [8/qn ] and l := [n/k]. For 1 ≤ j ≤ k, define
Mn,j :=

max
(j−1)l+1≤i≤jl

ρ(Xi ) .

Then for any x ≥ 0,
P(Sn ≥ kx) ≥ P(Mn,j ≥ x for all 1 ≤ j ≤ k)
= (P(Mn,1 ≥ x))k
= (1 − (P(ρ(X1 ) < x))l )k
= (1 − (P(Mn < x))l/n )k
= (1 − (1 − P(Mn ≥ x))l/n )k .

(4.3)

26

SOURAV CHATTERJEE AND PERSI DIACONIS

Since k ≤ 8/qn and l ≥ n/k − 1 ≥ qn n/8 − 1, this gives
P(Sn ≥ kx) ≥ (1 − (1 − P(Mn ≥ x))qn /8−1/n )8/qn .
Suppose that
1
qn
≤
.
n
16

(4.4)

Then the previous equation gives
P(Sn ≥ kx) ≥ (1 − (1 − P(Mn ≥ x))qn /16 )8/qn .
Taking x = qn n/4, assuming (4.2) and (4.4), and using (4.3), gives
P(Sn ≥ 2n) ≥ (1 − (1 − qn /4)qn /16 )8/qn .
Now note that 1 − (1 − y)y/4 is asymptotic to y 2 /4 as y → 0, and is positive
everywhere in the interval (0, 1). Therefore there is a positive constant C1
such that 1 − (1 − y)y/4 ≥ C1 y 2 for all y ∈ [0, 1]. Using this in the above
inequality gives
−1

P(Sn ≥ 2n) ≥ e−8qn

log(C2 /qn )

,

where C2 is a universal constant. By Markov’s inequality, P(Sn ≥ 2n) ≤ n .
Therefore
−1
e−8qn log(C2 /qn ) ≤ n .
This shows that as n → 0, qn must also tend to zero. Using this and the
monotonicity of the map x 7→ (log x)/x for x ≥ e, it is easy to show that
qn ≤

C3 log log(1/n )
,
log(1/n )

where C3 is a universal constant. Note that this holds under (4.2) and
(4.4). The maximum in the statement of the theorem accounts for these
constraints.

Proof of Theorem 3.1. By the integrability condition on H and the dominated convergence theorem, it is easy to see that F is infinitely differentiable.
Moreover, if Y is a random variable with law Gβ , then
F 0 (β) = −E(H(Y ))

(4.5)

F 00 (β) = Var(H(Y )) .

(4.6)

and
The probability density of Gβ with respect to Gβ0 is
ρ(x) =
Therefore

Z(β0 )
exp(−(β − β0 )H(x)) .
Z(β)
n

Ẑn (β)
1X
=
ρ(Xi ) .
Z(β)
n
i=1

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

27

In the notation of Theorem 1.1, this is nothing but In (1). Now note that if
Y ∼ Gβ , then by (4.5) and (4.6),
E(log ρ(Y )) = F (β0 ) − F (β) − (β − β0 )E(H(Y ))
= F (β0 ) − F (β) − (β0 − β)F 0 (β) = L ,
and
Var(log ρ(Y )) = (β0 − β)2 Var(H(Y )) = (β0 − β)2 F 00 (β) = σ 2 .
The proof is now easily completed by an application of Theorem 1.1, together
with Chebychev’s inequality for bounding the tail probabilities occurring in
the statement of Theorem 1.1.

Proof of Theorem 3.4. Let ρN be the probability density of GN,β with respect to GN,β0 . As in the proof of Theorem 3.1, we have
log ρN (x) = FN (β0 ) − FN (β) − (β − β0 )HN (x) .

(4.7)

For each γ, let YN,γ be a random variable with law GN,γ . A simple computation shows that for any bounded measurable function φ : R → R,
d
E(φ(HN (YN,γ ))) = Cov(φ(HN (YN,γ )), HN (YN,γ )) .
dγ
It is an easy fact that if X is a real-valued random variable and f and g
are two increasing functions, then Cov(f (X), g(X)) ≥ 0. From this and the
above identity, it follows that for any bounded increasing function φ,
d
E(φ(HN (YN,γ ))) ≥ 0 .
dγ
In particular, for any t ∈ R, P(HN (YN,γ ) ≥ t) is an increasing function of γ.
This is an important observation that will be used below.
Take any γ such that p is well-defined and differentiable in an open neighborhood of γ. Note that FN is a convex function, since FN00 is nonnegative
by (4.6). Therefore for any h > 0,
FN (γ + h) − FN (γ)
.
h
Consequently, if h is small enough, then
FN0 (γ) ≤

lim sup
N →∞

FN0 (γ)
p(γ + h) − p(γ)
≤
.
LN
h

Taking h → 0, we get
lim sup
N →∞

FN0 (γ)
≤ p0 (γ) .
LN

Similarly,
lim inf
N →∞

FN0 (γ)
≥ p0 (γ) .
LN

28

SOURAV CHATTERJEE AND PERSI DIACONIS

This proves that for all γ in an open neighborhood of β,
FN0 (γ)
= p0 (γ) .
N →∞ LN
lim

Using the monotonicity of FN0 and p0 and the continuity of p0 at β, it is easy
to conclude from the above identity that for any sequence γN → β,
FN0 (γN )
= p0 (β) .
N →∞
LN
lim

(4.8)

By (4.5), note that for any γ
|FN0 (γ)| = |E(HN (YN,γ ))| ≤ CLN .
Therefore
Z

−1/2

β+LN

β

−1/2

FN00 (γ)dγ = FN0 (β + LN
−1/2

Thus, there exists γN ∈ [β, β + LN

) − FN0 (β) ≤ 2CLN .

] such that
3/2

FN00 (γN ) ≤ 2CLN .

(4.9)

Since LN → ∞, therefore γN → β. Hence by (4.5), (4.6), (4.8) and (4.9),


−HN (YN,γN )
F 0 (γN )
= lim N
= p0 (β)
(4.10)
lim E
N →∞
N →∞
LN
LN
and


−HN (YN,γN )
F 00 (γN )
lim Var
= 0.
= lim N 2
N →∞
N →∞
LN
LN
This implies that −HN (YN,γN )/LN → p0 (β) in probability. Therefore, by
our previous observation about the monotonicity of tail probabilities,


−HN (YN,β )
0
lim P
≥ p (β) + δ = 0
N →∞
LN
for any δ > 0. In a similar manner, one can show that


−HN (YN,β )
0
lim P
≤ p (β) − δ = 0 .
N →∞
LN
Thus, −HN (YN,β )/LN → p0 (β) in probability. Consequently,
log ρN (YN,β )
→ p(β0 ) − p(β) − (β0 − β)p0 (β) = q(β)
LN
in probability. The proofs of parts (i) and (ii) are now easily completed by
applying Theorem 1.1. To prove part (iii), take any γ ∈ (β0 , β). Since p0 is

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

29

nonconstant in any neighborhood of β and p0 is an increasing function due
to the convexity of p, therefore p0 (γ) < p0 (β). Thus, by the convexity of p,
q(β) − q(γ) = (β − β0 )(p0 (β) − p0 (γ)) + (β − γ)p0 (γ) + p(γ) − p(β)
≥ (β − β0 )(p0 (β) − p0 (γ)) + (β − γ)(p0 (γ) − p0 (β))
= (γ − β0 )(p0 (β) − p0 (γ)) > 0 .

(4.11)

By part (i) of the theorem, this implies that if b = q(β), then
Ẑn,N (γ)
→1
ZN (γ)
in probability, and therefore
log Ẑn,N (γ)
→ p(γ)
LN

(4.12)

in probability. Now note that for any β 0 ,
Pn
HN (Xi ) exp(−(β 0 − β0 )HN (Xi ))
d
0
i=1
P
≤ CLN .
log
Ẑ
(β
)
=
n,N
n
0
dβ 0
i=1 exp(−(β − β0 )HN (Xi ))
Therefore
| log Ẑn,N (β) − log Ẑn,N (γ)| ≤ CLN (β − γ) .

(4.13)

Since γ is an arbitrary point in (β0 , β), it is now easy to complete the proof
of part (iii) using (4.12), (4.13) and the continuity of p.

Proof of Theorem 3.5. Suppose that {WN }N ≥1 is a sequence of real-valued
random variables and c is a real number. In this proof, we will use the
notation
P- lim inf WN ≥ c
N →∞

to mean that for any  > 0, limN →∞ P(WN ≥ c − ) = 1. Similarly,
P- lim supN →∞ WN ≤ c means that for any  > 0, limN →∞ P(WN ≤ c + ) =
1, and P- limN →∞ WN = c means that both of these hold, that is, WN → c
in probability.
First, suppose that b ≤ q(β). Since p has no interval of linear behavior in
the interval I, therefore the convexity of p implies that p0 is strictly increasing
in I. From this and a variant of (4.11) it is easy to see that in the interval
I ∩ [β0 , ∞), q is continuous and strictly increasing. Moreover, q(β0 ) = 0. It
follows that for any a ∈ [0, q(β)], there exists γ ∈ [β0 , β] such that q(γ) = a.
Therefore, since b ≤ q(β), therefore b = q(γ) for some γ ∈ [β0 , β]. Suppose
that γ > β0 . Then by part (i) and part (iii) of Theorem 3.4,
X

n
1
P- lim
log
exp(−(γ − β0 )HN (Xi ))
N →∞ LN
i=1

= q(γ) + p(γ) − p(β0 ) = (γ − β0 )p0 (γ) .

(4.14)

30

SOURAV CHATTERJEE AND PERSI DIACONIS

Let UN (γ) denote the left-hand side of (4.14), without the limit. Using the
positivity of the second derivative, it is easy to see that UN is a convex
function of γ. Take any γ 0 ∈ (β0 , γ). Then by the convexity of UN , we have
Pn
(X )) exp(−(γ − β0 )HN (Xi ))
max1≤i≤n (−HN (Xi ))
1
i=1 (−H
Pn N i
≥
LN
LN
i=1 exp(−(γ − β0 )HN (Xi ))
0
= UN
(γ)

≥

UN (γ) − UN (γ 0 )
.
γ − γ0

Now let N → ∞ on both sides and apply (4.14), and then let γ 0 → γ on the
right. This gives
P- lim inf
N →∞

max1≤i≤n (−HN (Xi ))
≥ p0 (γ) .
LN

(4.15)

Next, note that
X

n
log
exp(−(β − β0 )HN (Xi ))
i=1

≤ (β − γ) max (−HN (Xi )) + log
1≤i≤n

X
n


exp(−(γ − β0 )H(Xi ))

i=1

By (4.14) and (4.15), this implies that
P- lim sup
N →∞

− log Qn,N
≤ 0.
LN

(4.16)

Note that this inequality was proved under the assumption that γ > β0 .
Next, suppose that γ = β0 . Observe the easy inequality
X

n
log
exp(−(β − β0 )HN (Xi )) ≤ (β − β0 ) max (−HN (Xi )) + log n .
1≤i≤n

i=1

From this and the fact that L−1
N log n → q(β0 ) = 0, it follows that (4.16)
holds even if γ = β0 . Next, note that we trivially have
X



n
log
exp(−(β − β0 )HN (Xi )) ≥ log max exp(−(β − β0 )HN (Xi ))
1≤i≤n

i=1

which is same as
P- lim inf
N →∞

− log Qn,N (β)
≥ 0.
LN

(4.17)

Equations (4.16) and (4.17) prove that if b ≤ q(β), then L−1
N log Qn,N → 0
in probability. Next, note that Qn,N ∈ [0, 1], which implies that E(Qn,N ) ∈
[0, 1] and hence
log E(Qn,N )
≤ 0.
(4.18)
LN

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

On the other hand, Jensen’s inequality gives
E(log Qn,N )
log E(Qn,N )
≥
.
LN
LN

31

(4.19)

It is not difficult to see that since |HN | ≤ CLN and L−1
N log n → b < ∞,
therefore the random variable |L−1
log
Q
|
is
bounded
by a non-random
n,N
N
constant that does not vary with N . Since we already know that
L−1
N log Qn,N → 0
in probability, this shows that
E(log Qn,N )
= 0.
N →∞
LN
Combining this with (4.18) and (4.19), we get
lim

log E(Qn,N )
= 0.
N →∞
LN
This completes the proof of part (i) of the theorem. Next, suppose that
b > q(β). Then note that by Theorem 3.4,
n
ZN (β0 ) X
exp(−(β − β0 )HN (Xi )) = 1 .
(4.20)
P- lim
N →∞ nZN (β)
lim

i=1

Next, let
MN := max exp(−(β − β0 )HN (Xi )) .
1≤i≤n

Since p is continuously differentiable in the interval I and p0 is strictly
increasing, therefore there exists γ ∈ I ∩ (β, ∞) such that b > q(γ). If
MN > exp(LN (β − β0 )p0 (γ)), then
n
X
0
MN ≤
exp(−(β − β0 )HN (Xi ))1{−HN (Xi )>LN p0 (γ)} =: MN
.
i=1

Therefore
0
MN ≤ max{exp(LN (β − β0 )p0 (γ)), MN
}.

(4.21)

Define

0
ZN (β0 )MN
.
(4.22)
nZN (β)
Note that if Y is a random variable with law GN,β , then for any θ > 0,


ZN (β0 )
E(RN ) = E
exp(−(β − β0 )HN (X1 ))1{−HN (X1 )>LN p0 (γ)}
ZN (β)
= P(−HN (Y ) > LN p0 (γ))

RN :=

0

≤ e−θLN p (γ) E(e−θHN (Y ) )
= exp(−θLN p0 (γ) + FN (β + θ) − FN (β)) .
Let
c(θ) := p(β + θ) − p(β) − θp0 (γ) ,

(4.23)

32

SOURAV CHATTERJEE AND PERSI DIACONIS

and choose θ = (γ − β)/2. Then by the strict convexity of p in I,
c(θ) ≤ θ(p0 (β + θ) − p0 (γ)) < 0 .

(4.24)

By (4.23) and Markov’s inequality,


log RN
c(θ)
P
≥
≤ e−LN c(θ)/2 E(RN )
LN
2


LN c(θ)
0
≤ exp −
− θLN p (γ) + FN (β + θ) − FN (β) .
2
Taking logarithm on both sides, dividing by LN and sending N → ∞, we
get


log RN
c(θ)
1
log P
≥
lim sup
< 0.
(4.25)
LN
2
N →∞ LN
In particular,
P- lim sup
N →∞

c(θ)
log RN
≤
.
LN
2

(4.26)

Next, note that


1
ZN (β0 )
0
lim
log
exp(LN (β − β0 )p (γ))
N →∞ LN
nZN (β)
= p(β0 ) − p(β) − b + (β − β0 )p0 (γ)
≤ q(γ) − b .

(4.27)

From (4.21), (4.26) and (4.27) we get




1
ZN (β0 )MN
c(θ)
P- lim sup
log
≤ max q(γ) − b,
.
nZN (β)
2
N →∞ LN

(4.28)

By combining (4.20), (4.28), (4.24) and the fact that q(γ) < b, this shows
that there exists c < 0 such that P(L−1
N log Qn,N ≤ c) → 1 as N → ∞.
Next, let
n
ZN (β0 ) X
VN :=
exp(−(β − β0 )HN (Xi )) .
nZN (β)
i=1

Then VN is nothing but the importance sampling estimate In (1) when the
sampling measure is GN,β0 and the target measure is GN,β . In this setting,
we have already seen in the proof of Theorem 3.4 that the quantity L of
Theorem 1.1 is asymptotic to LN q(β) (to see this, simply combine the equations (4.7) and (4.10)). Combined with the fact that L−1
N log n → b, this
implies that the quantity t of Theorem 1.1 is asymptotic to LN (b − q(β)) in
the present setting.
Next, let Y ∼ GN,β and ρN be the probability density of GN,β with
respect to GN,β0 . The formula (4.7) implies that log ρN (Y ) is asymptotic to
LN (p(β0 ) − p(β)) − (β − β0 )HN (Y ). Combining all of these observations and

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

33

applying Theorem 1.1, it follows that there is a positive constant c (which
may depend on β, β0 and b) such that for all large enough N ,
p
E|VN − 1| ≤ e−cLN + P(−HN (Y ) ≥ LN (p0 (β) + c)) .
Take any θ > 0. Then
0

P(−HN (Y ) ≥ LN (p0 (β) + c)) ≤ e−θLN (p (β)+c) E(e−θHN (Y ) ) .
It is easy to see that log E(e−θHN (Y ) ) is asymptotic to LN (p(β + θ) − p(β)).
Thus, the logarithm of the right-hand side in the above display is asymptotic
to −θcLN + LN (p(β + θ) − p(β) − θp0 (β)). Since p0 is continuous in a
neighborhood of β, we can choose a θ small enough so that θc > p(β +
θ) − p(β) − θp0 (β). Therefore, there exists C1 > 0 such that P(−HN (Y ) ≥
LN (p0 (β) + c)) ≤ e−C1 LN for all large enough N . Combining these steps we
see that there is a positive constant C2 such that E|VN − 1| ≤ e−C2 LN for
all large N , and hence
P(VN < 1/2) ≤ 2e−C2 LN .

(4.29)

Now note that by (4.21),
Qn,N ≤

max{SN , RN }
,
VN

(4.30)

where RN is defined in (4.22) and
SN :=

ZN (β0 )
exp(LN (β − β0 )p0 (γ)) .
nZN (β)

Recall that by (4.25), there are positive constants C3 and C4 such that for
all large enough N ,
P(RN ≥ e−C3 LN ) ≤ e−C4 LN .

(4.31)

Since Qn,N ∈ [0, 1], (4.29), (4.30) and (4.31) imply that
E(Qn,N ) ≤ P(VN < 1/2) + P(RN ≥ e−C3 LN ) + 2 max{SN , e−C3 LN }
≤ 2e−C2 LN + e−C4 LN + 2 max{SN , e−C3 LN } .
However, we have already seen in (4.27) that there is a constant C5 > 0
such that SN ≤ e−C5 LN for all large enough N . Thus,
lim sup L−1
N log E(Qn,N ) < 0.
N →∞

This completes the proof of the theorem.



Acknowledgments. We thank Ben Bond, Brad Efron, Jonathan Huggins,
Don Knuth, Shuangning Li, Art Owen, Daniel Roy and David Siegmund for
helpful comments. We also thank the referees and the associate editor for
many helpful suggestions, and the editorial board of AAP for their patience
with our long delay in submitting the revision.

34

SOURAV CHATTERJEE AND PERSI DIACONIS

References
[1] Agapiou, S., Papaspiliopoulos, O., Sanz-Alonso, D. and Stuart, A. M. (2015). Importance sampling: computational complexity
and intrinsic dimension. arXiv preprint arXiv:1511.06196
[2] Asmussen, S. and Glynn, P. W. (2007). Stochastic simulation: algorithms and analysis. Springer, New York.
[3] Bahadur, R. R. (1960). Some approximations to the binomial distribution function. Ann. Math. Statist., 31, 43–54.
[4] Bassetti, F. and Diaconis, P. (2006). Examples comparing importance sampling and the Metropolis algorithm. Illinois J. Math., 50 nos.
1-4, 67–91.
[5] Baxter, R. J. (1982). Exactly solved models in statistical mechanics.
Academic Press, London.
[6] Bhattacharya, B. B., Ganguly, S., Lubetzky, E. and Zhao, Y.
(2015). Upper tails and independence polynomials in random graphs.
arXiv preprint arXiv:1507.04074
[7] Blanchet, J. and Glynn, P. (2008). Efficient rare-event simulation
for the maximum of heavy-tailed random walks. Ann. Appl. Probab.,
18 no. 4, 1351-1378.
[8] Blanchet, J., Glynn, P. and Leder, K. (2012). On Lyapunov
inequalities and subsolutions for efficient importance sampling. ACM
Trans. Model. Comput. Simul., 22 no. 3, 1104–1128.
[9] Blanchet, J. and Liu, J. (2008). State-dependent importance sampling for regularly varying random walks. Adv. Appl. Probab., 40 no. 4,
1104–1128.
[10] Blanchet, J. and Liu, J. (2010). Efficient importance sampling in
ruin problems for multidimensional regularly varying random walks. J.
Appl. Probab., 47 no. 2, 301–322.
[11] Blitzstein, J. and Diaconis, P. (2010). A sequential importance
sampling algorithm for generating random graphs with prescribed degrees. Internet Math., 6 no. 4, 489–522.
[12] Bousquet-Mélou, M. (2014). On the importance sampling of selfavoiding walks. Combin. Probab. Comput., 23 no. 5, 725–748.
[13] Cappé, O., Moulines, E. and Rydén, T. (2005). Inference in hidden
Markov models. Springer, New York.
[14] Chan, H. P. and Lai, T. L. (2007). Efficient importance sampling for
Monte Carlo evaluation of exceedance probabilities. Ann. Appl. Probab.,
17 no. 2, 440–473.
[15] Chan, H. P. and Lai, T. L. (2011). A sequential Monte Carlo approach to computing tail probabilities in stochastic models. Ann. Appl.
Probab., 21 no. 6, 2315–2342.
[16] Chatterjee, S. and Diaconis, P. (2013). Estimating and understanding exponential random graph models. Ann. Statist., 41 no. 5,
2428–2461.

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

35

[17] Chen, Y., Diaconis, P., Holmes, S. P. and Liu, J. S. (2005).
Sequential Monte Carlo methods for statistical analysis of tables. J.
Amer. Statist. Assoc., 100 no. 469, 109–120.
[18] Chen, Y. and Liu, J. S. (2007). Sequential Monte Carlo methods for
permutation tests on truncated data. Statist. Sinica, 17 no. 3, 857–872.
[19] Del Moral, P. (2004). Feynman-Kac formulae. Genealogical and interacting particle systems with applications. Springer-Verlag, New York.
[20] Del Moral, P. (2013). Mean field simulation for Monte Carlo integration. CRC Press, Boca Raton, FL.
[21] Del Moral, P., Kohn, R. and Patras, F. (2015). A duality formula
for Feynman-Kac path particle models. C. R. Math. Acad. Sci. Paris,
353 no. 5, 465–469.
[22] Diaconis, P. and Zabell, S. (1991). Closed form summation for classical distributions: variations on a theme of de Moivre. Statist. Sci., 6
no. 3, 284–302.
[23] Doucet, A., de Freitas, N. and Gordon, N. (Editors) (2001). Sequential Monte Carlo methods in practice. Springer-Verlag, New York.
[24] Dupuis, P., Spiliopoulos, K. and Wang, H. (2012). Importance
sampling for multiscale diffusions. Multiscale Model. Simul., 10 no. 1,
1–27.
[25] Dupuis, P. and Wang, H. (2004). Importance sampling, large deviations, and differential games. Stoch. Stoch. Rep., 76 no. 6, 481–508.
[26] Efron, B. (2012). Bayesian inference and the parametric bootstrap.
Ann. Appl. Stat., 6 no. 4, 1971–1997.
[27] Freer, C. E., Mansinghka, V. K. and Roy, D. M.
(2010). When are probabilistic programs probably computationally tractable?
Presented at the NIPS Workshop on Monte
Carlo Methods for Modern Applications, 2010. Downloadable at
http://danroy.org/papers/FreerManRoy-NIPSMC-2010.pdf
[28] Gelman, A. and Meng, X.-L. (1998). Simulating normalizing constants: from importance sampling to bridge sampling to path sampling.
Statist. Sci., 13 no. 2, 163–185.
[29] Hammersley, J. M. and Handscomb, D. C. (1965). Monte Carlo
methods. Methuen & Co., Ltd., London.
[30] Hesterberg, T. (1995). Weighted average importance sampling and
defensive mixture distributions. Technometrics, 37 no. 2, 185–194.
[31] Huggins, J. H. and Roy, D. M. (2015). Convergence of Sequential Monte Carlo-based Sampling Methods. arXiv preprint
arXiv:1503.00966
[32] Hult, H. and Nyquist, P. (2016). Large deviations for weighted empirical measures arising in importance sampling. Stoc. Proc. Appl., 126
no. 1, 138–170.
[33] Kahn, H. and Marshall, A. W. (1953). Methods of reducing sample size in Monte Carlo computations. J. Operations Research Soc. of
America, 1 no. 5, 263–278.

36

SOURAV CHATTERJEE AND PERSI DIACONIS

[34] Kenyon, R., Kral, D., Radin, C. and Winkler, P.. (2015). A
variational principle for permutations. arXiv preprint arXiv:1506.02340
[35] Kenyon, R., Radin, C., Ren, K. and Sadun, L. (2014). Multipodal
Structure and Phase Transitions in Large Constrained Graphs. arXiv
preprint arXiv:1405.0599
[36] Kenyon, R. and Yin, M. (2014). On the asymptotics of constrained
exponential random graphs. arXiv preprint arXiv:1406.3662
[37] Knuth, D. E. (1976). Mathematics and computer science: coping with
finiteness. Science, 194 no. 4271, 1235–1242.
[38] Knuth, D. E. (1996). Selected papers on computer science. CSLI Lecture Notes, 59. CSLI Publications, Stanford, CA; Cambridge University
Press, Cambridge.
[39] Lelièvre, T., Rousset, M. and Stoltz, G. (2010). Free energy
computations: A mathematical perspective. World Scientific.
[40] Liu, J. S. (2008). Monte Carlo strategies in scientific computing.
Springer, New York.
[41] Liu, J. S. and Chen, R. (1995). Blind Deconvolution via Sequential
Imputations. J. Amer. Statist. Assoc., 90 no. 430, 567–576.
[42] Madras, N. (1998). Umbrella sampling and simulated tempering. In
Numerical Methods for Polymeric Systems (pp. 19–32). Springer, New
York.
[43] Madras, N. and Piccioni, M. (1999). Importance sampling for families of distributions. Ann. Appl. Probab., 9 no. 4, 1202–1225.
[44] McCoy, B. (2010). Advanced statistical mechanics. Oxford University
Press, Oxford.
[45] Mukherjee, S. (2013). Estimation in exponential families on permutations. arXiv preprint arXiv:1307.0978
[46] Naiman, D. Q. and Wynn, H. P. (1997). Abstract tubes, improved
inclusion-exclusion identities and inequalities and importance sampling.
Ann. Stat., 25 no. 5, 1954–1983.
[47] Owen, A. B. (2005). Multidimensional variation for quasi-Monte
Carlo. In Contemporary multivariate analysis and design of experiments, 49–74, Ser. Biostat., 2, World Sci. Publ., Hackensack, NJ.
[48] Owen, A. B. (2006). Quasi-Monte Carlo for integrands with point
singularities at unknown locations. In Monte Carlo and quasi-Monte
Carlo methods 2004, 403–417, Springer, Berlin.
[49] Owen, A. and Zhou, Y. (1999). Adaptive importance sampling by
mixtures of products of beta distributions. Technical Report No. 1999–
25, Department of Statistics, Stanford University.
[50] Owen, A. and Zhou, Y. (2000). Safe and effective importance sampling. J. Amer. Statist. Assoc., 95, no. 449, 135–143.
[51] Robert, C. P. and Casella, G. (2004). Monte Carlo statistical methods. Second edition. Springer-Verlag, New York.
[52] Rosenbluth, M. N. and Rosenbluth, A. W. (1955). Monte Carlo
calculation of the average extension of molecular chains. J. Chem.

THE SAMPLE SIZE REQUIRED IN IMPORTANCE SAMPLING

37

Phys., 23 no. 2, 356–359.
[53] Shi, J., Siegmund, D. and Yakir, B. (2007). Importance sampling
for estimating p values in linkage analysis. J. Amer. Stat. Assoc., 102
no. 479, 929–937.
[54] Siegmund, D. (1976). Importance sampling in the Monte Carlo study
of sequential tests. Ann. Statist., 4 no. 4, 673–684.
[55] Srinivasan, R. (2002). Importance sampling. Applications in communications and detection. Springer-Verlag, Berlin.
[56] Starr, S. (2009). Thermodynamic limit for the Mallows model on Sn .
J. Math. Phys., 50 no. 9, 095208, 15 pp.
[57] Torrie, G. M. and Valleau, J. P. (1977). Nonphysical sampling distributions in Monte Carlo free-energy estimation: Umbrella sampling.
J. Comput. Phys., 23 no. 2, 187–199.
[58] Whiteley, N., Lee, A. and Heine, K. (2016). On the role of interaction in sequential Monte Carlo algorithms. Bernoulli, 22 no. 1,
494–529.
Department of Statistics
Stanford University
Sequoia Hall, 390 Serra Mall
Stanford, CA 94305
souravc@stanford.edu
diaconis@math.stanford.edu

