Variance reduction and unbiased estimators

Definition Let the target be $\theta = \mathbb{E}[Y]$, for example a discounted payoff under a pricing measure $\mathbb{Q}$, with $\mathbb{E}[Y^2] < \infty$. The plain Monte Carlo estimator averages $n$ independent copies of $Y$ and has variance $\operatorname{Var}(Y)/n$. A variance reduction method replaces $Y$ by another random variable $\tilde Y$, built from the same model inputs, with

and averages independent copies of $\tilde Y$. Suppose one copy of $Y$ costs $c$ units of computing work and one copy of $\tilde Y$ costs $\tilde c$. Ignoring the rounding of the number of copies, a budget $C$ buys $C/c$ or $C/\tilde c$ copies, so the two estimators have variances $c \operatorname{Var}(Y)/C$ and $\tilde c \operatorname{Var}(\tilde Y)/C$, and the method is more efficient exactly when

The standard error is the sample standard deviation of the independent copies divided by the square root of their number, and it measures sampling error only. If instead $\mathbb{E}[\tilde Y] = \theta + \delta$ with $\delta \neq 0$, the average of $n$ independent copies has mean squared error $\operatorname{Var}(\tilde Y)/n + \delta^2$, which never falls below $\delta^2$, however large $n$ is.

Definition Let $Z$ be a random vector in $\mathbb{R}^d$ whose law is symmetric, meaning that $-Z$ has the same law as $Z$, for example a vector of independent standard normals that drives a simulated path. Let $Y = g(Z)$ with $\mathbb{E}[g(Z)^2] < \infty$. The antithetic estimator from one pair is

Since $g(-Z)$ has the same law as $g(Z)$, linearity gives $\mathbb{E}[Y_A] = \mathbb{E}[g(Z)]$, so the pair average is unbiased for every such $g$. With $c_A = \operatorname{Cov}\bigl(g(Z), g(-Z)\bigr)$ its variance is

Two independent evaluations averaged have variance $\tfrac12 \operatorname{Var}(g(Z))$, so at the same number of payoff evaluations the pair is better exactly when $c_A < 0$, no better when $c_A = 0$ and worse when $c_A > 0$. In one dimension, if $g$ is monotone, then $c_A \le 0$. To see this, let $Z'$ be an independent copy of $Z$ and $h(z) = g(-z)$. Expanding the product gives

and because $g$ and $h$ are monotone in opposite directions, the two differences never have the same strict sign, so the product is never positive. For payoffs of many inputs, or payoffs that are not monotone, the sign of $c_A$ has to be checked separately. The standard error comes from $n$ independent pairs, with the $n$ pair averages as the observations, not from the $2n$ dependent evaluations.

Definition Let $Y$ be the target with $\mathbb{E}[Y^2] < \infty$, and let $X$ be a control with $\mathbb{E}[X^2] < \infty$ whose mean $\mu_X = \mathbb{E}[X]$ is known exactly, under the same measure that defines $\theta = \mathbb{E}[Y]$. For a constant $\beta$, the control variate estimator from one draw of $(Y, X)$ is

The subtracted term has mean zero, so $\mathbb{E}[Y_C] = \theta$ for every fixed $\beta$, and

The same argument covers a coefficient $\hat\beta$ estimated from an independent pilot sample, provided $\mathbb{E}[\lvert \hat\beta \rvert] < \infty$. Conditional on the pilot, the coefficient is a constant, so the conditional mean is $\theta$ and the conditional variance is the formula above with $\beta = \hat\beta$. A coefficient fitted on the same draws it is applied to is not covered by this argument, and the resulting estimator is in general biased for finite $n$. Correcting that bias lies beyond this lesson. A control mean that is only approximate, say $m \neq \mu_X$, moves the mean of the estimator to $\theta - \beta(\mu_X - m)$, a bias that no number of draws removes.

Definition Suppose in addition that $\operatorname{Var}(X) > 0$. The variance $v(\beta) = \operatorname{Var}(Y_C)$ is then a strictly convex quadratic in $\beta$, and completing the square gives

with the unique minimizer

and the minimum

The last form needs $\operatorname{Var}(Y) > 0$ as well, so that the correlation $\rho = \operatorname{Corr}(Y, X)$ is defined. The coefficient $\beta_*$ is the slope of the population linear regression of $Y$ on $X$, in payoff units per control unit. Since $v(\beta) - v(0) = \operatorname{Var}(X)\, \beta\, (\beta - 2\beta_*)$, every $\beta$ strictly between $0$ and $2\beta_*$ lowers the variance when $\operatorname{Cov}(Y, X) \neq 0$, and $\beta = 2\beta_*$ gives back exactly $\operatorname{Var}(Y)$. In practice $\beta_*$ is unknown and is estimated, from an independent pilot sample when exact unbiasedness is required.

Definition Let the model inputs $X$ have a density $p$ on $\mathbb{R}^d$ under the pricing measure, and let $\theta = \mathbb{E}_p[f(X)]$ with $\mathbb{E}_p[\lvert f(X) \rvert] < \infty$, where $\mathbb{E}_p$ and $\mathbb{E}_q$ denote expectations when $X$ has density $p$ or $q$. Let $q$ be a proposal density with $q(x) > 0$ wherever $f(x)\,p(x) \neq 0$. Then

where the last two integrals run over the set $\{q > 0\}$, which contains every point where $fp \neq 0$, and $w = p/q$ is the importance weight of the next card. The importance sampling estimator draws $X_1, \dots, X_n$ independently from $q$ and averages $f(X_i)\, w(X_i)$, so it is unbiased under the support and integrability conditions alone. Its variance per draw is

which can be smaller or larger than the plain variance $\operatorname{Var}_p(f(X))$, and can even be infinite. The usual standard error and normal confidence interval need it to be finite. For a nonnegative $f$ with $\theta > 0$, the proposal $q = fp/\theta$ would give zero variance, but it needs $\theta$ itself, so it guides the choice of $q$ rather than being a method.

Definition The importance weight, or likelihood ratio, of a target density $p$ relative to a proposal density $q$ is

It is dimensionless and nonnegative, and $\mathbb{E}_q[w(X)]$ equals the target probability of the set $\{q > 0\}$, which is $1$ when $q > 0$ wherever $p > 0$. For the standard normal target $\varphi$ and the shifted proposal $\varphi(\cdot - a)$,

so $w(z) = e^{-az + a^2/2}$. Its second moment under the proposal is $\mathbb{E}_q[w^2] = \mathbb{E}_p[w] = e^{a^2}$, so the weights have variance $e^{a^2} - 1$, which grows very fast with the shift. In path form, let $\widetilde W$ be a Brownian motion under a sampling measure $\widetilde{\mathbb{Q}}$ and simulate the driver $W_t = \widetilde W_t + at$. The density

makes $W$ a Brownian motion under $\mathbb{Q}$ by Girsanov’s theorem, and Novikov’s condition holds because $a$ is constant. This is the convention of Exponential martingales and measure changes with the tilt $\lambda = a$, and at $T = 1$, with $Z = W_1$, it is exactly the weight above, since $-a\widetilde W_1 - a^2/2 = -aZ + a^2/2$.