markov_chain

マルコフ連鎖

マルコフ性を持つマルコフ過程で、状態が離散、時間間隔も離散で等間隔の確率過程をマルコフ連鎖という。

マルコフ性とマルコフ過程

時間をtで表し、時間の経過とともに変化する状態X[t]を考える。時間の間隔は等間隔とし、整数で表す。

X[0], X[1], …, X[t-1],X[t],X[t+1],…は時間の添え字を持つ確率変数の列である。この確率変数の列は(離散時間)確率過程と呼ばれる。任意の時点tより昔の確率変数の実現値の列x[0], x[1], …, x[t-1]を時点tより前の履歴(history)といい、H[t-]と記す。

任意の時点tの状態X[t]の、それ以前のすべての時点の履歴を与えた条件付き確率分布Pr[X[t]=i|H[t-]] = Pr[X[t]=i|X[t-1]=x[t-1],X[t-2]=x[t-2],X[t-3]=x[t-3],…]が、直前の１時点のみを与えて定まる、すなわちPr[X[t]=i|H[t-]] = Pr[X[t]=i|X[t-1]=x[t-1]]を満たす時、その確率過程はマルコフ性を持つという。

マルコフ性を持つ確率過程をマルコフ過程という。

以上ではX[t]が離散確率変数の場合を紹介したが、連続確率変数でも条件付き確率密度関数を用いて、同様の議論が展開できる。それを連続状態離散時間マルコフ過程という。

現在の時点をt、少し先の未来の時点をt+1と置くと、 Pr[X[t+1]=i|H[t]] = Pr[X[t+1]=i|X[t]=x[t]] となり、未来を予測するのに、過去のすべてのデータを参照する必要はなく、現在の状態x[t]が必要なすべての情報である、ということにマルコフ性は等しい。

なお、互いに独立な確率変数の列もマルコフ性は満たす。

マルコフ過程に関する簡単なことはこの資料(東京大学の都市生活学・ネットワーク行動学研究室の勉強会資料)によくまとまっているので、５分から１０分ほどかけて、一読しておくといい。

状態の分類

P[i,i]=1という遷移確率を持つ状態iを吸収状態という。

チャップマン・コルモゴロフ方程式

停止時刻

再帰的

収束定理

定常分布

マルコフ連鎖の例

本に目を通す、というマルコフ連鎖を考える。まずは本を手にとって、カバーを見る。カバーを見た時点の次には、確率20%(0.2)でカバーを見続けるか、確率70%(0.7)で目次に目を移すか、あるいは確率10%(0.1)で興味を失って閉じる。

目次を開いた時点の次には、確率40%(0.4)で目次を見続けて内容を把握するか、確率50%(0.5)で第一章に進むか、あるいは確率10%(0.1)で興味を失って閉じる。

このような目の通し方を確率表で表すと、次のようになる。

	カバー	目次	第1章	第2章	第3章	第4章	第5章	第6章	索引	閉じる
カバー	0.2	0.7								0.1
目次		0.4	0.5							0.1
第1章			0.5	0.3					0.1	0.1
第2章				0.5	0.3				0.1	0.1
第3章					0.5	0.3			0.1	0.1
第4章						0.5	0.3		0.1	0.1
第5章							0.5	0.3	0.1	0.1
第6章								0.5	0.1	0.3
索引	0	0.2	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1
閉じる										1

確率0は空欄とした。

この行列は水平方向(行)の和が100%(確率1)になる。各行は、ある時点でその行に居たときの、次の時点の状態の条件付き確率分布である。これを行列で表したものを状態推移確率行列といい、またマルコフ行列と呼ばれることもある。

Rの行列として定義すると、次のようになる。

P = matrix(c(
0.2,0.7,0,0,0,0,0,0,0,0.1,
0,0.4,0.5,0,0,0,0,0,0,0.1,
0,0,0.5,0.3,0,0,0,0,0.1,0.1,
0,0,0,0.5,0.3,0,0,0,0.1,0.1,
0,0,0,0,0.5,0.3,0,0,0.1,0.1,
0,0,0,0,0,0.5,0.3,0,0.1,0.1,
0,0,0,0,0,0,0.5,0.3,0.1,0.1,
0,0,0,0,0,0,0,0.5,0.1,0.4,
0,0.2,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,
0,0,0,0,0,0,0,0,0,1),ncol=10,byrow=TRUE)

> P
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]  0.2  0.7  0.0  0.0  0.0  0.0  0.0  0.0  0.0   0.1
 [2,]  0.0  0.4  0.5  0.0  0.0  0.0  0.0  0.0  0.0   0.1
 [3,]  0.0  0.0  0.5  0.3  0.0  0.0  0.0  0.0  0.1   0.1
 [4,]  0.0  0.0  0.0  0.5  0.3  0.0  0.0  0.0  0.1   0.1
 [5,]  0.0  0.0  0.0  0.0  0.5  0.3  0.0  0.0  0.1   0.1
 [6,]  0.0  0.0  0.0  0.0  0.0  0.5  0.3  0.0  0.1   0.1
 [7,]  0.0  0.0  0.0  0.0  0.0  0.0  0.5  0.3  0.1   0.1
 [8,]  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.5  0.1   0.4
 [9,]  0.0  0.2  0.1  0.1  0.1  0.1  0.1  0.1  0.1   0.1
[10,]  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0   1.0

たとえばある時点で表紙にいるとは、次のベクトルで表す。

x = matrix(c(1,0,0,0,0,0,0,0,0,0),nrow=1,ncol=10)

実行してみると、表紙に1、他の状態は0という行ベクトルが表示去れる。

> x
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    1    0    0    0    0    0    0    0    0     0

この次の時点にいる状態の確率分布は

x %*% P

で得られる。ここで%*%は、ベクトルとベクトル、ベクトルと行列、あるいは行列と行列の掛け算である。

> x %*% P
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]  0.2  0.7    0    0    0    0    0    0    0   0.1

これは別名、確率ベクトルと呼ばれる。総和が1は、条件付き確率分布の全確率が1であることに符号する。

２時点先にいる状態の確率分布は

x %*% P %*% P

で与えられる。

> x %*% P %*% P
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 0.04 0.42 0.35    0    0    0    0    0    0  0.19

マルコフ連鎖では、Pをかけた回数分だけ未来の確率分布が、簡単に得られる。この計算をチェインルールと呼ぶこともある。本を手に取ってから10時点先は

round(x %*% P %*% P %*% P %*% P %*% P %*% P %*% P %*% P %*% P %*% P,3)
     [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
[1,]    0 0.015 0.034 0.051 0.063 0.059 0.042 0.028 0.036 0.673

となる。時点の間隔が１時間ならば、10時間後には読み終えているか、飽きるかして、67.3%の確率で本を閉じている。

markovchain

markovchainパッケージは、離散状態離散時間マルコフ過程(通称は離散マルコフ過程、あるいはマルコフ連鎖)をRで扱うのに便利な機能を提供する。

install.packages(c(“dplyr”,“stringr”,“DiagrammeR”,“networkD3”))

MDPtoolbox

MDPtoolboxパッケージは、マルコフ過程を少し拡張した、マルコフ決定過程をRで扱うのに便利な機能を提供する。

msm

パネルデータのための多状態モデル。

mcmcR

モンテカルロマルコフ連鎖。

hmm

共変量を持つ隠れマルコフモデル。

mstate

生存解析のためのマルコフ連鎖の上の多状態モデルの推定。