Lesson 3: Replication, Variance Reduction, and Convergence

1 Modelling context

The standard error of a Monte Carlo estimator scales as 1/√N. Reducing it by a factor of 10 requires 100 times as many samples. For expensive simulations, this is often impractical. Variance-reduction techniques offer an alternative: reduce the variance of the estimator itself, without increasing the number of samples.

This lesson covers the design of simulation experiments — the choices about replication, sample allocation, and estimator construction that determine how much information each sample provides. The techniques range from the simple (antithetic variates) to the sophisticated (importance sampling), and each is effective in a different setting.

Efficiency is not the same as accuracy

Variance reduction improves the efficiency of the estimator: the same level of precision at lower cost. It does not improve the underlying model, and it cannot correct a biased estimator. Both accuracy and efficiency matter; the techniques here address the latter.

2 Learning objectives

By the end of this lesson you will be able to

Design a replication scheme for a Monte Carlo experiment.
Apply antithetic variates and explain when they reduce variance.
Apply control variates and explain the role of the correlation with the target.
Explain importance sampling and when it is preferable to naive sampling.
Use common random numbers to compare two configurations efficiently.
Diagnose convergence and choose a sample size for a target precision.

3 Prerequisite review

Covariance and correlation: For two random variables X and Y, Cov(X, Y) = E[XY] − E[X]E[Y] and Corr(X, Y) = Cov(X, Y) / √(Var(X) Var(Y)). Correlation ranges in [−1, 1].
Variance of a sum: Var(X + Y) = Var(X) + Var(Y) + 2 Cov(X, Y). Negative covariance reduces the variance of the sum.
Standard error: SE = s / √N, where s is the sample standard deviation. Reduced by increasing N or reducing s.
Variance reduction factor: The ratio of the variance under naive sampling to the variance under a variance-reduction technique, for the same number of samples. A factor of 100 means 100 times fewer samples are needed for the same precision.

4 Mathematical formulation

Antithetic variates

Suppose we want to estimate θ = E[g(U)] where U ~ Uniform(0, 1). The antithetic variates technique uses pairs (U, 1 − U) and computes

θ̂ = (1/N) Σ [ g(U_i) + g(1 − U_i) ] / 2

where the samples U₁, …, U_N are independent uniform values.

The variance of the antithetic estimator is

Var(θ̂_anti) = [ Var(g(U)) + Cov(g(U), g(1 − U)) ] / (2N)

Compared to the naive variance Var(g(U)) / (2N) — since we use 2N samples in the antithetic case — the antithetic variance is smaller when Cov(g(U), g(1 − U)) < 0. This negative covariance occurs when g is monotone.

Control variates

Suppose we want to estimate θ = E[g(X)], and we have a correlated random variable h(X) whose expectation E[h(X)] = μ_h is known exactly. Define the control-variate estimator:

θ̂_cv = (1/N) Σ [ g(Xᵢ) − β ( h(Xᵢ) − μ_h ) ]

for some coefficient β. The estimator is unbiased for any choice of β. Its variance is

Var(θ̂_cv) = [ Var(g(X)) − 2 β Cov(g(X), h(X)) + β² Var(h(X)) ] / N

The variance-minimising choice is

β* = Cov(g(X), h(X)) / Var(h(X))

which can be estimated from the sample. The reduction in variance is proportional to Corr(g(X), h(X))².

Importance sampling

Suppose we want to estimate θ = E_p[g(X)] where the subscript indicates that X ~ p. If q is a density with the same support as p, then

θ = E_q[ g(X) · p(X) / q(X) ]

The importance-sampling estimator is

θ̂_is = (1/N) Σ g(Xᵢ) · p(Xᵢ) / q(Xᵢ),    Xᵢ ~ q

The ratio w(X) = p(X) / q(X) is the importance weight. If q is chosen to concentrate sampling where g is large, the variance is reduced relative to naive sampling. Choosing q well is the art of importance sampling.

Common random numbers

Suppose we want to compare two configurations A and B of a system, and we want the difference θ_A − θ_B. If the same random stream is used for both, the variance of the difference is

Var(θ̂_A − θ̂_B) = Var(θ̂_A) + Var(θ̂_B) − 2 Cov(θ̂_A, θ̂_B)

Using common random numbers makes the estimates positively correlated, reducing the variance of the difference. This is why simulations comparing two designs should use the same seed for both.

Figure 4.7. Antithetic variates. For a monotone function, the values at u and 1 − u lie on opposite sides of the mean, producing negative correlation and reducing the variance of the average.

Choose the technique that fits

Antithetic variates work for monotone functions. Control variates need a correlated known quantity. Importance sampling needs a good proposal distribution. Common random numbers need two comparable configurations. Each technique has a natural application context.

5 Worked example

Antithetic variates for a monotone integrand

Estimate θ = ∫₀¹ e^{x} dx = e − 1 ≈ 1.71828 using naive and antithetic sampling.

Naive sampling.

Draw N = 1,000 uniform values Uᵢ, compute e^{Uᵢ}, and average:

θ̂_naive = (1/N) Σ e^{Uᵢ}
SE_naive ≈ s / √N

Antithetic sampling.

Draw N = 500 uniform values, and for each compute both e^{Uᵢ} and e^{1−Uᵢ}. Average the 1,000 values:

θ̂_anti = (1/(2N)) Σ [ e^{Uᵢ} + e^{1−Uᵢ} ]

Comparison.

Naive vs antithetic sampling for `∫₀¹ e^x dx`
Method	Estimate	Standard error	Variance reduction
Naive (N = 1,000)	1.7181	0.0024	—
Antithetic (N = 500, 1,000 evals)	1.71830	0.0014	≈ 3.0

The antithetic estimator achieves the same number of function evaluations as the naive estimator, but with a smaller standard error. The variance is reduced by a factor of about 3.

Why it works.

The function e^x is strictly increasing on [0, 1]. When U is small, e^U is small and e^{1−U} is large. When U is large, the reverse holds. The two evaluations are negatively correlated, so their average has a lower variance than the average of two independent evaluations.

6 Verification check

Checks to perform

Compare the reduced variance against the naive variance. The variance-reduction factor should be reported explicitly.
Check that the estimator is still unbiased. The mean of the variance-reduced estimator should equal the true value.
Verify the correlation assumption. For antithetic variates, confirm that the pairs are negatively correlated. For control variates, confirm that the control is positively correlated with the target.
Test with independent seeds. Rerun the simulation with several seeds and confirm the variance-reduced estimator has consistently smaller spread than the naive one.
Check that the technique does not introduce bias. The standard error of the variance-reduced estimator should shrink, but its mean should still equal the true value.

7 Interpretation

Variance reduction is a design activity. The choice of technique depends on the structure of the problem, and the wrong technique can fail to help or even increase the variance.

Antithetic variates work when the target function is monotone in the sampling variable. They are the simplest technique and often give modest but reliable reductions.
Control variates work when a strongly correlated random variable with a known mean is available. The reduction is proportional to the squared correlation, so a strong control can give dramatic gains.
Importance sampling works when the target probability is small or the integrand is concentrated in a small region. Naive sampling rarely hits this region; importance sampling focuses on it.
Common random numbers work when comparing two configurations. The same random stream cancels the random noise common to both, isolating the difference due to the configurations.

Report the variance-reduction factor

The efficiency of a variance-reduction technique is measured by the factor by which it reduces the variance (or equivalently, by the square root of the factor by which it reduces the standard error). Report this factor when describing the technique's effectiveness.

8 Uncertainty and limitations

Variance-reduction techniques carry their own limitations, and their use must be documented.

Limitations of variance-reduction techniques
Technique	Limitation
Antithetic variates	Effective only for monotone functions; can increase variance otherwise
Control variates	Requires a correlated variable with a known mean; `β` must be estimated
Importance sampling	Sensitive to the choice of proposal; poor choice increases variance
Common random numbers	Only applicable to comparative studies with matched inputs
All techniques	Do not reduce structural error; only reduce sampling variance

Efficiency is not accuracy

Variance reduction reduces the standard error of the estimator. It does not fix a biased estimator, and it does not improve the underlying model. A biased estimator with a small variance is still biased.

9 Common implementation errors

Watch for these

Applying antithetic variates to a non-monotone function. If the function is not monotone, the correlation between paired evaluations may be positive, and the technique can increase the variance.
Using the same seed for both naive and antithetic runs. This can obscure the comparison. Use the same seed for the underlying uniform values, but account for the pairing correctly.
Estimating β from the same sample used to compute the estimator. The optimal β depends on Cov(g, h) and Var(h). Using an estimate from the same sample introduces a small bias; larger samples mitigate this.
Choosing a poor proposal in importance sampling. A proposal that does not match the target distribution's shape produces highly variable weights and can increase the variance dramatically.
Applying common random numbers to incompatible configurations. The technique assumes the configurations respond to the same underlying randomness. If the mapping from randomness to output differs, the correlation is weaker than expected.
Reporting the estimate without noting that variance reduction was used. The standard error formula differs for the reduced estimator. The technique must be documented.

10 Independent modelling task

Your turn

Choose a quantity to estimate that can be expressed as E[g(U)] for U ~ Uniform(0, 1) with g monotone.
Implement the naive estimator with N = 1,000 samples. Compute the estimate and the standard error.
Implement the antithetic estimator with N = 500 pairs (equivalently, 1,000 evaluations). Compute the estimate and the standard error.
Compute the variance-reduction factor. Report it.
Repeat the exercise with a non-monotone g of your choice. Does the antithetic technique still help? If not, why not?
For a control-variate example: choose a problem where a correlated variable with a known expectation is available. Estimate β* from a pilot run, apply the control-variate estimator, and report the variance-reduction factor.

This exercise forms the variance-reduction component of Assignment 4.

11 Reflection prompt

Reflect before continuing

Variance-reduction techniques reduce the variance of the estimator. Can they reduce the variance of the model?

Two or three sentences. Consider the difference between sampling error and structural error, and what each technique can and cannot change.

12 Lesson summary

Key takeaways

Variance reduction improves the efficiency of an estimator. It reduces the standard error without increasing the number of samples.
Antithetic variates pair U with 1 − U. They work for monotone functions.
Control variates use a correlated variable with a known mean. The variance reduction is proportional to the squared correlation.
Importance sampling uses a proposal distribution that concentrates sampling where it matters. Effective for rare-event estimation.
Common random numbers use the same random stream for both configurations. Reduce the variance of the difference.
Variance reduction does not fix bias. The estimator must still target the correct quantity.

Module 4 complete

You have defined Monte Carlo estimators, applied them to integrals and probabilities, quantified their sampling error, generated and validated pseudorandom inputs, transformed uniform values to useful distributions, and designed experiments that reduce variance. Module 5 turns to Markov chains and discrete-event simulation — the models for systems that jump between states and systems that queue.

§ Self-quiz, practice, and homework

Practice exercises

For the estimator θ̂ = (1/N) Σ g(Uᵢ), write the antithetic estimator using N/2 pairs. State the variance reduction condition.
Given Corr(g(X), h(X)) = 0.8, compute the variance-reduction factor for the control-variate estimator with the optimal β.
Suppose the naive estimator has a standard error of 0.01. A variance-reduction technique achieves a variance-reduction factor of 4. What is the new standard error?
Explain in two sentences why common random numbers reduce the variance of the difference but not the variance of either individual estimate.

Homework problems

Antithetic variates. For θ = ∫₀¹ e^{−x} dx, implement both the naive and the antithetic estimators. Compute the variance-reduction factor at N = 1,000 and N = 10,000. Confirm the factor is stable across sample sizes. Write a 500-word report.
Control variates. For the same integral, use h(X) = X as a control variate (whose mean on [0, 1] is 0.5). Estimate the optimal β from a pilot run and compute the variance-reduction factor. Compare to the antithetic case.
Importance sampling. Estimate P(Z > 3) for Z ~ Normal(0, 1), using both naive sampling and importance sampling with a shifted normal proposal. Compare the variance-reduction factors and the runtime.
Common random numbers. Compare two configurations of a simple system (e.g. two queueing disciplines) using independent runs versus common random numbers. Report the variance of the difference in each case.

Mini project

Design and implement a variance-reduced Monte Carlo estimator for a quantity of your choice. Choose one of the four techniques, justify the choice in terms of the structure of the problem, estimate the variance-reduction factor, and verify that the estimator is unbiased. Submit the spreadsheet and a two-page technical report. This completes Assignment 4.