Goodな生活

Goodな生活

環境エネルギー分野のシンクタンク職員です。統計学や計量経済学の学習メモ、読んだ本や映画、たまに登山や音楽の話。

【統計検定準1級】マルコフ連鎖

はじめに

この記事ではマルコフ連鎖(Markov chain)を扱います。統計検定準1級の出題範囲表の一部です。

大項目 中項目 項目(学習しておくべき用語)例
マルコフ連鎖と確率過程の基礎 マルコフ連鎖 推移確率、既約性、再帰性、定常分布

だいたいこれくらいの範囲を簡単にカバーできればokとします。

目次

マルコフ連鎖

確率変数がとる値の集合S状態空間(state space)といい、その要素を状態(state)と呼びます。状態i,j \in Sに対して確率p_{ij}は 、p_{ij} \geq 0\sum_{j \in S} p_{ij} =1を満たします。ここでi,j,x_{n-1},\cdots.x_{0} \in Sに対して、


 {
\begin{eqnarray}
P(X_{n+1} =j|X_n =i) = p_{ij} \tag{1} \\
P(X_{n+1} =j|X_n =i,X_{n-1}=x_{n-1},\cdots,X_0=x_0) = p_{ij} \tag{2} 
\end{eqnarray}
}


を仮定します。(1)(2)を満たす確率過程を(離散)マルコフ連鎖(Markov chain)と呼びます*1

(1)は状態iから状態jに移る確率がp_{ij}で与えられており、 p_{ij}推移確率(transition probability)と呼びます。(2)は推移確率が直前の状態(X_n =i)のみに依存し、過去の履歴(X_{n-1}=x_{n-1},\cdots,X_0=x_0)に依存しないことを意味します。過去の履歴が直前の状態に集約される、とも言えます。この性質をマルコフ性(Markov property)と呼びます。このマルコフ性によって、(2)の同時分布は(1)の推移確率と初期分布(P(X_0 =i))が与えられれば計算することが可能です。

推移確率行列

(i,j)成分がp_{ij}からなる行列を推移確率行列(transition probability matrix)と呼びます。第i成分が1で他は0からなるベクトルをe_iとすると、n回の推移によって状態iから状態jに推移する確率は、


 {
\begin{eqnarray}
P(X_{n} =j|X_0 =i) = e_i^{\mathrm{T}} \mathbf{P}^n e_j \tag{3} 
\end{eqnarray}
}


と表されます。

S=\{0,1,2,\cdots \}の場合、推移確率行列は、

 {
\begin{eqnarray}
\mathbf{P} = 
\begin{bmatrix}
p_{00} & p_{01} & p_{02} & \cdots \\
p_{10} & p_{11} & p_{12} & \cdots \\
p_{20} & p_{21} & p_{22} & \cdots \\
\vdots & \vdots & \vdots & \ddots \tag{4}
\end{bmatrix}
\end{eqnarray}
}

ただし\sum_{j \in S} p_{ij} =1です。

X_nが2つの値0,1だけをとる、つまりS=\{0,1\}の場合、推移確率行列は、

 {
\begin{eqnarray}
\mathbf{P} = 
\begin{bmatrix}
p_{00} & p_{01}  \\
p_{10} & p_{11} \tag{5}
\end{bmatrix}
\end{eqnarray}
}

ただしp_{00} + p_{01}  = p_{10} + p_{11} = 1を満たします。

既約性

状態i,j\in Sに対してP(X_n = j|X_0 = i) >0となる正の整数nがとれるとき、iからj到達可能であるといい、i \rightarrow jと表します。ijを入れ替えても成立するとき、ij相互到達可能であるといい、i \leftrightarrow jと表します。

任意の状態i,j\in Sが相互到達可能であるとき、マルコフ連鎖既約(irreducible)である、といいます。

再帰性

マルコフ連鎖では、ある状態が繰り返し出現することがあります。P(X_n=i|X_0=i)>0となる整数nの最大公約数を状態i周期(period)と呼び、d(i)と定義します。そのようなnが存在しないときはd(i)=0です。d(i)=1のときつまり周期が1のとき、状態i非周期的(aperiodic)であり、d(i)>1のとき状態i周期的(periodic)です。すべての状態が非周期的であるときマルコフ連鎖は非周期的となります。

マルコフ連鎖の中には、繰り返し実現する確率が1、つまり同じ状態に必ず戻るものがあります。必ず戻ることを再帰(reccurent)だと呼びます。再帰性を定義するため、次の2つの記号を導入します。


 {
\begin{eqnarray}
 p_{ij}^{(n)} &=& P(X_{n} =j|X_0 =i) \tag{6} \\
 f_{ij}^{(n)} &=& P(X_{n} =j,X_k \neq j, k=1,2,\cdots,n-1|X_0 =i) \tag{7}
\end{eqnarray}
}


(6)は状態iから出発してn回目に状態jに到着する確率を表します。ただし途中で何回でもjに到着しても問題ありません。これに対して(7)は、状態iから出発してn回目で初めて状態jに到着する確率です。さらに次の確率を導入します。


 {
\begin{eqnarray}
 f_{ij} = \sum_{n=1}^{\infty}  f_{ij}^{(n)} \tag{8}
\end{eqnarray}
}


これは状態iを出発していつかは状態jに到着する確率を表します。したがって、f_{ii}iから出発していつかはiに戻ってくる全確率です。

f_{ii}を使って、再帰性を定義すると、

となります。

定常分布

十分に長い時間が経過したとき、マルコフ連鎖の状態の確率分布はどのようになるのでしょうか。

π_i,i \in S\sum_{i \in S} π_i = 1なる確率分布とします。任意のj \in Sに対して\sum_{i \in S}π_i p_{ij} = π_jが成立するとき、π_i,i \in Sマルコフ連鎖定常分布(stationary distribution)と言います。

時点nで定常分布π_i,i \in Sに至ったと仮定します。すなわち任意のj \in Sに対して、

 {
\begin{eqnarray}
 P(X_n = j) = π_{j} \tag{9}
\end{eqnarray}
}

です。このとき、

 {
\begin{eqnarray}
 P(X_{n+1} = j) &=& \sum_{i \in S} P(X_n = i, X_{n+1} =j ) \\
                        &=& \sum_{i \in S}  P(X_n = i)P(X_{n+1}=j|X_n =i) \\
                        &=& \sum_{i \in S} π_i p_{ij} \\
                        &=& π_j \tag{10}
\end{eqnarray}
}

となり、n以降はすべて定常分布になります。
これを行列で表します。推移行列が\mathbf{P}マルコフ連鎖が時点nに状態iにある確率をπ_n(i)として、\mathbf{π_n}=(π_n(1),π_n(2),\cdots)と表します。(10)の状態では、次の漸化式


 {
\begin{eqnarray}
\mathbf{π_{n+1}} = \mathbf{π_n} \mathbf{P} \tag{11}
\end{eqnarray}
}


が成立していることになります。初期分布\mathbf{π_0}からn回の推移を繰り返すと考えると、


 {
\begin{eqnarray}
\mathbf{π_{n+1}} = \mathbf{π_0} \mathbf{P^n} \tag{12}
\end{eqnarray}
}


nを無限大に大きくして\mathbf{π}が一定値に近づくとき、


 {
\begin{eqnarray}
\mathbf{π} = \mathbf{π} \mathbf{P} =\mathbf{π} \mathbf{P^2} = \cdots = \mathbf{π} \mathbf{P^n}   \tag{13}
\end{eqnarray}
}


が成立します。したがって、


 {
\begin{eqnarray}
\lim_{n \rightarrow \infty} p_{ij}^{(n)} = π_{j}  \tag{14}
\end{eqnarray}
}


が成立します。もちろんπ_j\sum_{i \in S} π_i = 1\sum_{i \in S}π_i p_{ij} = π_jを満たします。(14)厳密には既約なマルコフ連鎖が正再帰的で非周期的という条件が必要ですが、ここでは省略します。

(13)は漸化式を使って求めることができます。定常分布自体は分かりやすい考え方ですが、計算ミスなく定常分布ベクトルを導出できるかどうかが問題ですね。

読んでいただいてありがとうございました。

参考文献

日本統計学会公式認定 統計検定 1級・準1級 公式問題集[2018〜2019年]

日本統計学会公式認定 統計検定 1級・準1級 公式問題集[2018〜2019年]

  • 発売日: 2020/03/11
  • メディア: 単行本(ソフトカバー)

東京理科大学・木村先生のスライドが大変参考になりました。
https://www.rs.noda.tus.ac.jp/skimura/AppMath3/AppMathIII-7.pdf

弱点克服 大学生の確率・統計

弱点克服 大学生の確率・統計

*1:確率変数が連続の場合はマルコフ過程と呼びます。