Variance reduction

Variance reduction is the generic term for various techniques for increasing efficiency in Monte Carlo simulations . These were first described in 1955 by Herman Kahn . Important variance reduction techniques are:

• Antithetic Variate ( antithetic sampling )
• Kontrollvariate ( control variates )
• Weighted samples ( importance sampling )
• Stratified sample ( stratified sampling )

Basic idea

The standard procedure in Monte Carlo simulations consists in expressing a desired variable , such as an integral , a complicated sum or an unknown parameter of a probability distribution , in terms of an expected value , for example in the form ${\displaystyle s}$

${\displaystyle s=\operatorname {E} (f(X))}$

with a suitable real-valued function and a random variable for which a large number of realizations can easily be generated algorithmically, generally using pseudo-random numbers . ${\displaystyle f}$ ${\displaystyle X}$

If there is such a sample of independent random variables, all of which have the same distribution as , then the arithmetic mean can be used as an approximation for large ones ${\displaystyle X_{1},\dotsc ,X_{n}}$ ${\displaystyle X}$ ${\displaystyle s}$ ${\displaystyle n}$

${\displaystyle S_{n}={\frac {1}{n}}\sum _{i=1}^{n}f(X_{i})}$,

because because of the linearity of the expected value, and according to the strong law of large numbers , the approximations almost certainly converge to the value sought . ${\displaystyle \operatorname {E} (S_{n})=s}$ ${\displaystyle S_{n}}$ ${\displaystyle s}$

The accuracy of this estimate can be measured using the variance of . According to Bienaymé's equation , because of the independence of (and thus also of ) ${\displaystyle S_{n}}$ ${\displaystyle X_{i}}$ ${\displaystyle f(X_{i})}$

${\displaystyle \operatorname {Var} (S_{n})={\frac {1}{n}}\operatorname {Var} (f(X))}$.

The proportionality of the variance to the reciprocal of the sample size , and thus the order of convergence of the standard deviation of , cannot generally be improved any further. For this reason, methods for variance reduction start with the proportionality factor itself by specifying possibilities for specific cases to choose the function and the distribution of so that it is as small as possible. ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}\left({\tfrac {1}{\sqrt {n}}}\right)}$ ${\displaystyle S_{n}}$ ${\displaystyle \operatorname {Var} (f(X))}$ ${\displaystyle f}$ ${\displaystyle X}$

In the case of realistic applications, the variance of cannot generally be calculated exactly, since then not even the expected value of this random variable is known. In this case, with the help of the sample variance ${\displaystyle f(X)}$ ${\displaystyle \operatorname {Var} (f(X))}$

${\displaystyle {\frac {1}{n-1}}\sum _{i=1}^{n}(f(X_{i})-S_{n})^{2}}$

to be appreciated.

literature

• Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo algorithms . Springer, 2012, ISBN 978-3-540-89140-6 .

Individual evidence

1. ↑ Herman Kahn, Use of different Monte Carlo Sampling Techniques, http://www.rand.org/pubs/papers/2008/P766.pdf