2015/03/24

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


確率過程の基本的な話題の一つ,マルコフ連鎖について解説します!

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

未来の状態(の確率)が過去の状態によらず現在の状態のみで決まるような確率過程のことをマルコフ過程と言います(以下の具体例を見るとイメージがつかめると思います)。

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

マルコフ連鎖の具体例

マルコフ連鎖の具体例として,以下のようなモデルを考えます(確率はかなり適当ですがマルコフ連鎖の理解には役立ちます)。

  • 昨日以前の天気は翌日の天気に影響しない。
  • 今日晴れ→翌日晴れる確率は $0.7$,曇の確率は $0.3$,雨の確率は $0$
  • 今日曇→翌日晴れる確率は $0.4$,曇の確率は $0.4$,雨の確率は $0.2$
  • 今日雨→翌日晴れる確率は $0.3$,曇の確率は $0.3$,雨の確率は $0.4$
状態遷移図

このモデルは図のように表現することができます。このような図を状態遷移図と言います。
状態空間は $S=\{$晴れ,曇,雨 $\}$ です。晴れ,曇,雨の各状態をそれぞれ $1,2,3$ で表すと便利です。このとき $S=\{1,2,3\}$ と書けます。

また,$t$ 日目の天気を表す確率変数を $X_t$ とおきます。例えば,$t$ 日目に晴れたもとで $t+1$ 日目も晴れる確率は $0.7$ なので,$P(X_{t+1}=1\mid X_t=1)=0.7$
と書くことができます。

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

推移確率行列

状態遷移の確率を各要素に持つ行列を考えると何かと便利です!

$ij$ 成分に $i$ から $j$ に遷移する確率を入れたものを推移確率行列(または遷移確率行列,遷移行列)と言います。例えば,上のマルコフ連鎖の例では推移確率行列 $P$ は以下のようになります:
$P=\begin{pmatrix} 0.7 &0.3& 0\\0.4 & 0.4 & 0.2\\ 0.3 & 0.3 & 0.4\end{pmatrix}$

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

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

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

最後に「推移確率行列の $n$ 乗」と「 $n$ 回の遷移の確率」が対応することを説明します。

$n$ 時刻経過に対する推移確率行列を $P^{(n)}$ と書くことにします。つまり,$P(X_{t+n}=j\mid X_t=i)$ を $ij$ 成分に持つ行列を $P^{(n)}$ とします。

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

証明

  • $n=1$:定義より $P^{(1)}=P$
  • $n=2$:時刻 $t+1$ での状態で場合分けして $t\to t+2$ への遷移確率を計算する。 $P$ の $ij$ 成分を $p_{ij}$ と書く。

$P^{(2)}$ の $ij$ 成分
$=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}$
$=P^2$ の $ij$ 成分
・ $n=3$ 以降も同様に証明できる。


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

先ほどの天気の例:
推移確率行列の二乗 $P^2$ を計算してみると,$P^2=\begin{pmatrix} 0.61 &0.33& 0.06\\0.5 & 0.34 & 0.16\\ 0.45 & 0.33 & 0.22\end{pmatrix}$
よって,今日の天気をもとに二日後の天気がどうなるかの確率が求まった。 $n$ 日後の天気の確率を求めたいときは $P^n$ を計算すればよい。

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

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