複数回挑戦できるメトロポリス

マルコフ連鎖モンテカルロ法では、メトロポリス・ヘイスティングス法（MH）を用いることで、直接サンプリングが難しい確率分布からサンプリングを行うことができます。しかし、MH法では、ユーザーが提案分布を指定する必要があり、これは比較的任意に設定できます。多くの場合、確率空間内の現在の点を中心とするガウス分布が用いられ、その形式は次のようになります。${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\sigma ^{2}I)\,}$この提案分布はサンプリングしやすく、目標分布についてほとんど知識がない場合には最良の選択肢となる可能性があります。${\displaystyle \pi (x)\,}$必要に応じて、より一般的な多変量正規分布を使用することもできます。${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\mathbf {\Sigma } )}$、 どこ${\displaystyle \mathbf {\Sigma } }$これは、ユーザーが目標分布に類似していると考える共分散行列です。

この方法は無限のサンプルサイズでは定常分布に収束するはずですが、実際にはその進展は非常に遅い場合があります。${\displaystyle \sigma ^{2}\,}$が大きすぎると、MHアルゴリズムのほぼすべてのステップが拒否されます。一方、${\displaystyle \sigma ^{2}\,}$が小さすぎると、ほとんどすべてのステップが受け入れられ、マルコフ連鎖は確率空間を通るランダムウォークに似たものになります。より単純なケースでは、${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,}$我々は、${\displaystyle N\,}$ステップは距離を移動するだけで$\displaystyle {\sqrt {N}}\,}$この場合、マルコフ連鎖は妥当な時間内に確率空間を完全に探索することはできません。したがって、MH アルゴリズムではスケールパラメータ(${\displaystyle \sigma ^{2}\,}$または${\displaystyle \mathbf {\Sigma } }$)

スケールパラメータが適切に調整されていても、問題の次元が増加するにつれて、進捗は依然として非常に遅くなる可能性があります。これを確認するために、もう一度考えてみましょう。${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,}$1次元では、これは平均0、分散1のガウス分布に対応します。1次元の場合、この分布の平均ステップはゼロですが、平均二乗ステップサイズは次のように与えられます。

${\displaystyle \langle x^{2}\rangle =\int _{-\infty }^{\infty }x^{2}{\frac {1}{\sqrt {2\pi }}}e^{-{\frac {x^{2}}{2}}}dx=1}$

次元数が増加するにつれて、期待されるステップサイズはますます大きくなります。${\displaystyle N\,}$次元、半径方向の距離を移動する確率${\displaystyle r\,}$はカイ分布に関連しており、次式で与えられる。

${\displaystyle P_{n}(r)\propto r^{n-1}e^{-r^{2}/2}}$

この分布はピークが${\displaystyle r={\sqrt {N-1}}\,}$それは${\displaystyle \approx {\sqrt {N}}\,}$大型${\displaystyle N\,}$これは、ステップサイズが次元数の平方根にほぼ比例して増加することを意味します。MHアルゴリズムでは、大きなステップはほぼ必ず確率の低い領域に到達し、そのため棄却されます。

ここでスケールパラメータを追加すると${\displaystyle \sigma ^{2}\,}$戻ってみると、妥当な受入率を維持するためには、変換を行う必要があることがわかります。$\displaystyle \sigma ^{2}\rightarrow \sigma ^{2}/N$この状況では、受理率は妥当なものにできますが、確率空間の探索はますます遅くなります。これを確認するには、問題の任意の1次元に沿ったスライスを考えてみましょう。上記のスケール変換を行うことで、任意の1次元の期待ステップサイズは、${\displaystyle \sigma \,}$しかし、代わりに${\displaystyle \sigma /{\sqrt {N}}}$このステップサイズは確率分布の「真の」スケールよりもはるかに小さいので（${\displaystyle \sigma \,}$が何らかの形で事前にわかっている場合（これが最良のケースです）、アルゴリズムは各パラメータに沿ってランダムウォークを実行します。

マルチトライメトロポリス法では、エネルギーを計算する必要がある。${\displaystyle 2k-1}$各ステップで他の状態も計算します。処理の遅い部分がエネルギーの計算である場合、この方法は遅くなる可能性があります。処理の遅い部分が特定の点の近傍を見つけること、または乱数を生成することである場合も、この方法は遅くなる可能性があります。この方法が速く見えるのは、メトロポリス・ヘイスティングス法よりも「1ステップ」に多くの計算を詰め込んでいるためだと主張することもできます。