メトロポリス・ヘイスティングス法
M-H アルゴリズムは目標確率分布 P ( x ) {\displaystyle P(x)} に従ったサンプルの生成を行うことが目的である。 これを達成するために、漸近的に唯一の定常分布π(x)に収束するマルコフ連鎖を用いる。
ここでは簡単のため、離散の状態空間を考えることにする。マルコフ連鎖は、2つの状態間の遷移確率 P ( x ′ | x ) {\displaystyle P(x'|x)} によって一意に定義される。 次の2つの条件が満たされるとき、マルコフ連鎖は定常分布に収束する。このとき、マルコフ連鎖はエルゴード性をもつという。
定常分布の存在:定常である確率分布 π ( x ) {\displaystyle \pi (x)} が存在しなければならない。一つの十分条件として、詳細釣り合い条件がある。詳細釣り合い条件とは、状態 x {\displaystyle x} が π ( x ) {\displaystyle \pi (x)} からの乱数であるとき、状態 x {\displaystyle x} から状態 x ′ {\displaystyle x'} への遷移確率が状態 x ′ {\displaystyle x'} から状態 x {\displaystyle x} への遷移確率と等しいこと、つまり、 π ( x ) P ( x ′ | x ) = π ( x ′ ) P ( x | x ′ ) {\displaystyle \pi (x)P(x'|x)=\pi (x')P(x|x')} となることである。