Comment la preuve de l'échantillonnage de rejet est-elle logique?

9

Je prends un cours sur les méthodes de Monte Carlo et nous avons appris la méthode d'échantillonnage par rejet (ou Accept-Reject Sampling) lors de la dernière conférence. Il y a beaucoup de ressources sur le web qui montrent la preuve de cette méthode mais je ne suis pas convaincu avec elles.

Ainsi, dans l'échantillonnage de rejet, nous avons une distribution f(x)qui est difficile à échantillonner. Nous choisissons une distribution facile à échantillonnerg(x) et trouver un coefficient c tel que f(x)cg(x). Ensuite, nous échantillonnonsg(x) et pour chaque tirage, xi, nous échantillonnons également un u à partir d'une distribution uniforme standard U(u|0,1).

L'échantillon xi est accepté s'il est cg(xi)uf(xi) et rejeté autrement.

Les preuves que j'ai rencontrées montrent généralement que p(x|Accept)=f(x) et arrêtez-vous là.

Ce que je pense de ce processus, c'est que nous avons une séquence de variables x1,Accept1,x2,Accept2,...,xn,Acceptn et un xi,Accepti la paire correspond à notre i.th échantillon (xi) et s'il est accepté (Accepti). Nous savons que chacunxi,Accepti la paire est indépendante l'une de l'autre, de sorte que:

P(x1,Accept1,x2,Accept2,...,xn,Acceptn)=i=1nP(xi,Accepti)

Pour un (xi,Accepti) paire, nous savons que P(xi)=g(xi) et P(Accepti|xi)=f(xi)cg(xi). Nous pouvons facilement calculerp(xi|Accepti)mais je ne comprends pas comment cela suffit comme preuve. Nous devons montrer que l'algorithme fonctionne, donc je pense qu'une preuve devrait montrer que la distribution empricial des échantillons acceptés converge versf(x) comme n. Je veux dire, avecn étant le nombre de tous les échantillons acceptés et rejetés:

Numberofsampleswith(AxiB)NumberofacceptedsamplesABf(x)dx comme n.

Ai-je tort avec ce schéma de pensée? Ou existe-t-il un lien entre la preuve commune de l'algorithme et celle-ci?

Merci d'avance

Ufuk Can Bicici
la source

Réponses:

8

Vous devez penser à l'algorithme comme produisant des tirages à partir d'une variable aléatoire, pour montrer que l'algorithme fonctionne, il suffit de montrer que l'algorithme tire à partir de la variable aléatoire que vous souhaitez.

Laisser X et Y être des variables aléatoires scalaires avec pdfs fX et fY respectivement, où Yest quelque chose que nous savons déjà échantillonner. Nous pouvons également savoir que nous pouvonsfX par MfYM1.

Nous formons maintenant une nouvelle variable aléatoire AA|yBernoulli (fX(y)MfY(y)), cela prend la valeur 1 avec probabilité fX(y)MfY(y) et 0autrement. Cela représente l'algorithme «acceptant» un tirage deY.

Maintenant, nous exécutons l'algorithme et collectons tous les tirages de Y qui sont acceptés, appelons cette variable aléatoire Z=Y|A=1.

Montrer que ZX, pour tout événement E, nous devons montrer que P(ZE)=P(XE).

Essayons donc cela, utilisons d'abord la règle de Bayes:

P(ZE)=P(YE|A=1)=P(YE&A=1)P(A=1),

et la partie supérieure que nous écrivons

P(YE&A=1)=EfY,A(y,1)dy=EfA|Y(1,y)fY(y)dy=EfY(y)fX(y)MfY(y)dy=P(XE)M.

Et puis la partie inférieure est tout simplement

P(A=1)=fY,A(y,1)dy=1M,

par le même raisonnement que ci-dessus, E=(,+).

Et ceux-ci se combinent pour donner P(XE), c'est ce que nous voulions, ZX.

C'est ainsi que fonctionne l'algorithme, mais à la fin de votre question, vous semblez être préoccupé par une idée plus générale, à savoir quand une distribution empirique converge-t-elle vers la distribution échantillonnée? C'est un phénomène général concernant tout échantillonnage que ce soit si je vous comprends bien.

Dans ce cas, laissez X1,,Xn être iid variables aléatoires toutes avec distribution X. Alors pour tout événementE, i=1n1XiEn a des attentes P(XE) par la linéarité de l'attente.

De plus, étant donné les hypothèses appropriées, vous pouvez utiliser la loi forte des grands nombres pour montrer que la probabilité empirique converge presque sûrement vers la vraie probabilité.

Harri
la source
Merci d'avoir répondu. Pouvez-vous préciser comment puis-je montrer que la distribution empricale converge vers la distribution cible en utilisant la loi des grands nombres? C'est exactement ce que j'essaie de montrer dans ce cas.
Ufuk Can Bicici
@Harri Ce qui me dérange, c'est le fait qu'on apprend la variable aléatoire indiquant l'acceptation du tirage (A=1) après avoir appris la valeur de la variable réelle. On observe les variables selon la séquenceY1,A1,Y2,A2,...,Yn,An, donc si nous allons observer la variable Y2, ce que nous savons du système est Y1 et A1 et depuis Y2 est indépendant d'eux, ce que nous traitons est d'abord P(Y2), puis P(A2|Y2)pas l'inverse.
Ufuk Can Bicici
Pourriez-vous en dire plus sur la raison pour laquelle l'ordre de savoir P(Y2) et alors P(A2|Y2)vous dérange?
Harri
1

Tout d'abord, gardez à l'esprit qu'une procédure complète de la méthode d'échantillonnage de rejet ne produit qu'une seule variable aléatoire. Quand certainsxi est acceptée, la procédure s'arrête et il n'y a pas xi+1plus. Si vous voulez plusieurs variables aléatoires, répétez simplement la procédure plusieurs fois.

Dans certains manuels, ils dénotent l’acceptation par A et calculer la probabilité

P(A)=dx0f(x)cg(x)g(x)du=1cf(x)dx=1c.

Et

fX(x|A)=fX(x)P(A|x)P(A)=g(x)f(x)cg(x)1c=f(x).

La chose déroutante est que l'acceptation A ici semble être l'acceptation d'un seul échantillon de xi, mais toute la procédure peut rejeter plusieurs xi's.

Oui, une preuve plus rigoureuse devrait considérer la probabilité d'acceptation à différentes étapes. LaisserXi dénoter la ie échantillon, fXi dénoter la fonction de densité de probabilité de Xi, Ai dénoter la ie acceptation, et Xindique la valeur finale acceptée. Ensuite, la fonction de densité de probabilité deX est

fX(x)=P(A1)fX1(x|A1)+P(A2)fX2(x|A2)+.
P(A1) est 1c et fX1(x|A1) est f(x)comme calculé auparavant. RemarqueP(A2) est (11c)1c11c est la probabilité de rejet de X1 depuis seulement quand X1 est rejeté avons-nous une chance de choisir un X2.

Et fX2(x|A2) est f(x)trop parce que la deuxième étape n'est pas affectée par les étapes précédentes, sa probabilité devrait être la même que la première étape. Si cette explication ne vous convainc pas, nous pouvons également la travailler avec rigueur. Faites attentionX2 n'est pas défini lorsque X1 est accepté (ou vous pouvez le définir comme un nombre arbitraire lorsque X1 est acceptée si une valeur indéfinie vous met mal à l'aise), donc pour les probabilités concernant X2, seules les probabilités conditionnelles sont données A1c ou des sous-ensembles de A1cfaire sens. Maintenant

fX2(x|A2)=P(A1c)fX2(x|A1c)P(A2|X2=x)P(A2)=P(A1c)fX2(x|A1c)P(A2|X2=x)P(A1c)P(A2|A1c)=fX2(x|A1c)P(A2|X2=x)P(A2|A1c)=g(x)f(x)cg(x)1c=f(x).
Donc
fX(x)=P(A1)f(x)+P(A2)f(x)+=(P(A1)+P(A2)+)f(x)=(1c+(11c)1c+(11c)21c+)f(x)=f(x).
Voilà le résultat souhaité. RemarqueP(A1)+P(A2)+ = 1 a une signification intuitive, c'est-à-dire qu'un échantillon sera finalement accepté à un moment donné i.
Cosyn
la source