確率分布\(f(x)\)に従う乱数を生成したいとする。このとき、次のように一様乱数を用いて目的の乱数を生成する方法を棄却法という。
- \(u_1\)を\(f(x)\)の定義域\([a,b]\)上の一様分布とする。
- \(u_2\)を\(f(x)\)の値域\([0,c]\)上の一様分布とする。
- \(u_2\lt f(u_1)\)でなければ棄却して以上の手順を繰り返し行う。
- \(u_1,u_2\)が上の条件を満たしたとき\(u_1\)を生成した乱数\(x\)とする。
棄却法ではこのようにして条件を満たすまで何度も一様分布に従う乱数を生成する。直観的にも採用された乱数列は目的の確率分布\(f(x)\)に従う。
証明
まず、2つの一様分布に従う乱数を\(U_1,U_2\)とし、それぞれ区間\([a,b]\)と\([0,c]\)上の一様分布に従うとする。まず\(U_1\)が\(u_1\in[a,b]\)をとる確率は\(f_u(u_1)\mathrm{d}u=\mathrm{d}u/(b-a)\)である。