Variance Reduction Techniques

Why This Matters

Monte Carlo estimation has a fundamental limitation: the standard error of the mean decreases as $O(1/\sqrt{n})$. To halve the error, you need four times as many samples. Variance reduction techniques break this bottleneck by using structure in the problem to get more information per sample. In Bayesian inference, reinforcement learning, and simulation, these techniques can reduce computation by orders of magnitude.

Mental Model

Imagine estimating the average height of people in a city by random sampling. Naive: pick people at random. Smarter: sample equal numbers from each neighborhood (stratification). Even smarter: if you know the average income of each neighborhood and income correlates with height, use that information to adjust your estimate (control variates). The idea is always the same: use what you already know to reduce uncertainty in what you do not.

Formal Setup and Notation

We want to estimate $\mu = \mathbb{E}[f(X)]$ where $X \sim p$. The naive Monte Carlo estimator is:

$\hat{\mu}_n = \frac{1}{n} \sum_{i=1}^{n} f(X_i), \quad X_i \sim p \text{ i.i.d.}$

with variance $\mathrm{Var}(\hat{\mu}_n) = \sigma^2 / n$ where $\sigma^2 = \mathrm{Var}(f(X))$. Variance reduction constructs an alternative estimator $\hat{\mu}_n'$ with $\mathrm{Var}(\hat{\mu}_n') < \mathrm{Var}(\hat{\mu}_n)$ while keeping $\mathbb{E}[\hat{\mu}_n'] = \mu$.

Definition

Antithetic Variates

Generate pairs $(X_i, X_i')$ that are negatively correlated but each marginally distributed as $p$. The estimator:

$\hat{\mu}_n^{\text{AV}} = \frac{1}{n} \sum_{i=1}^{n} \frac{f(X_i) + f(X_i')}{2}$

has variance $\frac{1}{n}[\frac{\sigma^2}{2} + \frac{1}{2}\mathrm{Cov}(f(X), f(X'))]$. When $\mathrm{Cov}(f(X), f(X')) < 0$, this variance is less than $\sigma^2/n$.

For example, if $X \sim \text{Uniform}(0,1)$, set $X' = 1 - X$. Then $X'$ is also $\text{Uniform}(0,1)$ but negatively correlated with $X$. If $f$ is monotone, $f(X)$ and $f(1-X)$ are negatively correlated, so the variance drops.

Definition

Control Variates

Let $g(X)$ be a function whose expectation $\mathbb{E}[g(X)] = \mu_g$ is known. The control variate estimator is:

$\hat{\mu}_n^{\text{CV}} = \frac{1}{n} \sum_{i=1}^{n} [f(X_i) - c(g(X_i) - \mu_g)]$

for some coefficient $c$. This is unbiased for any $c$ because $\mathbb{E}[g(X_i) - \mu_g] = 0$. Its variance is:

$\mathrm{Var}(\hat{\mu}_n^{\text{CV}}) = \frac{1}{n}[\sigma^2 - 2c\,\mathrm{Cov}(f,g) + c^2\mathrm{Var}(g)]$

Definition

Stratified Sampling

Partition the sample space into disjoint strata $\Omega_1, \ldots, \Omega_K$ with $P(\Omega_k) = w_k$. Sample $n_k$ points from each stratum (the conditional distribution $p(\cdot | \Omega_k)$) and combine:

$\hat{\mu}^{\text{strat}} = \sum_{k=1}^{K} w_k \hat{\mu}_k, \quad \hat{\mu}_k = \frac{1}{n_k}\sum_{i=1}^{n_k} f(X_i^{(k)})$

This is always at least as good as naive Monte Carlo, and strictly better whenever the stratum means differ.

Definition

Rao-Blackwellization

If $X = (U, V)$ and you can compute $h(u) = \mathbb{E}[f(U,V) | U = u]$ analytically, then replace $f(X_i)$ with $h(U_i)$:

$\hat{\mu}_n^{\text{RB}} = \frac{1}{n} \sum_{i=1}^{n} h(U_i)$

By the law of total variance, $\mathrm{Var}(h(U)) = \mathrm{Var}(f(X)) - \mathbb{E}[\mathrm{Var}(f(X)|U)] \leq \mathrm{Var}(f(X))$. Conditioning out part of the randomness always reduces variance.

Main Theorems

Proposition

Optimal Control Variate Coefficient

Statement

The variance of the control variate estimator $\hat{\mu}^{\text{CV}} = f(X) - c(g(X) - \mu_g)$ is minimized by:

$c^* = \frac{\mathrm{Cov}(f(X), g(X))}{\mathrm{Var}(g(X))}$

The minimum variance is:

$\mathrm{Var}(f - c^*g) = \mathrm{Var}(f)(1 - \rho_{fg}^2)$

where $\rho_{fg}$ is the correlation between $f(X)$ and $g(X)$.

Intuition

The optimal $c^*$ is the regression coefficient of $f$ on $g$. The variance reduction factor is $1 - \rho_{fg}^2$: if $f$ and $g$ are highly correlated ($|\rho_{fg}| \approx 1$), almost all variance is eliminated. The control variate is like subtracting the "explained" part of $f$.

Proof Sketch

$\mathrm{Var}(f - cg) = \mathrm{Var}(f) - 2c\,\mathrm{Cov}(f,g) + c^2 \mathrm{Var}(g)$. This is a quadratic in $c$ with minimum at $c^* = \mathrm{Cov}(f,g)/\mathrm{Var}(g)$. Substitute back to get $\mathrm{Var}(f)(1 - \rho_{fg}^2)$.

Why It Matters

This tells you exactly how powerful a control variate will be: it depends entirely on the correlation $\rho_{fg}$. With $|\rho_{fg}| = 0.99$, you reduce variance by $99\%$, equivalent to using $100\times$ more samples. In practice, you estimate $c^*$ from data, which adds small overhead.

Failure Mode

If $\rho_{fg} \approx 0$, the control variate does nothing. Also, estimating $c^*$ from the same samples introduces a small bias in finite samples (the product of two estimated quantities). With large $n$, this bias is negligible.

Theorem

Rao-Blackwell Theorem (Variance Reduction)

Statement

Let $h(U) = \mathbb{E}[f(U,V) | U]$. Then:

$\mathbb{E}[h(U)] = \mathbb{E}[f(X)]$ $\mathrm{Var}(h(U)) \leq \mathrm{Var}(f(X))$

with equality if and only if $f(X) = h(U)$ almost surely (i.e., $f$ does not actually depend on $V$).

Intuition

By conditioning on $U$, you analytically average out the randomness in $V$. This removes the component of variance due to $V$, leaving only the variance due to $U$. It is like having infinitely many samples of $V$ for each value of $U$.

Proof Sketch

By the law of total variance: $\mathrm{Var}(f(X)) = \mathrm{Var}(\mathbb{E}[f|U]) + \mathbb{E}[\mathrm{Var}(f|U)] = \mathrm{Var}(h(U)) + \mathbb{E}[\mathrm{Var}(f|U)]$. Since $\mathbb{E}[\mathrm{Var}(f|U)] \geq 0$, we get $\mathrm{Var}(h(U)) \leq \mathrm{Var}(f(X))$.

Why It Matters

Rao-Blackwellization is the most principled variance reduction technique: it is guaranteed to help and never hurts. In Gibbs sampling, if you can compute conditional expectations for some variables analytically, always do so. It is free variance reduction.

Failure Mode

The technique requires being able to compute $\mathbb{E}[f|U]$ analytically, which is often intractable. It also requires choosing the partition $(U,V)$ wisely. If $V$ contributes little variance, the reduction is small.

Canonical Examples

Example

Control variate for option pricing

Estimating $\mathbb{E}[\max(S_T - K, 0)]$ for a call option. Use $g(X) = S_T$ (the terminal stock price) as a control variate. Under risk-neutral pricing, $\mathbb{E}[S_T] = S_0 e^{rT}$ is known. Since the payoff is highly correlated with $S_T$, this dramatically reduces variance.

Example

Antithetic variates for integral estimation

Estimate $\int_0^1 e^x \, dx$. Generate $U_i \sim \text{Uniform}(0,1)$ and use pairs $(U_i, 1-U_i)$. Since $e^x$ is increasing, $e^{U_i}$ and $e^{1-U_i}$ are negatively correlated. The estimator $\frac{1}{2}(e^{U_i} + e^{1-U_i})$ has lower variance than $e^{U_i}$ alone.

Common Confusions

Watch Out

Variance reduction does not change the rate

All these techniques reduce the constant in $\mathrm{Var} = C/n$ but keep the $1/n$ rate. You still need $4\times$ samples to halve the error. The improvement is in the constant $C$, which can be enormous in practice but does not change the asymptotic rate.

Watch Out

Control variates require known expectations

The control variate $g$ must have a known mean $\mu_g$. If you have to estimate $\mu_g$, it is no longer a control variate. It becomes an importance sampling or regression adjustment problem.

Summary

• Antithetic variates: use negative correlation between sample pairs
• Control variates: subtract a known-mean quantity correlated with the target; optimal coefficient is $\mathrm{Cov}(f,g)/\mathrm{Var}(g)$
• Stratification: partition the space and sample within strata; always helps
• Rao-Blackwellization: condition out part of the randomness analytically; guaranteed to reduce variance by the law of total variance
• Variance reduction changes the constant, not the $O(1/\sqrt{n})$ rate

Exercises

ExerciseCore

Problem

You want to estimate $\mathbb{E}[e^X]$ where $X \sim N(0,1)$. Explain how to use antithetic variates and why it reduces variance.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Derive the optimal control variate coefficient $c^*$ and show that the variance reduction is $(1 - \rho^2) \cdot \mathrm{Var}(f)$ where $\rho$ is the correlation between $f(X)$ and $g(X)$.

Hint

Reveal Solution

References

Canonical:

• Robert & Casella, Monte Carlo Statistical Methods (2004), Chapter 4
• Ross, Simulation (2012), Chapter 9

Current:

• Owen, Monte Carlo Theory, Methods, and Examples (2013), Chapters 8-9

• Gelman et al., Bayesian Data Analysis (2013), Chapters 10-12

• Brooks et al., Handbook of MCMC (2011), Chapters 1-5

Next Topics

The natural next steps from variance reduction:

• Burn-in and convergence diagnostics: knowing when MCMC samples are usable
• Hamiltonian Monte Carlo: a sampler that naturally has low variance