拒否サンプリング

数値解析と計算統計学において、棄却サンプリングは分布から観測値を生成するために使用される基本的な手法です。これは一般的に受容拒否法または「受容拒否アルゴリズム」とも呼ばれ、厳密なシミュレーション手法の一種です。この方法は、あらゆる分布に適用できます。$\displaystyle \mathbb {R} ^{m}}$密度を持つ。

棄却サンプリングは、1 次元のランダム変数をサンプリングするには、2 次元のデカルトグラフを一様ランダムサンプリングし、その密度関数のグラフの下の領域にサンプルを保持できるという観察に基づいています。 ^{[ 1 ] [ 2 ] [ 3 ]}この性質はN次元関数にも拡張できることに注意してください。

ジョン・フォン・ノイマン^{[ 4 ]}が使用し、ビュフォンの針にまで遡るこのアルゴリズムは、 （目標とする）確率密度関数からサンプルを抽出する。${\displaystyle f(x)}$これは、${\displaystyle f_{\varpropto }(x)}$より単純な（提案）確率密度からの抽出を使用する${\displaystyle g(x)}$次のように：

棄却サンプリング

入力

ターゲット密度${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$提案密度${\displaystyle g(x)}$、 絶え間ない${\displaystyle M}$そのため${\displaystyle f_{\varpropto }(x)\leq Mg(x)}$すべての人々のために${\displaystyle x}$。

アルゴリズム

1. サンプル${\displaystyle X\sim g(x)}$
2. サンプル${\displaystyle U\sim \mathrm {Unif} (0,1)}$独立して${\displaystyle X}$。
3. 尤度比を計算する${\displaystyle W={\dfrac {f_{\varpropto }(X)}{g(X)}}}$。
4. もし${\displaystyle W<M\times U}$、 拒否する${\displaystyle X}$ステップ1から繰り返します。そうでない場合は、受け入れて出力します。${\displaystyle X}$。

出力

サンプル${\displaystyle X}$から引き出された${\displaystyle f}$。

アルゴリズムは平均を取ります${\displaystyle {\frac {M}{\int f_{\varpropto }(y)dy}}}$サンプルを入手するための拒否。

棄却サンプリングの動機を視覚化するために、確率変数の確率密度関数(PDF) を大きな長方形のボードにグラフ化し、そこにダーツを投げることを想像してください。ダーツはボード全体に均等に分布していると仮定します。次に、曲線の下の領域外にあるすべてのダーツを取り除きます。残りのダーツは曲線の下の領域内に均等に分布し、${\displaystyle x}$これらのダーツの位置は、確率変数の密度に従って分布します。これは、曲線が最も高い位置、つまり確率密度が最も高い位置にダーツが着地する余地が最も大きいためです。

先ほど説明した視覚化は、「提案分布」が一様である特定の形式の棄却サンプリングに相当します。したがって、そのグラフは長方形になります。一般的な形式の棄却サンプリングでは、ボードは必ずしも長方形ではなく、何らかの提案分布の密度（必ずしも正規化されているとは限らない）に従って形状が決まると想定しています。${\displaystyle 1}$（例えば、反転サンプリングを用いるなどして）サンプリング方法が分かっている曲線領域である。その形状は、サンプリング対象の分布と同じ高さ以上でなければならず、曲線領域がサンプリング対象の分布を完全に包み込むようにする必要がある。そうでない場合、サンプリング対象の曲線領域の一部に到達できないことになる。

棄却サンプリングは次のように機能します。

1. サンプルポイント${\displaystyle x}$提案分布からの軸。
2. この場所に垂直線を引いてください。${\displaystyle x}$-位置、提案分布の確率密度関数のy値まで。
3. この線に沿って均一にサンプリングします。サンプリングされた値がこの垂直線上の目的の分布の値よりも大きい場合は、その分布を棄却します。${\displaystyle x}$-値を取得し、ステップ1に戻ります。そうでない場合は、${\displaystyle x}$-値は、目的の分布からのサンプルです。

このアルゴリズムは、関数が1に積分されるかどうかに関係なく、任意の曲線の下の領域からサンプリングするために使用できます。実際、関数を定数でスケーリングしても、サンプリングされた値には影響しません。${\displaystyle x}$したがって、このアルゴリズムは、正規化定数が不明な分布からサンプリングするために使用できます。これは、計算統計学ではよくあることです。

以下の解析では、簡略化のために以下のことを仮定する。 ${\displaystyle f\equiv f_{\varpropto }}$棄却サンプリング法は、確率密度関数を持つ目標分布からサンプリング値を生成する。 ${\displaystyle f(x)}$確率密度を持つ提案分布を使用することにより${\displaystyle g(x)}$アイデアは、サンプル値を生成できるということです。${\displaystyle f}$代わりにサンプリングすることで${\displaystyle g}$そしてサンプルを受け入れる${\displaystyle f}$確率で${\displaystyle f(x)/(Mg(x))}$から抽選を繰り返す${\displaystyle g}$値が受け入れられるまで。 ${\displaystyle M}$尤度比には一定の有限の上限がある${\displaystyle f(x)/g(x)}$満足${\displaystyle M<\infty }$の支援を超えて${\displaystyle f}$; 言い換えると、${\displaystyle M}$満たさなければならない${\displaystyle f(x)\leq Mg(x)}$すべての値に対して${\displaystyle x}$。ただし、これには以下のサポートが必要です。${\displaystyle g}$以下のサポートを含める必要があります${\displaystyle f}$-言い換えると、${\displaystyle g(x)>0}$いつでも${\displaystyle f(x)>0}$。

この方法の検証はエンベロープ原理です。ペアをシミュレートすると${\textstyle (x,v=u\cdot Mg(x))}$部分グラフ上で均一なシミュレーションを生成する${\textstyle Mg(x)}$次のようなペアのみを受け入れる${\textstyle u<f(x)/(Mg(x))}$そしてペアを生成する${\displaystyle (x,v)}$サブグラフ全体に均一に分布${\displaystyle f(x)}$したがって、わずかに、${\displaystyle f(x).}$

これは、十分な数の複製があれば、アルゴリズムは目的の分布からサンプルを生成することを意味します。${\displaystyle f(x)}$このアルゴリズムには、メトロポリスアルゴリズムなど、いくつかの拡張版があります。

この方法は、モンテカルロ法全般に関連するものであり、マルコフ連鎖モンテカルロアルゴリズムも対象分布からのシミュレーションを実現するために代理分布を使用する。${\displaystyle f(x)}$これは、メトロポリスアルゴリズムなどのアルゴリズムの基礎を形成します。

無条件受諾確率は、提案されたサンプルのうち受諾される割合であり、$${\displaystyle {\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} \mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\\[6pt]&=\operatorname {E} \left[\operatorname {E} [\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y]\right]&{\text{(by tower property)}}\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr |}Y\right)\right]\\[6pt]&=\operatorname {E} \left[{\frac {f(Y)}{Mg(Y)}}\right]&({\text{because }}\Pr(U\leq u)=u,{\text{when }}U{\text{ is uniform on }}(0,1))\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}}$$どこ${\displaystyle U\sim \mathrm {Unif} (0,1)}$、そしてその価値は${\displaystyle Y}$毎回、密度関数に基づいて生成されます${\displaystyle g(\cdot )}$提案配布の。

必要なサンプル数${\displaystyle g}$受け入れられた値を得るには、確率で幾何分布に従う必要がある。${\displaystyle 1/M}$平均${\displaystyle M}$直感的に、${\displaystyle M}$これは、アルゴリズムの計算複雑度を測る指標として、必要とされる反復回数の期待値です。

上記の式を書き直すと、$${\displaystyle M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}}$$ ご了承ください${\textstyle 1\leq M<\infty }$上記の式により、${\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}$は、区間内の値しか取れない確率です。${\displaystyle [0,1]}$。 いつ${\displaystyle M}$が1に近いほど、その比率の変化が少ないほど無条件の受容確率は高くなる。${\displaystyle M}$尤度比の上限値${\textstyle f(x)/g(x)}$実際には、${\displaystyle M}$1に近い値が好ましい。これは、平均して棄却されるサンプルが少なくなり、アルゴリズムの反復回数が少なくなることを意味するからである。この意味で、${\displaystyle M}$できるだけ小さく（それでも満足できる）${\displaystyle f(x)\leq Mg(x)}$これは、${\displaystyle g(x)}$一般的には似ているべきである${\displaystyle f(x)}$何らかの形で。ただし、${\displaystyle M}$1 と等しくなることはない。それは、${\displaystyle f(x)=g(x)}$つまり、目標分布と提案分布は実際には同じ分布であるということです。

棄却サンプリングは、多くの場合、${\displaystyle f(x)}$サンプリングが困難になる。棄却アルゴリズムの 1 つの反復では、提案分布からのサンプリング、一様分布からの抽出、および評価が必要となる。${\displaystyle f(x)/(Mg(x))}$表現。したがって、棄却サンプリングは、次のような場合に他の方法よりも効率的です。${\displaystyle M}$これらの操作にかかる費用（これは、棄却サンプリングによってサンプルを取得する際の予想費用です）は、他の方法を使用してサンプルを取得する費用よりも低くなります。

棄却サンプリングは、状況によっては単純な方法に比べてはるかに効率的になることがあります。たとえば、サンプリングの問題が与えられた場合${\textstyle X\sim F(\cdot )}$条件付き${\displaystyle X}$与えられた集合${\displaystyle A}$つまり、${\textstyle X|X\in A}$、 時々${\textstyle X}$単純な方法（例えば逆変換サンプリング）を用いて容易にシミュレートできる。

• サンプル${\textstyle X\sim F(\cdot )}$独立して、満足できるものを受け入れる${\displaystyle \{n\geq 1:X_{n}\in A\}}$
• 出力：${\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}$（統計における切り捨ても参照）

問題は、このサンプリングが困難で非効率的である可能性があるということです。${\textstyle \mathbb {P} (X\in A)\approx 0}$予想される反復回数は${\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}$これは無限大に近い値になる可能性がある。さらに、棄却サンプリング法を適用した場合でも、境界値を最適化することは常に困難である。${\displaystyle M}$尤度比の場合。多くの場合、${\displaystyle M}$が大きく、拒否率が高い場合、アルゴリズムは非常に非効率になる可能性があります。自然指数族（存在する場合）、別名指数傾斜は、計算複雑度と値を下げることができる提案分布のクラスを提供します。${\displaystyle M}$計算を高速化します（例：自然指数型分布族の扱いを参照）。

確率変数が与えられた場合${\displaystyle X\sim F(\cdot )}$、${\displaystyle F(x)=\mathbb {P} (X\leq x)}$は目標分布です。簡略化のため、密度関数は明示的に次のように書けると仮定します。${\displaystyle f(x)}$提案を次のように選択してください

$${\displaystyle {\begin{aligned}F_{\theta }(x)&=\mathbb {E} \left[\exp(\theta X-\psi (\theta ))\mathbb {I} (X\leq x)\right]\\&=\int _{-\infty }^{x}e^{\theta y-\psi (\theta )}f(y)dy\\g_{\theta }(x)&=F'_{\theta }(x)=e^{\theta x-\psi (\theta )}f(x)\end{aligned}}}$$

どこ${\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}$そして${\displaystyle \Theta =\{\theta$ :\psi (\theta )<\infty \}} 。明らかに、${\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}$は自然指数型分布族に属する。さらに尤度比は

$${\displaystyle Z(x)={\frac {f(x)}{g_{\theta }(x)}}={\frac {f(x)}{e^{\theta x-\psi (\theta )}f(x)}}=e^{-\theta x+\psi (\theta )}}$$

ご了承ください${\displaystyle \psi (\theta )<\infty }$これは、それが確かにキュムラント生成関数であることを意味します。つまり、

${\displaystyle \psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }}$。

提案のキュムラント生成関数、ひいては提案のキュムラントを導出することは容易である。

${\displaystyle {\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}\right|_{\eta =0}\\\mathrm {Var} _{\theta }(X)&=\left.{\frac {\partial ^{2}\psi _{\theta }(\eta )}{\partial ^{2}\eta }}\right|_{\eta =0}\end{aligned}}}$

簡単な例として、${\displaystyle F(\cdot )}$、${\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}$、 と${\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}$目標はサンプリングすることです${\displaystyle X|X\in \left[b,\infty \right]}$、 どこ${\displaystyle b>\mu }$分析結果は以下のとおりです。

• 提案書の配布形式を選択してください${\displaystyle F_{\theta }(\cdot )}$キュムラント生成関数は

${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\theta )=(\mu +\theta \sigma ^{2})\eta +{\frac {\sigma ^{2}\eta ^{2}}{2}}}$、

これはさらに正規分布であることを示唆している${\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}$。

• よく選ばれたものを決定する${\displaystyle \theta ^{*}}$提案配布の場合。この設定では、直感的に選択する方法は${\displaystyle \theta ^{*}}$設定する

${\displaystyle \mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b}$、

それは${\displaystyle \theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}.}$提案の分布は次のようになる。${\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}$。

• 目標値、提案値、尤度比を明確に記述してください。

$${\displaystyle {\begin{aligned}f_{X|X\geq b}(x)&={\frac {f(x)\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\\g_{\theta ^{*}}(x)&=f(x)\exp(\theta ^{*}x-\psi (\theta ^{*}))\\Z(x)&={\frac {f_{X|X\geq b}(x)}{g_{\theta ^{*}}(x)}}={\frac {\exp(-\theta ^{*}x+\psi (\theta ^{*}))\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\end{aligned}}}$$

• 境界を導出する${\displaystyle M}$尤度比について${\displaystyle Z(x)}$これは減少関数である${\displaystyle x\in [b,\infty ]}$、 したがって

$${\displaystyle M=Z(b)={\frac {\exp(-\theta ^{*}b+\psi (\theta ^{*}))}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} \left(\mathrm {N} (0,1)\geq {\frac {b-\mu }{\sigma }}\right)}}}$$

• 棄却サンプリング基準:${\displaystyle U\sim \mathrm {Unif} (0,1)}$、 もし

$${\displaystyle U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)}$$

保持する、値を受け入れる${\displaystyle X}$そうでない場合は、新しいサンプルを引き続きサンプリングします。${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$そして新しい${\textstyle U\sim \mathrm {Unif} (0,1)}$承認されるまで。

上記の例では、効率の測定として、自然指数族に基づく棄却サンプリング法の反復回数の期待値はオーダーである。${\displaystyle b}$つまり${\displaystyle M(b)=O(b)}$一方、単純な方法では、反復回数の期待値は${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$これははるかに非効率的です。

一般的に、提案分布のパラメトリッククラスを指数的に傾斜させることで、提案分布を直接特徴付ける有用な特性により、最適化問題を都合よく解決できます。この種の問題をシミュレートするには、${\displaystyle X}$条件付き${\displaystyle X\in A}$単純分布のクラスの中で、計算の複雑さをある程度制御し、計算速度を大幅に向上させるには、自然指数型分布族を用いるのがコツです。実際、自然指数型分布族を用いるのには、深い数学的な理由があります。

棄却サンプリングでは、目標分布を知ること（具体的には、任意の時点で目標確率密度関数を評価できること）が必要です。

棄却サンプリングでは、サンプリング対象の関数が特定の領域に高度に集中している場合（例えば、ある場所にスパイクがある関数など）、不要なサンプルが多数取得される可能性があります。多くの分布では、この問題は適応拡張（適応棄却サンプリングを参照）を使用するか、一様分布の比率法による適切な変数変換によって解決できます。さらに、問題の次元が大きくなるにつれて、埋め込みボリュームと埋め込みボリュームの「角」の比率がゼロに近づくため、有用なサンプルが生成される前に多くの棄却が発生し、アルゴリズムが非効率的で実用的でなくなります。次元の呪いを参照してください。高次元では、通常、メトロポリスサンプリングやギブスサンプリングなどのマルコフ連鎖モンテカルロ法といった別のアプローチを使用する必要があります。（ただし、多次元サンプリング問題を一連の低次元サンプルに分解するギブスサンプリングでは、ステップの1つとして棄却サンプリングを使用する場合があります。）

有限定数がない場合${\displaystyle M}$条件を満たす${\displaystyle M\geq \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$ 存在する、または適切な有限${\displaystyle M<\infty }$計算が非常に困難であるため、修正版の棄却サンプリングアルゴリズムを使用して、ターゲットから（近似的に）シミュレーションを行うことができます。${\displaystyle f}$以下のように。^{[ 5 ]}

再生型拒否サンプリング

入力

ターゲット密度${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$提案密度${\displaystyle g(x)}$大きな定数 ${\displaystyle M}$。

アルゴリズム

カウンターを設定${\displaystyle t\leftarrow 0}$。

1. サンプル${\displaystyle X\sim g(x)}$および増加${\displaystyle t\leftarrow t+1}$。
2. 尤度比を計算する${\displaystyle W_{t}={\dfrac {f_{\varpropto }(X)}{g(X)}}}$。
3. もし${\displaystyle W_{1}+\cdots +W_{t}<M}$、 拒否する${\displaystyle X}$ステップ1から繰り返します。そうでない場合は、受け入れて出力します。${\displaystyle X}$。

出力

サンプル${\displaystyle X}$おおよそ${\displaystyle f}$。

上記の再生バージョンと古典的な棄却サンプリングとの唯一の違いは、受容決定がすべての尤度比の累積和に基づいているかどうかである。${\displaystyle W_{1}+\cdots +W_{t}}$を超える${\displaystyle M}$（つまり、${\displaystyle W_{1}+\cdots +W_{t}>M}$現在の尤度比が${\displaystyle W_{t}}$を超える${\displaystyle M\times U}$（つまり、${\displaystyle W_{t}>M\times U}$)

次のように示せる。${\displaystyle M\rightarrow \infty }$アルゴリズムの出力変数 ${\displaystyle X=X_{M}}$分布は密度の目標値に収束する${\displaystyle f}$[ ^{5 ]​}

最適な境界定数に関する知識を必要としない別のアプローチ ${\displaystyle \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$これは経験的上限棄却サンプリング法である。^{[ 6 ]}

多くの分布において、無駄なスペースをあまり使わずに、与えられた分布を含む提案分布を見つけることは困難です。この困難を克服し、さまざまな分布から効率的にサンプリングするために使用できる棄却サンプリングの拡張は、適応型棄却サンプリング（ARS）として知られています（ただし、対数凹型の密度関数を持つ分布に限ります。実際、一般的な分布のほとんどは対数凹型の密度関数を持ち、密度関数自体が凹型でない分布も同様です） 。

ギルクスが1992年に最終的に導入したこの技術には、3つの基本的な考え方があります。^{[ 7 ]}

1. 役に立つなら、代わりにエンベロープ分布を対数空間（例えば対数確率や対数密度）で定義してください。つまり、${\displaystyle h\left(x\right)=\log g\left(x\right)}$の代わりに${\displaystyle g\left(x\right)}$直接。
   • 代数的に複雑な密度関数を持つ分布は、対数密度関数が比較的単純であることが多い（つまり、${\displaystyle f\left(x\right)}$散らかっていて、${\displaystyle \log f\left(x\right)}$扱いやすい、あるいは少なくとも区分的線形性に近いかもしれない。
2. 単一の均一なエンベロープ密度関数の代わりに、区分的線形密度関数をエンベロープとして使用してください。
   • サンプルを拒否する必要があるたびに、次の値を使用できます。${\displaystyle f\left(x\right)}$区分的近似を改善するために評価した${\displaystyle h\left(x\right)}$したがって、これにより次回の試行が却下される可能性が低くなります。漸近的には、サンプルを却下する必要が生じる確率はゼロに収束し、実際には非常に速やかに収束することがよくあります。
   • 提案されているように、選択された点が却下された場合はいつでも、選択された点と同じx座標を持つ点で曲線に接する別の線分で包絡線を引き締めます。
   • 提案された対数分布の区分的線形モデルは、区分的指数分布のセット（つまり、1つ以上の指数分布のセグメントを端から端まで連結したもの）をもたらします。指数分布は性質が良く、よく理解されています。指数分布の対数は直線であるため、この方法は本質的に密度の対数を一連の線分で囲むことになります。これが対数凹制約の源です。分布が対数凹である場合、その対数は凹（逆U字型）となり、曲線に接する線分は常に曲線を越えることを意味します。
   • 対数空間で作業しない場合は、区分的線形密度関数を三角形分布を介してサンプリングすることもできます^{[ 8 ]。}
3. （対数）凹性要件をさらに活用して、評価コストを回避できる可能性があります。${\displaystyle f\left(x\right)}$サンプルが受理された場合。
   • 値を使用して区分的線形上限（「包絡線」関数）を構築できるのと同様に${\displaystyle h\left(x\right)}$現在の拒否の連鎖で評価する必要があったこれらの値を使用して、区分的線形下限（「圧縮」関数）を構築することもできます。
   • 評価する前に（費用がかかる可能性のある）${\displaystyle f\left(x\right)}$サンプルが受け入れられるかどうかを確認するために、(理想的にはより安価な) と比較することで、受け入れられるかどうかがすでにわかっている場合があります。${\displaystyle g_{l}\left(x\right)}$（または${\displaystyle h_{l}\left(x\right)}$この場合）利用可能な圧縮機能。
   • この絞り込み処理は、Gilks​​氏が推奨している場合でも、必須ではありません。せいぜい、（複雑で計算コストの高い）目標密度関数の評価を1回分削減できるだけです。しかし、特に計算コストの高い密度関数（棄却率が急速にゼロに収束すると仮定した場合）では、最終的な実行時間に大きな違いが生じる可能性があります。

この方法は基本的に、固定数の線分（場合によっては単一の接線）から始めて、曲線より上に留まりつつ、対数にますますよく近似する直線セグメントの包絡線を順次決定していくというものです。切り捨てられた指数分布に従う乱数からのサンプリングは簡単です。適切な区間と対応する切り捨て条件を持つ一様乱数の対数を取るだけです。

残念ながら、ARS は対数凹型の目標密度からのサンプリングにしか適用できません。そのため、非対数凹型の目標分布に対処するために、文献では ARS の拡張がいくつか提案されています。^{[ 9 ] [ 10 ] [ 11 ]}さらに、自己調整型の提案密度 (つまり、目標に合わせて自動的に構築され適応される提案) を構築する汎用サンプラーを得るために、ARS とメトロポリス・ヘイスティングス法のさまざまな組み合わせが設計されています。この種のメソッドは、適応型棄却メトロポリスサンプリング (ARMS) アルゴリズムと呼ばれることがよくあります。^{[ 12 ] [ 13 ]}結果として得られる適応型手法は常に適用できますが、この場合、生成されたサンプルは相関しています (ただし、反復回数が増えるにつれて相関はすぐにゼロになります)。

• 逆変換サンプリング
• 制服の比率
• 擬似乱数サンプリング
• ジッグラトアルゴリズム

• Robert, CP; Casella, G. (2004).モンテカルロ統計法（第2 版）. ニューヨーク：Springer-Verlag.