1 Introduction to reducing variance in Monte Carlo …

1 Copyrightc 2007 by Karl Sigman1 Introduction to reducing variance in Monte Carlo Review of confidence intervals for estimating a meanIn statistics, we estimate an unknown mean =E(X) of a distribution by collectingniidsamples from the distribution,X1, .. , Xnand using the sample meanX(n) =1nn j=1Xj.(1)Letting 2=V ar(X) denote the variance of the distribution, we conclude thatV ar(X(n)) = 2n.(2)Thecentral limit theoremasserts that asn , the distribution ofZndef= n (X(n) ) tends toN(0,1), the unit normal distribution. LettingZdenote aN(0,1) rv, we conclude that fornsufficiently large,Zn Zin distribution.

2 From here we obtain for anyz 0,P(|X(n) |> z n) P(|Z|> z) = 2P(Z > z).(We can obtain any value ofP(Z > z) by referring to tables, etc.)For any >0 no matter how small (such as = ), lettingz /2be such thatP(Z >z /2) = /2, we thus haveP(|X(n) |> z /2 n) ,which implies that the unknown mean lies within the intervalX(n) z /2 nwith (approxi-mately) probability 1 .This allows us to constructconfidence intervalsfor our estimate:we say that the intervalX(n) z /2 nis a100(1 )%confidence interval for themean .Typically, we would use (say) = in which casez /2= , and we thusobtain a 95% confidence intervalX(n) ( ) length of the confidence interval is 2( ) nwhich of course tends to 0 as the samplesizengets practice we would not actually know the value of 2; it would be unknown (just as is).

3 But this is not really a problem: we instead use an estimate for it, thesample variances2(n)defined bys2(n) =1n 1n j=1(Xj Xn) can be shown thats2(n) 2, with probability 1, asn and thatE(s2(n)) = 2, n , in practice we would uses(n) is place of when constructing our confidence example, a 95% confidence interval is given byX(n) ( )s(n) following recursions can be derived; they are useful when implementing a simulationrequiring a confidence interval:Xn+1=Xn+Xn+1 Xnn+ 1,S2n+1=(1 1n)S2n+ (n+ 1)(Xn+1 Xn) Application to Monte Carlo simulationIn Monte Carlo simulation, instead of collecting the iid dataX1.

4 , Xn, we simulate , we can choosenas large as we want;n= 10,000 for example, so the central limittheorem justification for constructing confidence intervals can safely be used. Thus we canimmediately obtain confidence intervals for Monte Carlo simulation also allows us to be clever: We can purposely try to induce negative cor-relation among the variablesX1, .. , Xn, or generate copies that while having the same mean,have a smaller variance , so that the variance of the estimator in (1) becomes smaller than 2nresulting in a smaller confidence interval. The idea is to try to get even better estimates byreducing the uncertainty in our estimate.

5 In the next sections, we explore ways of doing Antithetic variates methodLetXidenote our copies ofX(each has the same distribution hence the same mean andvariance 2) but let us not assume that they are independent. Letn= 2m, for somem 1,that is,nis even. Note thatX(n) =12m2m j=1Xj=1mm j=1Yj=Y(m),(3)whereY1=X1+X22Y2=X3+ 1+Xn2,and we conclude thatThe two estimatorsY(m)andX(n)forE(X)in (3) are they are identical, we can and will useY(m) in what follows. Moreover,E(Yi) =E(X) = (remember we are assuming that theXiall have the same distribution hence thesame mean). This means that for purposes of argument here we can view eachYias the end2 copy that we wish to simulate from (instead of theXi).

6 We letY=X1+X22denote a genericYi. The problem of estimation can be re-cast as we are trying to estimate =E(Y) .Computing variances,V ar(Y) = (1/4)( 2+ 2+ 2 Cov(X1, X2))= (1/2)( 2+Cov(X1, X2)).In the case when theXiare iid,Cov(X1, X2) = 0 and thusV ar(Y) = 2/2 yielding (as wealready know, recall (2))V ar(Y(m)) = ifCov(X1, X2)<0, thenV ar(Y)<(1/2) 2yieldingV ar(Y(m))< 2n; variance isreduced. So it is in our interest to somehow create some negative correlation within each pair(X1, X2),(X3, X4), .., but keep the pairs iid so that theYiare iid (and thus the CLT stillapplies); for thenV ar(Y(m)) will be lowered from what it would be if we simply used iid copiesof motivate how we might create the desired negative correlation, recall that we can generatean exponentially distributed rvX1= (1/ ) ln (U) withUuniformly distributed on (0,1).

7 Nowinstead of using a new independent uniform to generate a second such copy, use 1 Uwhichwe well know is also uniformly distributed on (0,1); that is, defineX2= (1/ ) ln (1 U).ClearlyX1andX2are negatively correlated since ifUincreases, then 1 Udecreases and thefunction ln(y) is an increasing function ofy:X1increases iffUincreases iff 1 Udecreases iffX2decreases. More generally, for any distributionF(x) =P(X x) with inverseF 1(y) wecould generate a negatively correlated pair viaX1=F 1(U), X2=F 1(1 U) sinceF 1(y)is a monotone increasing function ofy. The random variablesUand 1 Uhave a correlationcoefficient = 1, they are negatively correlated (to the largest extent), thus the monotonicitypreserves the property of negative correlation; X1,X2<0 (not necessarily 1 though).

8 In a general Monte Carlo simulation ourXis of the formX=h(U1, .. , Uk), for some(perhaps very complicated) functionh, and somek(perhaps large), that is, we needkiidUito generate each copy ofX. For example, if we are consideringX=C2= (122 i=1Si K)+,the payoff at timeT= 2 of an Asian call option under the binomial lattice model, then re-writing122 i=1Si= (1/2)S0Y1[1 +Y2],where theYiare the iid up-down rvs, we haveh(U1, U2) =((1/2)S0(uI{U1 p}+dI{U1> p})[1 + (uI{U2 p}+dI{U2> p})] K)+.This function is monotone decreasing inU1andU2: as either variable increases, they willexceed the valuepand hence the indicators will tend towards the lower valuedas opposedto the higher valueu > d.

9 Because the vectors (U1, U2) and (1 U1,1 U2) are identicallydistributed, so are the rvsX1=h(U1, U2) andX2=h(1 U1,1 U2); in particular they havethe same meanE(X). But the monotonicity ofhresults in negative correlation between them,Cov(X1, X2)< general, as long as the functionhis monotone (either increasing or decreasing) in eachvariable, then it can be shown thatX1=h(U1, .. , Uk) andX2=h(1 U1, .. ,1 Uk) are3indeed negatively correlated, and are referred to asantithetic variates. Again, because thevectors (U1, U2, .. Uk) and (1 U1,1 U2, ..1 Uk) have the same distribution, so doX1andX2; in particular they have the same meanE(X).

10 But because of the induced negativecorrelation (whenhis monotone) the two are themselves negatively correlated copies:Proposition the functionhfor generatingX=h(U1, .. , Uk)is monotone in eachvariable, thenX1=h(U1, .. , Uk)andX2=h(1 U1, .. ,1 Uk)with theUiiid uniform on(0,1)are in fact negatively correlated;Cov(X1, X2)<0.(EquivalentlyE(X1X2)< E(X1)E(X2) =E2(X).)Algorithm for using antithetic variates to estimate =E(X), whenX=h(U1, .. , Uk)ismonotone in theUi:The method of simulating our pairs is straightforward:1. GenerateU1, .. Uk. Construct a first pair: SetX1=h(U1, .. , Uk) andX2=h(1 U1.)