Variance reduction
Encyclopedia
In mathematics, more specifically in the theory of Monte Carlo method
s, variance reduction is a procedure used to increase the precision of the estimates that can be obtained for a given number of iterations. Every output random variable from the simulation is associated with a variance which limits the precision of the simulation results. In order to make a simulation statistically efficient, i.e., to obtain a greater precision and smaller confidence intervals for the output random variable of interest, variance reduction techniques can be used. The main ones are: Common random numbers, antithetic variates
, control variate
s, importance sampling
and stratified sampling
. Under these headings are a variety of specialized techniques; for example particle transport simulations make extensive use of "weight windows" and "splitting/Russian roulette" techniques, which is a form of importance sampling.
CRN requires synchronization of the random number streams, which ensures that in addition to using the same random numbers to simulate all configurations, a specific random number used for a specific purpose in one configuration is used for exactly the same purpose in all other configurations. For example, in queueing theory, if we are comparing two different configurations of tellers in a bank, we would want the (random) time of arrival of the Nth customer to be generated using the same draw from a random number stream for both configurations.
and 
are the observations from the first and second configurations on the jth independent replication.
We want to estimate
If we perform n replications of each configuration and let
then
and Z(n) = Σ Zj / n is an unbiased estimator of 
.
And since the
's are independent identically distributed random variables,
In case of independent sampling, i.e., no common random numbers used then Cov(X1j, X2j) = 0. But if we succeed to induce an element of positive correlation between X1 and X2 such that Cov(X1j, X2j) > 0, it can be seen from the equation above that the variance is reduced.
It can also be observed that if the CRN induces a negative correlation, i.e., Cov(X1j, X2j) < 0, this technique can actually backfire, where the variance is increased and not decreased (as intended).
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
s, variance reduction is a procedure used to increase the precision of the estimates that can be obtained for a given number of iterations. Every output random variable from the simulation is associated with a variance which limits the precision of the simulation results. In order to make a simulation statistically efficient, i.e., to obtain a greater precision and smaller confidence intervals for the output random variable of interest, variance reduction techniques can be used. The main ones are: Common random numbers, antithetic variates
Antithetic variates
The antithetic variates method is a variance reduction technique used in Monte Carlo methods. Considering that the error reduction in the simulated signal has a square root convergence , a very large number of sample paths is required to obtain an accurate result.-Underlying principle:The...
, control variate
Control variate
The control variates method is a variance reduction technique used in Monte Carlo methods. It exploits information about the errors in estimates of known quantities to reduce the error of an estimate of an unknown quantity.-Underlying principle:...
s, importance sampling
Importance sampling
In statistics, importance sampling is a general technique for estimating properties of a particular distribution, while only having samples generated from a different distribution rather than the distribution of interest. It is related to Umbrella sampling in computational physics...
and stratified sampling
Stratified sampling
In statistics, stratified sampling is a method of sampling from a population.In statistical surveys, when subpopulations within an overall population vary, it is advantageous to sample each subpopulation independently. Stratification is the process of dividing members of the population into...
. Under these headings are a variety of specialized techniques; for example particle transport simulations make extensive use of "weight windows" and "splitting/Russian roulette" techniques, which is a form of importance sampling.
Common Random Numbers (CRN)
The common random numbers variance reduction technique is a popular and useful variance reduction technique which applies when we are comparing two or more alternative configurations (of a system) instead of investigating a single configuration. CRN has also been called Correlated sampling, Matched streams or Matched pairs.CRN requires synchronization of the random number streams, which ensures that in addition to using the same random numbers to simulate all configurations, a specific random number used for a specific purpose in one configuration is used for exactly the same purpose in all other configurations. For example, in queueing theory, if we are comparing two different configurations of tellers in a bank, we would want the (random) time of arrival of the Nth customer to be generated using the same draw from a random number stream for both configurations.
Underlying principle of the CRN technique
Suppose and are the observations from the first and second configurations on the jth independent replication.We want to estimate
If we perform n replications of each configuration and let
then
and Z(n) = Σ Zj / n is an unbiased estimator of .And since the
's are independent identically distributed random variables,In case of independent sampling, i.e., no common random numbers used then Cov(X1j, X2j) = 0. But if we succeed to induce an element of positive correlation between X1 and X2 such that Cov(X1j, X2j) > 0, it can be seen from the equation above that the variance is reduced.
It can also be observed that if the CRN induces a negative correlation, i.e., Cov(X1j, X2j) < 0, this technique can actually backfire, where the variance is increased and not decreased (as intended).