将来の運命が現在の状態だけで決定され、過去と無関係である

マルコフ連鎖

遷移確率行列

状態遷移確率行列は、ある状態 Xi から別の状態 Xj に遷移する確率 p(Xi, Xj) を、i = 0, 1, 2, ... および j = 0, 1, 2, ... のすべての組み合わせを行列で表したものである。

たとえば、ある遺伝子の塩基 A が、Δt の時間で、0.6 の確率で不変で、0.2 の確率で塩基 T に置換し、0.1 の確率で塩基 C に置換し、0.1 の確率で塩基 G に置換される、と仮定する。塩基 C についても、同様に、0.8 の確率で不変で、0.1 の確率で塩基 G に置換し、0.05 の確率で塩基 A に置換し、0.05 の確率で塩基 T に置換される、と仮定する。このように、塩基 A, C, G, T が Δt の時間で他の塩基に変異する確率を表にまとめると次のようになる。

元の塩基変異後の塩基と変異確率
ACGT
A0.60.10.10.2
C0.050.80.10.05
G0.050.10.80.05
T0.20.10.10.6

この行をそのまま行列にしたものが状態遷移確率行列である。ある塩基から他の塩基のいずれかに遷移する他ので、遷移確率の合計(各行の合計)が 1 となる。

\[ \begin{eqnarray} \left( \begin{array}{cccc} 0.6 & 0.1 & 0.1 & 0.2 \\ 0.05 & 0.8 & 0.1 & 0.05 \\ 0.05 & 0.1 & 0.8 & 0.05 \\ 0.2 & 0.1 & 0.1 & 0.6 \\ \end{array} \right) \end{eqnarray} \]

マルコフ過程

現在の状態(確率変数) Xn が与えられたとき、Xn + 1 は Xn だけで決定され、過去のいかなる状態(X0, X1, ..., Xn - 1)とも無関係である。このような性質をマルコフ性という。これを数式で表すと次のようになる。

\[ P(X_{n+1} | X_n, X_{n-1}, ... X_0) = P(X_{n+1} | X_n) \]

ある状態 Xi から別の状態 Xj に確率 p(Xn, Xn + 1) で遷移するとき、確率 p(Xn, Xn + 1) がマルコフ性を持つならば、その確率過程をマルコフ過程という。ある状態 Xi から別の状態 Xj に遷移する確率 p は、状態遷移確率行列で表されることが多い。

マルコフ連鎖

マルコフ過程において、確率変数が離散的な値をとるとき、これをマルコフ連鎖という。例えば、確率変数を塩基 A, C, G, T としたとき、塩基の変異過程がマルコフ連鎖となる。マルコフ連鎖は、よく状態遷移図で視覚化される。例えば、塩基の置換過程に関するマルコフ連鎖の状態遷移図は次のように描かれる。

塩基置換モデルのマルコフ連鎖の状態遷移図