Question

The method of antithetic variates is a technique for reducing the variance of simulation estimators. Antithetic variates are negatively correlated random variables with an expected mean and variance. The variance of the average of two antithetic variates is smaller than the variance of the average of two i.i.d. variables. In this exercise, we shall see how to use antithetic variates for importance sampling, but the method is very general. Suppose that we wish to compute \(\smallint \,g\left( x \right)\,\,dx\), and we wish to use the importance function f. Suppose that we generate pseudo-random variables with the p.d.f. f using the integral probability transformation. For \(\,{\bf{i = 1,2,}}...{\bf{,\nu ,}}\,\)let \({{\bf{X}}^{\left( {\bf{i}} \right)}}{\bf{ = }}{{\bf{F}}^{{\bf{ - 1}}}}\left( {{\bf{1 - }}{{\bf{U}}^{\left( {\bf{i}} \right)}}} \right)\), where \({{\bf{U}}^{\left( {\bf{i}} \right)}}\)has the uniform distribution on the interval (0, 1) and F is the c.d.f. Corresponding to the p.d.f. f . For each \(\,{\bf{i = 1,2,}}...{\bf{,\nu ,}}\,\) define

\(\begin{aligned}{l}{{\bf{T}}^{\left( {\bf{i}} \right)}}{\bf{ = }}{{\bf{F}}^{ - {\bf{1}}}}\left( {{\bf{1}} - {{\bf{U}}^{\left( {\bf{i}} \right)}}} \right)\,\,{\bf{.}}\\{{\bf{W}}^{\left( {\bf{i}} \right)}}{\bf{ = }}\frac{{{\bf{g}}\left( {{{\bf{X}}^{\left( {\bf{i}} \right)}}} \right)}}{{{\bf{f}}\left( {{{\bf{X}}^{\left( {\bf{i}} \right)}}} \right)}}\\{{\bf{V}}^{\left( {\bf{i}} \right)}}{\bf{ = }}\frac{{{\bf{g}}\left( {{{\bf{T}}^{\left( {\bf{i}} \right)}}} \right)}}{{{\bf{f}}\left( {{{\bf{T}}^{\left( {\bf{i}} \right)}}} \right)}}\\{{\bf{Y}}^{\left( {\bf{i}} \right)}}{\bf{ = 0}}{\bf{.5}}\left( {{{\bf{W}}^{\left( {\bf{i}} \right)}}{\bf{ + k}}{{\bf{V}}^{\left( {\bf{i}} \right)}}} \right){\bf{.}}\end{aligned}\)

Our estimator of\(\smallint \,{\bf{g}}\left( {\bf{x}} \right)\,\,{\bf{dx}}\)is then\({\bf{Z = }}\frac{{\bf{I}}}{{\bf{\nu }}}\sum\nolimits_{{\bf{i = 1}}}^{\bf{\nu }} {{{\bf{Y}}^{\left( {\bf{i}} \right)}}{\bf{.}}} \).

a. Prove that\({T^{\left( i \right)}}\)has the same distribution as\({X^{\left( i \right)}}\).

b. Prove that\({\bf{E}}\left( {\bf{Z}} \right){\bf{ = }}\smallint \,\,{\bf{g}}\left( {\bf{x}} \right)\,\,{\bf{dx}}\).

c. If\({\bf{g}}\left( {\bf{x}} \right)\,{\bf{/f}}\left( {\bf{x}} \right)\)it is a monotone function, explain why we expect it \({{\bf{V}}^{\left( {\bf{i}} \right)}}\)to be negatively correlated.

d. If \({{\bf{W}}^{\left( {\bf{i}} \right)}}\) and \({{\bf{V}}^{\left( {\bf{i}} \right)}}\)are negatively correlated, show that Var(Z) is less than the variance one would get with 2v simulations without antithetic variates.

Short answer

1. \({F^{ - 1}}\)is a monotone increasing function
2. Use equality of random variables\({X^{\left( i \right)}}\)and\({T^{\left( i \right)}}\)

\(\,E\left( Z \right)\,\,\,\,\,\mathop = \limits^{\left( 1 \right)} \frac{I}{2}\,\,.\,\,2E\left( {{W^{\left( i \right)}}} \right) = \smallint \,g\left( x \right)\,\,dx\)

3. See how\({X^{\left( i \right)}}\)and\({T^{\left( i \right)}}\)behave
4. Compare two variances.

\( - 1 \le \rho \le 1\)

Step-by-step solution

(a) Uniform distribution

This follows directly from the fact that\({U^{\left( i \right)}}\)and\(1 - {U^{\left( i \right)}}\)are from the uniform distribution on (0, 1).

\({F^{ - 1}}\) is a monotone increasing function

(b) Find \({\bf{E}}\left( {\bf{Z}} \right)\) the value

It follows from the importance sampling method as

\(\begin{aligned}{}E\left( Z \right) = E\left( {\frac{I}{\nu }\sum\limits_{I = 1}^\nu {{Y^{\left( i \right)}}} } \right) = 0.5\frac{I}{\nu }\,\,.\,\,\nu E\left( {{W^{\left( i \right)}}} \right) + 0.5\frac{I}{\nu }\,\,.\,\,\nu E\left( {{V^{\left( i \right)}}} \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^{\left( 1 \right)} \frac{I}{2}\,\,.\,\,2E\left( {{W^{\left( i \right)}}} \right) = \smallint \,g\left( x \right)\,\,dx\end{aligned}\)

(1): from (a) \({X^{\left( i \right)}}\) and \({T^{\left( i \right)}}\) have the same distribution, which implies that \({W^{\left( i \right)}}\) and \({V^{\left( i \right)}}\) have the same distribution.

(c) Definition of \({{\bf{X}}^{\left( {\bf{i}} \right)}}\) and \({{\bf{T}}^{\left( {\bf{i}} \right)}}\)

From the definition of\({X^{\left( i \right)}}\)and\({T^{\left( i \right)}}\), because\({F^{ - 1}}\)is a monotone increasing function, when\({X^{\left( i \right)}}\)increases\({T^{\left( i \right)}}\)decrease and opposite.

By the assumption that \(g\left( x \right)/f\left( x \right)\) is a monotone function, the relation between \({W^{\left( i \right)}}\) and \({V^{\left( i \right)}}\) would be the same as the relation between \({X^{\left( i \right)}}\) , which means that when one increases, the other decreases and the opposite, which indicates that the random variables should be negatively correlated.

(d) Find \({\bf{Var}}\left( {\bf{Z}} \right)\) the value

Compare the following two variances. The first variance is

\(\begin{aligned}{}Var\left( Z \right) = Var\left( {\frac{I}{\nu }\sum\limits_{I = 1}^\nu {{Y^{\left( i \right)}}} } \right) = \frac{I}{{{\nu ^2}}}\,\,.\,\nu {0.5^2}\,Var\left( {{W^{\left( i \right)}}\,\, + \,{V^{\left( i \right)}}} \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = 0.25\,\,.\,\,\left( {Var\,\,\left( {{W^{\left( i \right)}}} \right) + Var\,\left( {\,{V^{\left( i \right)}}} \right) + \,\,2\rho } \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \frac{I}{\nu }\,\,.\,\,0.5\,\left( {1 - \rho } \right)\,\,Var\,\left( {{W^{\left( i \right)}}} \right)\end{aligned}\)

The variances are equal (the distribution is the same). The second variance to compare is

\(Var\,\,\left( {\frac{I}{{2\nu }}\sum\limits_{I = 1}^{2\nu } {{W^{\left( i \right)}}} } \right) = \frac{I}{{2\nu }}\,Var\,\,\left( {{W^{\left( i \right)}}} \right).\)

The following is true

\(\frac{I}{\nu }\,\,.\,\,0.5\,\left( {1 - \rho } \right)\,\,Var\,\left( {{W^{\left( i \right)}}} \right) < \frac{I}{{2\nu }}\,Var\,\,\left( {{W^{\left( i \right)}}} \right)\)

if and only if

\(\left( {1 - \rho } \right)\,\, < 1\)

This is true for (remember that which is confirmed by assuming they are negatively correlated.

Here, the result of part (a), part (b), part (c) and part (d)

1. \({F^{ - 1}}\)is a monotone increasing function
2. Use equality of random variables\({X^{\left( i \right)}}\)and\({T^{\left( i \right)}}\)
3. See how\({X^{\left( i \right)}}\)and\({T^{\left( i \right)}}\)behave
4. Compare two variances.