マルコフ連鎖 - Goodな生活

推移確率行列
定常分布
- 確率推移のイメージ
極限分布
MCMC
- メトロポリス法

推移確率行列

確率変数 $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

新たに作った $y$ が $x$ より密度関数のグラフの高いところならそれを新しい乱数 $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} }$