acceptance-rejection (A-R) サンプリング

確率密度関数π(x)=f(x)/Kからサンプリングしたい。f(x)はunnormalized (非標準？)分布で、Kはnormalizing constant。f(x)は離散分布でも連続分布でもよい。

ここでf(x)<=ch(x)なるcとh(x)をとる。

アルゴリズム

1. Z~h(・)、u~U(0,1)をとる。
2. u<=f(Z)/ch(Z)ならZ=Xを返す。
3. そうでなければ元に戻る。

2がacceptance、3がrejection。意味的には、横にZ、縦にuの座標を取り各Zにおいてランダムにとったu<=f(Z)/ch(Z)となる点を返す(f(x)/ch(x)<=1なので、点が返されないZはない)。

意味は？

P(X≦x)=P(Z≦x|u≦f(Z)/ch(Z))

ところでP(Z≦x)=∫-∞~x h(y)dyで、

P(Z≦x, u≦f(Z)/ch(Z))=∫ f(y)/ch(y) ・ h(y)dy=(K/c) ∫-∞~x π(y)dy

ここでx→∞とすると

P(u≦f(Z)/ch(Z))=K/c

なので

P(X≦x)=P(Z≦x|u≦f(Z)/ch(Z))=P(Z≦x, u≦f(Z)/ch(Z))/P(u≦f(Z)/ch(Z))=∫-∞~x π(y)dy

というわけでZは確率密度関数f(Z)/cからのランダムなサンプリングとなる。