はじめに
Hoff (2009)およびHoff et al. (2022) 10.4.2 Why does the Metropolis-Hastings algorithm work? (メトロポリス・ヘイスティングスアルゴリズムはなぜうまくいくのか) で行われている証明について、つまずいた点があったので自分の中の整理がてら書いてみます。
Hoffの証明の流れ
Hoff (2009)およびHoff et al. (2022)では、 M-Hアルゴリズムによって生成されたマルコフ連鎖が目標分布\(p_0\)を近似できる理由の証明が以下の流れで行われています。
-
M-Hアルゴリズムは、 irreducible (非可約), aperiodic (非周期的), positive recurrent (正再帰的) なマルコフ連鎖を生成する。
-
Ergodic Theoremより、\(s \to \infty\)で
- \(\mathrm{Pr}(x^{(s)} \in A) \to \pi(A)\) for any set \(A\);
- \(\frac{1}{S} \sum g(x^{(s)}) \to \int g(x) \pi(x) dx\).
を満たす\(\pi\)が一意に存在する。
-
このような\(\pi\)は定常分布と呼ばれ、以下の 性質 を持つ
If \(x^{(s)} \sim \pi\),
and \(x^{(s+1)} \) is generated from the Markov chain starting at \(x^{(s)}\),
then \(\mathrm{Pr}(x^{(s+1)} \in A) = \pi(A)\).(一度定常分布からサンプリングされると、 それ以降のサンプルも定常分布からサンプリングされる。)
-
\(\pi(x) = p_0(x)\)が成り立つ。
1-4より、M-Hアルゴリズムによって生成されたマルコフ連鎖は、 目標分布\(p_0\)を近似できる。
引っかかった点
上記4: \(\pi(x) = p_0(x)\)の証明を見てみると、
仮に\(x^{(s)}\)を目標となる分布\(p_0\)からサンプリングし、 \(x^{(s)}\)に対してメトロポリス・ヘイスティングスアルゴリズムを用いて\(x^{(s+1)}\)を生成したと仮定する。
と書いており、この仮定を起点にして証明が進められています。 自分はここで、「その仮定が成り立つ保証なくね？」と思いました。 なぜなら、2で保証されているのは、マルコフ連鎖からサンプリングされた値がいずれ\(\pi\)からサンプリングされるということであり、目標分布\(p_0\)からサンプリングされるということではないからです。
よって満たされることが示されていない仮定をもとに証明されている\(\pi(x) = p_0(x)\)は、 この一連の証明の1-3と論理的な接続がなく、 「M-Hアルゴリズムによって生成されたマルコフ連鎖が目標分布\(p_0\)を近似できる」 ことの証明にはなっていないのではないか？という疑問が生じました。
どう納得に至ったか？
答えは簡単で、3のマルコフ連鎖の定常分布の 性質 を、 定義 として考えることで納得できました。
というのも、最初は3のマルコフ連鎖の定常分布の 性質 を、定常分布であることの 必要条件 として考えており、逆は必ずしも成り立たないと思っており、これが混乱の原因でした。 ちなみに、教科書ではこれが以下のように 性質 として紹介されています。
分布\(\pi\)はマルコフ連鎖の定常分布(stationary distribution)と呼ばれる。 この名前は以下の性質に由来する。 \(x^{(s)} \sim \pi\)のとき、\(x^{(s+1)}\)は\(x^{(s)}\)から始まるマルコフ連鎖から生成されたとすると、 \(\mathrm{Pr}(x^{(s+1)} \in A) = \pi(A)\)が成り立つ。
この書き方だと、定常分布ならばこの性質を満たすということになるけど、これを満たすから定常分布とは言っていないようにも読めますよね？
では、定常分布はそもそもどのように定義されているのでしょうか？ 例えば中妻照雄 (2019)や古澄 (2015) では、マルコフ連鎖の定常分布について、以下のように定義されています。
マルコフ連鎖の定常分布とは、遷移核\(K\)に対して、 \[ \bar{f} = \bar{f} \circ K \] を満たす分布\(\bar{f}\)のことである。
この定義を遷移核を使わずに表現したものが、3のマルコフ連鎖の定常分布の 性質 であると考えると、Hoffの証明は整合性が取れるように思えてスッキリしました。
他の教科書ではどのように証明されているか？
M-Hアルゴリズムによって生成されたマルコフ連鎖が目標分布\(p_0\)を近似できることの証明について自分が最もわかりやすく感じたのは、 我らが慶應経済学研究科のトップに君臨しておられる中妻照雄 (2019) の証明です。 詳細な証明は省きますが、以下のような流れで証明されています。
- M-Hアルゴリズムによって生成されたマルコフ連鎖の遷移核は詳細釣り合い条件を満たす
- マルコフ連鎖は詳細釣合条件を満たすような分布に対して、その不変分布を持つ
Hoff (2009)には詳細釣り合い条件についての記述がないのですが、自分的には中妻照雄 (2019)の証明の方が直接的でしっくりきました。
まとめ
本記事では、 Hoff (2009)およびHoff et al. (2022)で行われているM-Hアルゴリズムがうまくいくことの証明について、 教科書の証明の流れを紹介し、その中でつまずいた点を述べました。 また、他の証明の方法として中妻照雄 (2019) を紹介しました。
もし、この記事の主張が間違っている場合、連絡をいただけると大変ありがたいです。 最後まで読んでいただき、ありがとうございました。