Simple Sampling

Im einfachsten Fall (einfache Stichprobenentnahme, englisch simple sampling) werden aus dem Ergebnisraum gleichverteilt zufällig Zustände ${\displaystyle Y_{i}\sim {\text{uniform}}(\Omega )}$ für die Stichprobe S ausgewählt. Dann ergibt sich für den geschätzten Mittelwert:

${\displaystyle {\hat {E}}_{X}[f(X)]={\frac {\sum _{y\in S}P(y)\,f(y)}{\sum _{y\in S}P(y)}},}$

wobei die Summation über die zufälligen Realisierungen ${\displaystyle y_{i}\sim Y_{i}}$in der Stichprobe läuft. ${\displaystyle P(y)}$ ist die ursprüngliche Wahrscheinlichkeit(sdichte) für die - durch Simple Sampling erzeugte - Realisierung ${\displaystyle y}$. ${\displaystyle f(y)}$ ist eine Funktionsauswertung.

Grundidee des Importance Sampling mit Beispiel

Der Standardansatz zur Approximation des Erwartungswertes ${\displaystyle \mathbb {E} [X]}$ einer Zufallsvariablen ${\displaystyle X}$ durch Monte-Carlo-Simulation besteht darin, Zufallszahlen ${\displaystyle x_{1},\dots ,x_{n}}$ als Realisierungen stochastisch unabhängiger und identisch verteilter Zufallsvariablen ${\displaystyle X_{1},\dots ,X_{n}}$ mit der Wahrscheinlichkeitsverteilung von ${\displaystyle X}$ zu erzeugen und dann den gesuchten Erwartungswert ${\displaystyle \mathbb {E} [X]}$ durch den Schätzwert

${\displaystyle {\widehat {\mathbb {E} }}[X]={\bar {x}}={\frac {1}{n}}\sum _{i=1}^{n}x_{i}}$

zu approximieren.

Beim Importance Sampling werden stattdessen Zufallszahlen aus einer modifizierten Wahrscheinlichkeitsverteilung mit dem Ziel verwendet, durch eine Varianzreduktion zu rechentechnisch effizienteren Berechnung zu kommen.

Die Grundidee sei an einem einfachen Beispiel veranschaulicht. Die Zufallsvariable ${\displaystyle X}$ mit der Wahrscheinlichkeitsfunktion

${\displaystyle P(X=x)={\begin{cases}{\frac {1}{10}}&{\text{für }}x\in \{-10,10\}\\{\frac {8}{10}}&{\text{für }}x=0\\0&{\text{sonst}}\end{cases}}}$

hat den Erwartungswert ${\displaystyle \mathbb {E} [X]=0}$ und die Varianz ${\displaystyle \mathrm {Var} [X]=20.}$ Der Monte-Carlo-Schätzer ${\displaystyle {\bar {X}}={\frac {1}{100}}\sum _{i=1}^{100}X_{i}}$ für ${\displaystyle \mathbb {E} [X]}$ basierend auf ${\displaystyle n=100}$ Zufallszahlen aus der Verteilung von ${\displaystyle X}$ hat dann die Varianz

${\displaystyle \mathrm {Var} [{\bar {X}}]={\frac {\mathrm {Var} [X]}{100}}={\frac {20}{100}}={\frac {1}{5}}\;.}$

Der Erwartungswert ${\displaystyle \mathbb {E} [X]}$ kann mit den drei Stellen ${\displaystyle x_{(1)}=-10}$, ${\displaystyle x_{(2)}=0}$ und ${\displaystyle x_{(3)}=10}$ und den Wahrscheinlichkeiten ${\displaystyle p_{j}=P(X=x_{(j)})}$ für ${\displaystyle j=1,2,3}$ als

${\displaystyle \mathbb {E} [X]=\sum _{j=1}^{3}x_{(j)}p_{j}=\sum _{j=1}^{3}x_{(j)}{\frac {p_{j}}{w_{j}}}{w_{j}}}$

geschrieben werden. Dabei werden die ${\displaystyle w_{j}}$ so gewählt, dass sie positiv sind und sich zu Eins addieren und damit als Wahrscheinlichkeiten interpretiert werden können.

Für die Zufallsvariable ${\displaystyle Y}$ mit der Wahrscheinlichkeitsfunktion

${\displaystyle P(Y=y)={\begin{cases}w_{j}&{\text{für }}y=x_{j}{\frac {p_{j}}{w_{j}}},\quad j=1,2,3\\0&{\text{sonst}}\end{cases}}}$

gilt dann ${\displaystyle \mathbb {E} [Y]=\mathbb {E} [X]}$ und ${\displaystyle \mathrm {Var} [Y]=\sum _{j=1}^{3}x_{j}^{2}{\frac {p_{j}^{2}}{w_{j}}}}$. Die Varianz von ${\displaystyle Y}$ hängt von den gewählten Wahrscheinlichkeiten ${\displaystyle w_{1},w_{2},w_{3}}$ ab und kann bei geeigneter Wahll erheblich kleiner als die Varianz von ${\displaystyle X}$ sein.

Z. B. ergibt sich für die Wahl ${\displaystyle w_{1}=w_{2}=w_{3}=1/3}$ die Varianz ${\displaystyle \mathrm {Var} [Y]=\sum _{j=1}^{3}x_{j}^{2}{\frac {p_{j}^{2}}{1/3}}=2\cdot 100{\frac {1/100}{1/3}}=6}$ im Vergleich zu ${\displaystyle \mathrm {Var} [X]=20}$. Der Monte-Carlo-Schätzer ${\displaystyle {\bar {X}}={\frac {1}{100}}\sum _{i=1}^{100}X_{i}}$ für ${\displaystyle \mathbb {E} [Y]}$ basierend auf ${\displaystyle n=100}$ Zufallszahlen aus der Verteilung von ${\displaystyle Y}$ hat dann die Varianz

${\displaystyle \mathrm {Var} [{\bar {Y}}]={\frac {\mathrm {Var} [Y]}{100}}={\frac {6}{100}}\;.}$

Durch Zufallszahlenerzeugung mit der Verteilung von ${\displaystyle Y}$ lässt sich also der Erwartungswert ${\displaystyle \mathbb {E} [Y]=\mathbb {E} [X]}$ mit kleinerer Varianz und damit bei gleicher Anzahl ${\displaystyle n}$ von erzeugten Zufallszahlen mit größerer Genauigkeit bestimmen.