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:

• 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} und einer Zufallsvariable Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} , für die leicht eine große Anzahl von Realisierungen algorithmisch generiert werden kann, im Allgemeinen mithilfe von Pseudozufallszahlen.

Ist nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_1, \dotsc, X_n} eine solche Stichprobe von unabhängigen Zufallsvariablen, die alle die gleiche Verteilung wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} besitzen, so lässt sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} für große Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{E}(S_n) = s} und nach dem starken Gesetz der großen Zahlen konvergieren die Näherungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} fast sicher gegen den gesuchten Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} .

Die Genauigkeit dieser Schätzung lässt sich mithilfe der Varianz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} messen. Nach der Gleichung von Bienaymé gilt wegen der Unabhängigkeit der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X_i} (und damit auch der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(X_i)} )

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}\left(\tfrac{1}{\sqrt{n}}\right)} der Standardabweichung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} , lässt sich im Allgemeinen nicht weiter verbessern. Aus diesem Grund setzen Verfahren zur Varianzreduktion beim Proportionalitätsfaktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{Var}(f(X))} selbst an, indem sie für konkrete Fälle Möglichkeiten angeben, die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} und die Verteilung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} so zu wählen, dass dieser möglichst klein wird.

Bei realistischen Anwendungen kann im Allgemeinen die Varianz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(X)} nicht exakt berechnet werden, da dann ja nicht einmal der Erwartungswert dieser Zufallsvariable bekannt ist. In diesem Fall kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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.