Monte Carlo and importance sampling

Summary

Monte Carlo estimates an expectation by averaging sampled contributions; importance sampling changes the sampling law and corrects those contributions. The proposal must cover the relevant target contribution, and useful uncertainty calculations require suitable moment and dependence conditions. Normalized weights, unbiased expectations, and diagnostic effective sample size are different objects.

Plain Monte Carlo

For iid $X_{i} \sim p$ and integrable f, $\overset{μ}{^} = n^{- 1} \sum_{i} f (X_{i})$ is unbiased. If contribution variance $σ^{2}$ is finite, $V a r (\overset{μ}{^}) = σ^{2} / n$ and the iid CLT supports asymptotic normal approximations. The $n^{- 1/2}$ standard-error rate does not remove dimension-dependent variance constants or guarantee superiority over deterministic integration.

Let outcomes be zero and one, target $p = (0.9, 0.1)$ , and $f = (0, 10)$ . Then target mean is one and direct-sampling contribution variance is $0.1 (100) - 1 = 9$ .

Importance sampling

For iid proposal draws from q and known normalized p, use:

E_{p} [f (X)] = E_{q} [f (X) \frac{p ( X )}{q ( X )}] \approx \frac{1}{n} i \sum f (X_{i}) w_{i}, w_{i} = \frac{p ( X _{i} )}{q ( X _{i} )} .

Choose $q = (0.5, 0.5)$ for the fixture. Weights become $(1.8, 0.2)$ and corrected contributions $(0, 2)$ , each appearing with probability one-half. Their mean remains one but variance becomes $0.5 (4) - 1 = 1$ . Draws [0,1,0,1] give ordinary estimate one; exact four-draw estimator variance is $1/4$ , versus $9/4$ under direct sampling. This particular proposal improves variance; other proposals can worsen it or give infinite variance.

Require q positive wherever $p f$ contributes, and integrability of the weighted contribution. Proposal (1,0) misses the nonzero contribution entirely: every estimate is zero although the target mean is one.

Lose the Target Normalizing Constant

New task: Evaluate only $\tilde{p} = 3 p$ .

Picture and change: Use self-normalized estimate $\sum_{i} w_{i} f_{i} / \sum_{i} w_{i}$ so the common factor cancels. This requires target coverage and a positive denominator, plus appropriate convergence conditions.

Check: The four fixture weights are $5.4, 0.6, 5.4, 0.6$ ; numerator and denominator both equal twelve. Dividing only that numerator by four gives three, not the desired expectation one.

Use when: The target density is known only up to a common factor. The ratio is generally finite-sample biased, although consistent under suitable conditions.

Move Proposal Mass toward the Integrand

New task: Replace q with $(0.1, 0.9)$ , keeping p and f fixed.

Picture and change: Recompute weights as $(9, 1/9)$ and corrected contributions as $(0, 10/9)$ .

Check: Contribution mean is still one and variance is $0.9 (10/9)^{2} - 1 = 1/9$ . Old proposal weights cannot be reused.

Use when: Proposal draws can concentrate where the integrand contributes; validate coverage and weighted moments rather than weights alone.

Effective sample size

A diagnostic of nonnegative-weight concentration is:

ESS = \frac{( \sum w _{i} ) ^{2}}{\sum w _{i}^{2}} .

For illustrative weights [1,1,1,1,6], normalized shares are $10%, 10%, 10%, 10%, 60%$ and ESS is $100/40 = 2.5$ . These are sample weight shares, not each sample’s fraction of a general estimate, which also depends on f.

Importance weights

Five draws remain five draws even when unequal weights yield ESS 2.5

Derivation

Read it this way: draw from q, then compute importance ratios. The fifth sample has 60% of total weight, not necessarily 60% of the final estimate. ESS is a concentration diagnostic, not a literal independent sample count. Original illustration follows Owen, Vehtari et al., and Elvira et al..

Check: Why are there five actual draws but only 2.5 effective samples?

Read it this way: Five weights (6,1,1,1,1) sum to 10. ESS is 10 squared divided by 40, or 2.5; the actual draw count stays five.
Does enlarging the first draw create another independent observation?

Equal weights give ESS n; one dominating weight pushes it toward one. This diagnostic cannot reveal missing support, guarantee error bars, or replace weighted-integrand variance checks. It is distinct from autocorrelation-based ESS for dependent Monte Carlo chains.

Where it shows up in ML

Use case	What’s the integral
REINFORCE policy gradient	$\nabla_{θ} E_{π_{θ}} [R]$
Variational inference (ELBO gradient via reparam alternatives)	$\nabla_{ϕ} E_{q_{ϕ}} [lo g p - lo g q]$
Off-policy RL (importance sampling correction)	$E_{π_{behavior}} [\frac{π _{target}}{π _{behavior}} R]$
Bayesian posterior predictive	$\int p (y ∣ θ) p (θ ∣ D) d θ$
Importance-weighted autoencoders (IWAE)	tighter ELBO via $K$ -sample IS

Variance reduction

Control variates: subtract $c (g - E [g])$ while preserving expectation; select c and account for its estimation.
Antithetic variates: preserve each sample’s marginal law; benefit requires suitable negative contribution covariance.
Stratification: sample strata and combine with target mass weights, not an arbitrary unweighted average.
Rao-Blackwellization: conditional expectations reduce variance when their required moments exist.

Common pitfalls

Heavy tails: finite target expectation does not imply finite weighted-contribution variance.
Changing proposals: reuse requires the correct proposal accounting; trajectory likelihood ratios need their specified sequential factorization.
False normal coverage: $\overset{μ}{^} \pm 1.96 \overset{σ}{^} / n$ is an asymptotic iid approximation under suitable moments, not universal finite-sample coverage.
Finite-sample bias: with one draw, self-normalization returns f(X), whose q-expectation need not match the p-expectation.