# Variance reduction technique in Monte Carlo integration

I have some trouble understanding the variance reduction method called "Antithetic variables":

Suppose that the integrand is $g(x)=x^2$ and the reference density $f(x)=e^{-x}I_{[0,\infty]}$ is the Exp(1) density. The associated cdf is $$F_X(x)=\{1-e^{-x}\}\mathbb{I}_{[0,\infty]}(x)$$

The antithetic variable method then uses the inverse cdf representation \begin{align*} U&=1-e^{-X}\\ X&=-\log(1-U) \end{align*} where $U~U[0,1]$. To find an antithetic variable, I used \begin{align*}U^*&=1-U\\ 1-U&=1-e^{-X^*}\\X^*&=-\log(U)\end{align*}

Therefore, given $U$, $$Y=-\log(1-U),Y^*=-\log(U)$$ and $Y$ and $Y^*$ are Exp(1) variables. Both can be used in a Monte Carlo integration as e.g. $$\int_0^\infty g(x)f(x)\text(d)x \approx \frac{1}{2n}\sum_{i=1}^n (Y_i+Y^*_i)$$

Please correct me where I'm wrong

• You did nothing wrong, except forgetting the square in $Y_i$ and $Y_i^*$; however you cannot guarantee that $Y_i^2$ and $\{Y_i^*\}^2$ are negatively correlated. Apr 16 '15 at 18:08
• @Xi'an Assuming I was solving this issue in a test without computer assistance, as I see that they are negatively correlated. I need to square $Y_i and Y^*_i$ right? Otherwise I would not be using g (x)
– user72621
Apr 16 '15 at 18:21
• yes, you need $g(Y_i)+g(Y_i^*)$ but again they are not necessarily negatively correlated... Apr 16 '15 at 18:25
• @Xi'an I do not know if I understand it wrong, but there is a condition that they necessarily have to be negatively correlated? How do I check it without computer assistance?
– user72621
Apr 16 '15 at 18:29
• @Xi'an: isn't enough that $\mathrm{Cov}[U,1-U]<0$ and $t\mapsto(\log t)^2$ is monotonically decreasing for $t\in[0,1]$?
– Zen
Apr 16 '15 at 18:39

All the theory you need

$Z\sim F$, and you want to estimate $\mathrm{E}[Z]$.

Let $\sigma^2=\mathrm{Var}[Z]<\infty$.

Simple Monte Carlo

Construct $X_1,X_2,\dots$ IID with $X_1\sim F$.

Define $\bar{X}_n=\frac{1}{n}\sum_{i=1}^n X_i$.

Result: $\mathrm{Var}[\bar{X}_n]=\sigma^2/n$.

Strong Law: $\bar{X}_n\to\mathrm{E}[Z]$ a.s.

Antithetic Variables

Construct $X'_1,X'_2,\dots$ such that, for $i\geq 1$,

1. $X'_i\sim F$;
2. $\mathrm{Cov}[X'_{2i-1},X'_{2i}]<0$;
3. The pairs $(X'_1,X'_2),(X'_3,X'_4) ,\dots$ are IID.

Define $Y_i=(X'_{2i-1}+X'_{2i})/2$ and $\bar{Y}_n=\frac{1}{n}\sum_{i=1}^n Y_i$.

Result: $$\mathrm{Var}[\bar{Y}_n] =\frac{\sigma^2+\mathrm{Cov}[X'_1,X'_2]}{2n} < \frac{\sigma^2}{2n}<\mathrm{Var}[\bar{X}_n].$$

Strong Law: $\bar{Y}_n\to\mathrm{E}[Z]$ a.s.

Define $U_1,U_2,\dots$ IID $\mathrm{U}[0,1]$.

For $i\geq 1$, define $X'_{2i-1}=(\log(1-U_i))^2$ and $X'_{2i}=(\log(U_i))^2$.

Prove 1, 2, 3 above.

Remember that $U_i\sim 1-U_i$, and $\mathrm{Cov}[U_i,1-U_i]<0$.

Also, $x\mapsto (\log x)^2$ is monotonically decreasing for $x\in(0,1]$.

Simulation

n <- 10^6
u <- runif(n)

# simple
x <- (log(1-u))^2
mean(x)
sqrt(var(x)/n)

# antithetic
y <- ((log(1-u))^2 + (log(u))^2)/2
mean(y)
sqrt(var(y)/n)

• In reference I'm using it sets the estimator as $\theta=\int \phi(x)f(x)dx$. In this case $\phi(x)=x^2$ so $\bar{X}_n=\frac{1}{n}\sum_{i=1}^n X_i^2$ right?
– user72621
Apr 16 '15 at 18:25
• @askazy: Yes, think $Z=X^2$.
– Zen
Apr 16 '15 at 18:43
• Friend you can tell me some good reference for these topics: Monte Carlo integration, Control Variates, Antithetic Variables, Hit or Miss, Importance Sampling?
– user72621
Apr 16 '15 at 18:44
• Good Monte Carlo book: amazon.com/Monte-Statistical-Methods-Springer-Statistics/dp/…
– Zen
Apr 16 '15 at 19:29
• – Zen
Apr 16 '15 at 19:30