Acceptance-Rejection-Verfahren

Die Verwerfungsmethode (auch Acceptance-Rejection-Verfahren) ist eine Methode zur Erzeugung von Zufallszahlen zu einer vorgegebenen Verteilung und geht auf John von Neumann zurück.[1] Sie kann genutzt werden, wenn die Anwendung der Inversionsmethode aufgrund der Komplexität der behandelten Funktion zu schwierig wäre.

Inhaltsverzeichnis

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 ferner ein konstantes k \in \mathbb{R} 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 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: = vj der Verteilungsfunktion F. Man wartet gewissermaßen auf einen ersten Treffer, der unterhalb von f liegt.

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

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

akzeptiert (Acceptance), also dann, wenn erstmals un < 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 \tfrac 15 auftreten soll, kann man einen herkömmlichen Spielwürfel werfen. Erscheint eine 6, wirft man ein erneutes Mal. 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 x-y-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 vi, und die y-Koordinate erhält man aus der standardverteilten Zahl ui: y_i = u_i \cdot k \cdot g(v_i).

Von diesen Zufallspunkten werden diejenigen verworfen, die oberhalb des Graphs von f(x) liegen (yi > f(vi)). 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.

Quellen

  1. John von Neumann: Various techniques used in connection with random digits. Monte Carlo methods. In: Nat. Bureau Standards, 12 (1951), S. 36–38.

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Acceptance-Rejection — Die Verwerfungsmethode (auch Acceptance Rejection Verfahren) ist eine Methode zur Erzeugung von Zufallszahlen zu einer vorgegebenen Verteilung und geht auf John von Neumann zurück.[1] Sie kann genutzt werden, wenn die Anwendung der… …   Deutsch Wikipedia

  • Acceptance-Rejection-Methode — Die Verwerfungsmethode (auch Acceptance Rejection Verfahren) ist eine Methode zur Erzeugung von Zufallszahlen zu einer vorgegebenen Verteilung und geht auf John von Neumann zurück.[1] Sie kann genutzt werden, wenn die Anwendung der… …   Deutsch Wikipedia

  • Verwerfungsmethode — Die Verwerfungsmethode (auch Acceptance Rejection Verfahren; engl. rejection sampling) ist eine Methode zur Erzeugung von Zufallszahlen zu einer vorgegebenen Verteilung und geht auf John von Neumann zurück.[1] Sie kann genutzt werden, wenn die… …   Deutsch Wikipedia

  • Biometrischer Reisepass — Symbol für biometrische Pässe, in der Regel auf die Vorderseite des Passes gedruckt …   Deutsch Wikipedia

  • Saspo — Dies ist der fünfte Teil der Liste Abkürzungen/Luftfahrt. Liste der Abkürzungen Teil 1 A A Teil 2 B–D B; C; D Teil 3 E–K …   Deutsch Wikipedia

  • Abkürzungen/Luftfahrt/S–Z — Dies ist der fünfte Teil der Liste Abkürzungen/Luftfahrt. Liste der Abkürzungen Teil 1 A A Teil 2 B–D B; C; D Teil 3 E–K E; F; G; H; I; J; …   Deutsch Wikipedia

  • Authentifikation — Der Unterschied zwischen Authentifizierung und Authentisierung in einer Benutzer Server Beziehung. Authentifizierung (v. griech. authentikos für „Anführer“) ist der Vorgang der Überprüfung (Verifikation) einer behaupteten Identität,… …   Deutsch Wikipedia

  • Authentifizierung — und Authentisierung in einer Benutzer Server Beziehung Authentifizierung (griechisch αυθεντικός authentikós ‚echt‘, ‚Anführer‘; Stammform verbunden mit lateinisch facere ‚machen‘) ist der Nachweis (Verifizierung …   Deutsch Wikipedia

  • Authentisierung — Der Unterschied zwischen Authentifizierung und Authentisierung in einer Benutzer Server Beziehung. Authentifizierung (v. griech. authentikos für „Anführer“) ist der Vorgang der Überprüfung (Verifikation) einer behaupteten Identität,… …   Deutsch Wikipedia

  • Identifikationsprotokoll — Der Unterschied zwischen Authentifizierung und Authentisierung in einer Benutzer Server Beziehung. Authentifizierung (v. griech. authentikos für „Anführer“) ist der Vorgang der Überprüfung (Verifikation) einer behaupteten Identität,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”