Monte Carlo Estimation and Importance Sampling

Let $X$ be a random variable with target probability mass or density $p(x)$, and let $f(x)$ be an integrable function. The target quantity is

$$I = \mathbb E_{X\sim p}[f(X)] = \sum_x f(x)p(x),$$

or an integral in the continuous case.

The direct Monte Carlo estimator draws $x_1,\ldots,x_T \sim p$ and uses

$$\hat I_{\mathrm{MC}} = \frac{1}{T}\sum_{t=1}^T f(x_t).$$

When the samples are iid and the variance is finite,

$$\mathbb E[\hat I_{\mathrm{MC}}]=I, \qquad \mathrm{Var}(\hat I_{\mathrm{MC}}) = \frac{\mathrm{Var}_p(f(X))}{T}.$$

Importance sampling chooses a proposal $q(x)$ such that $q(x)>0$ whenever $f(x)p(x)$ can be nonzero. Then

$$\begin{aligned} I &= \sum_x f(x)p(x) \\ &= \sum_x f(x)\frac{p(x)}{q(x)}q(x) \\ &= \mathbb E_{X\sim q}\left[f(X)w(X)\right], \end{aligned}$$

where

$$w(x)=\frac{p(x)}{q(x)}.$$

The standard importance-sampling estimator is

$$\hat I_{\mathrm{IS}} = \frac{1}{T}\sum_{t=1}^T f(x_t)w(x_t), \qquad x_t\sim q.$$

It is unbiased under the support and integrability assumptions above. Its variance is

$$\mathrm{Var}(\hat I_{\mathrm{IS}}) = \frac{1}{T} \left( \mathbb E_q[f(X)^2w(X)^2]-I^2 \right).$$

This equation is the whole design problem. A proposal can be algebraically valid and still terrible if $f(x)w(x)$ has heavy tails.

For nonnegative $f$, the ideal proposal is proportional to the target contribution:

$$q^\star(x) = \frac{f(x)p(x)}{\sum_z f(z)p(z)}.$$

Then $f(x)p(x)/q^\star(x)$ is constant on contributing states, so the estimator has zero variance in the finite toy case. In real problems we usually cannot sample exactly from this proposal because its normalizer is the target expectation or something equally hard. But it tells us the direction: sample where the contribution lives, not merely where $p$ is large.

When $p$ is known only up to a normalizing constant, or when estimating posterior ratios, a self-normalized estimator is common:

$$\hat I_{\mathrm{SNIS}} = \sum_{t=1}^T \bar w_t f(x_t), \qquad \bar w_t = \frac{w_t}{\sum_{j=1}^T w_j}.$$

Self-normalization is generally biased at finite $T$, but it is consistent under standard assumptions and often useful in approximate inference.

A quick diagnostic is effective sample size:

$$\mathrm{ESS} = \frac{\left(\sum_{t=1}^T w_t\right)^2} {\sum_{t=1}^T w_t^2}.$$

ESS is high when weights are balanced and low when a few weights dominate. It is a warning light, not the full variance formula: if $q=p$, all weights equal one and ESS is maximal, but $f(X)$ itself may still vary a lot.