Variance reduction

methods
 Improving the speed of convergence
of the Monte Carlo methods
• Main disadvantage of crude Monte Carlo: slow convergence
→ error decreases as 𝑂 𝜎
ൗ 𝑛
• Modify the method resulting in faster decrease of the variance
→ speed up the computations: achieving a desired accuracy requires less simulation
runs
• Such modifications are called variance reduction
• Aspects to be kept in mind:
➢ Implementing/adapting variance reduction methods requires effort in programming and
mathematical considerations
→ gain should be judged against additional effort
• In the following: outline several possible improvement techniques
 Antithetic variates: the idea
• Idea: combine a random choice of points with a systematic one.
• Main principle: variance reduction by introducing symmetry
• Easiest variance reduction method
• Assume we want to compute 𝐸(𝑓 𝑈 ) with 𝑈 ∼ 𝑈[0, 1]
1
• Crude Monte Carlo estimate: 𝑓 ҧ 𝑈 = σ𝑛𝑖=1 𝑓 𝑈𝑖 with 𝑈𝑖 independent copies of 𝑈
𝑛
• Method of antithetic variates: also use the numbers 1 − 𝑈1 , . . . , 1 − 𝑈𝑛

→ Antithetic Monte Carlo estimator:

𝑛 𝑛
1 1 1
ҧ
𝑓𝑎𝑛𝑡𝑖 𝑈 = ෍ 𝑓 𝑈𝑖 + ෍ 𝑓 1 − 𝑈 𝑖
2 𝑛 𝑛
𝑖=1 𝑖=1
 Variance of the antithetic estimator
• Since 𝑈 and 1 − 𝑈 have the same distribution, both sums on the right-hand side of
the above equation are unbiased estimators for 𝐸(𝑓 (𝑈))
→ the antithetic estimator is also unbiased
• The variance of the antithetic estimator is given by
ҧ 1 Var(𝑓 𝑈 ) 1
Var(𝑓𝑎𝑛𝑡𝑖 𝑈 )= + Cov(𝑓 𝑈 ,𝑓 1 − 𝑈 )
2 𝑛 2𝑛

• Reduction of the variance compared to the crude MC estimator based on 2𝑛 random numbers if
𝑓(𝑈) and 𝑓(1 − 𝑈) are negatively correlated
• Save computational effort: only generate 𝑛 instead of 2𝑛 random numbers
• Proposition: If f is monotone (nondecreasing or nonincreasing), then
𝐶𝑜𝑣(𝑓 (𝑈), 𝑓 (1 − 𝑈)) ≤ 0
 Control variates: the idea
• Idea: For the computation of 𝐸(𝑋), one should try to compute as much as possible
exactly and only compute that part by MC simulation that cannot be avoided
• Assume that a rv 𝑌 is available
• for which 𝐸(𝑌) can be computed known exactly, and
• which is close to 𝑋 (in some sense; e.g., positively correlated to 𝑋)
• Random variable 𝑌 chosen as control variate, i.e., use the relation
𝐸 𝑋 = 𝐸 𝑋 − 𝑌 + 𝐸 𝑌
• Control variate Monte Carlo estimator for 𝐸 𝑋 :
𝑋𝑌 = 𝑋 − 𝑌 + 𝐸(𝑌)
1
and 𝑋ത𝑌 = σ𝑛𝑖=1 𝑋𝑖 − 𝑌𝑖 + 𝐸(𝑌)
𝑛
where 𝑋𝑖 , 𝑌𝑖 are independent copies of 𝑋 and 𝑌
 Variance of the control variate
estimator
• The variance of the control variate estimator is given by
1 1
Var 𝑋ത𝑌 = Var 𝑋 − 𝑌 = (Var 𝑋 + Var 𝑌 − 2Cov 𝑋, 𝑌 )
𝑛 𝑛
• The variance Var 𝑋ത𝑌 is reduced with respect to crude Monte Carlo, if

Var(𝑋) ≥ Var(𝑋 − 𝑌)
or if
2Cov(𝑋, 𝑌) − Var(𝑌) ≥ 0

• The left-hand side of the last expression gives the amount of reduction of Var(𝑋)
 Properties (1)
• If 𝑌 is very close to 𝑋, this can lead to the elimination of nearly all the variance of the crude
Monte Carlo estimator (the closer 𝑌 to 𝑋, the more variance of the CMC is eliminated)

• The efficiency of the control variate depends on the following:

➢ Can we directly simulate the difference 𝑋𝑖 − 𝑌𝑖 as one rv? Meaning that we know its exact
distribution and it is enough to simulate just one random number and use a suitable
transformation

➢ How much additional computation time do we introduce? Do we have to use the inverse
transformation method for both 𝑋𝑖 and 𝑌𝑖 separately (still using the same random number for
both or draw them from their joint distribution)

• How can we find a suitable control variate?

→ Some intuition is needed, not always based on systematic search algorithm
 Example: Integrate 𝑥 2 with control variate 𝑥

1 2
1. Calculate ‫׬‬0 𝑥 𝑑𝑥 via the Monte Carlo method using the control variate method
2. Use the control variate 𝑌~𝑈 0,1 . Hence, 𝑋𝑖 = 𝑌𝑖2
3. Since we know 𝐸 𝑌 = 0.5 we only have to simulate 𝑋𝑖 − 𝑌𝑖 = 𝑌𝑖2 − 𝑌𝑖

See R code !
 Optimizing the control variate (1)
• Can this approach be further improved?

• If 𝑌 is a control variate, 𝑎𝑌 (𝑎 > 0) can also be used as a control variate (due to

the linearity of the expectation)

• For positive 𝑎 it generates a variance reduction if 𝑌 has already lead to a variance

reduction (negative 𝑎 would have increased the variance)
 Optimizing the control variate (2)
Minimize:
Var 𝑋𝑎𝑌 = Var 𝑋 − 𝑎𝑌 = Var 𝑋 + 𝑎2 Var 𝑌 − 2𝑎Cov(𝑋, 𝑌)
Hence
Cov(𝑋, 𝑌)
𝑎∗ =
Var 𝑌
It follows
2
Cov 𝑋, 𝑌 2
Var 𝑋𝑎∗ 𝑌 = Var 𝑋 − = Var 𝑋 (1 − 𝜌𝑋,𝑌 )
Var 𝑌
• Only efficient when 𝜌𝑋,𝑌 near to 1 or −1
• In most cases,Cov 𝑋, 𝑌 and Var 𝑌 will not be known, so need to be simulated as
well (a priori or in parallel)
 Multiple controls
• Use vectors of control variates 𝑌 = (𝑌1 , … , 𝑌 𝑑 )
𝑑 𝑑

𝑋𝑌 = 𝑋 − ෍ 𝑌 𝑖 + ෍ 𝐸(𝑌 𝑖 )
𝑖=1 𝑖=1
• Again unbiased estimator with reduced variance if

Caution: control variates can also decrease performance, so it needs to be chosen with care
Again if every 𝑌 𝑖 is multiplied with 𝑎𝑖 , variance reduction is possible
 Importance sampling (1)
• Idea: direct transformation of the density function of X such that higher probability is
assigned to those values that are important for computing the quantity of interest,
e.g., 𝐸[𝑔(𝑋)]
➢ generate more random numbers in the areas where g has large values
➢ take advantage of knowledge of 𝑔: change the distribution function of the random
variable 𝑋 in a suitable way to avoid changing the value of the expectation

• Consider the Monte Carlo integration

𝑓 𝑥
𝐸𝑔 𝑋 = න 𝑔 𝑥 𝑓 𝑥 𝑑𝑥 = න 𝑔 𝑥 𝑓 ҧ 𝑥 𝑑𝑥 = 𝐸𝑓ҧ 𝑔෤ 𝑋
𝑓ҧ 𝑥
𝑓 𝑥
• The weight function is called the likelihood ratio function
𝑓ҧ 𝑥
Importance sampling (2)
 Importance sampling (3)
• The variance of the importance sampling estimator is given by

• How to choose 𝑓 ҧ ?
 Ways to determine 𝑓 ҧ
ҧ
• 𝑓(𝑥) similar to 𝑓(𝑥)𝑔(𝑥)
ҧ
• 𝑓(𝑥) should be large whenever 𝑔2 (𝑥)𝑓(𝑥) is large
ҧ
• 𝑓(𝑥) should be small whenever 𝑔2 (𝑥)𝑓(𝑥) is small
ҧ
• 𝑓(𝑥) should be easy to evaluate
ҧ
• Random variables with density 𝑓(𝑥) should be easy to simulate
• Optimal 𝑓 ҧ ∗ 𝑥 = |𝑔 𝑥 𝑓 𝑥 | Τ𝐸 𝑔 𝑋 ⟹ if 𝑔 𝑥 ≥ 0 then but
𝐸 𝑔 𝑋 unknown
ҧ
• Several popular ways to determine 𝑓(𝑥)
➢ Shift the density: 𝑓𝜃ҧ 𝑥 = 𝑓 𝑥 + 𝜃
1 𝑥
➢ Scale the density: 𝑓𝜃ҧ 𝑥 = 𝑓
𝜃 𝜃
𝑒 𝜃𝑥
➢ Exponential twisting : 𝑓𝜃ҧ 𝑥 = 𝐸 𝑒 𝜃𝑋
𝑓 𝑥 (Esscher transform)
 Conditional Monte Carlo
• Idea: variance reduction is obtained with the help of a second variable 𝑌 (generated at the same
time as 𝑋) and the use of conditional expectations. Let

• is an unbiased estimator of
• The variance is given by:

One always has a reduction of variance, but it is not always easy to find an appropriate 𝒀.
Stratified sampling (1)
Divide sample space Ω of 𝑋 in 𝑠 different parts (stratas) Ω1 , … , Ω𝑠 (𝑝𝑖 ≔ 𝑃(𝑋𝜖 Ω𝑖 ))
Evaluate 𝑔 𝑋 on each Ω𝑖 separately
Stratified sampling (2)
The variance of the estimator is given by

How to choose ?
Optimal (1)
Optimal (2)