Importance Sampling

Importance Sampling estimates $\mathbb{E}_p[f]$ without sampling from $p$ directly: when $p$ is hard to sample, draw from an easy $q$ and reweight,

the weight $w = p/q$ corrects the mismatch between proposal and target; the sample mean $\hat\mu = \frac{1}{n} \sum_{i=1}^{n} f(x_i) w(x_i)$ is unbiased. Its variance is

which explodes (extreme-weight problem) when $q$ has thinner tails than $p$, making the ratio $w$ unbounded.

Bayesian posterior expectations, off-policy reinforcement learning (importance ratio $\pi(a \mid s) / \mu(a \mid s)$), and variance reduction in Monte Carlo integration; interviews often probe the weight formula, variance conditions and the optimal proposal.

expectations without drawing target samples, and one batch of $q$-samples serves many target distributions (off-policy reuse); the theoretically optimal proposal $q^*(x) \propto p(x) |f(x)|$ makes $fw$ constant with zero variance, but its normalization is unknown and it still requires sampling from $p|f|$, so in practice one uses heavy-tailed proposals and monitors the effective sample size $ESS = 1 / \sum_i \hat{w}_i^2$ to guard against weight collapse.

Derive $\mathbb{E}_p[f] = \mathbb{E}_q[f w]$ with weight $w = p/q$; why is the sample-mean estimator unbiased?

What is the variance formula $\mathrm{Var}_q[f w]$? Why does a mismatched $q$ blow up the variance?

What is the optimal proposal? Why does it drive variance to 0, and why can't it be used in practice?

How is the effective sample size $ESS = 1/\sum \hat{w}_i^2$ defined and what does it measure?

Importance sampling vs rejection sampling: estimating expectations vs generating samples; weighted average vs 0/1 acceptance?