メトロポリス・ヘイスティングス法
現時点のサンプル値は x t {\displaystyle x^{t}\,} であるとする。 メトロポリス・ヘイスティングス法では、次のサンプル x ′ {\displaystyle x'} は 確率密度関数 Q ( x ′ | x t ) {\displaystyle Q(x'|x^{t})\,} に従い生成される。 そして以下の値を計算する。
a = a 1 a 2 {\displaystyle a=a_{1}a_{2}\,}
ここで、
a 1 = P ( x ′ ) P ( x t ) {\displaystyle a_{1}={\frac {P(x')}{P(x^{t})}}\,\!}
はサンプルの候補 x ′ {\displaystyle x'\,} とその一つ前のサンプル x t {\displaystyle x^{t}\,} の尤度比であり、
a 2 = Q ( x t | x ′ ) Q ( x ′ | x t ) {\displaystyle a_{2}={\frac {Q(x^{t}|x')}{Q(x'|x^{t})}}}
は2つの提案分布( x t {\displaystyle x^{t}\,} から x ′ {\displaystyle x'\,} へとその逆方向)の比率である。 提案分布が状態に関して対称の場合は a 2 {\displaystyle \displaystyle a_{2}} は 1 となる。
次に、以下のルールにもとづき新しい状態 x t + 1 {\displaystyle x^{t+1}\,} が選択される。
a ≥ 1 {\displaystyle \displaystyle a\geq 1} の場合:
Q ( x ′ | x ) {\displaystyle \displaystyle Q(x'|x)} に従い x ′ {\displaystyle x'} を生成する
A ( x ′ , x ) {\displaystyle \displaystyle A(x',x)} に従い採択し x ′ {\displaystyle x'} に遷移する。採択されない場合は、 x ′ = x {\displaystyle x'=x} となり値を更新しない。
T {\displaystyle T} 回以下であれば2に戻る
値を保存する。2に戻る。
サンプルを適切に集めるためには、 T {\displaystyle T} は提案分布や採択率とが別に決められ、ステップ4においてサンプルが相関していないことが必要である。マルコフ過程の自己相関時間の時間のオーダーによる。
一般的にこのパラメータの決定は簡単ではないことは重要な点である。問題に対して適切にパラメータは決定されるべきである。分布に関する知識が全くない場合には一様分布が提案分布として選ばれることもある。この場合、状態 x {\displaystyle x} と状態 x ′ {\displaystyle x'} はいつも相関しないために T {\displaystyle T} の値は 1 {\displaystyle 1} に設定される。
初期化: 初期値 x 0 {\displaystyle x_{0}} と任意の確率密度関数 Q ( x | y ) {\displaystyle Q(x|y)} を決める。 関数 Q ( x | y ) {\displaystyle Q(x|y)} は過去の状態 y {\displaystyle y} が与えられたときに、候補となる状態 x {\displaystyle x} を生成する関数である。メトロポリスアルゴリズムでは Q {\displaystyle Q} は対称でなければならない。つまり Q ( x | y ) = Q ( y | x ) {\displaystyle Q(x|y)=Q(y|x)} を満たさなければならない。典型的な Q ( x | y ) {\displaystyle Q(x|y)} の選択として、 y {\displaystyle y} を平均としたガウス分布があり、この場合、 y {\displaystyle y} の近くは次も選択しやすいことになる。 Q {\displaystyle Q} は提案分布と呼ばれる。
t {\displaystyle t} 番目の更新: 確率分布 Q ( x ∗ | x t ) {\displaystyle Q(x^{*}|x_{t})} から次の状態となる候補 x ∗ {\displaystyle x^{*}} を生成する。 採択率 α = f ( x ∗ ) f ( x t ) {\displaystyle \alpha ={\frac {f(x^{*})}{f(x_{t})}}} を計算する。