Verwerfungsmethode

Die Verwerfungsmethode oder Rückweisungsmethode (auch Acceptance-Rejection-Verfahren; engl. rejection sampling) ist eine Methode, um aus Standardzufallszahlen – das sind Realisierungen stochastisch unabhängiger, auf dem Einheitsintervall gleichverteilter Zufallsvariablen – Zufallszahlen aus anderen Wahrscheinlichkeitsverteilungen zu erzeugen. Sie geht auf John von Neumann zurück. Sie kann genutzt werden, wenn die Inversion der Verteilungsfunktion nicht möglich oder zu aufwendig ist.

Idee

$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 zudem ein konstantes $k\in ℝ$ existieren, so dass $f(x)\le k\cdot g(x)$ für jedes $x\in ℝ$ erfüllt ist. Das $k$ wird benötigt, da die Fläche unter einer Dichtefunktion immer 1 ist. Ohne den Vorfaktor $k$ gäbe es deshalb zwangsläufig Stellen mit $f(x)>g(x)$.

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)<f(v_n)\}$ die Zufallszahl $x:=v_j$ der Verteilungsfunktion $F$. Man wartet gewissermaßen auf einen ersten Treffer, der unterhalb von $f$ liegt.

Anders gesagt: Es werden Zufallszahlen $v_i$ nach der Verteilungsfunktion $G$ erzeugt, und die Zahl $v_n$ wird jeweils mit der Wahrscheinlichkeit

$p=\frac{f(v_n)}{k\cdot g(v_n)}$

akzeptiert (Acceptance), also dann, wenn erstmals $u_n<p$ ist. Die vorhergehenden Zufallszahlen werden dagegen verworfen (Rejection).

Einfaches Beispiel

Um eine Zufallszahl aus $\{1,2,3,4,5\}$ zu wählen, wobei jede Zahl mit der gleichen Wahrscheinlichkeit $\frac{1}{5}$ auftreten soll, kann man einen herkömmlichen Spielwürfel mit 6 Seiten werfen. Erscheint eine 6, wirft man ein erneutes Mal, damit stutzt man die möglichen Ergebnisse. Meist wird aber bereits beim ersten Wurf eine Zahl zwischen 1 und 5 (einschließlich) erscheinen.

Implementierung

Programmiertechnisch wird die Verwerfungsmethode allgemein wie folgender Pseudocode realisiert:

   function F_verteilte_Zufallszahl()
     var x, u
     repeat
       x := G_verteilte_Zufallszahl()
       u := gleichförmig_verteilte_Zufallszahl()
     until u * k * g(x) < f(x)
     return x
   end

Der Erwartungswert für die Anzahl der Schleifendurchläufe ist $k$ (siehe unten, Effizienz).

Grafische Veranschaulichung

Beispiel: Der erste Treffer ist hier durch C angedeutet

Man kann sich die Methode so vorstellen, dass in der xy-Ebene zwischen der x-Achse und dem Graph von $k\cdot g(x)$ gleichmäßig auf der Fläche verteilte Zufallspunkte verstreut werden. Als x-Koordinate des Punkts $i$ nimmt man die G-verteilte Zufallszahl $v_i$, und die y-Koordinate erhält man aus der standardverteilten Zahl $u_i$: $y_i=u_i\cdot k\cdot g(v_i)$.

Von diesen Zufallspunkten werden diejenigen verworfen, die oberhalb des Graphs von $f(x)$ liegen ($y_i>f(v_i)$). Die x-Koordinaten der übrigen Punkte sind dann nach der Dichtefunktion $f(x)$ verteilt.

Um eine Zufallszahl nach dieser Verteilung zu erzeugen, werden also solange neue Zufallspunkte erzeugt, bis einer unterhalb von $f(x)$ liegt (im Bild der Punkt C). Dessen x-Koordinate ist die gesuchte Zufallszahl.

Effizienz

Die Fläche unter der Dichtefunktion $f(x)$ ist 1, und unter $k\cdot g(x)$ ist die Fläche entsprechend $k$. Deshalb 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, damit man $k$ klein wählen kann.

Literatur

• Luc Devroye: Non-Uniform Random Variate Generation. (PDF; 758 kB) Springer-Verlag, New York NY u. a. 1986, ISBN 0-387-96305-7, S. 41ff.
• Donald E. Knuth: The Art of Computer Programming. Volume 2: Seminumerical Algorithms. 3. Auflage. Addison-Wesley, Reading MA u. a. 1997, ISBN 0-201-89684-2, S. 120ff. (Addison-Wesley Series in Computer Science and Information Processing).
• Vorlage:Literatur
• Vorlage:Literatur