3.2 エントロピーレート

定常性を置いたので，「1 文字あたりの不確かさ」を定義する用意ができた．自然な候補は二つある．長さ $𝑛$ のブロック全体の不確かさを $𝑛$ で割った時間平均と， $𝑛$ 文字読んだあとで次の 1 文字に残る不確かさである．前者は第2章の圧縮の議論にそのまま乗る量で，後者は「次の文字がどれだけ読めないか」という予測の言葉になっている．定常情報源では，この二つがどちらも収束し，しかも同じ値になる．それが本節の定理である．

以下，上付きの $𝑋 𝑛$ は先頭 $𝑛$ 文字のブロック，下付きの $𝑋 𝑛$ は次に来る 1 文字を表す（第2章の補題 2.3.3 の証明と同じ約束である）．添字が $0$ 始まりなので， $𝑋 𝑛$ の次の文字がちょうど $𝑋 𝑛$ になる． $𝑛 = 0$ のとき $𝑋 0$ は空の組で，それで条件付けた $𝐻 (𝑋 0 ∣ 𝑋 0)$ は条件が空なので無条件の $𝐻 (𝑋 0)$ に等しい（定義 1.2.2 で条件を定数にとった場合である）．

定義

定義 3.2.1（ブロックエントロピーとエントロピーレート）. 定常情報源 ${𝑋 𝑖}$ に対し，ブロックエントロピー を

𝐻 𝑛 : = 𝐻 (𝑋 𝑛) (𝑛 \geq 1), 𝐻 0 : = 0

で定める．極限

𝐻 (X) : = l i m 𝑛 \to \infty 𝐻 𝑛 𝑛, 𝐻' (X) : = l i m 𝑛 \to \infty 𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)

が存在するとき，それぞれを情報源の エントロピーレート と呼ぶ．

$𝐻 𝑛$ はブロックが長くなるほど大きくなりうる量なので，そのままでは情報源どうしを比べられない． $𝑛$ で割ってはじめて「1 文字あたり」になる． $𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)$ のほうは割らなくてよい．最初から 1 文字分の量だからである．定義に二つの記号を置いたのは，収束先が同じであることがまだ分かっていないからで，定理 3.2.6 でこれが一致する．

形式化: ブロックエントロピー blockEntropy，増分 conditionalEntropyTail，エントロピーレートentropyRate (ソース)

例 3.2.2（i.i.d. 情報源のエントロピーレート）. i.i.d. 情報源では，補題 2.3.3 より $𝐻 𝑛 = 𝑛 𝐻 (𝑋 0)$ だから $𝐻 𝑛 / 𝑛 = 𝐻 (𝑋 0)$ で， $𝐻 (X) = 𝐻 (𝑋 0)$ である．もう一方は， $𝑋 𝑛$ が $𝑋 𝑛$ と独立なので $𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) = 𝐻 (𝑋 𝑛) = 𝐻 (𝑋 0)$ （補題 2.3.3 の証明で確かめた等式である）．どちらも $𝐻 (𝑋 0)$ になり，第2章のエントロピーがそのまま再現される．

ブロックを 1 文字ずつに分ける

補題 3.2.3. 任意の情報源 ${𝑋 𝑖}$ と任意の $𝑛 \geq 0$ に対し

𝐻 𝑛 = 𝑛 - 1 \sum 𝑖 = 0 𝐻 (𝑋 𝑖 ∣ 𝑋 𝑖) .

証明（ $𝑛$ についての数学的帰納法）. $𝑛 = 0$ のときは両辺とも $0$ である（右辺は空和）． $𝑛$ で成り立つとして $𝑛 + 1$ の場合を見る．ブロック $𝑋 𝑛 + 1$ は対 $(𝑋 𝑛, 𝑋 𝑛)$ にほかならないから，エントロピーのチェイン則（定理 1.2.3）より

𝐻 𝑛 + 1 = 𝐻 (𝑋 𝑛, 𝑋 𝑛) = 𝐻 (𝑋 𝑛) + 𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) = 𝐻 𝑛 + 𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) .

第 1 項に帰納法の仮定を当てると $\sum 𝑛 - 1 𝑖 = 0 𝐻 (𝑋 𝑖 ∣ 𝑋 𝑖)$ になり，第 2 項はちょうど $𝑖 = 𝑛$ の項である． $◻$

形式化: blockEntropy_eq_sum_conditionalEntropyTail，証明の 1 段分にあたるblockEntropy_succ_chain_rule (ソース)

この分解に定常性は使っていない．エントロピーのチェイン則だけで出るからである．定常性が効くのは次の補題である．

分解が言っているのは，ブロックを一気に読むかわりに 1 文字ずつ読んでいったときの，不確かさの増分の足し合わせだ，ということである． $𝑖$ 番目の増分は「先頭 $𝑖$ 文字を知ったうえで $𝑋 𝑖$ を当てる」不確かさで，記憶のある情報源ではこれが $𝑖$ とともに減っていく．次の補題がそれである．

増分は減っていく

補題 3.2.4. 定常情報源では，数列 $(𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)) 𝑛 \geq 0$ は非増加であり，かつ任意の $𝑛 \geq 0$ で $𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) \geq 0$ である．

証明. 非負性は，条件付きエントロピーが非負量の平均であることによる（定義 1.2.2 と命題 1.1.4）．

非増加を見る．条件付けの単調性（定理 1.2.4）を $𝑌 \leftarrow (𝑋 1, \dots, 𝑋 𝑛)$ ， $𝑍 \leftarrow 𝑋 0$ として使うと

𝐻 (𝑋 𝑛 + 1 ∣ 𝑋 0, 𝑋 1, \dots, 𝑋 𝑛) \leq 𝐻 (𝑋 𝑛 + 1 ∣ 𝑋 1, \dots, 𝑋 𝑛)

である．定常性（定義 3.1.1， $ℓ = 1$ ）より $(𝑋 1, \dots, 𝑋 𝑛 + 1)$ の同時分布は $(𝑋 0, \dots, 𝑋 𝑛)$ のそれに等しいから，右辺は $𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)$ に等しい．左辺は $𝐻 (𝑋 𝑛 + 1 ∣ 𝑋 𝑛 + 1)$ である． $◻$

形式化: conditionalEntropyTail_antitone，conditionalEntropyTail_nonneg (ソース)

証明で使ったのは二手だけである．条件を一つ減らすと不確かさは増えない（あるいは同じ），というのが一手目．減らして残ったものが，時計をずらせば元の問題そのものになる，というのが二手目である．定常性が効くのはこの二手目だけで，そこがなければ「 $𝑛$ が違う量どうしを比べる」ことができない．

読み方は素直である．過去を長く見せられるほど，次の 1 文字は当てやすくなる．ただしどこまでも下がり続けるわけではない．非負なので底がある．その底こそが，情報源の「どうしても残る 1 文字あたりの不確かさ」である．

平均も同じところへ行く

補題 3.2.4 で片方の極限は片付いた．もう一方の $𝐻 𝑛 / 𝑛$ は，補題 3.2.3 によれば同じ数列の相加平均である．数列が収束すればその相加平均も同じ値に収束する，という解析の事実を使えばよい．

補題 3.2.5（Cesàro 平均）. 実数列 $(𝑎 𝑖) 𝑖 \geq 0$ が $𝐿$ に収束するならば， $1 𝑛 \sum 𝑛 - 1 𝑖 = 0 𝑎 𝑖 \to 𝐿$ （ $𝑛 \to \infty$ ）．

証明. $𝜀 > 0$ をとる． $𝑎 𝑖 \to 𝐿$ だから，ある $𝑁$ があって $𝑖 \geq 𝑁$ ならば $| 𝑎 𝑖 - 𝐿 | < 𝜀 / 2$ である． $𝑛 > 𝑁$ に対し

∣ 1 𝑛 𝑛 - 1 \sum 𝑖 = 0 𝑎 𝑖 - 𝐿 ∣ \leq 1 𝑛 𝑛 - 1 \sum 𝑖 = 0 | 𝑎 𝑖 - 𝐿 | = 1 𝑛 𝑁 - 1 \sum 𝑖 = 0 | 𝑎 𝑖 - 𝐿 | + 1 𝑛 𝑛 - 1 \sum 𝑖 = 𝑁 | 𝑎 𝑖 - 𝐿 |

と分ける．第 2 項は $𝑛 - 𝑁 𝑛 \cdot 𝜀 2 < 𝜀 / 2$ で抑えられる．第 1 項の分子は $𝑛$ に依らない定数だから， $𝑛$ を十分大きくとれば $𝜀 / 2$ 未満にできる．合わせて $𝜀$ 未満である． $◻$

定理 3.2.6（エントロピーレート定理）. 定常情報源では $𝐻 (X)$ と $𝐻' (X)$ がともに存在し，しかも一致する．すなわち極限

l i m 𝑛 \to \infty 𝐻 𝑛 𝑛 = l i m 𝑛 \to \infty 𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)

は両側とも存在して等しい．

証明. 補題 3.2.4 より数列 $(𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)) 𝑛$ は非増加かつ下に $0$ で有界だから，ある $𝐿 \geq 0$ に収束する．これが $𝐻' (X)$ の存在である．

補題 3.2.3 より $𝐻 𝑛 / 𝑛 = 1 𝑛 \sum 𝑛 - 1 𝑖 = 0 𝐻 (𝑋 𝑖 ∣ 𝑋 𝑖)$ であり，これはいま収束を示した数列の相加平均である．補題 3.2.5 よりこれも $𝐿$ に収束する．これが $𝐻 (X)$ の存在と，二つの一致である． $◼$

形式化: 極限の存在 entropyRate_exists_of_stationary，二つの定義の一致entropyRate_eq_lim_condEntropy (ソース)

二つの定義が一致することの意味. 左辺は「長いブロックを丸ごと符号化したときの1 文字あたりの費用」で，第2章の圧縮の言葉である．右辺は「次の 1 文字がどれだけ読めないか」で，予測の言葉である．定理 3.2.6 は，圧縮の限界と予測の困難さが同じ数だと言っている．橋渡しをしているのは Cesàro 平均で，証明はそれ以上のことを何もしていない．増分が落ち着けば，その平均も同じところに落ち着く，というだけである．最初の何文字かは記憶が浅いぶん不確かさが大きいが， $1 / 𝑛$ で薄まって消える．

両端で確かめる. i.i.d. なら増分は最初から一定 $𝐻 (𝑋 0)$ で，平均も $𝐻 (𝑋 0)$ （例 3.2.2）．逆に $𝑋 0$ を一度決めたら以後ずっと同じ文字を出し続ける情報源では， $𝐻 (𝑋 0 ∣ 𝑋 0) = 𝐻 (𝑋 0)$ のあと増分は $0$ に落ちるので，レートは $0$ である．長さ $𝑛$ のブロックが実質 1 文字分の情報しかもたないのだから，1 文字あたりに直せば $0$ になるのが正しい．

形式化上の注記. entropyRate は「収束するならその極限」を返す形で定義されており，定義の時点では収束を要求しない．極限が実際に存在することは entropyRate_exists_of_stationary が別に述べ，その値が条件付きエントロピーの極限に一致することを entropyRate_eq_lim_condEntropy が述べる．本文が定義 3.2.1 で「存在するとき」と断って定理 3.2.6 で存在を示したのと，同じ二段構えである．

単位は本文と違う．形式化は本章を通じて $l o g$ を自然対数にとるので，ブロックエントロピー・増分・エントロピーレート，および 3.5 節の経験エントロピーはいずれもナットが単位である．本文は 3.1 節で底を 2 に固定したので，そこだけが表層で食い違う．ビットで測るエントロピーレートは entropyRate₂ として別に定義されている．

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