Importance sampling

1. Overview

Importance sampling is a computational technique used when it’s difficult to directly sample from a posterior distribution $p(θ|y)$.
Instead of drawing samples from $p(θ|y)$, we draw from a simpler proposal distribution $g(θ)$, and then reweight the samples to correct for the difference.

It is closely related to rejection sampling and serves as a precursor to the Metropolis algorithm used in MCMC.

---

2. Mathematical idea

We want to compute a posterior expectation:

$E[h(θ)|y] = \int h(θ) p(θ|y) \, dθ$

If we cannot sample directly from $p(θ|y)$, we use another distribution $g(θ)$ from which we can draw samples.

We rewrite the expectation using the ratio between $p$ (target) and $g$ (proposal):

$E[h(θ)|y] = \frac{\int h(θ) q(θ|y)/g(θ) \, g(θ) \, dθ} {\int q(θ|y)/g(θ) \, g(θ) \, dθ}$

where $q(θ|y)$ is an unnormalized posterior, i.e., $q(θ|y) = C \cdot p(θ|y)$ for some constant $C$ that does not depend on $\theta$.

---

3. Monte Carlo estimation

If we draw $S$ samples $θ_1, …, θ_S$​ from $g(θ)$, we can estimate the expectation as:

$E[h(θ)|y] \approx \frac{\frac{1}{S}\sum_{s=1}^S h(θ_s) w(θ_s)} {\frac{1}{S}\sum_{s=1}^S w(θ_s)}$

where $w(θ_s) = \frac{q(θ_s|y)}{g(θ_s)}$

are called importance weights (or importance ratios).

It’s generally best to use the same sample set in both numerator and denominator to reduce sampling variability.

---

4. Choosing a good proposal $g(θ)$

A good proposal distribution $g(θ)$ should be close in shape to the target posterior $p(θ|y)$.
If $h(θ) q(θ|y) / g(θ)$ is roughly constant, the estimator will be accurate.

However, if the importance weights vary too much, the estimator becomes unstable.

Worst case:

• Most weights are tiny, but a few are enormously large.
• This happens when $q(θ|y)$ has heavier tails than $g(θ)$.

---

5. Evaluating accuracy and efficiency

(1) Inspect the weight distribution

• Plot the histogram of log(weights).
• If a few weights dominate (very large compared to the average), the estimate will be unreliable.
• Small weights are not a problem — they have little influence on the result.

---

(2) Effective sample size (ESS)

To measure efficiency, compute:

$S_{\text{eff}} = \frac{1} {\sum_{s=1}^S (\tilde{w}(θ_s))^2}$

where normalized weights are $\tilde{w}(θ_s) = \frac{w(θ_s)}{\sum_{s=1}^S w(θ_s)}$

• A small $S_{\text{eff}}$​ means a few very large weights dominate.
• However, if very large weights occur rarely, $S_{\text{eff}}$ itself becomes noisy—so treat it only as a rough guide.

---

6. Importance Resampling (SIR)

To obtain equally weighted, approximately independent samples, we can perform Importance Resampling (also known as Sampling-Importance-Resampling, SIR).

Algorithm:

1. Draw $S$ samples $θ_1, …, θ_S$​ from $g(θ)$.
2. Compute weights $w(θ_s) = q(θ_s|y)/g(θ_s)$.
3. Resample $k < S$ points from the set ${θ_1,…,θ_S}$
   with probabilities proportional to $w(θ_s)$.
4. Optionally, sample without replacement to avoid duplicates.

---

Sampling with or without replacement

Type	Effect
With replacement	The same few large-weight samples may be drawn repeatedly.
Without replacement	Produces a more balanced sample set when weights are highly uneven.

If weights are fairly uniform, both approaches yield similar results.
If weights vary greatly, sampling without replacement is preferable.

---

7. Uses in Bayesian computation

• Improving analytic approximations:
  Later, importance sampling helps refine analytical posterior approximations.
• Initializing iterative algorithms:
  Importance sampling or resampling can provide good starting points for MCMC.
• Adjusting slightly modified posteriors:
  For example:
  • Replace a Normal distribution with a t-distribution in the 8-schools model.
  • Compute leave-one-out cross-validation efficiently.
  Here, the original posterior acts as an approximation to the modified one.

---

8. Practical understanding — good vs. bad approximations

You can build intuition by trying simple examples:

Example	Quality
$g(θ) = t_3$​, $p(θ) = \text{Normal}(0,1)$	Good approximation (heavy-tailed proposal)
$g(θ) = \text{Normal}(0,1)$, $p(θ) = t_3$	Bad approximation (proposal too light-tailed)

---

9. Key takeaways

Concept	Explanation
Core idea	Draw samples from an easy-to-sample distribution $g(θ)$ and reweight them to approximate the target posterior distribution $p(θ \mid y)$.
Weights	The importance weight for each sample is $w(θ) = \dfrac{q(θ \mid y)}{g(θ)}$​, where $q(θ \mid y)$ is the unnormalized posterior (proportional to $p(θ \mid y)$).
Good proposal	The proposal distribution $g(θ)$ must cover all important regions and both tails of the target posterior $p(θ \mid y)$; otherwise, the approximation will miss key probability mass.
Efficiency measure	Efficiency is measured by the effective sample size, $S_{\text{eff}} = \dfrac{1}{\sum_{s=1}^S \tilde{w}(θ_s)^2}$​, where $\tilde{w}(θ_s)$ are normalized weights. Larger $S_{\text{eff}}$ means higher efficiency.
Applications	Used for posterior approximation, MCMC initialization, and cross-validation corrections.
Pitfall	If $g(θ)$ has too light tails, a few extreme weights dominate the estimate, causing instability and unreliable results.

---

Summary

Importance Sampling estimates posterior expectations by:

1. Sampling from a simpler proposal distribution $g(θ)$,
2. Weighting samples to correct for the difference between $g(θ)$ and $p(θ|y)$.

It’s powerful and conceptually simple but only efficient if the proposal $g(θ)$ closely resembles the target posterior, especially in the tails.