棄却法

$f : \mathbb{R}^d \to [0, \infty)$ を $0 < \int f < \infty$ を満たすボレル可測関数（目標。正規化されていなくてよい）、$g$ を $\mathbb{R}^d$ 上の確率密度（提案密度）、$M > 0$ を定数（包絡定数）とする。$\mathbb{R}^{d+1}$ 値の確率変数の列 $(Y_i, U_i)$（$i = 1, 2, \ldots$）は独立同分布で、各々が密度 $g(y)\mathbf{1}_{(0,1)}(u)$ をもつとする（$Y_i$ は密度 $g$ に従い、$U_i \sim \mathrm{U}(0,1)$ は $Y_i$ と独立）。事象

が起きたとき $i$ 回目の候補を採択するという。最初に採択が起きる回 $\tau = \min\{i : A_i \text{ が起きる}\}$ の候補 $X = Y_\tau$ を出力する手続きを棄却法という。$\mathbb{P}(A_1)$ を採択率という。