メトロポリス・ヘイスティングス法
そのため、確率分布が定義されている状態空間の次元が高い場合、マルコフ連鎖モンテカルロ法を用いることは自然である。そのためマルコフ連鎖モンテカルロ法は、多くの分野で使用されている階層ベイズモデルや高次元な統計モデルの事後分布の近似方法としてよく選ばれている。
次元が高い場合には、個々の次元ごとに異なった振る舞いをすることや、遅い混合を避けるためにすべての次元に関して適切なジャンプの大きさを決定することが問題となるため、提案分布を適切に選択することが自体が困難である。 そのような状況でしばしば取られる代替案としてはギブスサンプリングがある。ギブスサンプリングは、すべての次元から一度にサンプルするのではなく、個々の次元に関してサンプリングを行う。 これは多くの典型な階層モデルにあるように、少数の変数が他の変数を条件付けている場合には有効な方法である。 個々の変数は他の変数に関して条件づけされて1度にサンプリングされる。 他には適応的棄却サンプリング、一次元M-H ステップ、スライスサンプリングが考えられる。
提案密度 Q ( x ′ | x t ) {\displaystyle \displaystyle Q(x'|x_{t})} が x t {\displaystyle \displaystyle x_{t}} に一切依存しないことも可能であり、その場合はアルゴリズムは「独立型メトロポリス・ヘイスティングス法」という。 ふさわしい提案分布を持った独立型メトロポリス・ヘイスティングス法は高い精度が期待されるが、目標となる確率分布の事前の知識を必要とするし、次元の呪いを強く受ける危険がある。
M-H アルゴリズムを用いると、確率分布 P ( x ) {\displaystyle \displaystyle P(x)} の確率密度関数もしくは確率関数(煩雑なので、以下では「確率密度関数」に統一する)に比例する関数が計算できるならば、 いかなる確率分布 P ( x ) {\displaystyle \displaystyle P(x)} からでも、基本的には乱数列を得ることができる。
統計学や統計物理学では、しばしば興味のある確率密度関数の定数倍しかわからないことがある。定数倍部分がわからなくても乱数の生成が可能である点はM-H アルゴリズムの大きな長所である。
M-H アルゴリズムは乱数列を生成する。 乱数列の長さが長ければ長いほど、その乱数列は目標の分布P(x)を近似することになる。 乱数は反復計算によって生成される。次の乱数が従う確率分布は現在の乱数の値にのみ依存する。すなわち、乱数列はマルコフ連鎖である。
乱数列を生成する反復計算方法がアルゴリズムの重要な点である。反復計算は、次の状態となる候補を計算することと、それを採択、もしくは棄却する手続きで構成される。 採択とは候補となった状態が次の反復計算の際に使用されることで、棄却とは次の反復計算でも現在の状態が使用されることである。採択、もしくは棄却を決定する採択確率は、P(x)に関する現在の状態と次の状態の確率密度関数を比較して決定される。
以下では簡単のために、M-H アルゴリズムの最も基本的な例である、メトロポリスアルゴリズムを示す。
メトロポリスアルゴリズム
f ( x ) {\displaystyle f(x)} を目標分布 P ( x ) {\displaystyle P(x)} の確率密度関数に比例する関数とする。
数学や物理において、メトロポリス・ヘイスティングス法(もしくは M-H アルゴリズム)(メトロポリス・ヘイスティングスほう、Metropolis-Hastings algorithm) はマルコフ連鎖モンテカルロ法の一つで、直接的に乱数の生成が難しい確率分布に対し、その確率分布に収束するマルコフ連鎖を生成する手法である。生成されたマルコフ連鎖は、確率分布の近似(ヒストグラム)などの期待値、すなわち積分の近似計算に用いられる。