4.5 McMillan の不等式

4.1 節で，語頭符号は一意復号可能な符号の真に狭いクラスであることを見た（例 4.1.5）．狭いクラスに制限しているのだから，読みながら区切れるという便利さの代わりに，平均符号長で損をしていてもおかしくない．本節はそうではないことを示す．鍵は，定理 4.2.1 の不等式が語頭性をまったく使わずに一意復号可能性だけから出る，という点にある．

証明では二項定理，すなわち実数 $𝛿 > 0$ と整数 $𝑘 \geq 0$ に対して $(1 + 𝛿) 𝑘 = \sum 𝑘 𝑗 = 0 (𝑘 𝑗) 𝛿 𝑗$ が成り立つことを既知として使う．

一意復号可能な符号への拡張

定理 4.5.1（McMillan の不等式）. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とする． $𝑐$ を $X$ 上の一意復号可能な $𝐷$ 元情報源符号， $ℓ (𝑥)$ をその符号語長とすると

\sum 𝑥 \in X 𝐷 - ℓ (𝑥) \leq 1

が成り立つ．

証明. $X$ が空なら左辺は $0$ で主張は成り立つから，空でないとしてよい． $𝐾 : = \sum 𝑥 𝐷 - ℓ (𝑥)$ ， $ℓ m a x : = m a x 𝑥 ℓ (𝑥)$ とおく．定義 4.1.1 より符号語は空でないので $ℓ (𝑥) \geq 1$ であり， $ℓ m a x \geq 1$ である．

$𝐾$ の冪を長さごとに数え直す．整数 $𝑘 \geq 1$ をとると，積を展開して

𝐾 𝑘 = \sum (𝑥 1, \dots, 𝑥 𝑘) \in X 𝑘 𝐷 - (ℓ (𝑥 1) + \dots + ℓ (𝑥 𝑘))

である．列 $(𝑥 1, \dots, 𝑥 𝑘)$ に対して $𝑐 * (𝑥 1, \dots, 𝑥 𝑘)$ の長さはちょうど $ℓ (𝑥 1) + \dots + ℓ (𝑥 𝑘)$ であり，この値は $𝑘$ 以上 $𝑘 ℓ m a x$ 以下である．そこで， $𝑐 *$ での像の長さが $𝑚$ になる $X 𝑘$ の元の個数を $𝑁 (𝑚)$ と書くと

𝐾 𝑘 = 𝑘 ℓ m a x \sum 𝑚 = 𝑘 𝑁 (𝑚) 𝐷 - 𝑚

となる．

一意復号可能性を数え上げに変える． $𝑐 *$ は単射だから，像の長さが $𝑚$ である $X 𝑘$ の元は，長さ $𝑚$ の相異なる列に写る．長さ $𝑚$ の列は $𝐷 𝑚$ 本しかないので $𝑁 (𝑚) \leq 𝐷 𝑚$ であり，上の和の各項は $1$ 以下である．項の個数は $𝑘 ℓ m a x - 𝑘 + 1$ だから

𝐾 𝑘 \leq 𝑘 ℓ m a x - 𝑘 + 1 \leq 𝑘 ℓ m a x

を得る．これがすべての $𝑘 \geq 1$ で成り立つ．

$𝐾$ が $1$ を超えられないことを見る． $𝐾 > 1$ として $𝛿 : = 𝐾 - 1 > 0$ とおく．二項定理の展開はすべての項が正だから， $𝑘 \geq 2$ のとき $𝑗 = 2$ の項だけを残して

𝐾 𝑘 = (1 + 𝛿) 𝑘 \geq (𝑘 2) 𝛿 2 = 𝑘 (𝑘 - 1) 2 𝛿 2

である．上の評価と合わせると $𝑘 (𝑘 - 1) 2 𝛿 2 \leq 𝑘 ℓ m a x$ ，すなわち $(𝑘 - 1) 𝛿 2 \leq 2 ℓ m a x$ がすべての $𝑘 \geq 2$ で成り立つことになる．左辺は $𝑘$ とともにいくらでも大きくなるので，これは矛盾である．よって $𝐾 \leq 1$ である． $◼$

形式化: kraftSum_le_one_of_uniquelyDecodable (ソース)

形式化上の注記. 形式化は，定義 4.1.2 の一意復号可能性を二つに分けて仮定している．符号語の集合に対する述語（符号語を並べてつないだ列が，並べ方が違えば違う列になる）と，写像 $𝑐$ が単射であることの二つで，合わせると定義 4.1.2 と同じことを言っている．ただし，定義 4.1.2 の一意復号可能性からこの二つを取り出すには $𝑐$ の単射性が要り，それは命題 4.1.3 の後半にあたるので，対応する宣言はない．また，証明の中核にあたる数え上げの定理は Mathlib にあり，形式化はそれを本書の枠組みへつないでいる．

証明の中身は，語頭符号のときの数え上げ（定理 4.2.1）とは別のものである．あちらは深さ $ℓ m a x$ で場所が重ならないことを一度数えただけだったが，こちらは $𝑘$ 文字の列をまとめて符号化し， $𝑘$ を大きくして矛盾を出す．定理 4.2.1 が語頭性を $1$ 回の数え上げに直せたのに対し，一意復号可能性から直に取り出せるのは「 $𝑘$ 文字ぶんの列が相異なる列に写る」という形で，本節の証明はそれを $𝑘$ について効かせている． $𝐾 > 1$ なら $𝐾 𝑘$ は指数で増えるのに，長さで数えた上界は $𝑘$ について一次でしか増えないという，増え方の差が矛盾を生んでいる．

系 4.5.2. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑋$ を $X$ 上に分布 $𝑝$ をもつ確率変数とする． $X$ 上の任意の一意復号可能な $𝐷$ 元情報源符号 $𝑐$ について $𝐻 𝐷 (𝑋) \leq 𝐿 (𝑐)$ である．

証明. $𝑐$ の符号語長を $ℓ$ とすると，定理 4.5.1 より $ℓ$ は Kraft の不等式を満たす．定理 4.3.2 を当てて $𝐻 𝐷 (𝑋) \leq \sum 𝑥 𝑝 (𝑥) ℓ (𝑥) = 𝐿 (𝑐)$ を得る． $◼$

形式化上の注記. 下界には対応する宣言があるが，すべての記号の確率が正である場合について述べてあるので，本文の主張をそのまま覆ってはいない．宣言は entropyD_le_expectedLength_of_uniquelyDecodable (InformationTheory/Shannon/McMillanKraftBridge.lean) である．

系 4.5.3. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とする． $X$ 上の一意復号可能な $𝐷$ 元情報源符号 $𝑐$ に対し， $X$ 上の $𝐷$ 元語頭符号で，各 $𝑥$ の符号語長が $𝑐$ のそれに等しいものが存在する．

証明. $𝑐$ の符号語長を $ℓ$ とする．定義 4.1.1 より $ℓ (𝑥) \geq 1$ であり，定理 4.5.1 より $\sum 𝑥 𝐷 - ℓ (𝑥) \leq 1$ である．定理 4.2.2 を当てればよい． $◼$

形式化上の注記. 系 4.5.3 に対応する単独の宣言はない．定理 4.5.1 の形式化と定理 4.2.2 の形式化を組み合わせれば得られるが，その組み合わせを書いた宣言はない．二つの宣言は符号アルファベットの表し方も違っていて，前者は大きさ $𝐷$ の有限集合として一般にとり，後者は $0$ から $𝐷 - 1$ までの整数に固定している．この取り替えも形式化では別に要る．

例 4.5.4（語頭符号への置き換え）. 例 4.1.5 の符号は一意復号可能だが語頭符号ではない．その符号語長の組は $ℓ (1) = 1$ ， $ℓ (2) = 2$ ， $ℓ (3) = 3$ であり，同じ長さの組をもつ二元語頭符号として例 4.1.4 の $𝑐 (1), 𝑐 (2), 𝑐 (3)$ がとれる． $X = {1, 2, 3}$ 上のどの分布についても，二つの符号の平均符号長は等しい．

証明. 例 4.1.5 の符号語は $0$ ， $01$ ， $011$ で，長さは $1, 2, 3$ である．例 4.1.4 の $𝑐 (1) = 0$ ， $𝑐 (2) = 10$ ， $𝑐 (3) = 110$ も長さが $1, 2, 3$ で，例 4.1.4 の証明よりこの三つのあいだに語頭の関係はない．平均符号長は定義 4.1.1 より符号語長の組と分布だけで決まるから，二つの符号で同じ値になる． $◼$

系 4.5.2 と系 4.3.3 を並べると，下界 $𝐻 𝐷 (𝑋)$ は語頭符号に限っても一意復号可能な符号まで広げても同じである．系 4.5.3 はその理由をもっと直接に述べていて，一意復号可能な符号は，長さを一切変えずに語頭符号に取り替えられる．読みながら区切れるという性質は，ただで手に入るということである．したがって最小の平均符号長を求める問題は，Kraft の不等式を満たし，かつすべての $𝑥$ で $ℓ (𝑥) \geq 1$ である長さの組 $ℓ$ のうちで $\sum 𝑥 𝑝 (𝑥) ℓ (𝑥)$ を最小にするものを探す問題に，何も失わずに書き換えられる．系 4.2.5 より，この二つの条件を満たす長さの組はちょうど $𝐷$ 元語頭符号の符号語長の組である．次節は，符号アルファベットが $2$ 文字の場合について，その最小を与える手続きを作る．

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