Verwerfungsmethode

Die Verwerfungsmethode ist eine Methode zur Erzeugung von Zufallszahlen zu einer vorgegebenen Verteilung.

Idee

Beispiel: Der erste Treffer ist hier durch C angedeutet

$F\,$ sei hierbei die Verteilungsfunktion der Verteilung, zu der Zufallszahlen erzeugt werden sollen. $G\,$ sei eine Hilfsverteilungsfunktion, zu der sich auf einfachem Weg – etwa über die Inversionsmethode – Zufallszahlen erzeugen lassen. Es seien ferner $f\,$ und $g\,$ die zugehörigen Dichten.

Um die Verwerfungsmethode anwenden zu können, muss ferner ein konstantes $k > 1\,$ existieren, so dass $f(x) \le k \cdot g(x)$ für jedes $x \in \mathbb{R}$ erfüllt ist. Das $k$ wird benötigt, da die Fläche aller Dichten 1 ist. Ohne $k$ würden sich $f$ und $g$ zwangsläufig schneiden.

Seien nun $u_i\,$ Standardzufallszahlen und $v_i\,$ Zufallszahlen, die der Verteilungsfunktion $G\,$ genügen.

Dann genügt mit $j := \inf \{ n \ge 1 \mid k \cdot u_n \cdot g(v_n) \le f (v_n) \}$ die Zufallsvariable $x := v_j\,$ der Verteilungsfunktion $F\,$ . Man wartet gewissermaßen auf einen ersten Treffer, der unterhalb von $f\,$ liegt.

Fazit

Zur Erzeugung von Zufallszahlen müssen im Mittel $k$ Standardzufallszahlen und $k$ Zufallszahlen, die $G$ genügen, verbraucht werden, bis der erste Treffer erzielt wird. Daher ist es von Vorteil, wenn die Hilfsdichte $g$ die Dichte $f$ möglichst gut approximiert.

Quelle:

Artikel Verwerfungsmethode aus der freien Enzyklopädie Wikipedia mit dieser Versionsgeschichte

Lizenz:

GFDL

Kategorien:

Lexikalischer Artikel