以下は、Haggstrom(2017)「やさしいMCMC入門」(原著2002) の2-6章からのメモである。
仕事の都合で、MCMCの基礎的な部分について考える羽目になり、いやいやちょっと待って、そもそもマルコフ連鎖がひとつの定常分布を持つってなぜいえるんだ？ と疑問に思った次第である。学力がないもので、こういうところで躓くのです。
それにしても、いったいみんなこういうのどこで覚えるの？ 大学ってところで教えてるの？ 俺も大学ってとこに在籍してたんだけど(それもずいぶん長い間)、全然習わなかったですけどね。参っちゃうなあ。
以下は次の3点についてのメモである。
- マルコフ連鎖に定常分布は存在するか？
- 定常分布が存在するけど時点0での分布が定常分布じゃなかったらマルコフ連鎖はどうなるか？
- マルコフ連鎖の定常分布はひとつに決まるか？
話がはじまるまでの準備が長いぞ。
準備1. マルコフ連鎖ってなんですか
状態空間\(S = \{s_1, \ldots, s_k\}\)があるとします。\(S\)上を動くマルコフ連鎖\((X_0, X_1, \ldots)\)があるとします。
その推移行列を\(P\)とします。つまり、すべての\(n\), すべての\(i, j \in \{1, \ldots, k\}\)、すべての\(i_0, \ldots, i_{n-1}\)について以下が成り立つ。$$ P(X_{n+1} = s_j | X_0 = s_{i_0}, X_1 = s_{i_1}, \ldots, X_n = s_i) = P_{ij}$$
たとえば、とても小さな町があって、街角\(s_1, s_2, s_3, s_4\)が時計回りに四角形をなしている。各街角には隣の街角が2つある。ある人が時点0において\(s_1\)に立っている(\(X_0 = s_1\))。各時点にコインを投げ、表ならいっぽうの街角に, 裏ならもういっぽうの街角にジャンプする。これを各時点で繰り返す、としよう。
この人の時点\(0, 1, \ldots\)での位置を\(X_0, X_1, \ldots\)としよう。\(X_n\)は\(X_{n-1}\)にのみ依存し、その条件付き分布は時点によらずに決まる。こういうのがマルコフ連鎖である。
この例での推移行列は$$ P = \left( \begin{array}{cccc} 0 & 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 & 0\end{array} \right) $$である。
時点\(n\)における\(X_n\)の確率分布を行ベクトル\(\mu^{(n)} = (\mu^{(n)}_1, \ldots, \mu^{(n)}_k)\)で表す。
定理2.1 状態空間\(S = \{s_1, \ldots, s_k\}\), 初期分布\(\mu^{(0)}\), 推移行列\(P\)を持つマルコフ連鎖の、時点\(n\)における分布\(\mu^{(n)}\)は、次で与えられる。$$ \mu^{(n)} = \mu^{(0)} P^n$$
(証明) 略。
準備2. マルコフ連鎖の定常分布とは
さて、この状態空間の上に確率分布\(\pi = (\pi_1, \ldots, \pi_k)\)があるとして、もし\(\pi P = \pi\)だったら、\(\pi\)はこのマルコフ連鎖の定常分布だ、という。「行列\(P\)について定常だ」という言い方をすることもある。
いいかえると、\(j=1,\ldots,k\)について\(\sum_{i=1}^k \pi_i P_{ij} = \pi_j\)、ということである。さらにいいかえると、「時点0での分布が\(\pi\)ならば、その後の分布もずっと\(\pi\)」ということである。
上の例で言うと、\(\pi = (1/4, 1/4, 1/4, 1/4)\)が定常分布ですね。
準備3. 非負の整数である確率変数の期待値
確率変数についての基本知識。
確率変数\(X\)が非負の整数ならば、その期待値$$ E[X] = \sum_{k=1}^\infty k P(X=k) $$ は次の表にばらせますね。$$ \begin{array}{cccc} P(X=1) & P(X=2) & P(X=3) & P(X=4) & \ldots \\ & P(X=2) & P(X=3) & P(X=4) & \ldots \\ & & P(X=3) & P(X=4) & \ldots \\ & & & P(X=4) & \ldots \\ & & & \vdots & \vdots \end{array} $$ この表の1列目の和は\(P(X=1)\), 2列目の和は\(2P(X=2)\), 3列目の和は\(3P(X=3)\), …なので、うん、辻褄があっている。
この表の各行の和は、\(P(X \geq 1), P(X \geq 2), P(X \geq 3), \ldots\)とも書ける。だから、$$ E[X] = \sum_{k=1}^\infty P(X \geq k)$$ とも書ける。
準備4. マルコフ連鎖の既約性
マルコフ連鎖が既約だというのは、長い目で見ればどこからどこにでもいけるぜ、ってことです。
きちんというと、状態\(s_i\)から出発していつの日か状態\(s_j\)に辿り着く確率がゼロでないとき、つまり$$ P(X_{m+n} = s_j | X_m = s_i) > 0$$ となる\(n\)が存在するとき、\(s_i\)は\(s_j\)に到達可能だ、という。で、すべての\(s_i, s_j \in S\)について相互に到達可能なら、これを既約という。
準備5. マルコフ連鎖の非周期性
マルコフ連鎖が非周期的だっていうのはこういうことである。時点0にある状態から出発したとして、その状態に戻ってくるかもしれない時点を列挙したとき、それがたとえば\(2, 4, 6, 8, \ldots\)だったら、これは周期的である。非周期的というのは、そういうことが起きない、っていうことである。
きちんというと、状態\(s_i\)に戻りうる時間の集合の最大公約数が1であるとき、状態\(s_i\)は非周期的だという。すべての状態が非周期的ならば、そのマルコフ連鎖は非周期的だという。
準備6. 非周期的なマルコフ連鎖なら、どこからでもそこに戻りうる日が来る
なんでも数学の世界では、こういうことがわかっているのだそうだ。
補題4.1 正の整数の集合\(A\)について、
- (1)その最大公約数が1であり、
- (2)それが和の演算について閉じていれば(つまり\(a, a’ \in A\)について \(a + a’ \in A\)ならば)、
このとき、\(n \geq N\)ならば\(n \in A\)であるような\(N \lt \infty\)が存在する。
(証明) 略。
定理4.1 状態空間\(S = \{s_1, \ldots, s_k\}\)と推移行列\(P\)をもつマルコフ連鎖\( (X_0, X_1, \ldots ) \)が非周期的であるとき、すべての\(i \in \{1, \ldots, k\}\)とすべての\(n \geq N\)に対して \( (P^n)_{ii} > 0\)となる \(N < \infty\)が存在する。
文系の私向けにひらたく言い換えるとこういうことだと思う。村々をマルコフ連鎖に従って毎日移動している家族がいるとして(大変ですね)、いつの日か娘がある村で素敵な彼を見つけ、この村に戻ってきたいようと泣くかもしれないとしよう。娘はまだ泣いていないが(つまり娘はまだ彼氏を見つけてない)、お父さんとしては気が重い。このとき、「娘よ、それがどの村であっても、翌日も同じ村にいるかもしれないよ」とはいえない(つまり遷移行列\(P\)の対角成分のなかには0があるかもしれない)。「それがどの村であっても、翌々日にはその村に戻っているかもしれない」ともいえない(つまり\(P^2\)の対角成分のなかには0があるかもしれない)。しかし、「それがどの村であっても、\(N\)日後以降の日ならばいつだって、その村に戻っているかもしれないよ」といえる\(N\)が必ずや存在する(つまり、すべての\(n \geq N\)について\(P^n\)の対角成分に0がないような有限の\(N\)が存在する)。娘さん、よかったですね。戻ったときにはおばあちゃんかもしれないけどな。
(証明) 問題のマルコフ連鎖について、状態\(s_i\)から出発して元の状態に戻ってくることのできる時間の集合を \(A_i = \{n \geq 1 : (P^n)_{ii} > 0\}\)とする。この\(A_i\)は、補題4.1のふたつの条件を満たしているでしょうか？
- (1)について。非周期的なマルコフ連鎖なので、\(A_i\)の最大公約数は1である。満たしてますね。
- (2)について。\(a, a’ \in A_i\)としますね。定義より、\(a\)時点後も\(a’\)時点後にも戻ってこれる可能性がある。ってことは、\(a + a’\)時点後にも戻ってこれる可能性がある(\(a\)時点後にいったん戻ってきてるかもしれないんじゃん)。つまり\(a + a’ \in A_i\)だ。おお、閉じておるぞ。
つまり、\(n \geq N_i\)ならば\(n \in A_i\)であるような\(N_i \lt \infty\)が存在するわけだ。\(N_1, \ldots, N_k\)の最大値を\(N\)とすれば、定理4.1が示せる。(証明終わり)
準備7. 既約かつ非周期的なら、どこからでもどこにでも行きうる日が来る
系4.1 状態空間\(S = \{s_1, \ldots, s_k\}\)と推移行列\(P\)をもつマルコフ連鎖\( (X_0, X_1, \ldots ) \)が既約かつ非周期的であるとき、すべての\(i,j \in \{1, \ldots, k\}\)とすべての\(n \geq M\)に対して \( (P^n)_{ij} > 0\)となる \(M < \infty\)が存在する。
ひらたく言い換えるとこういうことだと思う。村々をマルコフ連鎖に従って毎日移動している家族がいるとして、いつの日か娘がどこかの村の素敵な彼を見つけ(マッチングアプリとかで)、彼がいる村に行きたいよと泣くかもしれないとしよう。父としては、「娘よ、それがどの村であっても、翌日にはその村にいるかもしれないよ」とはいえない(つまり遷移行列\(P\)の成分のなかには0があるかもしれない)。「翌々日にはその村にいるかもしれないよ」ともいえない(つまり\(P^2\)の成分のなかは0があるかもしれない)。しかし、「\(M\)日後以降の日ならばいつだって、その村に戻っているかもしれないよ」といえる\(M\)が必ずや存在する(つまり、すべての\(n \geq M\)について\(P^n\)の成分に0がないような有限の\(M\)が存在する)。
既約性とはちょっと違いますね。既約性というのは、どの2状態をとっても、なんらかの期間をとれば、一方から他方へと行きうるよ、という話である。いっぽうここでいっているは、期間をある期間よりも長くとれば、どこからどこにでも行きうるよ、という話である。
(証明) 非周期性と定理2.1より、すべての\(i \in \{1, \ldots, k\}\)とすべての\(n \geq N\)について\((P^n)_{ii} \gt 0\)となる\(N \lt \infty\)が存在する。
ふたつの状態\(s_i, s_j \in S\)について考えよう。既約性より、\( (P^{n_{ij}})_{ij} \gt 0\)となる\(n_{ij}\)をみつけることができる。\(M_{ij} = N + n_{ij}\)としよう。任意の\(m \geq M_{ij}\)について、「\(s_i\)から出発して\(m\)時点後に\(s_j\)にいる確率」は「\(s_i\)から出発して\(m-n_{ij}\)時点後に\(s_i\)に戻ってきて\(m\)時点後に\(s_j\)にいる確率」より大きい。すなわち$$ P(X_m = s_j | X_0 = s_i) $$ $$ \geq P(X_{m-n_{ij}} = s_i, X_m = s_j | X_0 = s_i) $$ $$ = P(X_{m-n_{ij}} = s_i | X_0 = s_i) P(X_m=s_j | X_{m-n_{ij}} = s_i)$$ 第1項についてみると、\(m \geq M_{ij} = N+n_{ij}\)なんだから\(m -n_{ij} \geq N\)、したがって正である。第2項は\(n_{ij}\)の定義により正である。よって、すべての\(m \geq M_{ij}\)について\((P^m)_{ij} > 0\)である。\(M = \max\{ M_{11}, M_{12}, \ldots, M_{kk}\} \)とすれば系4.1が示せる。(証明終わり)
準備8. 既約かつ非周期的なマルコフ連鎖なら、到達時間は有限だ
マルコフ連鎖が\(s_i\)から出発して\(s_j\)にはじめて到達するまでの時間を、到達時間\(T_{ij}\)とする。きちんと書くと、\(X_0 = s_i\)として$$ T_{ij} = \min \{n \geq 1 : X_n = s_j \} $$ である。その平均を$$ \tau_{ij} = E[T_{ij}]$$ とする。
補題5.1. 状態空間\(S = \{s_1, \ldots, s_k\}\)と推移行列\(P\)をもつマルコフ連鎖\( (X_0, X_1, \ldots ) \)が既約かつ非周期的であるとき、任意の2つの状態\(s_i, s_j \in S\)において、\(s_i\)から出発するとき次が成り立つ。
(a) \(P(T_{ij} \lt \infty) = 1\)
(b) \(\tau_{ij} \lt \infty\)
えっ、(a)も証明しないといけないの？ 既約なんだから自明じゃない？ と思ってしまったが、考えてみたら既約であるということは、うまくすれば有限時間内に到達するよということであって、到達時間が必ず有限だということではないですね。
(b)も(a)から直接には得られない。確率変数\(X\)が有限の値しかとらないとしても、その期待値が有限だとは限らない。
(証明) 系4.1より、すべての\(i,j \in \{1, \ldots, k\}\)について \( (P^M)_{ij} \gt 0\)を満たす\(M \gt 0\)が存在する。その\(M\)について\((P^M)\)の要素の最小値を \( \alpha = \min\{ (P^M)_{ij} : i, j \in \{1, \ldots, k\}\}\) としよう。当然ながら\(\alpha \gt 0\)である。出発点を\(X_0 = s_i\)としよう。
\(s_j\)への到達時間が\(M\)より長い確率はどのくらいだろうか？ 到達時間が\(M\)より長いとき、少なくとも時点\(M\)で\(s_j\)にいることはないけど、時点\(M\)で\(s_j\)にいなかったからと言ってそれまでに着いてないとは限らないから、$$ P(T_{ij} \gt M) $$ $$ \leq P(X_M \neq s_j)$$ \(P(X_M = s_j) \geq \alpha\)より $$ \leq 1-\alpha$$ である。
こんどは、到達時間が\(2M\)より長い確率は $$ P(T_{ij} \gt 2M) $$ $$ = P(T_{ij} \gt M) P(T_{ij} \gt 2M|T_{ij} \geq M) $$ $$\leq P(T_{ij} \gt M) P(X_{2M} \neq s_j | T_{ij} \gt M) $$ $$ \leq (1-\alpha)^2$$ 同様に、到達時間が\(lM\)より長い確率は $$ P(T_{ij} \gt lM) \leq (1-\alpha)^l$$ \(l\rightarrow \infty\)のときこれは0に近づくから、$$ P(T_{ij} = 0) = 0$$ となり、(a)が示せる。
こんどは(b)について。\(T_{ij}\)は非負の整数だから、$$ E[T_{ij}] = \sum_{n=1}^\infty P(T_{ij} \geq n) = \sum_{n=0}^\infty P(T_{ij} \gt n)$$ \(M\)個ずつのブロックに区切ろう。$$ = \sum_{l=0}^\infty \sum_{n=lM}^{(l+1)M-1} P(T_{ij} \gt n)$$ 各ブロックの一番下の要素の確率で代用する(当然すこし大きめになる)。$$ \leq M \sum_{l=0}^\infty P(T_{ij} \gt lM) $$ さきほど\(P(T_{ij} \gt lM) \leq (1-\alpha)^l\)だということになりましたので$$ \leq M \sum_{l=0}^\infty (1-\alpha)^l$$ \(\sum_{k=0}^\infty \lambda^k = \frac{1}{1-\lambda}\)より $$ = M \frac{1}{1-(1-\alpha)} = \frac{M}{\alpha}$$ \(\alpha \gt 0\)だから$$ \lt \infty$$であり、(b)が示せた。(証明終わり)
準備9. 全変動収束
状態空間\(S = \{s_1, \ldots, s_k\}\)の上に、確率分布\(v^{(1)} = (v_1^{(1)}, \ldots, v_k^{(1)})\)と\(v^{(2)} = (v_1^{(2)}, \ldots, v_k^{(2)})\)があるとしよう。このふたつの分布のあいだのずれを測りたい。
その方法はいろいろあるけれど、そのひとつが、全変動距離$$ d_{TV}(v^{(1)}, v^{(2)}) = \frac{1}{2} \sum_{i=1}^k |v_i^{(1)} – v_i^{(1)}| $$ である。確率の差の絶対値の和の1/2ね。なぜ2で割るかというと、距離が0と1の間の値をとるようにしたいからである。
ちょっと話は逸れるけど、こういう風に考えても良い。状態空間\(S\)における任意の下位集合\(A\)の確率\(v^{(1)}(A), v^{(2)}(A)\)について考える。全変動距離とは、この確率の差の最大値になっている。すなわち$$ d_{TV}(v^{(1)}, v^{(2)}) = \max_{A \subset S} | v^{(1)}(A) – v^{(2)}(A) | $$ (これの証明は演習問題になっている。答えをつけてほしいよ…)
さて、いま確率分布\(v, v^{(1)}, v^{(2)}, \ldots\)があるとしよう。$$ \lim_{n \rightarrow \infty} d_{TV} (v^{(n)}, v) = 0 $$ が成り立つとき、\(v^{(n)}\)は\(v\)に全変動収束する \( v^{(n)} \rightarrow^{TV} v\)という。
大変ながらくお待たせしました。ここからが本番です。
Q1. 定常分布は存在するか？
定理5.1 任意の既約かつ非周期的なマルコフ連鎖において、少なくともひとつの定常分布が存在する。
(証明) 例によって、状態空間\(S = \{s_1, \ldots, s_k\}\)と推移行列\(P\)を持つマルコフ連鎖\((X_0, X_1, \ldots)\)について考える。\(X_0 = s_1\)とする。出発点に戻ってくるまでの時間を\(T_{11}\)、その期待値を\(\tau_{11}\)とする。
この連鎖が出発点に戻ってくるまでに\(s_i\)を訪れる回数の期待値を$$ \rho_i = \sum_{n=0}^\infty P(X_n = s_i, n \lt T_{11} ) $$ とする。戻ってくるまでの平均時間\(\tau_{11}= E[T_{11}]\)と比べると、\(\rho_i\)が\(\tau_{11}\)以上になることはできない。かつ、補題5.1(b)より、\(\tau_{11}\)は有限である。だから\(\rho_i\)も有限である。
実は、$$ \pi = \left(\frac{\rho_1}{\tau_{11}}, \frac{\rho_2}{\tau_{11}}, \ldots, \frac{\rho_k}{\tau_{11}} \right)$$ は定常分布である。以下ではそのことを示そう。
ここからは、次の3つにわけて示す。
- (a) \(j=2,\ldots,k\)について\(\sum_{i=1}^k \pi_i P_{ij} = \pi_j\)だ
- (b) \(j=1\)についても\(\sum_{i=1}^k \pi_i P_{ij} = \pi_j\)だ
- (c) \(\pi\)は確率分布だ
(a)の証明
\(j \neq 1\)としよう。
$$ \pi_j = \frac{\rho_j}{\tau_{11}} = \frac{1}{\tau_{11}} \sum_{n=0}^\infty P(X_n = s_j, n \lt T_{11} ) $$ \(j \neq 1\)だから、時点0に\(s_j\)にはいられないので$$ = \frac{1}{\tau_{11}} \sum_{n=1}^\infty P(X_n = s_j, n \lt T_{11} ) $$ \(j \neq 1\)だから、出発点に戻ってくるまでの時間が\(n\)だったら時点\(n\)に\(s_j\)にはいられないので$$ = \frac{1}{\tau_{11}} \sum_{n=1}^\infty P(X_n = s_j, n-1 \lt T_{11} ) $$ 時点\(n-1\)にどこにいたかでわけてみよう。$$ = \frac{1}{\tau_{11}} \sum_{n=1}^\infty \sum_i^k P(X_{n-1} = s_i, X_n = s_j, n-1 \lt T_{11})$$ $$ = \frac{1}{\tau_{11}} \sum_{n=1}^\infty \sum_i^k P(X_{n-1} = s_i, n-1 \lt T_{11}) P(X_n = s_j | X_{n-1} = s_i, n-1 \lt T_{11})$$ 第2項の条件のところに\(n-1 \lt T_{11}\)とあるけれど、これは削ってよい。なぜなら、\(n-1 \lt T_{11}\)かどうかは\(X_0, X_1, \ldots, X_{n-1}\)で決まるからだ。\(X_n\)からしてみたら\(X_{n-1}\)で条件付けられるかどうかだけが問題なのであり、もう\(X_{n-1} = s_i\)と条件付けられちゃっているから、\(T_{11}\)がどうかなんてどうでもよいのである。つまり第2項は\(P(X_n = s_j | X_{n-1} = s_i) = P_{ij}\)であるから、$$ = \frac{1}{\tau_{11}} \sum_{n=1}^\infty \sum_i^k P_{ij} P(X_{n-1} = s_i, n-1 \lt T_{11})$$ サメーションの順序をいれかえまっせ。$$ = \frac{1}{\tau_{11}} \sum_i^k P_{ij} \sum_{n=1}^\infty P(X_{n-1} = s_i, n-1 \lt T_{11})$$ \(m = n-1\)と書き換えて $$ = \frac{1}{\tau_{11}} \sum_i^k P_{ij} \sum_{m=0}^\infty P(X_m = s_i, m \lt T_{11} )$$ 最後のサメーションは\(\rho_i\)なので$$ = \sum_{i=1}^k \frac{\rho_i}{\tau_{11}} P_{ij} = \sum_{i=1}^k \pi_i P_{ij}$$ と、(a)を示すことができました。
(b)の証明
$$\pi_1 = \frac{\rho_1}{\tau_{11}} $$ をずーっと変形していって、\(\sum_{i=1}^k \frac{\rho_i P_{i1}}{\tau_11} = \sum_{i=1}^k \pi_i P_{i1} \) に辿り着けばいいわけだ。ところで実は\(\rho_1\)とは、この連鎖が出発点に戻ってくるまでに出発点を訪れる回数の期待値、すなわち1である。天下りでちょっとずるいけど、補題5.1(a)より、\(P(T_{11} \lt \infty)\)も1である。$$ \rho_1 = 1 = P(T_{11} \lt \infty) = \sum_{n=1}^\infty P(T_{11} = n) $$ 時点\(n-1\)にどこにいたかでわける。$$ = \sum_{n=1}^\infty \sum_{i=1}^k P(X_{n-1} = s_i, T_{11} = n)$$ 時点\(n\)には出発点にいたんだから$$ = \sum_{n=1}^\infty \sum_{i=1}^k P(X_{n-1} = s_i, X_n = s_1, T_{11} \gt n-1) $$ お、(a)の証明とほぼ同じ展開になってきたぞ。$$ = \sum_{n=1}^\infty \sum_i^k P(X_{n-1} = s_i, n-1 \lt T_{11}) P(X_n = s_1 | X_{n-1} = s_i)$$ $$ = \sum_{n=1}^\infty \sum_i^k P_{i1} P(X_{n-1} = s_i, n-1 \lt T_{11})$$ $$ = \sum_i^k P_{i1} \sum_{n=1}^\infty P(X_{n-1} = s_i, n-1 \lt T_{11})$$ $$ = \sum_i^k P_{i1} \sum_{m=0}^\infty P(X_m = s_i, m \lt T_{11} )$$ $$ = \sum_{i=1}^k \rho_i P_{i1}$$ よって $$ \pi_1 = \frac{\rho_1}{\tau_{11}} = \sum_{i=1}^k \frac{\rho_i P_{i1}}{\tau_{11}} = \sum_{i=1}^k \pi_i P_{i1}$$ と、(b)を示すことができました。
(c)の証明
\(\pi_i\)がすべて0以上なのはあきらかなので、あとは\(\pi_i\)の和が1であることを示せればよい。\(\pi_i\)の分子\(\tau_{11}\)について考えると、$$ \tau_{11} = E[T_{11}] = \sum_{n=0}^\infty P(T_{11} \gt n) $$ 時点\(n\)にどこにいるかでわけよう。$$ = \sum_{n=0}^\infty \sum_{i=1}^k P(X_n = s_i, T_{11} \gt
n)$$ サメーションの順序を入れ替えると $$ = \sum_{i=1}^k \rho_i$$ というわけで、$$ \sum_{i=1}^k \pi_i = \frac{1}{\tau} \sum_{i=1}^k \rho_i = 1 $$ と、(c)を示せました。(証明終わり)
Q2. 定常分布が存在するけど時点0での分布が定常分布じゃなかったらどうなるか？
定理5.2 (マルコフ連鎖の収束定理)
初期分布\(\mu^{(0)}\), 状態空間\(S\), 推移行列\(P\)を持つマルコフ連鎖を\((X_0, X_1, \ldots)\)とする。このマルコフ連鎖が既約かつ非周期的であるとき、その任意の定常分布\(\pi\)に対して、\(\mu^{(n)} \rightarrow^{TV} \pi\)が成り立つ。
この定理は、十分に長い時間マルコフ連鎖を走らせれば、初期分布がなんであれ、時点\(n\)における分布が定常分布に近づく、ということを示している。なお、あとで示すけど、定常分布はひとつしかない。
これから証明しますけど、この証明の方法のことをカップリングというのだそうです。
(証明) 初期分布\(\mu^{(0)}\)から初期状態\(X_0\)を得るための関数を\(\psi_{\mu^{(0)}}(U_0)\)とする。\(U_0\)は\([0,1]\)上の一様分布に従う変数である。
前の状態\(X_{n-1}\)から状態\(X_n\)を得る関数を\(\phi(X_{n-1}, U_n)\)とする。\(U_n\)は\([0,1]\)上の一様分布に従う変数である。\((U_0, U_1, \ldots)\)は互いに独立とする。
これらの関数を使って、マルコフ連鎖$$X_0 = \psi_{\mu^{(0)}}(U_0)$$ $$X_1 = \phi(X_0, U_1)$$ $$X_2 = \phi(X_1, U_2)$$ …を得たとしよう。
さらに、これとは別に、初期分布を定常分布\(\pi\)とするマルコフ連鎖$$ X’_0 = \psi_{\pi}(U’_0)$$ $$X’_1 = \phi(X’_0, U’_1)$$ $$X’_2 = \phi(X’_1, U’_2)$$ …を得たとしよう。\((U_0, U_1, \ldots)\)と\((U’_0, U’_1, \ldots)\)は互いに独立とする。よって二本の連鎖も互いに独立である。
これから、確率1で二本の連鎖が出会うということを示す。
二本の連鎖が最初に出会う時刻を \(T = \min\{n: X_n = X’_n\}\)とする。
マルコフ連鎖は既約かつ非周期的なので、系4.1より、すべての\(i, j \in \{1, \ldots, k\}\)において\( (P^M)_{ij} \gt 0\)であるような時点\(M \lt \infty\)が存在する。この\( P^M\)の要素の最小値を$$ \alpha = \min \{(P^M)_{ij} : i, j \in \{1, \ldots, k\}\}$$ とする。当然ながら\(\alpha \gt 0\)である。
時点\(M\)までに出会う確率は、時点\(M\)に出会う確率以上だから $$ P(T \leq M) \geq P(X_M = X’_M)$$ さらにそれは「時点\(M\)に\(s_1\)で出会う確率」以上だから $$ \geq P(X_M = s_1, X’_M = s_1) = P(X_M = s_1) P(X’_M = s_1)$$ 第1項について考える。出発点で分けて$$ P(X_M = s_1) = \sum_i^k P(X_0 = s_i) P(X_M = s_1| X_0 = s_1) $$ サメーションのなかの第2項は\((P^M)_{i1}\)だから、それは\(\alpha\)より大きい。$$ \geq \alpha \sum_i^k P(X_0 = s_i) = \alpha$$ 第2項についても同様である。なので、結局 $$ P(T \leq M) \geq \alpha^2$$ である。逆にいえば、時点\(M\)までに出会わない確率は$$ P(T \gt M) \leq 1-\alpha^2$$ である。
では、時点\(2M\)までに出会わない確率はどうなるか。$$ P(T \gt 2M) = P(T \gt M)P(T \gt 2M|T \gt M)$$ さきほどの結果より $$ \leq (1-\alpha^2) P(T \gt 2M|T \gt M)$$ 第2項の「時点Mまでに出会っていない条件下で時点2Mまでに出会わない条件付き確率」は「時点Mまでに出会っていない条件下で時点2Mで出会わない条件つき確率」以上だから$$ \leq (1-\alpha^2) P(X_{2M} \neq X’_{2M} | T \gt M)$$ さきほどと同様、\(P(X_{2M} = X’_{2M} | T \gt M) \geq \alpha^2\)なので、第2項は\(1-\alpha^2\)以下である。よって$$ \leq (1-\alpha^2)^2$$ 同様に$$ P(T \gt lM) \leq (1-\alpha^2)^l$$ ここから $$ \lim_{n \rightarrow \infty} P(T \gt n) = 0$$ こうして、2本の連鎖は確率1で出会うということが示せた。
ここで、3本目の連鎖\((X”_0, X”_1, \ldots\))をご紹介しよう。こいつは、2本の連鎖が出会うまでは1本目の連鎖と同じで(つまり初期分布\(\mu^{(0)}\)と一様乱数\(U_n\)で決まり)、出会ったあとは2本目の連鎖と同じである(つまり一様乱数\(U’_n\)で決まる)。こいつの推移行列もやはり\(P\)である。こいつの時点\(n\)における分布はなにかというと、1本目の連鎖と同じく、\(\mu_{(n)}\)である。ううう、なんだか騙されているような気がするけど、反論できないぜ。
任意の\(i \in \{1, \ldots, k\}\)について以下が成り立つ。$$ \mu_i^{(n)} – \pi_i = P(X”_n = s_1) – P(X’_n = s_i)$$ 2×2の表を書いてみるとわかるけど、$$ = P(X”_n = s_i, X’_n \neq s_i) – P(X”_n \neq s_i, X’_n = s_i)$$ $$ \leq P(X”_n = s_i, X’_n \neq s_i) $$ この確率は「時点\(n\)で出会ってない」確率以下だから$$ \leq P(X”_n \neq X’_n) $$ この確率は「時点\(n\)までに出会ってない」確率以下だから $$ \leq P(T \gt n)$$ さきほど示したように、これは\(n \rightarrow \infty\)のとき0に収束する。
同様に、$$ \pi_i – \mu_i^{(n)} \leq P(T \gt n)$$ であり、これも\(n \rightarrow \infty\)のとき0に収束する。
従って$$ \lim_{n \rightarrow \infty} | \mu^{(n)}_i – \pi_i | = 0$$ よって $$ \lim_{n \rightarrow \infty} d_{TV}(\mu^{(n)}, \pi) = \frac{1}{2} \lim_{n \rightarrow \infty} \sum_i^k |\mu^{(n)}_i – \pi_i| = 0$$ すなわち \(\mu^{(n)} \rightarrow^{TV} \pi\)が成り立つ。 (証明終わり)
Q3. 定常分布はひとつに決まるか？
定理5.3 (定常分布の一意性)
任意の既約かつ非周期的なマルコフ連鎖は唯一の定常分布を持つ。
(証明) 定理5.1により、定常分布は少なくともひとつの定常分布を持つ。
異なっているかもしれない2つの定常分布\(\pi, \pi’\)を想定し、初期分布を\(\pi’\)としよう。\(\pi’\)は定常分布だから、すべての\(n\)において\(\mu^{(n)} = \pi’\)である。いっぽう、定理5.2により $$ \lim_{n \rightarrow \infty} d_{TV} (\mu^{(n)}, \pi) = 0$$ である。\(\mu^{(n)} = \pi’\)を代入して$$ \lim_{n \rightarrow \infty} d_{TV} (\pi’, \pi) = 0$$ \(d_{TV} (\pi’, \pi)\)は\(n\)に依存しないから \(d_{TV} (\pi’, \pi) =0\)。よって\(\pi = \pi’\)である。(証明終わり)
おまけ. 可逆なマルコフ連鎖
状態空間\(S\)と推移行列\(P\)を持つマルコフ連鎖について、\(S\)上の確率分布\(\pi\)が、任意の\(i,j \in \{1, \ldots, k\}\)に対して$$ \pi_i P_{ij} = \pi_j P_{ji} $$ を満たすとき、\(\pi\)はマルコフ連鎖に対して可逆であるという。また、このマルコフ連鎖は可逆であるともいう。
えーと、「私がいま\(s_i\)にいて次は\(s_j\)に行く」確率と、「私がいま\(s_j\)について次は\(s_i\)に行く」確率が同じだってことですね。
定理6.1 確率分布\(\pi\)がマルコフ連鎖に対して可逆なら、\(\pi\)はその連鎖の定常分布である。
(証明) 任意の\(j\)について$$ \pi_j = \pi_j \sum_i^k P_{ji} = \sum_i^k \pi_j P_{ji} $$ 可逆だから $$ = \sum_i^k \pi_i P_{ij} $$ ゆえに\(\pi\)は定常分布である。(証明終わり)
いっぽう、定常だからといって可逆とは限らない。
たとえば、四角形\(v_1, v_2, v_3, v4\)の上を確率的にさまよう点があるとする。各時点にコインを投げ、表なら時計回り(たとえば\(v_1\)から\(v_2\)へ)、裏なら反時計回りに(たとえば\(v_1\)から\(v_4\)へ)、瞬時に移動する。これを繰り返す。ところがこのコインに偏りがあり、確率3/4で表が出るとしよう。
この連鎖は定常である(\(\pi = (\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4})\))。じゃあ可逆かというと、そんなことはない。\(v_1\)から\(v_2\)への移動についてみると、$$ \pi_1 P_{12} = \frac{1}{4} \times \frac{3}{4} = \frac{3}{16}$$ $$ \pi_2 P_{21} = \frac{1}{4} \times \frac{1}{4} = \frac{1}{16}$$ ね？ 定常だけど可逆ではない。
まとめるとこういうことです
任意の既約かつ非周期的なマルコフ連鎖は唯一の定常分布を持つ。初期分布がなんであれ、\(n\)が十分に大きければ、時点\(n\)における分布は定常分布に近づく。
以上の性質のためには、可逆性はいらないのである。可逆なら定常だけど、可逆である必要はない。
やれやれ… ようやく納得いたしました。