imported>Sigma^2: /* Einleitung */

2023-10-07T10:25:34Z

Einleitung

Neue Seite

Die '''Verwerfungsmethode''' oder '''Rückweisungsmethode''' (auch '''Acceptance-Rejection-Verfahren'''; engl. ''rejection sampling'') ist eine Methode, um aus [[Standardzufallszahl]]en – das sind Realisierungen stochastisch unabhängiger, auf dem [[Einheitsintervall]] [[Stetige Gleichverteilung|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 [[Inversionsmethode|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 [[Dichtefunktion|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> [[Standardzufallszahl]]en und <math>v_i\,</math> [[Zufallszahl]]en, 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
: <math>p = \frac{f(v_n)} {k \cdot g(v_n)}</math>
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 [[Stutzung|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:

<syntaxhighlight lang="pascal">
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|miniatur|450px|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: [http://luc.devroye.org/handbooksimulation1.pdf ''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'').
* {{Literatur |Autor=[[Horst Rinne]] |Titel=Taschenbuch der Statistik |Verlag=Harri Deutsch |Ort=Frankfurt am Main |Datum=2008 |Auflage=4 |ISBN=978-3-8171-1827-4 |Fundstelle=''3.4.4.2 Verwerfungsmethode'', S. 210}}
* {{Literatur |Autor=Christian P. Robert, George Casella |Titel=Monte Carlo Statistical Methods |Auflage=2 |Reihe=Springer Texts in Statistics |Verlag=Springer |Datum=2004 |ISBN=0-387-21239-6 |Fundstelle=''2.3 Accept-Reject Methods'', S. 47–53 |DOI=10.1007/978-1-4757-4145-2 }}

== Einzelnachweise ==
<references />

[[Kategorie:Stochastik]]
[[Kategorie:Pseudozufallszahlengenerator]]

Verwerfungsmethode - Versionsgeschichte

imported>Sigma^2: /* Einleitung */