離散マルコフ連鎖
定義
状態空間が可算集合であり、次を満たす離散的確率過程$\left\{ X_{n} \right\}$を離散マルコフ連鎖dTMCあるいは簡単にマルコフ連鎖markov Chain, MCという。 $$ p \left( X_{n+1} = j \mid X_{n} = i , X_{n-1} = k , \cdots , X_{0} = l \right) = p \left( X_{n+1} = j \mid X_{n} = i \right) $$
関連リンク
説明
$p_{ij}:= p \left( X_{n+1} = j \mid X_{n} = i \right)$を遷移確率transition Probabilityといい、現在の状態を意味する$i$をソースステートsource State、目標の状態を意味する$j$をターゲットステートtarget Stateという。$k$ステップ後の遷移確率は$p_{ij}^{(k)}: = p \left( X_{n+k} = j \mid X_{n} = i \right)$のように表す。
マルコフ連鎖とは、これまでの歴史をすべて知っているときの次のステップの確率と、現在だけを知っているときの次のステップの確率が同じである確率過程のことをいう。簡単に言えば、現在の状態さえ正確に知っていれば、過去が未来に影響を及ぼさない確率過程である。よくこのような性質を無記憶性memorylessnessと呼ぶ。当然、このような仮定があれば計算でも何でも非常に楽になる。
例えば、降水確率に対するモデルをマルコフ連鎖で表すと考えてみよう。昨日雨が降ったかどうかにかかわらず、明日の降水確率は今日雨が降ったかどうかだけに影響を受けると仮定してみよう。雨が降った状態を$0$、雨が降らなかった状態を$1$とし、 $$\begin{matrix} p_{00} = 0.7 & p_{01} = 0.3 \\ p_{10} = 0.4 & p_{11} = 0.6 \end{matrix}$$ としよう。これは、今日雨が降ったならば明日も雨が降る確率が$70 %$で雨が降らない確率が$30 %$、今日雨が降らなかったならば明日も雨が降らない確率が$60 %$で雨が降る確率が$40 %$という意味である。
さて、 $$P:= \begin{bmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \end{bmatrix} = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} $$ のような行列を通じて、このような確率計算を簡単にしてみよう。このような行列を遷移確率行列と呼び、$k$ステップ後の遷移確率行列を$P^{(k)}:= \left( p_{ij}^{ ( k ) } \right)$のように表す。遷移確率行列の有用な性質として、$P^{(n)} = P^{n}$であることをチャップマン・コルモゴロフ方程式を通じて証明できる。
もし今日雨が降ったならば、二日後の降水確率は $$ \begin{align*} P^{ (2) } =& P^{2} \\ =& \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \\ =& \begin{bmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{bmatrix} \end{align*} $$ であり、$p_{00}^{(2)} = (0.7)^2 + (0.3) (0.4) = 0.61$と正確に一致する。普通、我々が関心を持つ問題はこれより複雑で比較的遠い未来に関心があるので、このような行列を扱うことが必須であることがわかる。
遷移確率行列の数式的定義
参考までに、遷移確率行列で同じ行の成分をすべて足すと必ず$1$になるが、当然ながら次のステップの確率をすべて足すと$1$だからである。数式で表すと$\displaystyle \sum_{j} p_{ij} = 1$のようになる。確率過程論をどこで勉強するかによっては、そもそもこの性質を定義として受け入れることもある。