Varianzreduktion

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

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

Grundidee

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

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

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

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

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

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

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

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

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

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

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

geschätzt werden.

Literatur

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