4.3 平均符号長の下界

4.2 節で，符号を作る問題は長さの組を選ぶ問題に置き換わった．残っているのは最小化である．Kraft の不等式を満たす $ℓ$ すべてにわたって $\sum 𝑥 𝑝 (𝑥) ℓ (𝑥)$ を小さくしたい．本節はその値を下から抑える．答えはエントロピーで，しかも下界を与える道具は第1章の情報不等式ただ一つである．

符号アルファベットが $𝐷$ 文字あるので，比べる相手も底を $𝐷$ にとったエントロピーになる．先に記号を用意する．

定義 4.3.1（底を $𝐷$ にとったエントロピー）. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑋$ を $X$ 上に分布 $𝑝$ をもつ確率変数とする．

𝐻 𝐷 (𝑋) : = - \sum 𝑥 \in X 𝑝 (𝑥) l o g 𝐷 𝑝 (𝑥)

と書く． $𝑝 (𝑥) = 0$ の項は定義 1.1.1 と同じく $0$ と約束する．

$l o g 𝐷 𝑡 = l o g 𝑡 / l o g 𝐷$ だから $𝐻 𝐷 (𝑋) = 𝐻 (𝑋) / l o g 𝐷$ であり，新しい量が増えたわけではない．エントロピーを「 $𝐷$ 文字を単位として測り直した」だけである． $𝐷 = 2$ なら $l o g 𝐷 = 1$ なので $𝐻 2 (𝑋) = 𝐻 (𝑋)$ である．

形式化: entropyD (ソース)

下界

定理 4.3.2. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑋$ を $X$ 上に分布 $𝑝$ をもつ確率変数とする． $ℓ : X \to {0, 1, 2, \dots}$ が Kraft の不等式を満たすならば

𝐻 𝐷 (𝑋) \leq \sum 𝑥 \in X 𝑝 (𝑥) ℓ (𝑥)

である．等号が成り立つのは，すべての $𝑥 \in X$ で $𝑝 (𝑥) = 𝐷 - ℓ (𝑥)$ となるとき，かつそのときに限る．

証明. $𝐾 : = \sum 𝑥 𝐷 - ℓ (𝑥)$ とおく． $X$ には分布 $𝑝$ が載っているから空ではなく，各項は正だから $𝐾 > 0$ であり，仮定より $𝐾 \leq 1$ である． $𝑟 (𝑥) : = 𝐷 - ℓ (𝑥) / 𝐾$ とおくと， $𝑟$ は $X$ 上の分布で，すべての $𝑥$ で $𝑟 (𝑥) > 0$ である．

差を二つの部分に分ける．定義 4.3.1 より

\sum 𝑥 𝑝 (𝑥) ℓ (𝑥) - 𝐻 𝐷 (𝑋) = \sum 𝑥 𝑝 (𝑥) (ℓ (𝑥) + l o g 𝐷 𝑝 (𝑥)) = \sum 𝑥 𝑝 (𝑥) l o g 𝐷 𝑝 (𝑥) 𝐷 - ℓ (𝑥)

である（ $𝑝 (𝑥) = 0$ の項はどの表示でも $0$ である）． $𝐷 - ℓ (𝑥) = 𝐾 𝑟 (𝑥)$ を入れ， $\sum 𝑥 𝑝 (𝑥) = 1$ を使うと

\sum 𝑥 𝑝 (𝑥) ℓ (𝑥) - 𝐻 𝐷 (𝑋) = \sum 𝑥 𝑝 (𝑥) l o g 𝐷 𝑝 (𝑥) 𝑟 (𝑥) + l o g 𝐷 1 𝐾

となる．

二つの項がどちらも非負であることを見る． $l o g 𝐷 𝑡 = l o g 𝑡 / l o g 𝐷$ と $l o g 𝐷 > 0$ より

\sum 𝑥 𝑝 (𝑥) l o g 𝐷 𝑝 (𝑥) 𝑟 (𝑥) = 1 l o g 𝐷 \sum 𝑥 𝑝 (𝑥) l o g 𝑝 (𝑥) 𝑟 (𝑥)

であり，右辺の和は分布 $𝑝$ と分布 $𝑟$ の相対エントロピーだから，定理 1.6.1 より $0$ 以上である．また $0 < 𝐾 \leq 1$ より $l o g 𝐷 (1 / 𝐾) \geq 0$ である．よって差は $0$ 以上で，不等式が従う．

等号を調べる．差が $0$ になるのは二つの項がともに $0$ のときに限る．定理 1.6.1 の等号条件より，第 1 項が $0$ になるのは $𝑝 = 𝑟$ のとき，かつそのときに限る．第 2 項が $0$ になるのは $𝐾 = 1$ のとき，かつそのときに限る．両方が成り立てば $𝑝 (𝑥) = 𝑟 (𝑥) = 𝐷 - ℓ (𝑥)$ である．逆にすべての $𝑥$ で $𝑝 (𝑥) = 𝐷 - ℓ (𝑥)$ ならば $𝐾 = \sum 𝑥 𝑝 (𝑥) = 1$ かつ $𝑟 = 𝑝$ となり，二つの項はどちらも $0$ になる． $◼$

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

証明の要点は一つだけである．Kraft の不等式を満たす長さの組 $ℓ$ は， $𝐷 - ℓ (𝑥)$ を正規化すれば分布 $𝑟$ を作る．そして平均符号長と $𝐻 𝐷 (𝑋)$ の差は，真の分布 $𝑝$ とその $𝑟$ との隔たりに，正規化で捨てたぶん $l o g 𝐷 (1 / 𝐾)$ を足したものになる．どちらも非負なので下界が出る．第1章 1.6 節で相対エントロピーを「 $𝑞$ だと思い込んで符号化したために余計に払う符号長」と読んだが，本節はその読み方を字義どおりに実現している．長さの組 $ℓ$ を選ぶことが分布 $𝑟$ を信じることに対応し，信じ違いのぶんが超過符号長の主要部になる．場所を余さず使いきったとき，すなわち $𝐾 = 1$ のときには，超過符号長は信じ違いのぶんちょうどである．

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

証明. $𝑐$ の符号語長を $ℓ$ とする．定義 4.1.1 より符号語は空でないから $ℓ (𝑥) \geq 1$ であり，定理 4.2.1 より $\sum 𝑥 𝐷 - ℓ (𝑥) \leq 1$ である．よって $ℓ$ は Kraft の不等式を満たし，定理 4.3.2 より $𝐻 𝐷 (𝑋) \leq \sum 𝑥 𝑝 (𝑥) ℓ (𝑥) = 𝐿 (𝑐)$ を得る． $◼$

形式化上の注記. 系 4.3.3 に対応する単独の宣言はない．定理 4.2.1 について形式化されているのは二元の場合だけで，一般の $𝐷$ については，より広い一意復号可能な符号についての形（4.5 節）が形式化されている．

例 4.3.4（三つの記号が等確率のとき）. $𝐷 = 2$ ， $X = {1, 2, 3}$ とし， $𝑋$ は $X$ 上の一様分布に従うとする．Kraft の不等式を満たすどの $ℓ : X \to {0, 1, 2, \dots}$ についても，定理 4.3.2 の等号は成り立たない．一方， $ℓ (1) = 1$ ， $ℓ (2) = ℓ (3) = 2$ は Kraft の不等式を満たし，その平均符号長は $5 / 3$ である．下界 $𝐻 2 (𝑋) = l o g 3$ との差は $0.0817 \dots$ である．

証明. 定理 4.3.2 の等号条件は，すべての $𝑥$ で $𝑝 (𝑥) = 2 - ℓ (𝑥)$ となることを要求する．ここで $𝑝 (𝑥) = 1 / 3$ であり， $ℓ (𝑥)$ が整数であるかぎり $2 - ℓ (𝑥)$ が $1 / 3$ になることはないから，等号は成り立たない．

後半は計算である． $2 - 1 + 2 - 2 + 2 - 2 = 1$ だから $ℓ$ は Kraft の不等式を満たし，平均符号長は $13 (1 + 2 + 2) = 53$ である．例 1.1.3 より $𝐻 (𝑋) = l o g 3$ で， $𝐷 = 2$ だから $𝐻 2 (𝑋) = l o g 3 = 1.5849 \dots$ であり， $5 / 3 = 1.6666 \dots$ との差が $0.0817 \dots$ になる． $◼$

定理 4.3.2 が言っているのは「Kraft の不等式を満たすどの長さの組でも，平均符号長は $𝐻 𝐷 (𝑋)$ を下回れない」ことだけで， $𝐻 𝐷 (𝑋)$ に届く符号があるとは言っていない．等号が成り立つのは，確率がちょうど $𝐷$ の冪の逆数に並んでいるという特別な場合に限る（例 4.1.4 がそれで，例 4.3.4 はそうでない）．一般には $l o g 𝐷 (1 / 𝑝 (𝑥))$ を整数に丸めるぶんだけ損をする．その損が高々 $1$ 文字で収まることを，すべての記号の確率が正である場合について次節で示す．そこで作る長さの組を符号として実現するには，アルファベットが $2$ 文字以上であることも要る．

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