Markov Process (マルコフ連鎖)

状態の時系列 \(h=(h_0,h_1,\ldots)\)が条件付き確率　\(p(h_t|h_{t-k},\ldots, h_{t-1}) \) によって与えられている時，
この確率過程を定常\(k\)次マルコフ連鎖と呼ぶ．

定義：定常１次マルコフ連鎖

以下の\(\{S,s_0,A\}\)の組を定常1次マルコフ連鎖と呼ぶ.
・状態集合：\(S = \{s_i\}; i=0,\ldots,N\)
・初期状態：\(s_0 \in S\)
・遷移確率行列：\(A = \{a_{i,j}\}\); \(i,j=1,\ldots,N\); \(a_{i,j}\) は状態\(s_i\)から状態\(s_j\)への遷移確率

Markov Model (マルコフモデル)

Markov ModelはMarkov Processの状態を直接観察できて、状態列そのものを出力列（信号列）とみなす.

定義：定常1次マルコフモデル

定常1次マルコフ連鎖\(\{S,s_0,A\}\)で，状態列そのものを出力列とみなした確率的情報源を定常1次マルコフモデルと呼ぶ．
・出力列＝状態列：\(x=x_1, \ldots , x_T\); \(x_t=h_t \in S\), for \(t=1,\ldots,T\)

出力列=状態列の確率は以下の式で表される（ただし\(x_0=h_0=s_0\)）.
\[ \begin{align}
p(x|A)=\prod_{t=1}^T p(x_t|x_{t-1}) =\prod_{t=1}^T a_{x_t,x_{t-1}}
\tag{hmm.1}\label{eq:mm_prob}
\end{align} \]

初期状態を \(s_0\) に固定する代わりに、状態の初期分布 \(p(h_1=s_i)\)を与える定式化も可能である．
一方，初期状態を \(s_0\) に固定するということは，初期分布を \(p(h_1=s_i)=a_{0,i}\) で与えることに相当する．

配列解析では，隣接した塩基、アミノ酸の相関を考慮するために，k次マルコフモデル（\(k>1)\))は有用である．しかしながら，本項の目的である隠れマルコフモデル（HMM）の導入に関しては，定常1次マルコフ連鎖、定常1次マルコフ過程だけが必要なので，以下，単にマルコフ連鎖・マルコフ過程と呼ぶ．

開始状態と終了状態

開始状態と終了状態を考慮するかどうかによって、合計が１となる確率を与える状態列空間が変わってくる。
初期分布と遷移確率だけが与えられている時、任意の長さ\(n\) の状態列について、同じ長さの状態列の確率の合計が１となる。
開始状態と終了状態を明示的に与え、この２つの特殊な状態も含めた遷移確率（開始状態は出ていく確率のみ、終了状態は入ってくる確率のみ）を与えると、起こりうる全ての長さの状態列の確率の合計が１となる。