第2章マルコフ連鎖と再生過程 ¶

第2章マルコフ連鎖と再生過程

2.1 離散型確率変数 ¶

2.1.4 離散型確率変数の例¶

ポアソン分布は \(\lambda > 0\) を用いて

\begin{align*} p_i = \dfrac{\lambda^i}{i!}e^{-\lambda} \end{align*}

と表される．二項分布 \(\mathrm{Bin}(n, p)\) において平均 \(\lambda = np\) を一定にして \(n \to \infty\) としたときに近づく分布である．

2.2 連続型確率変数 ¶

2.2.3 指数分布の性質¶

指数分布は連続時間マルコフ連鎖，連続時間マルコフ決定過程において重要な分布である．

\begin{align*} f(x) = \lambda e^{-\lambda x}, \quad x > 0 \end{align*}

期待値は \(1 / \lambda\) ，分散は \(1 / \lambda^2\) である(別に期待値において密度関数が最大値を取るわけでないよ)．

無記憶性の証明には次の累積密度関数を用いる．

\begin{align*} F(x) = \begin{cases} 0 & x \leq 0 \\ 1 - e^{-\lambda x} & x > 0 \end{cases} \end{align*}

つまり \(X > x\) となる確率が \(\exp (-\lambda x)\) である．

定理2.1
無記憶性: 確率変数 \(X\) が \(X \sim \mathrm{Exp}(1 / \lambda)\) に従うとする．このとき \(X > t_0\) という条件のもとで， \(X^{\prime} = X - t_0\) は \(X\) と同じ分布に従う．

この定理の意味するところは

確率変数 \(X\) が( \(X > 0\) の下で) \(X > t\) となる確率が， \(X > t_0\) のもとで \(X > t + t_0\) となる条件付き確率と等しい

ということである．

\begin{align*} P\left(X^{\prime}>t \mid X>t_{0}\right) &=\frac{P\left(X^{\prime}>t, X>t_{0}\right)}{P\left(X>t_{0}\right)} \\ &=\frac{P\left(X-t_{0}>t, X>t_{0}\right)}{P\left(X>t_{0}\right)}=\frac{P\left(X>t_{0}+t\right)}{P\left(X>t_{0}\right)} \\ &=\frac{e^{-\lambda\left(t_{0}+t\right)}}{e^{-\lambda t_{0}}}=e^{-\lambda t}=P(X>t) \end{align*}

2.3 離散時間マルコフ連鎖 ¶

状態 \(x_i\) から状態 \(x_j\) へと推移する確率を並べた隣接行列を推移行列 \(P\) と呼ぶ．

\begin{align*} P = \begin{pmatrix} P_{00} & P_{01} & \cdots \\ P_{10} & P_{11} & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix} \end{align*}

グラフにおける確率ベクトルが \(\boldsymbol{\pi}\) のように分布しているとき，この推移行列により推移した確率ベクトルは

\begin{align*} \boldsymbol{\pi}^{\prime} = \boldsymbol{\pi}P \end{align*}

と表される．

注釈

なぜ左から横ベクトルをかけるのか

これは推移行列 \(P_{ij}\) を \(i\) から \(j\) へ推移する確率として定義したからである． \(\boldsymbol{\pi}\) から \(\boldsymbol{\pi}^{\prime}\) を求めるには， \(j\) (dst)を固定して \(j\) に至る各ノード \(i\) (src) についての和をとる 必要がある．つまり左からかけなければならない．推移行列 \(P_{ji}\) を \(i\) から \(j\) へ推移する確率として定義していれば \(\boldsymbol{\pi}\) を縦ベクトルとして， \(\boldsymbol{\pi}^{\prime} = P\boldsymbol{\pi}\) というふうに求められるのだが．

\(n\) 回推移した後の確率分布は

\begin{align*} \boldsymbol{\pi}^{(n)} = \boldsymbol{\pi}^{(0)}P^{n} \end{align*}

である．

2.2.3 状態の分類¶

\(i\) から \(j\) へと到達可能性であることを \(i \rightarrow j\) と表記する．お互いに到達可能であるならば \(i \leftrightarrow j\) と表記する．

ノード \(i\) と互いに到達可能なノードの集合 \(C(i)\) はノードの集合を互いに素に分割するため，以下のように \(\leftrightarrow\) に関する同値類を形成する．これは有向グラフの強連結成分ということである．

\(j, k \in C(i) \Leftrightarrow j \leftrightarrow k\)

\(i \leftrightarrow j \Leftrightarrow C(i) = C(j)\)

\(C(i) \neq C(j) \Rightarrow C(i) \cap C(j) = \phi\)

クラス \(C\) の中から外に出られない場合，つまり

\begin{align*} \forall i \in C(i),\, \forall j \notin C(i) \Rightarrow \lnot\, [i \rightarrow j] \end{align*}

が成立するとき， \(C(i)\) は閉じているという．これは \(C(i)\) の 中からはどのようにしても外に出られないという意味で，閉集合に近い ．また \(C(i)\) と \(C(j)\) が共通部分を持つのならば，その共通部分を通じて二つは相互に到達可能となるため，合併される．よって状態空間はこの同値類によって分割される(群論における部分群による分割みたい)．

定義2.5
既約: クラス \(S\) 内のすべてのノード \(i, j\) について \(i \leftrightarrow j\) が成立するとき， \(S\) は既約であるという．

定義2.6
初到達時間: 状態 \(i\) から \(n\) 期後初めて \(j\) に到達する確率を \(f^{(n)}_{ij}\) とする．このときの \(n\) を初到達時間という．

\(i\) から \(j\) への到達確率を \(f^{*}_{ij} = \sum_{n=1}^{\infty} f_{ij}^{(n)}\) とする．これは \(i\) にいる状態からいずれ \(j\) に到達する確率である( \(j\) に至るすべての遷移(無限) / iからのすべての遷移(無限))．

\(f^{*}_{ij} = 1\) のとき \(\mu_{ij} = \sum_{n=1}^{\infty} n f^{(n)}_{ij}\) が定義できる．これを平均初到達時間という．さらに \(\mu_{ii}\) を平均再帰時間という．

平均再帰時間 \(\mu_{ii}\) の意味: これは一度 \(i\) を訪れてから平均して \(\mu_{ii}\) 回に一回，再度 \(i\) に戻ってくるということである．

下のように

定義2.7
再帰的: ノード \(i\) に必ず戻ってくる，つまり \(f_{ii}^{*} = 1\)
正再帰的: 再帰的かつ \(\mu_{ii} < \infty\) である(平均して \(\mu_{ii}\) 回に一回戻ってくる)
零再帰的: 再帰的だけど， \(\mu_{ii} = \infty\) となっている．よく分からない(後々述べるが，有限マルコフ連鎖では存在しない)．
一時的: そもそも \(f_{ii}^{*} < 1\) であるから， \(i\) にとどまり続けるか(一時的なノードのクラスの中に居座り続ける)，そこから出ていくかという二択．

と分類される．

到達確率に関する公式¶

既約で正再帰的なクラス \(C\) においては \(\forall i, j \in C\) について \(f^{*}_{ij} = 1\) である．
\(C\) が閉じている(中では既約)とする． \(C\) の外のノード \(i\) から \(C\) の中のノード \(j, k\) への到達確率は \(f_{ij}^{*} = f_{ik}^{*}\) となって等しい．
全確率の公式より \(f_{ij}^{*} = P_{ij} + \sum_{k\neq j} P_{ik}f_{kj}^{*}\) が成立する．

既約で正再帰的な(つまり \(\mu_{ii} < \infty\) が全てのノードで成立している)有限状態のマルコフ連鎖においては，

\begin{align*} \mu_{ij} = P_{ij} + \sum_{k \neq j} P_{ik} (1 + \mu_{kj}) \end{align*}

が成立する．つまり次の連立方程式を解けばよい．

\begin{align*} \mu_{ij} = 1 + \sum_{k \neq j}P_{ik} \mu_{kj} \end{align*}

同じクラスにある(強連結成分である)状態は，再帰性が等しい．

定理2.4

\(i \leftrightarrow j\) であるならば

\(i\) が正再帰的 \(\equiv\) \(j\) が正再帰的

\(i\) が零再帰的 \(\equiv\) \(j\) が零再帰的

\(i\) が一時的 \(\equiv\) \(j\) が一時的

性質が細かく分かれていて非常にややこしい．(i)強連結成分であるか，(ii)既約であるか，(iii)周期的であるか，の3つの軸があるからだろう．

2.4 周期 ¶

マルコフ連鎖の周期を求めるには，各ノードについて以下のように隣接行列のn乗の対角成分 \(P_{ii}^{(n)}\) が初めて0でなくなるnの値を求め，それらの最大公約数を求めればよい．

P1 = np.array([[0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
              [0.0, 0.0, 1.0, 0.0, 0.0, 0.0],
              [0.6, 0.0, 0.0, 0.4, 0.0, 0.0],
              [0.0, 0.0, 0.0, 0.0, 1.0, 0.0],
              [0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
              [1.0, 0.0, 0.0, 0.0, 0.0, 0.0]])

for i in range(1, 7):
    print("================ i = %d ==================" % (i))
    mat = np.linalg.matrix_power(P1, i)
    print(np.diag(mat))

以下のようになる．

================ i = 1 ==================
[ 0.  0.  0.  0.  0.  0.]
================ i = 2 ==================
[ 0.  0.  0.  0.  0.  0.]
================ i = 3 ==================
[ 0.6  0.6  0.6  0.   0.   0. ]
================ i = 4 ==================
[ 0.  0.  0.  0.  0.  0.]
================ i = 5 ==================
[ 0.  0.  0.  0.  0.  0.]
================ i = 6 ==================
[ 0.76  0.76  0.76  0.4   0.4   0.4 ]

この場合 \(\{1, 2, 3\}\) では3乗， \(\{4, 5, 6\}\) では6乗すると \(P_{ii}^{(n)} > 0\) となるので，周期は3である．

定理2.5: 状態 \(i, j \in S\) が強連結成分であるならば(同じクラスであるならば)同じ周期をもつ．

推移行列の側面でいうと， \(i\) が周期的ならば \(P_{ii}^{(n)}\) は時刻が周期倍ではないときに，ゼロになっているということである．

定理2.6

(a) \(j\) が非周期かつ正再帰的であるならば任意の状態 \(i\) に対して

\(\lim_{n \to \infty} P_{ij}^{(n)} = \dfrac{f_{ij}^{*}}{\mu_{jj}}\)

\(i\) から \(j\) への移動確率は \(f_{ij}^{*}\) であり，その後は平均して \(\mu_{jj}\) 回に一回訪れる．よって平均して \(f_{ij}^{*} / \mu_{jj}\) 回に一回訪れるという意味．

(b) \(i \leftrightarrow j\) ( \(i = j\) も含む)のとき

\(j\) が非周期かつ正再帰的ならば

(a)の特別な場合として \(i\) も再帰的であるから \(f_{ij}^{*} = 1\) となっており

\(\lim_{n \to \infty} P_{ij}^{(n)} = \dfrac{1}{\mu_{jj}} > 0\)

\(j\) が非周期かつ零再帰的ならば

\(\mu_{jj} = \infty\) より

\(\lim_{n \to \infty} P_{ij}^{(n)} = 0 \left( = \dfrac{1}{\mu_{jj}} \right)\)

\(j\) が非周期かつ一時的ならば

\(\lim_{n \to \infty} P_{ij}^{(n)} = 0\)

\(j\) が周期 \(q(j)\) を持ちかつ正再帰的であるならば

\(\lim_{n \to \infty} P_{ij}^{(nq(j))} = \dfrac{q(j)}{\mu_{jj}}\)

2.5 定常確率と極限確率 ¶

極限確率は推移行列 \(P\) の無限乗で表されるため，もしそれが一意に収束するなら Wikipedia も参照．

	極限分布
	定常分布
	均衡分布
既約かつ再帰的？	Yes	Yes	No
非周期的？	非周期的	周期的	両方
一意？	Yes	No	No
公式	\(\pi_j =\lim_{n\to \infty}p_{ij}^{(n)}=\dfrac{1}{\mu_{jj}}\)	\(\pi_j =\dfrac{1}{\mu_{jj}}\)	非周期的なら \(\lim_{n \to \infty} p_{ij}^{(n)} = \dfrac{f_{ij}}{\mu_{jj}}\)

第2章 マルコフ連鎖と再生過程¶

2.1 離散型確率変数¶