マルコフ連鎖

マルコフ連鎖とは

定義（マルコフ連鎖）

状態空間を \(S\) とする。確率変数の列 \(\{X_n\}\) が \(i_0,i_1,\cdots,i_n,j\in S\) に対して

\[ P(X_{n+1}=j~|~X_0=i_0,X_1=i_1,\cdots,X_n=i_n)=P(X_{n+1}=j~|~X_{n}=i_n) \]

を満たすとき、\(\{X_n\}\) を \(S\) 上のマルコフ連鎖という。

\(X_{n+1}=j\) となる確率は直前の \(X_n\) にのみ依存し、これ以前の \(X_{n-1},\cdots,X_0\) には依存しないということです。

状態の推移

定義（推移確率・推移行列）

\(\{X_n\}\) を状態空間 \(S=\{1,2,\cdots,r\}\) 上のマルコフ連鎖とする。このとき、状態 \(i\) から状態 \(j\) に推移する確率 \[ p_{ij}:=P(X_1=j~|~X_0=i) \quad (i,j\in S) \] を状態 \(i,j\) 間の推移確率といい、この \(p_{ij}\) を成分とする行列

\[ P= \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1r}\\ p_{21} & p_{22} & \cdots & p_{2r}\\ \vdots & \vdots & \ddots & \vdots\\ p_{r1} & p_{r2} & \cdots & p_{rr}\\ \end{bmatrix} \]

を推移行列という。

また、初期状態 \(i\) から時刻 \(n\) で状態 \(j\) に推移する確率を \[ p_{ij}^{(n)}:=P(X_n=j~|~X_0=i) \] と定義し、\(p_{ij}^{(n)}\) を成分とする行列を

\[ P^{(n)}= \begin{bmatrix} p_{11}^{(n)} & p_{12}^{(n)} & \cdots & p_{1r}^{(n)}\\ p_{21}^{(n)} & p_{22}^{(n)} & \cdots & p_{2r}^{(n)}\\ \vdots & \vdots & \ddots & \vdots\\ p_{r1}^{(n)} & p_{r2}^{(n)} & \cdots & p_{rr}^{(n)}\\ \end{bmatrix} \]

と定義する。

定理（高次の推移行列とべき乗）

推移行列 \(P\) 、高次の推移行列 \(P^{(n)}~~(n\in\mathbb{N})\) に対して、次式が成り立つ。

\[ P^{(n)}=P^n \]

証明

数学的帰納法で証明する。

\(n=1\) のとき

\[ P^{(1)}=P,~~P^1=P \]

より、\(P^{(1)}=P^1\) が成り立つ。

\(n=k~~(k\in\mathbb{N})\) に対して

\[ P^{(k)}=P^k \]

が成り立つと仮定する。このとき、\(n=k+1\) の場合を考えると

\[ P^{(k+1)}=P^{(k)}P=P^kP=P^{k+1} \]

よって、\(n=k+1\) のときも成り立つ。

したがって

\[ \forall n\in\mathbb{N},\quad P^{(n)}=P^n \]

が成り立つ。

これは、マルコフ連鎖において、1ステップの推移行列 \(P\) を繰り返し掛け合わせることで、任意のステップにおける推移確率を求められることを示しています。すなわち、\(P^n\) の \((i,j)\) 成分は「状態 \(i\) から状態 \(j\) に \(n\) ステップで推移する確率」を表します。

定理（チャップマン・コルモゴロフの方程式）

\(p_{ij}^{(n)}\) に対して、次式が成り立つ。

\[ p_{ij}^{(n)}=\sum_{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)} \]

再帰的と過渡的

状態 \(i\) に一度訪れて、いずれ必ずもう一度戻ってくるとき、状態 \(i\) は再帰的であるといいます。これに対して、状態 \(i\) に一度訪れて、いずれ戻らなくなる可能性があるとき、状態 \(i\) は過渡的であるといいます。

状態 \(i\) が再帰的（状態 \(i\) に何度も戻ってくる）：
\[i \to \cdots \to 他の状態 \to \cdots \to i \to \cdots\]

状態 \(i\) が過渡的（状態 \(i\) に戻らない可能性あり）：
\[i \to \cdots \to 他の状態 \to \cdots \to 他の状態 \to \cdots\]

このことを数学的に定義するために、まず次のものを定義します。

定義（初めて推移する確率・最終推移確率）

状態 \(i\) から時刻 \(n\) で状態 \(j\) に初めて推移する確率を

\[ f_{ij}^{(n)}:=P(X_n=j,~X_r\neq j,~r=1,2,\cdots,n-1~|~X_0=i) \]

と定義する。

\[ f_{ij}:=\sum_{n=1}^\infty f_{ij}^{(n)} \]

これを用いて、再帰的、過渡的は次のように定義されます。

定義（再帰的・過渡的）

状態 \(i\) が再帰的であるとは

\[ f_{ii}=\sum_{n=1}^\infty f_{ii}^{(n)}=1 \]

が成り立つことである。

また、状態 \(i\) が過渡的であるとは

\[ f_{ii}=\sum_{n=1}^\infty f_{ii}^{(n)}\lt1 \]

が成り立つことである。

例題を解いてみましょう。

例題

状態空間を \(S=\{0,1\}\) とし、推移行列が以下で与えられている。

\[ P=\begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix} \]

このとき、各状態は再帰的か過渡的かを判定せよ。

状態 \(0\) について

\(f_{00}^{(1)}=0.8\)
\(f_{00}^{(2)}=0.2\times0.3\)
\(f_{00}^{(3)}=0.2\times0.7\times0.3\)
\(f_{00}^{(4)}=0.2\times0.7^2\times0.3\)

なので

\[ f_{00}^{(1)}=0.8,\quad f_{00}^{(n)}=0.06\cdot0.7^{n-2} \quad (n\ge2) \]

よって

\[ \begin{align} f_{00}&=f_{00}^{(1)}+\sum_{n=2}^\infty f_{00}^{(n)}\\ &=0.8+\sum_{n=2}^\infty 0.06\cdot0.7^{n-2}\\ &=0.8+\frac{0.06}{1-0.7}\\ &=0.8+0.2\\ &=1 \end{align} \]

したがって、状態 \(0\) は再帰的である。

状態 \(1\) について

定理（極限遷移確率）

\(p_{ij}^{(n)}\) に対して、次式が成り立つ。

\[ \lim_{n\to\infty}p^{(n)}=\frac{f_{ij}}{\mu_j}=\pi_jf_{ij} \]

周期性

定義（周期）

マルコフ連鎖 \(\{X_t\}\) に対して

\[ \gcd\{t\ge1~|~P(X_t=i~|~X_0=i)\gt0\} \]

を状態 \(i\) の周期という。

また、マルコフ連鎖 \(\{X_t\}\) が規約であるとき、各状態の周期はすべて等しく、その値をマルコフ連鎖 \(\{X_t\}\) の周期という。

演習問題

問題

解答