メトロポリス・ヘイスティングス法
直感的にはこれがアルゴリズムの仕組みであり、目的の確率分布に従った乱数を近似的に生成する方法である。
棄却法など、確率分布から直接独立に乱数を生成する方法と異なり、M-H アルゴリズムなどのマルコフ連鎖モンテカルロ法はいくつかの短所がある。
乱数列が相関していること。長い乱数列を生成しても、近接した乱数は相関をもち、確率分布を正しく反映したものではない。相関が高ければ、目標となる確率分布を近似するのに、多くの反復計算が必要になる。相関を小さくする工夫はいくつかある。ひとつは、あらかじめ決めた整数 n {\displaystyle n} に対し、 n {\displaystyle n} 個飛ばしで乱数を集める方法である。整数 n {\displaystyle n} の値は、しばしば乱数列を用いて計算した自己相関関数をもとに決められる。しかし整数 n {\displaystyle n} の値が大きすぎると、その分反復計算が増えてしまう。もうひとつは、次の状態の候補を現在時点より、適度に遠くへ提案する方法である。しかしあまり遠くへ提案しすぎれば棄却確率が増加してかえって相関が小さくなる。
反復計算で生成されたマルコフ連鎖は、ゆるい十分条件のもとで、目標の分布に収束されることが保証されている。初期値が確率密度関数の小さい領域にあると、目標の分布に近づくのが遅れ、目標の分布の近似に大きなバイアスを生む危険がある。その対策として、反復計算の最初の方の部分を切り捨てる、burn-inがしばしば有効である。
確率分布の近似に使われる基本的な棄却法は、その棄却確率が次元数の関数として指数関数的に増加する、次元の呪いの影響を受ける。M-Hアルゴリズムなどマルコフ連鎖モンテカルロ法では、次元の影響が同程度には起きないことが多い。