棄却法（受理・棄却サンプリング）

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：逆関数法　|　関連：重点サンプリング　|　メトロポリス・ヘイスティングス法

要点（BLUF）

棄却法：目的分布 $f$ から直接引けなくても、引きやすい提案分布 $g$ から候補を出し、確率 $f(x)/(M g(x))$ で受理すればよい。
受理した候補は厳密に $f$ に従います。 $M$ は $f(x) \le M g(x)$ を満たす包絡定数で、受理率はちょうど $1/M$ 。
$M$ が小さい（提案が目的に近い）ほど効率的。Beta(2,2) を一様提案で生成し、受理率 0.666 が理論値 $1/M = 1/1.5$ と一致することを確かめます。

1. 原理：包絡して当たり判定

逆関数法は $F^{-1}$ が書けないと使えません（逆関数法）。棄却法はその制約を外す汎用法です。アイデアは「目的の密度 $f$ を、引きやすい密度 $g$ の定数倍 $Mg$ で覆い（包絡し）、覆いの下に当たった点だけ採用する」。

条件は、ある定数 $M \ge 1$ が存在して、 $f$ の台すべてで

f(x) \le M\, g(x)

手順は3ステップ：

提案 $X \sim g$ を引く
$U \sim \mathcal{U}(0,1)$ を引く
$U \le \dfrac{f(X)}{M g(X)}$ なら $X$ を受理、さもなくば棄却して1に戻る

flowchart TD
    A["提案 X ~ g を引く"] --> B["U ~ U(0,1) を引く"]
    B --> C{"U <= f(X)/(M g(X)) ?"}
    C -->|"はい（受理）"| D["X を採用"]
    C -->|"いいえ（棄却）"| A

2. なぜ受理されたサンプルが f に従うのか

受理される確率は、 $x$ で条件づけると $f(x)/(Mg(x))$ 。 $X \sim g$ なので、「 $x$ 付近を提案し、かつ受理する」同時密度は $g(x)\cdot \frac{f(x)}{Mg(x)} = \frac{f(x)}{M}$ 。これを全域で積分すると全体の受理確率は

P(\text{受理}) = \int \frac{f(x)}{M}\,dx = \frac{1}{M}

（ $f$ は密度なので積分は1）。よって受理されたサンプルの密度は $\frac{f(x)/M}{1/M} = f(x)$ 、すなわち厳密に目的分布。同時に、受理率が $1/M$ だとわかります。 $M$ が大きい＝覆いが目的より大きすぎる＝棄却が多く非効率、ということです。

3. 具体例：Beta(2,2) を一様提案で生成

目的を $f(x) = 6x(1-x)$ （ $[0,1]$ 上の Beta(2,2)）、提案を $g(x) = 1$ （一様）とします。 $f$ の最大は $x=0.5$ で $f(0.5) = 1.5$ なので $M = 1.5$ で覆えます。

import numpy as np

# 乱数シードを固定
rng = np.random.default_rng(4)

M = 1.5
N_try = 1_000_000
x = rng.random(N_try)              # 提案 ~ Uniform(0,1)
u = rng.random(N_try)
f = 6 * x * (1 - x)                # 目的密度 Beta(2,2)
accept = u <= f / (M * 1.0)        # 受理判定（g=1）
samples = x[accept]

print(f"受理率（シミュ） = {accept.mean():.4f}  (理論 1/M = {1/M:.4f})")
print(f"サンプル平均 = {samples.mean():.4f}  (理論 0.5)")
print(f"サンプル分散 = {samples.var():.4f}  (理論 0.05)")

出力：

受理率（シミュ） = 0.6662  (理論 1/M = 0.6667)
サンプル平均 = 0.5003  (理論 0.5)
サンプル分散 = 0.0501  (理論 0.0500)

出力の意味：受理率 0.666 が理論値 $1/M = 1/1.5 = 0.667$ とピタリ。受理されたサンプルの平均 0.500・分散 0.0501 も Beta(2,2) の理論値（平均 $\frac{\alpha}{\alpha+\beta}=0.5$ 、分散 $\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}=0.05$ ）と一致。覆いの定数 $M$ を最小（1.5）に取ったので、提案の約3分の2が活きています。

4. 効率と提案分布の選び方

受理率＝ $1/M$ なので、 $M$ を小さくする＝提案 $g$ を目的 $f$ に形を似せるのが効率の鍵。
一様提案でも低次元なら十分ですが、 $f$ が尖っていたり高次元だと $M$ が爆発し、受理率が指数的に落ちます（次元の呪い）。
提案を目的に近づける発想は、重点サンプリング（棄却せず重みで補正）やメトロポリス法（連鎖で局所的に提案）へと発展します。棄却法は「直接サンプリング」の限界点で、そこから先が MCMC の出番です。

数式の直観的意味

棄却法は「密度のグラフの下の面積に、一様に点をばらまく」操作と見ると直観的です。 $Mg$ で覆った長方形（一般には $g$ 形の領域）に一様に点を打ち、 $f$ の曲線より下の点だけ残す。残った点の $x$ 座標は、 $f$ が高いところほど密に分布する——だから $f$ に従います。受理率 $1/M$ は「覆いの面積 $M$ のうち、目的の面積 1 が占める割合」そのもの。 $M$ を目的にぴったり被せるほど無駄打ちが減る、という幾何が効率を決めています。

⚠️ よくある誤解・落とし穴

「棄却したサンプルも使える」ではない：棄却されたものは捨てます。使うと分布が歪みます。
「 $M$ は適当な大きい値でいい」ではない： $M$ が大きいほど受理率 $1/M$ が下がり非効率。 $M = \max_x f(x)/g(x)$ の最小値を取ります。
「 $f \le Mg$ が一部で破れてもいい」ではない：1点でも $f > Mg$ だとその領域が過小サンプルされ、分布が間違います。包絡は全域で成立必須。
「高次元でも使える」ではない：次元が上がると最適な $M$ でも受理率が急落（次元の呪い）。高次元では MCMC（第6章マルコフ連鎖モンテカルロ目次）に移ります。
「規格化定数が要る」ではない： $f, g$ が同じ未知定数倍でも比 $f/(Mg)$ に効かないので、規格化されていない密度でも $M$ を比に合わせれば使えます。

対応シミュレーション参照

本文の Beta(2,2) 棄却サンプリング（default_rng(4)、受理率 = 1/M の確認）。