Importance sampling

To estimate ${\mathbb{E}}_f[g(X)]$, sample $Y_1,\dots ,Y_m$ independently from a reference density $h$ whose support covers that of $gf$, and useThe summands have expectation $\int g(x)f(x)dx$, and the strong law of large numbers gives almost-sure convergence under integrability.

For rejection indicators with conditional acceptance $f(X_i)/(Mg(X_i))$, the conditional expectation of $(M/n){\sum }_i{I}_i\varphi (X_i)$ given all proposals is the unnormalized importance estimator. The Rao-Blackwell theorem reduces variance relative to that fixed-denominator estimator. It gives no such automatic comparison with the accepted-sample mean, whose denominator is the random count.

If $f\le Mg$, the importance weight $w=f/g$ is bounded by $M$, and ${\mathbb{E}}_g[{\varphi }^2{w}^2]\le M{\mathbb{E}}_f{\varphi }^2$. A finite target second moment therefore guarantees finite variance and the iid central limit theorem for the unnormalized importance-sampling average. Its proposal-budget variance is ${\mathbb{E}}_g[{\varphi }^2{w}^2]-({\mathbb{E}}_f\varphi {)}^2$.

For $\mu =\int hf$ and $0<A=\int |h|f<\infty$, the proposal $q_{\ast }=|h|f/A$ minimizes the variance of the ordinary unbiased importance sampling estimator. The Cauchy-Schwarz inequality gives $\int h^2{f}^2/q\ge A^2$, so the minimum variance for $n$ independent samples is $(A^2-{\mu }^2)/n$. The proposal need only cover the nonzero integrand.

An importance sampling proposal $q$ must be positive wherever the target-weighted integrand can contribute. The usual sufficient condition is that the target probability is absolutely continuous with respect to $q$. Otherwise multiplying observed draws by $f/q$ cannot recover a missing part of the integral. A strict rejection envelope supplies this condition for the rejected-proposal distribution.

For target density $f$ and proposal density $h$, the importance weight is the density ratio $w(x)=f(x)/h(x)$ wherever the target is supported.

For an unnormalized target density, self-normalized importance sampling uses weights $w_i=f(Y_i)/h(Y_i)$ and estimates expectations by ${\sum }_i{w}_{i}g(Y_i)/{\sum }_i{w}_i$. Resampling a point $Y_i$ with probability proportional to $w_i$ produces the associated weighted empirical distribution.

For estimating $I=\int g(x)f(x)dx$ by the unbiased importance estimator $g(Y)f(Y)/q(Y)$, the proposal minimizing variance isThis follows from the Cauchy-Schwarz inequality. Its normalizing constant and dependence on the particular integrand often make it impractical.

For normalized importance weights $w_i$, the standard effective sample size is $K_{\mathrm{eff}}=1/{\sum }_i{w}_i^2$.