www.wikidata.de-de.nina.az

Verwerfungsmethode Die oder Rückweisungsmethode auch Acceptance Rejection Verfahren engl rejection sampling ist eine Met

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 Bearbeiten

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

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

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

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.

Effizienz Bearbeiten

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.

Literatur Bearbeiten

  • 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).
  • Horst Rinne: Taschenbuch der Statistik. 4. Auflage. Harri Deutsch, Frankfurt am Main 2008, ISBN 978-3-8171-1827-4, 3.4.4.2 Verwerfungsmethode, S. 210.
  • Christian P. Robert, George Casella: Monte Carlo Statistical Methods (= Springer Texts in Statistics). 2. Auflage. Springer, 2004, ISBN 0-387-21239-6, 2.3 Accept-Reject Methods, S. 47–53, doi:10.1007/978-1-4757-4145-2.

Einzelnachweise 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Verwerfungsmethode oder Ruckweisungsmethode auch Acceptance Rejection Verfahren engl rejection sampling ist eine Methode um aus Standardzufallszahlen das sind Realisierungen stochastisch unabhangiger auf dem Einheitsintervall gleichverteilter Zufallsvariablen Zufallszahlen aus anderen Wahrscheinlichkeitsverteilungen zu erzeugen Sie geht auf John von Neumann zuruck 1 Sie kann genutzt werden wenn die Inversion der Verteilungsfunktion nicht moglich oder zu aufwendig ist Inhaltsverzeichnis 1 Idee 2 Einfaches Beispiel 3 Implementierung 4 Grafische Veranschaulichung 5 Effizienz 6 Literatur 7 EinzelnachweiseIdee BearbeitenF displaystyle F nbsp sei hierbei die Verteilungsfunktion der Verteilung zu der Zufallszahlen erzeugt werden sollen G displaystyle G nbsp sei eine Hilfsverteilungsfunktion zu der sich auf einfachem Weg etwa uber die Inversionsmethode Zufallszahlen erzeugen lassen Es seien ferner f displaystyle f nbsp und g displaystyle g nbsp die zugehorigen Dichten Um die Verwerfungsmethode anwenden zu konnen muss zudem ein konstantes k R displaystyle k in mathbb R nbsp existieren so dass f x k g x displaystyle f x leq k cdot g x nbsp fur jedes x R displaystyle x in mathbb R nbsp erfullt ist Das k displaystyle k nbsp wird benotigt da die Flache unter einer Dichtefunktion immer 1 ist Ohne den Vorfaktor k displaystyle k nbsp gabe es deshalb zwangslaufig Stellen mit f x gt g x displaystyle f x gt g x nbsp Seien nun u i displaystyle u i nbsp Standardzufallszahlen und v i displaystyle v i nbsp Zufallszahlen die der Verteilungsfunktion G displaystyle G nbsp genugen Dann genugt mit j inf n 1 k u n g v n lt f v n displaystyle j inf n geq 1 mid k cdot u n cdot g v n lt f v n nbsp die Zufallszahl x v j displaystyle x v j nbsp der Verteilungsfunktion F displaystyle F nbsp Man wartet gewissermassen auf einen ersten Treffer der unterhalb von f displaystyle f nbsp liegt Anders gesagt Es werden Zufallszahlen v i displaystyle v i nbsp nach der Verteilungsfunktion G displaystyle G nbsp erzeugt und die Zahl v n displaystyle v n nbsp wird jeweils mit der Wahrscheinlichkeit p f v n k g v n displaystyle p frac f v n k cdot g v n nbsp akzeptiert Acceptance also dann wenn erstmals u n lt p displaystyle u n lt p nbsp ist Die vorhergehenden Zufallszahlen werden dagegen verworfen Rejection Einfaches Beispiel BearbeitenUm eine Zufallszahl aus 1 2 3 4 5 displaystyle 1 2 3 4 5 nbsp zu wahlen wobei jede Zahl mit der gleichen Wahrscheinlichkeit 1 5 displaystyle tfrac 1 5 nbsp auftreten soll kann man einen herkommlichen Spielwurfel mit 6 Seiten werfen Erscheint eine 6 wirft man ein erneutes Mal damit stutzt man die moglichen Ergebnisse Meist wird aber bereits beim ersten Wurf eine Zahl zwischen 1 und 5 einschliesslich erscheinen Implementierung BearbeitenProgrammiertechnisch wird die Verwerfungsmethode allgemein wie folgender Pseudocode realisiert function F verteilte Zufallszahl var x u repeat x G verteilte Zufallszahl u gleichf o rmig verteilte Zufallszahl until u k g x lt f x return x end Der Erwartungswert fur die Anzahl der Schleifendurchlaufe ist k displaystyle k nbsp siehe unten Effizienz Grafische Veranschaulichung Bearbeiten nbsp Beispiel Der erste Treffer ist hier durch C angedeutetMan kann sich die Methode so vorstellen dass in der xy Ebene zwischen der x Achse und dem Graph von k g x displaystyle k cdot g x nbsp gleichmassig auf der Flache verteilte Zufallspunkte verstreut werden Als x Koordinate des Punkts i displaystyle i nbsp nimmt man die G verteilte Zufallszahl v i displaystyle v i nbsp und die y Koordinate erhalt man aus der standardverteilten Zahl u i displaystyle u i nbsp y i u i k g v i displaystyle y i u i cdot k cdot g v i nbsp Von diesen Zufallspunkten werden diejenigen verworfen die oberhalb des Graphs von f x displaystyle f x nbsp liegen y i gt f v i displaystyle y i gt f v i nbsp Die x Koordinaten der ubrigen Punkte sind dann nach der Dichtefunktion f x displaystyle f x nbsp verteilt Um eine Zufallszahl nach dieser Verteilung zu erzeugen werden also solange neue Zufallspunkte erzeugt bis einer unterhalb von f x displaystyle f x nbsp liegt im Bild der Punkt C Dessen x Koordinate ist die gesuchte Zufallszahl Effizienz BearbeitenDie Flache unter der Dichtefunktion f x displaystyle f x nbsp ist 1 und unter k g x displaystyle k cdot g x nbsp ist die Flache entsprechend k displaystyle k nbsp Deshalb mussen im Mittel k displaystyle k nbsp Standardzufallszahlen und k displaystyle k nbsp Zufallszahlen die G displaystyle G nbsp genugen verbraucht werden bis der erste Treffer erzielt wird Daher ist es von Vorteil wenn die Hilfsdichte g displaystyle g nbsp die Dichte f displaystyle f nbsp moglichst gut approximiert damit man k displaystyle k nbsp klein wahlen kann Literatur BearbeitenLuc 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 Horst Rinne Taschenbuch der Statistik 4 Auflage Harri Deutsch Frankfurt am Main 2008 ISBN 978 3 8171 1827 4 3 4 4 2 Verwerfungsmethode S 210 Christian P Robert George Casella Monte Carlo Statistical Methods Springer Texts in Statistics 2 Auflage Springer 2004 ISBN 0 387 21239 6 2 3 Accept Reject Methods S 47 53 doi 10 1007 978 1 4757 4145 2 Einzelnachweise Bearbeiten John von Neumann Various techniques used in connection with random digits Monte Carlo methods In Nat Bureau Standards 12 1951 S 36 38 Abgerufen von https de wikipedia org w index php title Verwerfungsmethode amp oldid 237950112