状態の分類

マルコフ連鎖 $\{X_n\}$ は離散形状態空間 $S$ と推移行列 $\{p_{i,j} \}$ を持つとする。

定義

$i,j \in S$ に対して、ある $n > 0$ があって、 $p_{i,j}^{(n)} > 0$ であるとき、 $i$ から $j$ へ到達可能であるといい、 $i \to j$ 　表す。
$i \to j$ かつ $j \to i$ であるとき、 $i \leftrightarrow j$ と表し、互いに到達可能 であるという。
全ての $i,j \in C \subset S$ に対して、 $i \leftrightarrow j$ ならば $C$ は既訳であるという。
状態 $i \in S$ から、他のどんな状態へも到達できないとき、 $i$ を吸収状態と呼ぶ。

$i \leftrightarrow j$ ならば $j \leftrightarrow i$ であり $i \leftrightarrow j$ かつ $j \leftrightarrow k$ ならば $i \leftrightarrow k$ であるので、 $\leftrightarrow$ は対称的かつ推移的である。この関係により状態を排反な集合に分類することができる。

閉集合・・・分類された集合の中で、集合の外への推移がないもの.

$S$ の部分集合 $C$ が閉集合である $\Leftrightarrow[(j\in C \land j\rightarrow k) \Rightarrow k \in C]$

となる。

状態空間 $S$ は既約かつ排反な閉集合の集まりと、既約な閉集合を含まない集合に分類できる。

$\because) \forall i \in S$ に対して

$C(i) = iを含む既約な閉集合$

と定義する。この時 $\forall i,j \in S$ に対して
$$
C(i) \cap C(j) \neq \phi
$$
ならば
$$
C(i)=C(j)
$$
である。
$$
T=S-\cup_{i\in S}C(i)
$$
とおく。この時 $S$ は $C(i),i \in S$ と $T$ に分割される。

(例)
f:id:doratai:20160127121447p:plain

例えば上の図において状態1と2,3と4は互いに到達可能である。
{1,2},{3,4}は既約、状態5は閉集合である。

周期

定義

$j \in S$ に対して
$$
\begin{equation}
d= \gcd\{n \ge 1; p_{j,j}^{(n)}>0\} (= \{n \ge 1; p_{i,j}^{(n)}>0\}の最大公約数)
\end{equation}
$$
とする時 $d$ を $j$ の周期という。特に $d=1$ の時、 $j$ は非周期的であるという。

周期に関して、Wikipediaの周期性の項目がわかりやすかったので引用したものを下記に記す。
マルコフ連鎖

状態i への回帰がk の倍数回のみに見られ、しかもk がこの性質を持つ最大の数ならば、「状態i の周期はk である」という。例えば、i への回帰が偶数回目にのみ起こるならば、i の周期は2である。

上式におけるdに当たるのが引用部分のkになる。

定理 $i,j \in S$ に対して、 $i \leftrightarrow j$ ならば、 $i$ と $j$ は同じ周期を持つ。

証明

$i,j$ の周期を $d(i),d(j)$ と表すことにする。 $d(i)$ が $d(j)$ で割切れることを証明する。

$i \rightarrow j$ より、ある $n$ に対して $p_{i,j}^{(n)} > 0$ であり、ある $m$ に対して $p_{i,j}^{(m)} > 0$ であるから、チャップマン・コルモゴロフの公式から

$$
\begin{equation}
p_{i,i}^{(n+m)} \ge p_{i,j}^{(n)}p_{j,i}^{(m)} > 0
\end{equation}
$$

が成り立つ。よって、 $n+m$ は $d(i)$ の倍数である。
$k$ を $p_{j,j}^{(k)} >$ $ を満たす任意の正整数とする。

$$
\begin{equation}
p_{i,i}^{(n+k+m)} \ge p_{i,j}^{(n)}p_{j,j}^{(k)}p_{j,i}^{(m)} > 0
\end{equation}
$$

より、 $n+m+k$ も $d(i)$ の倍数である。よって $k$ は $d(i)$ の倍数である。
従って $d(j)$ は $d(i)$ で割り切れる。
ここで、 $i,j$ は互いに到達可能であるので
$$
\begin{equation}
d(i) = d(j)
\end{equation}
$$
が言える。

この定理により、既約なマルコフ連鎖の状態は全て同じ周期を持つ。

先に示した例の図において、状態1と2は既約であり、状態1において何度となく状態1を繰り返す可能性がある。すると
$$
\begin{equation}
d(1) = \gcd\{1,2,3,4,5,\ldots\} = 1 \\
d(2) = \gcd\{2,3,4,5,6,\ldots\} = 1
\end{equation}
$$
となる。既約である二つの状態の周期は一致している。$d=1$であるので、状態1と2は非周期的である。状態3と4も既約である。状態3を考えると一旦状態4に移ってまた戻ってくるという推移をしなければならないから
$$
\begin{equation}
d(3) = \gcd\{2,4,6,8,\ldots\} = 2
\end{equation}
$$
になる。また状態3と4は既約なので当然 $d(4)=2$ になる。よって$d \neq 1$であるので、状態3,4は周期的である。
また状態5は永遠と状態5を繰り返すので
$$
\begin{equation}
d(5) = \gcd\{1,2,3,4,5,6,\ldots\} = 1
\end{equation}
$$
であり非周期的である。