記憶のある情報源
m重マルコフ情報源
過去の \(m\) 個の記号に依存して、記号を生起する情報源を \(m\) 重マルコフ情報源という。
特に、\(m=1\) のとき（直前の1個にのみ依存する場合）単純マルコフ情報源という。
定義（遷移確率・遷移確率行列）
状態 \(s_i\) から状態 \(s_j\) に遷移する確率を 状態 \(s_i,s_j\) 間の遷移確率といい
\[
p_{ij}:=P(s_j~|~s_i)
\]
と表す。
遷移確率 \(p_{ij}\) を要素とする行列
\[
P=
\begin{bmatrix}
p_{11} & p_{12} & \cdots & p_{1n}\\
p_{21} & p_{22} & \cdots & p_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
p_{n1} & p_{n2} & \cdots & p_{nn}\\
\end{bmatrix}
\]
を遷移確率行列という。
エルゴード的マルコフ情報源
次のいずれかが満たされる場合は情報源のモデルとして適さない。
・吸収的である：ある特定の状態になるとそこから抜けることができない
・周期性を持つ：同じパターンの遷移を繰り返す
吸収的でなく、周期性を持たない性質をエルゴード性という。
エルゴード性を持ったマルコフ情報源をエルゴード的マルコフ情報源（エルゴード情報源）という。
定義（定常確率）
エルゴード情報源において、ある状態が発生する確率を定常確率という。
\(n\) 個の状態を持つエルゴード情報源において、状態 \(s_j\) の定常確率を \(P(s_j)\) とすると
\[
\sum_{j=1}^nP(s_j)=1
\]
が成り立つ。
また、状態 \(s_i\) から状態 \(s_j\) に遷移するとき、遷移確率を \(p_{ij}\) として
\[
\sum_{i=1}^np_{ij}P(s_i)=P(s_j)
\]
が成り立つ。
マルコフ情報源のエントロピー
マルコフ情報源のエントロピーは、時間が進むにつれて生成される1記号あたりのエントロピーとして定義される。
情報源アルファベット \(A\) が
\[
A=\{a_1,~a_2,~\cdots,~a_M\}
\]
であるとき、状態 \(s_j\) の下でのエントロピーは
\[
H(A|s_j)=-\sum_{i=1}^MP(a_i|s_j)\log_2{P(a_i|s_j)}~~~[\mathrm{bit}]
\]
\(m\) 重マルコフ情報源における状態の種類の数は \(M^m\) 個である。
したがって、1記号あたりのエントロピー（エントロピー率）は
\[
H(A)=\sum_{j=1}^{M^m}P(s_j)H(A|s_j)~~~[\mathrm{bit}/\text{記号}]
\]
演習問題
問題