[メトロポリス・ヘイスティングス法]

1. まず，$x_t$ から $x_{t+1}$ の「候補」を条件付確率 $q(x_{t+1}\mid x_t)$ に従ってランダムに生成する．
2. 次に，$x_{t+1}$ を以下の確率に従って「採択」し，採択されない場合は 「棄却」する(つまり $x_{t+1}=x_t$ とする)

   $$\alpha(x_t, x_{t+1}) = \frac{p_T(x_{t+1})q(x_t\mid x_{t+1})} {p_T(x_t)q(x_{t+1}\mid x_t)}$$ (4)

   
   
   ただし $\alpha(x_{t+1},x_t)\ge1$ の場合は必ず採択する．

候補を選ぶ分布 $q$ (提案分布: proposal distribution) はよほど特殊なものを除きかなり広い範囲で 選ぶことが可能だが³， これをどのように設計するかによって最適化問題を解く 効率が左右される．

なお，メトロポリス・ヘイスティング法の特殊な場合として， ギブスサンプラー (Gibbs sampler) や メトロポリス法 (Metropolis method)， 独立サンプラー (independence sampler) などが位置づけられる． これらは $q$ として特別な クラスのものを考えていることに相当する．