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.<ref>John von Neumann: Various techniques used in connection with random digits. Monte Carlo methods. In: Nat. Bureau Standards, 12, 1951, S. 36–38.</ref> Sie kann genutzt werden, wenn die Inversion der Verteilungsfunktion nicht möglich oder zu aufwendig ist.

Idee

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

Um die Verwerfungsmethode anwenden zu können, muss zudem ein konstantes <math>k \in \mathbb{R}</math> existieren, so dass <math>f(x) \le k \cdot g(x)</math> für jedes <math>x \in \mathbb{R}</math> erfüllt ist. Das <math>k</math> wird benötigt, da die Fläche unter einer Dichtefunktion immer 1 ist. Ohne den Vorfaktor <math>k</math> gäbe es deshalb zwangsläufig Stellen mit <math>f(x) > g(x)</math>.

Seien nun <math>u_i\,</math> Standardzufallszahlen und <math>v_i\,</math> Zufallszahlen, die der Verteilungsfunktion <math>G\,</math> genügen.

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

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

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

Einfaches Beispiel

Um eine Zufallszahl aus <math>\{1,2,3,4,5\}</math> zu wählen, wobei jede Zahl mit der gleichen Wahrscheinlichkeit <math>\tfrac 15</math> 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

</syntaxhighlight>

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

Grafische Veranschaulichung

Datei:Beispiel Verwerfungsmethode.png

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 <math>k \cdot g(x) </math> gleichmäßig auf der Fläche verteilte Zufallspunkte verstreut werden. Als x-Koordinate des Punkts <math>i</math> nimmt man die G-verteilte Zufallszahl <math> v_i</math>, und die y-Koordinate erhält man aus der standardverteilten Zahl <math>u_i</math>: <math>y_i = u_i \cdot k \cdot g(v_i)</math>.

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

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

Effizienz

Die Fläche unter der Dichtefunktion <math> f(x)</math> ist 1, und unter <math>k \cdot g(x) </math> ist die Fläche entsprechend <math>k </math>. Deshalb müssen im Mittel <math>k</math> Standardzufallszahlen und <math>k</math> Zufallszahlen, die <math>G</math> genügen, verbraucht werden, bis der erste Treffer erzielt wird. Daher ist es von Vorteil, wenn die Hilfsdichte <math>g</math> die Dichte <math>f</math> möglichst gut approximiert, damit man <math>k</math> 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).
{{#invoke:Vorlage:Literatur|f}}
{{#invoke:Vorlage:Literatur|f}}

Einzelnachweise