Variance Reduction

Variance Reduction via Coupling

Let $X\sim F,Y\sim G$ for CDFs $F,G$. Estimate $\mathbb{E}\left\{X\pm Y\right\}={\mu }_{\pm }$. For MC Integration, a typical situation is

$$I=\int (g(u)+h(u))f(u)du.$$

But what if we wanted to reduce the Variance of $I_N$?

Set an unbiased estimator $W_{\pm }$ for ${\mu }_{\pm }=\mathbb{E}\left\{X\pm Y\right\}$. The goal is to choose a relationship between $X,Y$ to reduce the variance:

$$\begin{array}{rl}\text{Var}(W_{\pm })& =\text{Var}(X)+\text{Var}(Y)\pm 2\text{Cov}(X,Y)\\ & =\text{Var}(X)+\text{Var}(Y)\pm 2\text{Cov}(F^{-1}(U),G^{-1}(V)).\end{array}$$

If $U,V$ are independent then $\text{Var}(W_{\pm })=\text{Var}(X)+\text{Var}(Y)$. But we can do better by correlating them and thus having a nonzero covariance.

We care about $\pm$ because if we did only one, (i.e $+$) the covariance becomes negative, increasing variance. This requires us to care about both cases simultaneously.

Common Random Numbers (CRN)

Take $U=V$. This reduces $\text{Var}(W_{-})$ since

$$\text{Cov}(F^{-1}(U),G^{-1}(U))\ge 0⟹\text{Var}(W_{-})\le \text{Var}(X)+\text{Var}(Y).$$

Antithetic Variates

Take $V=1-U$. This reduces $\text{Var}(W_{+})$ since

$$\text{Cov}(F^{-1}(U),G^{-1}(1-U))\le 0⟹\text{Var}(W_{+})\le \text{Var}(X)+\text{Var}(Y).$$

Lemma (monotone covariance sign)

Let $U\sim U[0,1]$ and $\alpha ,\beta :[0,1]\to \mathbb{R}$. Then:

• $\text{Cov}(\alpha (U),\beta (U))\ge 0$ if $\alpha ,\beta$ are increasing.
• $\text{Cov}(\alpha (U),\beta (U))\le 0$ if $\alpha$ is increasing and $\beta$ is decreasing.

Remark

$F^{-1},G^{-1}$ are increasing. $G^{-1}(1-U)$ is decreasing. Therefore the lemma applies to the antithetic construction.

Proof:

Let $U,V\sim \mathcal{U}[0,1]$, iid. Assume $\alpha ,\beta$ are increasing functions. Then

$$\begin{array}{rl}0& \le \left[\alpha (U)-\alpha (V)\right]\cdot \left[\beta (U)-\beta (V)\right]\\ & \le \mathbb{E}\left\{(\alpha (U)-\alpha (V))\cdot (\beta (U)-\beta (V))\right\}\\ & =2\mathbb{E}\left\{\alpha (U)\beta (U)\right\}-2\mathbb{E}\left\{\alpha (V)\right\}\mathbb{E}\left\{\beta (V)\right\}\\ & =2\text{Cov}(\alpha (U),\beta (U)).\end{array}$$

We can switch $\mathbb{E}\left\{\alpha (V)\right\}$ to $\mathbb{E}\left\{\alpha (U)\right\}$ by iid. The inequality reverses if $\alpha$ is increasing and $\beta$ is decreasing.