Verwerfungsmethode

Die Verwerfungsmethode (auch Acceptance-Rejection-Verfahren; engl. rejection sampling) i​st eine Methode, u​m aus gleichverteilten Zufallszahlen andere Wahrscheinlichkeitsverteilungen z​u erzeugen. Sie g​eht auf John v​on Neumann zurück.[1] Sie k​ann genutzt werden, w​enn die Inversion d​er Verteilungsfunktion n​icht möglich o​der zu aufwendig ist.

Idee

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

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

Seien nun ${\displaystyle u_{i}\,}$ Standardzufallszahlen und ${\displaystyle v_{i}\,}$ Zufallszahlen, die der Verteilungsfunktion ${\displaystyle G\,}$ genügen.

Dann genügt mit ${\displaystyle j:=\inf\{n\geq 1\mid k\cdot u_{n}\cdot g(v_{n})<f(v_{n})\}}$ die Zufallszahl ${\displaystyle x:=v_{j}}$ der Verteilungsfunktion ${\displaystyle F}$. Man wartet gewissermaßen auf einen ersten Treffer, der unterhalb von ${\displaystyle f}$ liegt.

Anders gesagt: Es werden Zufallszahlen ${\displaystyle v_{i}}$ nach der Verteilungsfunktion ${\displaystyle G}$ erzeugt, und die Zahl ${\displaystyle v_{n}}$ wird jeweils mit der Wahrscheinlichkeit

${\displaystyle p={\frac {f(v_{n})}{k\cdot g(v_{n})}}}$

akzeptiert (Acceptance), also dann, wenn erstmals ${\displaystyle u_{n}<p}$ ist. Die vorhergehenden Zufallszahlen werden dagegen verworfen (Rejection).

Einfaches Beispiel

Um eine Zufallszahl aus ${\displaystyle \{1,2,3,4,5\}}$ zu wählen, wobei jede Zahl mit der gleichen Wahrscheinlichkeit ${\displaystyle {\tfrac {1}{5}}}$ 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 w​ird die Verwerfungsmethode allgemein w​ie 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 ${\displaystyle 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 xy-Ebene zwischen der x-Achse und dem Graph von ${\displaystyle k\cdot g(x)}$ gleichmäßig auf der Fläche verteilte Zufallspunkte verstreut werden. Als x-Koordinate des Punkts ${\displaystyle i}$ nimmt man die G-verteilte Zufallszahl ${\displaystyle v_{i}}$, und die y-Koordinate erhält man aus der standardverteilten Zahl ${\displaystyle u_{i}}$: ${\displaystyle y_{i}=u_{i}\cdot k\cdot g(v_{i})}$.

Von diesen Zufallspunkten werden diejenigen verworfen, die oberhalb des Graphs von ${\displaystyle f(x)}$ liegen (${\displaystyle y_{i}>f(v_{i})}$). Die x-Koordinaten der übrigen Punkte sind dann nach der Dichtefunktion ${\displaystyle f(x)}$ verteilt.

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

Effizienz

Die Fläche unter der Dichtefunktion ${\displaystyle f(x)}$ ist 1, und unter ${\displaystyle k\cdot g(x)}$ ist die Fläche entsprechend ${\displaystyle k}$. Deshalb müssen im Mittel ${\displaystyle k}$ Standardzufallszahlen und ${\displaystyle k}$ Zufallszahlen, die ${\displaystyle G}$ genügen, verbraucht werden, bis der erste Treffer erzielt wird. Daher ist es von Vorteil, wenn die Hilfsdichte ${\displaystyle g}$ die Dichte ${\displaystyle f}$ möglichst gut approximiert, damit man ${\displaystyle k}$ klein wählen kann.

Literatur

• 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).
• 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.

Einzelnachweise

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