Verwerfungsmethode

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Rejection Sampling)
Zur Navigation springen Zur Suche springen

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.[1] Sie kann genutzt werden, wenn die Inversion der Verteilungsfunktion nicht möglich oder zu aufwendig ist.

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

Um die Verwerfungsmethode anwenden zu können, muss zudem ein konstantes existieren, so dass für jedes erfüllt ist. Das wird benötigt, da die Fläche unter einer Dichtefunktion immer 1 ist. Ohne den Vorfaktor gäbe es deshalb zwangsläufig Stellen mit .

Seien nun Standardzufallszahlen und Zufallszahlen, die der Verteilungsfunktion genügen.

Dann genügt mit die Zufallszahl der Verteilungsfunktion . Man wartet gewissermaßen auf einen ersten Treffer, der unterhalb von liegt.

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

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

Einfaches Beispiel

[Bearbeiten | Quelltext bearbeiten]

Um eine Zufallszahl aus zu wählen, wobei jede Zahl mit der gleichen Wahrscheinlichkeit 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

[Bearbeiten | Quelltext bearbeiten]

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 (siehe unten, Effizienz).

Grafische Veranschaulichung

[Bearbeiten | Quelltext bearbeiten]
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 gleichmäßig auf der Fläche verteilte Zufallspunkte verstreut werden. Als x-Koordinate des Punkts nimmt man die G-verteilte Zufallszahl , und die y-Koordinate erhält man aus der standardverteilten Zahl : .

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

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

Die Fläche unter der Dichtefunktion ist 1, und unter ist die Fläche entsprechend . Deshalb müssen im Mittel Standardzufallszahlen und Zufallszahlen, die genügen, verbraucht werden, bis der erste Treffer erzielt wird. Daher ist es von Vorteil, wenn die Hilfsdichte die Dichte möglichst gut approximiert, damit man klein wählen kann.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. John von Neumann: Various techniques used in connection with random digits. Monte Carlo methods. In: Nat. Bureau Standards, 12, 1951, S. 36–38.