【簡単にわかりやすく】棄却サンプリングとは【乱数生成方法】

こちらもおすすめ
棄却サンプリングとは
棄却サンプリングのアルゴリズム
あわせて読みたい
こちらもおすすめ

【初心者から上級者まで】Pythonプログラミング独学におすすめの本6選 (難易度順)【感想あり】 | Quant College

【感想あり】C++プログラミングの独学におすすめの本4選【金融工学徒向け】 | Quant College

計算演習確率解析（ブラウン運動編その１）をリリースしました。 | Quant College

【大幅改定】LIBOR廃止とRFR移行の体系的まとめ（前編） | Quant College

【初心者向けにわかりやすく解説】CVA入門の体系的まとめ | Quant College

棄却サンプリングとは

棄却サンプリングとは、解析的に乱数を生成できないような、複雑な確率分布から乱数を生成する方法の一つである。採択棄却法などとも呼ばれる。

しかし、求める対象として、複雑な確率分布とは言っても、何でもいいというわけではなく、条件として、確率密度関数を解析的に求められることが必要となる。

棄却サンプリングの基本的な考え方は、本やネットでもよく見る「乱数で円周率を求める方法」と同じである。
その考え方は以下の通り。

乱数を容易に生成できるようなシンプルな分布でかつ、（複雑な）目標分布の全体をすっぽり覆うような分布を選ぶ（これを提案分布という）
（円周率計算では、円をすっぽり覆う正方形を考え、その一辺の長さを最大値とする一様分布を提案分布として選んでいる）
提案分布から乱数を発生させる
（円周率計算では、一様分布から２つの乱数を発生させている）
得られた提案分布の乱数が、目標分布の内側に入っていれば、目標分布の乱数として受け入れる
（円周率計算では、一様乱数２つで定まる点が、正方形に内接する円の内側に入っていれば、その点をカウントする）
得られた提案分布の乱数が、目標分布の内側に入っていなければ、目標分布の乱数としては受け入れずに、捨てる
（円周率計算では、一様乱数２つで定まる点が、正方形に内接する円の内側に入っていなければ、その点をカウントしない）
結果として、目標分布の確率（発生すべき頻度）に応じて乱数が受け入れられる。確率が高いところは受け入れられることが多いが、一方で、確率が低いところは捨てられることが多い。これによって狙い通りに、目標分布と整合的な乱数のヒストグラムが出来上がる。
（円周率計算では、円の面積に応じて、乱数の点がカウントされる。結果として、正方形の面積と円の面積の比率に応じて、乱数の点がカウントされる。）

棄却サンプリングのアルゴリズム

棄却サンプリングのアルゴリズムは以下の通り。

乱数を生成したい目的の分布を目標分布とする
（目標分布の確率密度関数を\(f\)とする）
乱数を容易に生成できるようなシンプルな分布でかつ、
（複雑な）目標分布の全体をすっぽり覆うような分布を決める
（これを提案分布という。提案分布の確率密度関数を\(g\)とする。）
横軸の点\(x_i\)をランダムに選ぶ。
例えば目標分布の確率密度がゼロでない領域から一様乱数を発生させる。
点\(x_i\)における目標分布の確率密度\(f(x_i)\)を求める（すでに述べた条件から、目標分布の確率密度は解析的に求められる）
提案分布から乱数\(r_i\)を発生させる（提案分布には、乱数を容易に生成できるような分布を選んでいるので、これは容易にできる）
発生させた乱数\(r_i\)が目標分布の確率密度\(f(x_i)\)を下回っていれば、この乱数\(r_i\)を目標分布からの乱数として受け入れる（acceptする/受容する）。上回っていれば、\(r_i\)は捨てる（rejectする/棄却する）。
目標分布の確率密度が低いところほど、それよりも低い値の\(r_i\)が出てくることは少ない（当てに行っているダーツの的がせまい）ので、多くの\(r_i\)が捨てられる（提案分布から発生させた乱数が受け入れられることが少ない）
- 捨てられることが多いので、結果として目標分布の確率密度が低いところは乱数が発生しにくく（発生確率が低く）なる。これはまさに狙い通りの結果である。
逆に、目標分布の確率密度が高いところほど、それよりも低い値の\(r_i\)が出てくることは多い（当てに行っているダーツの的が広い）ので、多くの\(r_i\)が受け入れられる（提案分布から発生させた乱数が捨てられることが少ない）
- 受け入れられることが多い（捨てられることが少ない）ので、結果として目標分布の確率密度が高いところは乱数が発生しやすく（発生確率が高く）なる。これもまさに狙い通りの結果である。