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)

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