マルコフ連鎖の基本とコルモゴロフ方程式

マルコフ連鎖とは,大雑把に言うと時刻 t+1t+1 の状態が,時刻 tt の状態のみに依存する(時刻 t1t-1 以前の状態には依存しない)ようなモデルのことです。

この記事では,確率過程の基本的な話題の1つである,マルコフ連鎖について紹介します。

マルコフ連鎖とは

マルコフ連鎖の定義

マルコフ連鎖とは,

P(Xt+1Xt,Xt1,,X1)=P(Xt+1Xt)P(X_{t+1}\mid X_t,X_{t-1},\dots,X_1)=P(X_{t+1}\mid X_t)

を満たすような確率変数の列 X1,X2,X_1,X_2,\dots のこと。

上の式は,Xt+1X_{t+1}XtX_t のみに依存する(Xt1X_{t-1} 以前には依存しない)ことを表しています。

例えば,tt 日目の天気を XtX_t とし,以下の2つが成立するとしましょう。

  • XtX_t によって Xt+1X_{t+1} の傾向が決まる
    (例. 今日晴れたら明日も晴れやすい)

  • Xt1X_{t-1} 以前は Xt+1X_{t+1} に影響しない
    (2日前の天気は関係ない)

このとき,{Xt}\{X_t\} はマルコフ連鎖になります。

マルコフ連鎖の用語

マルコフ連鎖に関する基本的な用語を整理しました。

XtX_t がとりうる値の集合のことを状態空間と言うことがあります。例えば,天気の例だと状態空間は S={S=\{ 晴れ,曇,雨 }\} と考えることができます。晴れ,曇,雨の各状態をそれぞれ 1,2,31,2,3 で表すと便利です。このとき S={1,2,3}S=\{1,2,3\} と書けます。

また,P(Xt+1Xt)P(X_{t+1}\mid X_t) のことを 遷移確率(推移確率)と言うことがあります。例えば「今日曇りだと確率 0.40.4 で明日晴れになる」場合,遷移確率は P(Xt+1=晴れXt=)=0.4P(X_{t+1}=晴れ\mid X_t=曇)=0.4 となります。

マルコフ連鎖の状態遷移図

また,状態空間を頂点で表し,遷移確率を枝で表した図のようなグラフを状態遷移図と言うことがあります。確率はかなり適当ですがマルコフ連鎖の理解には役立ちます。

注:この記事では時間的に均一(遷移確率が時刻によらない)なマルコフ連鎖を考えています。

マルコフ連鎖の推移確率行列

マルコフ連鎖において,遷移確率を並べた行列を考えてみましょう。

すなわち,ijij 成分に「 ii から jj に遷移する確率」を入れたものを推移確率行列(または遷移確率行列,遷移行列)と言います。例えば,上のマルコフ連鎖の例では推移確率行列 PP は以下のようになります:

P=(0.70.300.40.40.20.30.30.4)P=\begin{pmatrix} 0.7 &0.3& 0\\0.4 & 0.4 & 0.2\\ 0.3 & 0.3 & 0.4\end{pmatrix}

確率が満たすべき性質より,以下が分かります:

  • 推移確率行列の各要素は 00 以上 11 以下である。
  • 推移確率行列のどの行も,行和は 11 である。

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

マルコフ連鎖の推移確率行列について「推移確率行列の nn 乗」と「nn 回の遷移の確率」が対応するという性質が成り立ちます。

さきほどの天気の例

推移確率行列の二乗 P2P^2 を計算してみると,P2=(0.610.330.060.50.340.160.450.330.22)P^2=\begin{pmatrix} 0.61 &0.33& 0.06\\0.5 & 0.34 & 0.16\\ 0.45 & 0.33 & 0.22\end{pmatrix}

これは「今日の天気が分かったときに,二日後の天気がどうなるか」の確率を表します。例えば,今日晴れたら二日後晴れる確率は 0.610.61 です。

同様に,nn 日後の天気の確率を求めたいときは PnP^n を計算すればよいです。

もう少しきちんと書いてみます。nn 時刻経過に対する推移確率行列を P(n)P^{(n)} と書くことにします。つまり,P(Xt+n=jXt=i)P(X_{t+n}=j\mid X_t=i)ijij 成分に持つ行列を P(n)P^{(n)} とします。

すると,P(n)=PnP^{(n)}=P^n が成立します(右辺は推移確率行列の nn 乗)。

証明

n=1n=1 について,定義より P(1)=PP^{(1)}=P

n=2n=2 について考える。時刻 t+1t+1 での状態で場合分けして tt+2t\to t+2 への遷移確率を計算する。 PPijij 成分を pijp_{ij} と書く。

P(2)P^{(2)}ijij 成分

=P(Xt+2=jXt=i)=sSP(Xt+2=jXt+1=s)P(Xt+1=sXt=i)=sSpsjpis=P(X_{t+2}=j\mid X_t=i)\\ =\displaystyle\sum_{s\in S}P(X_{t+2}=j\mid X_{t+1}=s)P(X_{t+1}=s\mid X_t=i)\\ =\displaystyle\sum_{s\in S}p_{sj}p_{is}

=P2=P^2ijij 成分

n=3n=3 以降も同様に証明できる。

上記の定理より,P(n+m)=P(n)P(m)P^{(n+m)}=P^{(n)}P^{(m)} が成立します(nn 時刻ぶんの遷移の様子 P(n)P^{(n)}mm 時刻ぶんの遷移の様子 P(m)P^{(m)} が分かれば n+mn+m 時刻ぶんの遷移の様子 P(n+m)P^{(n+m)} も分かる)。この等式をチャップマン–コルモゴロフ方程式と言います。

マルコフ連鎖とマルコフ過程

この記事ではマルコフ連鎖について紹介しましたが,一般に,未来の状態(の確率)が過去の状態によらず現在の状態のみで決まるような確率過程のことをマルコフ過程と言います。

特に,確率変数がとりうる値の集合(状態空間)が離散的なマルコフ過程のことをマルコフ連鎖と言います。

マルコフ連鎖で記述できる入試問題もけっこうあります(特に行列が範囲内だった時代)。

Tag:数学的モデリングまとめ