Goodな生活

経済学修士→環境コンサル→データサイエンス

マルコフ連鎖

推移確率行列

確率変数X_0,X_1,\cdots,X_nマルコフ連鎖であるとき、1期前の状態のみに依存し、それ以前の状態には依存しないことを意味する。過去のすべての履歴が直前の状態に集約される、とも言える。

 {
\begin{align}
P(X_n = j | X_{n-1} = i, X_{n-2}, \cdots, X_0) = P(X_n = j | X_{n-1} = i) \tag{1}
\end{align}
}

マルコフ連鎖X_nが2つの値0,1しかとらないと仮定する。このときX_nの推移は次の確率の行列で表現できる。

 {
\begin{align}
P &= 
\begin{pmatrix}
p_{00} & p_{01}  \\
p_{10} & p_{11} 
\end{pmatrix} \\
&= \begin{pmatrix}
P(X_{n+1} = 0 | X_n = 0) & P(X_{n+1} = 1 | X_n = 0) \\
P(X_{n+1} = 0 | X_n = 1) & P(X_{n+1} = 1 | X_n = 1)
\end{pmatrix} \tag{2}
\end{align}
}

k期先の推移行列も同様に表せる。

 {
\begin{align}
P^k &= 
\begin{pmatrix}
p_{00} & p_{01}  \\
p_{10} & p_{11} 
\end{pmatrix}^k \\
&= \begin{pmatrix}
P(X_{n+k} = 0 | X_n = 0) & P(X_{n+k} = 1 | X_n = 0) \\
P(X_{n+k} = 0 | X_n = 1) & P(X_{n+k} = 1 | X_n = 1)
\end{pmatrix} \tag{3}
\end{align}
}

定常分布

π_n = (P(X_n = 0),P(X_n = 1))^\topとする。このときπ_n P


 {
\begin{align}
π_n P &=  (P(X_n = 0),P(X_n = 1))^\top 
\begin{pmatrix}
P(X_{n+1} = 0 | X_n = 0) & P(X_{n+1} = 1 | X_n = 0) \\
P(X_{n+1} = 0 | X_n = 1) & P(X_{n+1} = 1 | X_n = 1)
\end{pmatrix} \\ \\
&=
(P(X_n = 0)P(X_{n+1} = 0 | X_n = 0)  + P(X_n = 1)P(X_{n+1} = 0 | X_n = 1) \\
 & \quad P(X_n = 0)P(X_{n+1} = 1 | X_n = 0) + P(X_n = 1)P(X_{n+1} = 1 | X_n = 1) )
\\ \\
&=
(P(X_{n+1} =0, X_n = 0) + P(X_{n+1}=0, X_n = 1) \\
& \quad P(X_{n+1}=1,X_n = 0) + P(X_{n+1}=1,X_n=1) )\\
&= (P(X_{n+1} =0), P(X_{n+1}=1) \\
&= π_{n+1} \tag{4}
\end{align}
}

n期での分布π_nに右から推移確率行列Pを掛けるとn+1期の分布π_{n+1}となる。各期で不変な分布πマルコフ連鎖の定常分布といい、

 {
\begin{align}
πP = π \tag{5}
\end{align}
}

が成立する。

確率推移のイメージ

例えば推移確率行率を
 {
\begin{align}
P &= 
\begin{pmatrix}
0.6 & 0.4  \\
0.4 & 0.6 
\end{pmatrix}  \tag{6}
\end{align}
}
とすると、

π = (0.5, 0.5 ) \tag{7}

が成立する。図1において青が0、赤が1を表す。これは最初の時点で0と1が0.5の割合で存在したところ、確率推移行列を掛けることによって、最初の0のうち0.6の割合が0のまま、0.4の割合が1に推移する。同じく最初の1のうち0.4は0に推移し、残りの0.6は1のままである。0と1は期が変わるにつれ値を変えるものの、全体に占める0と1の割合は変わらない。これが定常分布の考え方。

f:id:good_na_life:20210619115111p:plain
図1

極限分布

0期でiだったマルコフ連鎖がずっと先の期でjになる確率\lim_{n \rightarrow \infty} P(X_n = j|X_0 = i)を極限分布という。多くの場合は0期のiに関係なく決まる。

 {
\begin{align}
\lim_{n \rightarrow \infty} P(X_n  = j | X_o = i) = π_j  \tag{8}
\end{align}
}

推移確率行列は次のものとする。

 {
\begin{align}
P &= 
\begin{pmatrix}
0.8 & 0.2  \\
0.4 & 0.6 
\end{pmatrix}  \tag{9}
\end{align}
}

最初(0期)時点の0の1期ごとの変化の推移を表す。0期には0と1の個数の割合は1:0なので、X_0=0からのスタートである。1期には0と1の割合は推移確率行列より、0.8:0.2に変わる。これを繰り返すと0.67:0.33に落ち着く。

f:id:good_na_life:20210619121101p:plain
表1
f:id:good_na_life:20210619121121p:plain
図2

同様に、最初(0期)時点の1の1期ごとの変化の推移を表す。こちらはX_0=1からのスタート。1期目の推移で青(1)と赤(0)の割合は0.4:0.6に変わり、こちらも0.67:0.33の割合に変わる。

f:id:good_na_life:20210619121158p:plain
表2
f:id:good_na_life:20210619121222p:plain
図3

図2,3より、最初のスタートが0か1かにかかわらず分布はnが大きいと、だいたい

 {
\begin{align}
P(X_n = 0|X_0 = 0) = \frac{2}{3}, \quad P(X_n = 1| X_0 = 0) = \frac{1}{3} \\
P(X_n = 0|X_0 = 1) = \frac{2}{3}, \quad P(X_n = 1| X_0 = 0) = \frac{1}{3} \tag{10}
\end{align}
}

となり、これはPの定常分布となる。図2,3の5,6期目以降の部分はどちらも定常分布のイメージを表している。

MCMC

MCMCマルコフ連鎖モンテカルロ)は乱数発生法の1つ。マルコフ連鎖を応用することで正規分布等ではない複雑な分布に従う確率変数を作ることができる。

メトロポリス

密度関数がp(x)である分布(目標分布)に従う乱数を発生させたい。例えば正規分布のような釣鐘型の分布をイメージすると、密度関数p(x)の高いところに乱数がたくさん発生し、低いところにはあまり発生しない。メトロポリス法はp(x)の値が大きい乱数xをたくさん作り、p(x)の値が小さいxは少しだけ作る乱数発生方法。

乱数x_tを作成したと仮定する。次の乱数x_{t+1}を次のように決める。まず正規分布等の適当な分布から乱数εを発生させる。y=x_t + εとおく。目標分布の密度関数からp(x_t)p(y)を計算する。次の乱数x_{t+1}

  • p(x_t)\leq p(y)の場合、x_{t+1}=y
  • p(x_t) > p(y)の場合、\frac{p(y_t)}{p(x_t)}x_{t+1}=y、確率1-\frac{p(y)}{p(x_t)}x_{t+1} = x_t
f:id:good_na_life:20210619161006p:plain
図4

新たに作ったyxより密度関数のグラフの高いところならそれを新しい乱数x{t+1}として採用し、もし低いところなら確率\frac{p(y)}{p(x_t)}でしか新しい乱数として採用しないというルール。またp(y)が今よりも低くなればなるほどyを新しい乱数として採択する確率は低くなる。上述のルールをまとめると、

 {
\begin{align}
\left\{\begin{array}{l}
&x_{t+1} = y \quad if \quad w・p \quad \min  \left(1, \frac{p(y)}{p(x_t)} \right) \\
&x_{t+1} = x_t \quad if \quad w・p \quad 1- \min \left( 1, \frac{p(y)}{p(x_t)} \right)
\end{array}
\right.  \tag{11}
\end{align}
}