Ich kann nicht verstehen, warum die Ablehnungsabtastung funktioniert

7

Ich möchte Stichprobenpunkte in einer beliebigen 2D-Form erzeugen , z. B. einen Kreis, der am Ursprung mit Radius 1 zentriert ist. $\{z_i\}$

Blick auf zwei einheitliche Zufallsvariablen über , und . $[0,1]$ $X$ $Y$
Beispiel und , Sie erhalten und , sagen wir. $X$ $Y$ $x$ $y$
Testen Sie, ob : $x^2+y^2\leq 1$
- Wenn ja, ist . $z=(x,y)$
- Wenn nein, probieren Sie und bis die Bedingung erfüllt ist. $X$ $Y$

Warum funktioniert das, dh warum simuliert dies das Abtasten einer Zufallsvariablen , die gleichmäßig über eine Disc verteilt ist? $Z$

uniform rejection-sampling ToniAz
quelle

@AdamO Ich denke, die WLLN ist irrelevant, da es um die Vorgehensweise geht und nicht um die Einschränkung der Eigenschaften der Daten. Es genügt zu zeigen, dass, wenn eine messbare Menge in der Ebene ist, diese Prozedur Punkte unabhängig von mit einer Wahrscheinlichkeit zeichnet , die proportional zur Fläche von (wobei die fragliche Einheitsscheibe ist).

A

$A$

A

$A$

A \cap D^{2}

$A \cap D^2$

D^{2}

$D^2$

whuber

@AdamO, das OP hat kein Interesse an der Messung der Fläche eines Kreises bekundet. Sie stellten der Frage "Ich möchte Samples generieren" voran. Wenn sie an einer Schätzung des Gebiets interessiert waren, ist Ihr Kommentar gültig, da sie verstehen, wie repräsentativ die durch Ablehnungsstichproben erhaltenen Proben sind. Sie wollen jedoch wissen, warum die erhaltenen Proben repräsentativ sind.

Greenparker

@ Greenparker danke ich verstehe warum ich die frage falsch verstanden habe.

AdamO

2

Um aus einer Verteilung mit der Dichte auf der Unterstützung eine Stichprobe zu erstellen , müssen wir im Allgemeinen so finden, dass eine Vorschlagsverteilung mit der Dichte wird $f(x,y)$ $\mathcal{S}$ $h(x,y)$ $M$

sup_{(x, y) \in S} \frac{f (x, y)}{h (x, y)} \leq M,

$\sup_{(x,y) \in\mathcal{S}} \dfrac{f(x,y)}{h(x,y)} \leq M,$

damit wir einen vorgeschlagenen Wert mit Wahrscheinlichkeit akzeptieren können

α = \frac{f (x, y)}{M h (x, y)} .

$\alpha = \dfrac{f(x,y)}{Mh(x,y)}\,.$

Akzeptieren mit entspricht dem Zeichnen von und Akzeptieren, wenn . $\alpha$ $U \sim U[0,1]$ $U < \alpha$

Ich gehe davon aus, dass Sie diese allgemeine Prämisse der Ablehnungsstichprobe verstehen. In diesem Beispiel zum Zeichnen von Mustern aus dem Kreis unter Verwendung eines einheitlichen quadratischen Vorschlags

f (x, y) = \frac{1}{π} \cdot I (\underset{= S}{\underset{⏟}{x^{2} + y^{2} < 1}}) and h (x, y) = \frac{1}{4} I (- 1 < x, y < 1) .

$f(x,y) = \dfrac{1}{\pi} \cdot I(\underbrace{x^2 + y^2 <1}_{=\mathcal{S}}) \quad \text{ and }\quad h(x,y) = \dfrac{1}{4} I(-1 < x,y < 1)\,.$

Lassen Sie uns zuerst finden . Zur Unterstützung von , $M$ $f$

sup_{x^{2} + y^{2} \leq 1} \frac{f (x, y)}{h (x, y)} = sup_{x^{2} + y^{2} \leq 1} \frac{I (x^{2} + y^{2} \leq 1) / π}{1 / 4} = \frac{4}{π} := M .

$\sup_{x^2 + y^2 \leq 1} \dfrac{f(x,y)}{h(x,y)} = \sup_{x^2 + y^2 \leq 1} \dfrac{ I(x^2 + y^2 \leq 1)/ \pi}{1/4} = \dfrac{4}{\pi} := M\,.$

Jeder vorgeschlagene Wert aus dem Quadrat wird also mit der Wahrscheinlichkeit erwartet.

\frac{f (x, y)}{M h (x, y)} = \frac{I (x^{2} + y^{2} \leq 1) / π}{M / 4} = I (x^{2} + y^{2} \leq 1) .

$\dfrac{f(x,y)}{M{h(x,y)}} = \dfrac{I(x^2 + y^2 \leq 1)/\pi}{M/{4}} = I(x^2 + y^2 \leq 1)\,.$

Für jeden Wert, der zur Unterstützung von , ist immer kleiner als , also akzeptieren wir immer. Es ist daher nicht erforderlich, von einem abzutasten, und wenn sich der abgetastete Punkt innerhalb des Kreises befindet, können wir ihn sofort akzeptieren. $f$ $U\sim U[0,1]$ $1$ $U$

Greenparker
quelle

2

Zunächst müssen und zwischen und ( ergibt einen viertel Kreis, da Sie nur und ). $x$ $y$ $-1$ $1$ $[0,1]$ $y \ge 0$ $x \ge0$

Dann stellen Sie fest, dass Sie zwei Listen zufällig verteilter Variablen entlang der und Achse haben - zwei Linien mit einer zufälligen Verteilung von Punkten. Kombinieren Sie diese und Sie haben ein Quadrat aus zufällig verteilten Punkten. $X$ $Y$

Sie lehnen dann die Bits des Quadrats ab, die nicht innerhalb eines Kreises liegen, der bei zentriert ist - daher - und alle Punkte, die diese Ungleichung erfüllen, liegen auf der Scheibe und, da die Punkte auf dem Quadrat gleichmäßig verteilt waren, auch die auf der Scheibe. $(0,0)$ $x^{2}+y^{2}\le1$

Lio Elbammalf
quelle

1

Sie haben mit gleicher Wahrscheinlichkeit einen beliebigen Punkt in [0,1] x [0,1] gewählt. Dann haben Sie alle entfernt, die sich außerhalb des Kreises befinden.

Dies ändert nichts an der Wahrscheinlichkeit, für jeden einzelnen Punkt innerhalb des Kreises ausgewählt zu werden (dh: Jeder Punkt innerhalb des Kreises hat immer noch die gleiche Wahrscheinlichkeit, ausgewählt zu werden wie jeder andere).

David
quelle

Ich kann nicht verstehen, warum die Ablehnungsabtastung funktioniert

Antworten: