Como a prova de amostragem por rejeição faz sentido?

9

Estou fazendo um curso sobre métodos de Monte Carlo e aprendemos o método Rejection Sampling (ou Accept-Reject Sampling) na última aula. Existem muitos recursos na web que mostram a prova desse método, mas de alguma forma não estou convencido com eles.

Portanto, no Rejection Sampling, temos uma distribuição qual é difícil extrair amostras. Escolhemos uma distribuição fácil de amostrar g ( x ) e encontramos um coeficiente c tal que f ( x ) c g ( x ) . Em seguida, a partir de amostra de g ( x ) e para cada sorteio, x i , que também mostra um L a partir de uma distribuição uniforme padrão L ( u | 0 , 1 ) .f(x)g(x)cf(x)cg(x)g(x)xiuU(u|0,1)

A amostra é aceite se é c g ( x i ) u f ( x i ) e rejeitada de outro modo.xicg(xi)uf(xi)

As provas que encontrei geralmente apenas mostram que e param por aí.p(x|Accept)=f(x)

O que eu penso sobre este processo é que temos uma sequência de variáveis e a x i , um par c c e p t i corresponde à nossa i -ésima amostra ( x ix1,Accept1,x2,Accept2,...,xn,Acceptnxi,Acceptixi) E se ele é aceito ( ). Sabemos que cada x i , A c c e p t i par é independentes umas das outras, de tal forma que:Acceptixi,Accepti

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

Para um par , sabemos que P ( x i ) = g ( x i ) e P ( A c c e p t i | x i ) = f ( x i )(xi,Accepti)P(xi)=g(xi) . Podemos calcular prontamentep(xi|Accepti),mas não entendo como isso basta como prova. Precisamos mostrar que o algoritmo funciona, então acho que uma prova deve mostrar que a distribuição empricial das amostras aceitas converge paraf(x)comon. Quero dizer, comnsendo o número de todas as amostras aceitas e rejeitadas:P(Accepti|xi)=f(xi)cg(xi)p(xi|Accepti)f(x)nn

como n.Numberofsampleswith(AxiB)NumberofacceptedsamplesABf(x)dxn

Estou errado com esse padrão de pensamento? Ou existe uma conexão entre a prova comum do algoritmo e isso?

desde já, obrigado

Ufuk Can Bicici
fonte

Respostas:

8

Você deve pensar no algoritmo como produzindo desenhos a partir de uma variável aleatória, para mostrar que o algoritmo funciona, basta mostrar que o algoritmo extrai da variável aleatória que você deseja.

Deixe e Y variáveis aleatórias escalares com pdfs f X e f Y , respectivamente, onde Y é algo que já sabe como provar a partir. Também podemos saber que podemos ligar f X por M f Y onde M 1 .XYfXfYYfXMfYM1

Agora formamos uma nova variável aleatória onde A | y Bernoulli  ( f X ( y )A, assume o valor1com probabilidadefX(y)A|yBernoulli (fX(y)MfY(y))1 e0caso contrário. Isto representa o algoritmo 'aceitar' um empate deY.fX(y)MfY(y)0Y

Agora, rodamos o algoritmo e coletamos todos os sorteios de que são aceitos, vamos chamar essa variável aleatória Z = Y | A = 1 .YZ=Y|A=1

Para mostrar que , para qualquer evento E , devemos mostrar que P ( Z E ) = P ( X E ) .ZXEP(ZE)=P(XE)

Então, vamos tentar isso, primeiro use a regra de Bayes:

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

e a parte superior escrevemos como

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.

E então a parte inferior é simplesmente

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

pelo mesmo raciocínio acima, configurando .E=(,+)

E estes se combinam para dar , que é o que queríamos, Z X .P(XE)ZX

É assim que o algoritmo funciona, mas no final da sua pergunta você parece estar preocupado com uma idéia mais geral, ou seja, quando uma distribuição empírica converge para a distribuição amostrada? Esse é um fenômeno geral sobre qualquer amostra, se eu entendi corretamente.

Neste caso, deixe- ser iid variáveis aleatórias, todos com distribuição X . Então, para qualquer evento E , n i = 1 1 X iEX1,,XnXE tem expectativaP(XE)pela linearidade da expectativa.i=1n1XiEnP(XE)

Além disso, dadas as premissas adequadas, você pode usar a lei forte de grandes números para mostrar que a probabilidade empírica converge quase certamente para a verdadeira probabilidade.

Harri
fonte
Obrigado pela resposta. Você pode esclarecer como posso mostrar que a distribuição emprical converge para a distribuição alvo usando a Lei dos Grandes Números? É exatamente o que eu tento mostrar neste caso.
Ufuk Can Bicici
A=1Y1,A1,Y2,A2,...,Yn,AnY2Y1A1Y2P(Y2)P(A2|Y2)
P(Y2)P(A2|Y2)
1

xixi+1

A

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

E

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

Axixi

XiifXiXiAiiXX

fX(x)=P(A1)fX1(x|A1)+P(A2)fX2(x|A2)+.
P(A1)1cfX1(x|A1)f(x)P(A2)(11c)1c11cX1X1X2

fX2(x|A2)f(x)X2X1X1X2A1cA1c

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).
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).
P(A1)+P(A2)+i
Cosyn
fonte