Varianzreduktion

Varianzreduktion ist der Oberbegriff für verschiedene Techniken zur Effizienzsteigerung bei Monte-Carlo-Simulationen. Diese wurden zuerst 1955 durch Herman Kahn beschrieben.^[1] Wichtige Varianzreduktionstechniken sind:

• Gemeinsame Zufallszahlen
• Antithetische Variate (antithetic sampling)
• Kontrollvariate (control variates)
• Gewichtete Stichproben (importance sampling)
• Geschichtete Stichproben (stratified sampling)

Das Standardvorgehen bei Monte-Carlo-Simulationen besteht darin, eine gesuchte Größe ${\displaystyle s}$, wie etwa ein Integral, eine komplizierte Summe oder einen unbekannten Parameter einer Wahrscheinlichkeitsverteilung, durch einen Erwartungswert auszudrücken, beispielsweise in der Form

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

mit einer geeigneten reellwertigen Funktion ${\displaystyle f}$ und einer Zufallsvariable ${\displaystyle X}$, für die leicht eine große Anzahl von Realisierungen algorithmisch generiert werden kann, im Allgemeinen mithilfe von Pseudozufallszahlen.

Ist nun ${\displaystyle X_{1},\dotsc ,X_{n}}$ eine solche Stichprobe von unabhängigen Zufallsvariablen, die alle die gleiche Verteilung wie ${\displaystyle X}$ besitzen, so lässt sich ${\displaystyle s}$ für große ${\displaystyle n}$ annähern durch das arithmetische Mittel

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

denn wegen der Linearität des Erwartungswerts gilt ${\displaystyle \operatorname {E} (S_{n})=s}$ und nach dem starken Gesetz der großen Zahlen konvergieren die Näherungen ${\displaystyle S_{n}}$ fast sicher gegen den gesuchten Wert ${\displaystyle s}$.

Die Genauigkeit dieser Schätzung lässt sich mithilfe der Varianz von ${\displaystyle S_{n}}$ messen. Nach der Gleichung von Bienaymé gilt wegen der Unabhängigkeit der ${\displaystyle X_{i}}$ (und damit auch der ${\displaystyle f(X_{i})}$)

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

Die Proportionalität der Varianz zum Kehrwert der Stichprobengröße ${\displaystyle n}$, und damit die Konvergenzordnung ${\displaystyle {\mathcal {O}}\left({\tfrac {1}{\sqrt {n}}}\right)}$ der Standardabweichung von ${\displaystyle S_{n}}$, lässt sich im Allgemeinen nicht weiter verbessern. Aus diesem Grund setzen Verfahren zur Varianzreduktion beim Proportionalitätsfaktor ${\displaystyle \operatorname {Var} (f(X))}$ selbst an, indem sie für konkrete Fälle Möglichkeiten angeben, die Funktion ${\displaystyle f}$ und die Verteilung von ${\displaystyle X}$ so zu wählen, dass dieser möglichst klein wird.

Bei realistischen Anwendungen kann im Allgemeinen die Varianz von ${\displaystyle f(X)}$ nicht exakt berechnet werden, da dann ja nicht einmal der Erwartungswert dieser Zufallsvariable bekannt ist. In diesem Fall kann ${\displaystyle \operatorname {Var} (f(X))}$ mit Hilfe der Stichprobenvarianz

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

geschätzt werden.

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

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