棄却法

包絡線の条件

すべての $x$ で $f(x)\le Mg(x)$ となる提案密度 $g$ と定数 $M$ を選ぶ。

採択ルール

$X\sim g$、$U\sim U(0,1)$ を引き、$U\le f(X)/(Mg(X))$ なら採択、そうでなければ棄却してやり直す。

効率は1/M

1試行の採択確率は $1/M$。$M$ が小さい（$g$ が $f$ に近い）ほど効率が良い。

頻出パターン：|X|の生成（正規→指数提案）

標準正規 $X$ の $|X|$ を、平均1の指数分布 $g(y)=e^{-y}$ を提案分布として棄却法で生成する出題が頻出する（2024年度）。$f(y)/g(y)=\sqrt{2e/\pi}\exp(-(y-1)^2/2)\le\sqrt{2e/\pi}$ なので $c=\sqrt{2e/\pi}$。採択条件は $U\le\exp(-(Y-1)^2/2)$（$-\log U\ge(Y-1)^2/2$ と同値）に整理できる。離散分布でも同じ枠組みが使える（2019年度：離散一様分布を提案分布にした例）。