手帳と試行

メトロポリス法を熱平衡状態の系のシミュレーションの観点から導入する。

• 📄 マルコフ連鎖モンテカルロ法
• 📄 メトロポリス・ヘイスティングス法
• 📄 メトロポリス法
• 📄 メトロポリス法とカノニカル分布
• 📄 ギブスサンプリング
• 📄 ハミルトニアン・モンテカルロ法
• 📄 リープフロッグアルゴリズム
• 📄 シミュレーテッドアニーリング

目次

熱平衡状態からの導入 シミューレーション メトロポリス法

確率分布 $P(\bm x)$を、熱平衡状態の系における自由度 $\bm x$ の分布とする。

エネルギー状態 $E(\bm x)$ から別のエネルギー状態 $E(\bm y)$ への遷移が発生する頻度を $W(\bm y | \bm x)$ と表すことにしよう。系は熱平衡状態であるという仮定により、詳細釣り合い条件が成立する。

これを変形すると、Wが満たすべき条件式を以下のように表すことができる。

これを満たすような遷移の頻度 $W(\bm y | \bm x)$ として、例えば次のようなものを考えることができる。

すなわち、エネルギーが低くなるような場合には確実に遷移し、エネルギーが高くなるような場合には確率 $\exp(-\beta \Delta E)$ で遷移する。定義式から明らかなように、遷移先のエネルギーが高ければ高いほど遷移する確率は低くなる。

以上を再現するために、次のようなものを考える。まず、2つのエネルギー状態 $E(\bm x)、E(\bm y)$ における自由度 $\bm x$ と $\bm y$ の差分を $\Delta \bm x$ として表す。そして、遷移後の自由度をサンプルする代わりに、この差分の各成分を一様分布からサンプルする。

その上でエネルギーの差分 $\Delta E = E(\bm x + \Delta \bm x) - E(\bm x)$ を計算した上で、

1. もしも $\Delta E \le 0$ ならば遷移後の自由度を受け入れる: $\bm x \gets \bm x + \Delta \bm x$
2. さもなくば、確率 $\exp(-\beta \Delta E)$ で $\bm x \gets \bm x + \Delta \bm x$

とする。こうして生成される自由度の系列 $\{\bm x^i\}_{i=1}^n$ は、確率分布 $P(\bm x)$ に従う。

以上の考察から、次のようなアルゴリズムが得られる。

Algorithm 1: Metropolis method.

$\begin{darray}{rl} 1. & X \gets \{\} \\ 2. & \text{for } t \in \{1, 2, \dots, n\} : \\ 3. & \qquad \text{for } i \in \{1, 2, \dots, N\} : \\ 4. & \qquad \qquad \Delta x_i \sim {\cal U}(\Delta x_i | -c_i, c_i) \\ 5. & \qquad \Delta E \gets E(\bm x + \Delta \bm x) - E(\bm x) \\ 6. & \qquad r \sim {\cal U}(r | 0, 1) \\ 7. & \qquad \text{if } \exp(-\beta \Delta E) \gt r : \\ 8. & \qquad \qquad \bm x \gets \bm x + \Delta \bm x \\ 9. & \qquad X \gets X \cup \{\bm x\} \\ 10. & \operatorname{return} X \end{darray}$

このアルゴリズムにより確率分布 $P(\bm x)$ に従う乱数列 $\{\bm x^i\}_{i=1}^n$ を生成する方法をメトロポリス法という。ここに $P(\bm x) = \exp(-\beta E(\bm x))$ を用いて書き換えを行なえば次のアルゴリズムに帰着する。