3.3 マルコフ情報源のエントロピーレート

定理 3.2.6 はエントロピーレートの存在を保証したが，値については何も教えない．極限としてしか書けない量は，具体的な情報源に当てはめようとした途端に困る．ところが記憶の深さが有限なら，増分 $𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)$ は途中から動かなくなり，極限が有限回の計算で書ける．その最も単純な場合が，記憶が 1 文字分しかないマルコフ情報源である．

定理 3.3.1. 定義 3.1.3 のマルコフ情報源で，初期分布 $𝜇$ が遷移確率 $𝑃$ の定常分布であるとする．このときエントロピーレートは

𝐻 (X) = 𝐻 (𝑋 1 ∣ 𝑋 0) = - \sum 𝑎 \in X 𝜇 (𝑎) \sum 𝑏 \in X 𝑃 (𝑎, 𝑏) l o g 𝑃 (𝑎, 𝑏)

である．

証明. $𝑛 \geq 1$ を固定し，増分 $𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)$ を計算する．定義 3.1.3 の分解より， $P r [𝑋 𝑛 = 𝑥 𝑛] > 0$ なる任意の $𝑥 𝑛 = (𝑥 0, \dots, 𝑥 𝑛 - 1)$ に対し

P r [𝑋 𝑛 = 𝑏 ∣ 𝑋 𝑛 = 𝑥 𝑛] = 𝜇 (𝑥 0) \prod 𝑛 - 1 𝑖 = 1 𝑃 (𝑥 𝑖 - 1, 𝑥 𝑖) \cdot 𝑃 (𝑥 𝑛 - 1, 𝑏) 𝜇 (𝑥 0) \prod 𝑛 - 1 𝑖 = 1 𝑃 (𝑥 𝑖 - 1, 𝑥 𝑖) = 𝑃 (𝑥 𝑛 - 1, 𝑏)

である．すなわち $𝑋 𝑛$ の条件付き分布は $𝑥 𝑛 - 1$ だけで決まる．したがって

𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) = \sum 𝑥 𝑛 P r [𝑋 𝑛 = 𝑥 𝑛] (- \sum 𝑏 𝑃 (𝑥 𝑛 - 1, 𝑏) l o g 𝑃 (𝑥 𝑛 - 1, 𝑏))

であり，右辺の括弧の中は $𝑥 𝑛 - 1$ だけの関数だから， $𝑥 0, \dots, 𝑥 𝑛 - 2$ について和をとってしまえる． $𝑋 𝑛 - 1$ の分布は命題 3.1.4 の証明より $𝜇$ だから

𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) = - \sum 𝑎 𝜇 (𝑎) \sum 𝑏 𝑃 (𝑎, 𝑏) l o g 𝑃 (𝑎, 𝑏),

これは $𝑛$ に依らない． $𝑛 = 1$ の場合がちょうど $𝐻 (𝑋 1 ∣ 𝑋 0)$ である．

増分が $𝑛 \geq 1$ で定数なのだから，その極限も同じ値である．定理 3.2.6 より $𝐻 (X)$ はこの極限に等しい． $◼$

証明の要点は一つだけである．条件付き分布が直前の 1 文字だけで決まるので，条件を長くしても増分が増えも減りもしない．補題 3.2.4 の非増加列は，マルコフ情報源では最初の1 歩で底に着いて，あとは平らになる． $𝐻 (𝑋 0)$ から $𝐻 (𝑋 1 ∣ 𝑋 0)$ への 1 歩ぶんだけが記憶の効き目で，それ以上は何も残っていない．

例 3.3.2（二状態マルコフ情報源のレート）. 例 3.1.5 の情報源のレートを求める．定常分布は $𝜇 (0) = 𝛽 / (𝛼 + 𝛽)$ ， $𝜇 (1) = 𝛼 / (𝛼 + 𝛽)$ だった．状態 $0$ から出る分布は $(1 - 𝛼, 𝛼)$ ，状態 $1$ から出る分布は $(𝛽, 1 - 𝛽)$ だから，定理 3.3.1 より

𝐻 (X) = 𝛽 𝛼 + 𝛽 𝐻 𝑏 (𝛼) + 𝛼 𝛼 + 𝛽 𝐻 𝑏 (𝛽)

である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．

典型例. $𝛼 = 0.1$ ， $𝛽 = 0.4$ とすると $𝜇 = (0.8, 0.2)$ で，

𝐻 (X) = 0.8 𝐻 𝑏 (0.1) + 0.2 𝐻 𝑏 (0.4) \approx 0.8 \times 0.469 + 0.2 \times 0.971 \approx 0.569

ビットである．いっぽう 1 文字だけを見たときの不確かさは $𝐻 (𝑋 0) = 𝐻 𝑏 (0.2) \approx 0.722$ ビットで，記憶を使うと $0.15$ ビットあまり下がる．

両端で確かめる. $𝛼 + 𝛽 = 1$ のとき，次の文字が $1$ になる確率は現在の状態によらず $𝛼$ である．つまり記憶がない．実際 $𝜇 (1) = 𝛼$ となり， $𝛽 = 1 - 𝛼$ だから例 1.1.2 の対称性より $𝐻 𝑏 (𝛽) = 𝐻 𝑏 (𝛼)$ である．よってレートは $𝛽 𝐻 𝑏 (𝛼) + 𝛼 𝐻 𝑏 (𝛼) = 𝐻 𝑏 (𝛼) = 𝐻 (𝑋 0)$ で，i.i.d. の場合（例 3.2.2）に戻る．逆に $𝛼 = 𝛽 \to 0$ とすると，状態はめったに変わらない． $𝜇 = (1 / 2, 1 / 2)$ なので $𝐻 (𝑋 0) = 1$ ビットのままだが，レートは $𝐻 𝑏 (𝛼) \to 0$ である．長い系列はほとんど同じ文字の繰り返しで，最初の 1 文字を除けば情報がない．

規模感. 1.1 節で，英字 26 文字が一様なら 1 文字あたり $l o g 26 \approx 4.70$ ビットだが，実際の英文はもっと小さいはずだと書いた．空白を入れた 27 文字を一様とすれば $l o g 27 \approx 4.76$ ビット，文字ごとの出現頻度だけを使うと約 $4.0$ ビット，直前の1 文字を使うマルコフ情報源として測ると約 $3.3$ ビットまで下がる．ここまでは定理 3.3.1がそのまま計算できる範囲である．さらに記憶を深くしていくと，Shannon の推定では1 文字あたり $1.3$ ビット程度に落ち着く． $4.76$ から $1.3$ への差（4 分の 3 近く）が，英語という情報源の「偏りと依存」のぶんである．ただし英文が定常情報源であるという保証はどこにもなく，これは英文をそう仮定して測った値である．

形式化上の注記. 本節の主張に対応する単独の宣言は形式化されていない．ライブラリは定常情報源を3.1 節の測度保存力学系として一般に扱っており，遷移確率を明示したマルコフ情報源のクラスを別に定義していないためである．定理 3.3.1 は形式化済みの定理 3.2.6 と，証明の前半（条件付き分布が直前の 1 文字だけで決まるという書き換え）の合成として得られるが，その合成を 1 本にした宣言はない．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．