離散マルコフ連鎖
定義
状態空間が可算集合で、次を満たす離散的確率過程 $\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$ となる。確率過程論をどこで学ぶかによって、この性質を定義として受け入れることもある。