12.1 万能符号と冗長度

第4章の符号語長は，どれも分布から作られていた．定義 4.4.1 の Shannon 符号語長は $𝑝 (𝑥)$ の値をそのまま見て決まり，4.6 節の Huffman 符号も同じである．符号を作る側が分布を知っていることが，そこでは前提になっていた．本章が扱うのは，その前提が外れた場合である．

分かっているのが，分布がある族 ${𝑃 𝜃} 𝜃 \in Θ$ のどれかであることだけで，どの $𝜃$ が真かは符号を作る時点で決まっていない，という状況を考える．たとえば，同じ言語の文章でも文字の出現の偏りは書き手ごとに違うので，三人の書き手のうち誰が書いたかによって分布が変わる．あるいは，同じ測定を A 社の装置で行うか B 社の装置で行うかによって，雑音の出方が変わる．このとき，一つの符号長の組で，族のどの分布に対しても平均符号長をそのエントロピーの近くに保てるだろうか．族のどれが真であっても $1$ 文字あたりの平均符号長がそのエントロピーに近づいていく符号がとれるなら，どの分布が真かを知らないことの代償は，長い系列に対してはほとんど払わずに済む．本節はこの問いを，近づき方を測る量を定め，その量で万能符号という語を定めるところまで形にする．

本章では対数の底を $2$ にとり，エントロピーと相対エントロピーの単位をビットで測る．本章の符号はすべて二元で， $2 - ℓ$ の形の量を扱うので，指数と対数の底をそろえておくと式が読みやすい．底を明示するため，以下では $l o g 2$ と書く．エントロピー $𝐻$ （定義 1.1.1）と相対エントロピー $𝐷 (\cdot ‖ \cdot)$ （1.6 節）もこの底で測る．対数が狭義単調増加であること（補題 8.2.5）は，以下ことわりなく使う．

符号長の組と冗長度

定義 12.1.1（情報源の族と二元の符号長の組）. $X$ を空でない有限アルファベット， $Θ$ を空でない有限集合とし，各 $𝜃 \in Θ$ に $X$ 上の分布 $𝑃 𝜃$ で全点で正であるものを与える．この対応を 情報源の族 と呼ぶ． $𝑛 \geq 1$ に対し， $𝑃 𝜃$ の $𝑛$ 重の積分布を $𝑃 𝑛 𝜃$ と書く（第11章と同じ肩の書き方で， $𝑃 𝑛 𝜃 ({𝑥}) : = \prod 𝑛 - 1 𝑖 = 0 𝑃 𝜃 (𝑥 𝑖)$ である）．また，関数 $ℓ 𝑛 : X 𝑛 \to {0, 1, 2, \dots}$ が 長さ $𝑛$ の符号長の組 であるとは，

\sum 𝑥 \in X 𝑛 2 - ℓ 𝑛 (𝑥) \leq 1

を満たすことをいう（ $𝐷 = 2$ の場合の定義 4.2.4 の Kraft の不等式である）．

第4章は符号アルファベットの大きさを裸の $𝐷$ と書いたが，本章はその値を $2$ に固定する．以下で $𝐷 = 2$ と書くのは第4章の主張を引くときにその値を指定するためで，それ以外の $𝐷$ はつねに二つの分布を引数にとる相対エントロピーである．定義 4.3.1 の $𝐻 𝐷$ も $𝐷 = 2$ の場合しか使わず，その値は $𝐻$ に等しい．

長さ $𝑛$ の符号長の組は，定義 4.2.4 が置いた $X 𝑛$ 上の長さの組のうち， $𝐷 = 2$ について Kraft の不等式を満たすものにほかならない．本章はこの条件をつねに付けて呼ぶので，短い名前を与えた．符号そのものではなく符号長の組を扱うのは，第4章 4.2 節と同じ理由である．Kraft の不等式を満たし，どの値も $1$ 以上である長さの組には，各点でその長さをもつ二元語頭符号がとれる（定理 4.2.2）ので，符号を作る問題は長さの組を選ぶ問題に置き換わる．逆向きも押さえておく．語頭符号よりも広い一意復号可能な符号まで許しても，その符号語長は Kraft の不等式を満たす（定理 4.5.1）から，長さの組に限って考えても取りこぼしはない（同じ長さをもつ語頭符号がとれることは系 4.5.3 が述べている）．族のほうに全点で正であることを課したのは，定義 4.4.1 の Shannon 符号語長と 1.6 節の相対エントロピーを，値が無限大になる場合を場合分けせずに使うためである． $Θ$ を有限にとったのは，三つの場所で効くからである．一つめは定義 12.1.5 で，族全体をわたる最悪の冗長度を最大値として書ける．二つめは 12.3 節で，この族を一つの通信路として読むときに入力アルファベットが有限であることを使う．三つめは系 12.4.9 で，上界に $l o g 2 | Θ |$ が現れる．文字の偏りや装置の雑音の強さが実数の範囲を連続に動く場合のように，パラメータが連続に動く族は本章では扱わない．

定義 12.1.2（冗長度）. 定義 12.1.1 の設定で， $𝑛 \geq 1$ ， $ℓ 𝑛$ を長さ $𝑛$ の符号長の組， $𝜃 \in Θ$ とする． $ℓ 𝑛$ の $𝜃$ における 冗長度 を

Δ 𝑛 (ℓ 𝑛, 𝜃) : = 1 𝑛 (\sum 𝑥 \in X 𝑛 𝑃 𝑛 𝜃 ({𝑥}) ℓ 𝑛 (𝑥) - 𝐻 (𝑃 𝑛 𝜃))

で定める（ $𝐻$ は定義 1.1.1 のエントロピーを分布に対して書いたもので，底は $2$ である）．

括弧の中は，真の分布が $𝑃 𝑛 𝜃$ であるときの平均符号長から，同じ分布のエントロピーを引いたものである．第4章 4.3 節が示したとおり，このエントロピーはどの符号長の組でも下回れない下界だったから，差は下界からの超過分を表している．それを長さ $𝑛$ で割って $1$ 文字あたりに直したのが冗長度である． $𝜃$ を引数にとっているのが要点で，一つの $ℓ 𝑛$ に対して $Θ$ の元の数だけ冗長度がある．万能符号を求めるとは，このすべてを同時に小さくする $ℓ 𝑛$ を求めることにほかならない．あとで見るように，符号長の組を選ぶことはある分布を信じることに対応し，冗長度の $𝑛$ 倍は，その信じ違いの大きさと，符号が場所を余らせたぶんとの和になる（補題 12.3.2）．

第6章 6.1 節は確率単体を裸の $Δ$ と書いたが，本章の $Δ 𝑛 (ℓ 𝑛, 𝜃)$ はつねに添字 $𝑛$ を持ち，二つの引数をとる．このあと置くミニマックス冗長度 $Δ * 𝑛$ も添字 $𝑛$ を持つ．裸の $Δ$ は本章に現れない．

形式化上の注記

冗長度に対応する宣言は無い．平均符号長 expectedLength とエントロピー entropyD (InformationTheory/Shannon/ShannonCode/Basic.lean) はどちらも形式化されているが，その差を $𝑛$ で割った量に名前を与えた宣言は無い．

命題 12.1.3. 定義 12.1.1 の設定で， $𝑛 \geq 1$ ， $ℓ 𝑛$ を長さ $𝑛$ の符号長の組， $𝜃 \in Θ$ とすると $Δ 𝑛 (ℓ 𝑛, 𝜃) \geq 0$ である．

証明. $𝑋 𝑛$ を $X 𝑛$ 上に分布 $𝑃 𝑛 𝜃$ をもつ確率変数とする． $ℓ 𝑛$ は $X 𝑛$ の上で定義され $0$ 以上の整数値をとり， $𝐷 = 2$ について Kraft の不等式を満たすから，定理 4.3.2 を $X 𝑛$ と $𝐷 = 2$ に当てて

𝐻 2 (𝑋 𝑛) \leq \sum 𝑥 \in X 𝑛 𝑃 𝑛 𝜃 ({𝑥}) ℓ 𝑛 (𝑥)

を得る．本章は底を $2$ にとっているので $𝐻 2 (𝑋 𝑛) = 𝐻 (𝑃 𝑛 𝜃)$ であり，差は $0$ 以上である． $𝑛 > 0$ で割っても符号は変わらない． $◼$

形式化上の注記

命題 12.1.3 に対応する単独の宣言は無い．定理 4.3.2 の形式化 entropyD_le_expectedLength_of_kraft (InformationTheory/Shannon/ShannonCode/Basic.lean) は全点で正の分布について述べているので $X 𝑛$ と $𝑃 𝑛 𝜃$ にそのまま当たるが，その差を $𝑛$ で割った冗長度の形にした宣言は無い（例 12.1.4 と同じ理由である）．

冗長度が負にならないというのは，符号長の組をどう選んでも平均符号長がエントロピーを下回れない，という定理 4.3.2 の言い換えである．したがって冗長度は， $0$ に近いほど良い符号だという読み方ができる． $0$ そのものになるのは，確率がちょうど $2$ の冪の逆数に並んでいる特別な場合に限る（定理 4.3.2 の等号条件）．

分布を知っている場合と，知らずに決めつけた場合

例 12.1.4（分布を知っている場合）. 定義 12.1.1 の設定で $𝜃 \in Θ$ を一つ固定し， $𝑛 \geq 1$ とする． $X 𝑛$ 上の分布 $𝑃 𝑛 𝜃$ について定義 4.4.1（ $𝐷 = 2$ ）の Shannon 符号語長

ℓ 𝑛 (𝑥) : = ⌈ l o g 2 1 𝑃 𝑛 𝜃 ({𝑥}) ⌉

をとると， $ℓ 𝑛$ は長さ $𝑛$ の符号長の組であり

0 \leq Δ 𝑛 (ℓ 𝑛, 𝜃) < 1 𝑛

である．

証明. $𝑃 𝜃$ は全点で正だから $𝑃 𝑛 𝜃$ も全点で正であり， $X 𝑛$ と $𝑃 𝑛 𝜃$ に定義 4.4.1 が当たる． $ℓ 𝑛$ が長さ $𝑛$ の符号長の組であることは，命題 4.4.2 を $X 𝑛$ ， $𝐷 = 2$ ，分布 $𝑃 𝑛 𝜃$ に当てればよい（値が $0$ 以上の整数であることは天井関数の定義から従う）．

$𝑋 𝑛$ を $X 𝑛$ 上に分布 $𝑃 𝑛 𝜃$ をもつ確率変数とし，定理 4.4.4 を同じ設定に当てると

𝐻 2 (𝑋 𝑛) \leq \sum 𝑥 \in X 𝑛 𝑃 𝑛 𝜃 ({𝑥}) ℓ 𝑛 (𝑥) < 𝐻 2 (𝑋 𝑛) + 1

である． $𝐻 2 (𝑋 𝑛) = 𝐻 (𝑃 𝑛 𝜃)$ だから，各辺から $𝐻 (𝑃 𝑛 𝜃)$ を引いて $𝑛$ で割れば主張を得る． $◼$

形式化上の注記

例 12.1.4 に対応する単独の宣言は無い．定理 4.4.4 の形式化 shannonCode_expected_length_bounds (InformationTheory/Shannon/ShannonCode/Basic.lean) は有限アルファベットと全点で正の分布について述べているので $X 𝑛$ と $𝑃 𝑛 𝜃$ にそのまま当たるが，それを $𝑛$ で割って冗長度の形にした宣言は無い（系 4.4.6 と同じ理由である）．

例 12.1.4 の $ℓ 𝑛$ は $𝜃$ を使って作られている．族の中の一つを狙って作った符号なので，真の分布が別の $𝜃$ のものだったときに何が起きるかは，これだけでは分からない．次の二つの定義で，族全体をわたる最悪の冗長度を測る量を置き，そのうえで万能符号という語を定める．そのあとで実際に起きることを二つのコインで見る．

定義 12.1.5（ミニマックス冗長度）. 定義 12.1.1 の設定で $𝑛 \geq 1$ とする．長さ $𝑛$ の ミニマックス冗長度 を

Δ * 𝑛 : = i n f ℓ 𝑛 m a x 𝜃 \in Θ Δ 𝑛 (ℓ 𝑛, 𝜃)

で定める．下限は長さ $𝑛$ の符号長の組の全体，最大は有限集合 $Θ$ の上でとる．

$Θ$ が有限なので内側は最大値である．外側を下限で書いたのは，最小を与える符号長の組があるかどうかを言わずに済ませるためである．下限をとる値の集合は空でなく（例 12.1.4 の $ℓ 𝑛$ が一つの元を与える），命題 12.1.3 よりどの元も $0$ 以上だから， $Δ * 𝑛$ は $0$ 以上の実数として定まる． $Δ * 𝑛$ が小さいということは，どの $𝜀 > 0$ をとっても， $Θ$ のどの元が真であっても $1$ 文字あたりの損が $Δ * 𝑛 + 𝜀$ に収まる符号長の組がある，ということである．下限がその集合の元であるとは限らないので， $𝜀$ を許さずに同じことは言えない．

これで，節のはじめに挙げた問いを言葉のまま述べられる．

定義 12.1.6（万能符号）. 定義 12.1.1 の設定で，各 $𝑛 \geq 1$ に長さ $𝑛$ の符号長の組 $ℓ 𝑛$ を一つずつ与えたものを $(ℓ 𝑛) 𝑛 \geq 1$ と書く．これが族 ${𝑃 𝜃} 𝜃 \in Θ$ に対する 万能符号 であるとは，

l i m 𝑛 \to \infty m a x 𝜃 \in Θ Δ 𝑛 (ℓ 𝑛, 𝜃) = 0

が成り立つことをいう（ $Δ 𝑛$ は定義 12.1.2 の冗長度）．

最大を $Θ$ の上でとっているところに，この節の問いがそのまま入っている． $𝜃$ ごとに符号を選び直してよいのなら例 12.1.4 が答えを与えるが，そこで得た $ℓ 𝑛$ は $𝜃$ に依っており，真の $𝜃$ を知らなければ選べない．一つの $ℓ 𝑛$ で族の全体を賄う以上，測るのはいちばん悪い $𝜃$ での冗長度になる．命題 12.1.3 よりこの最大は $0$ 以上だから，定義 12.1.6 が求めているのは，最悪の冗長度が $𝑛$ とともに $0$ へ減っていくことである．そのような列が実際にあるかどうかは，定義からは何も出てこない．次節がそれを一つ作る．

例 12.1.7（二つの偏ったコイン）. $X = {0, 1}$ ， $Θ = {1, 2}$ とし， $𝑃 1 (0) = 0.1$ ， $𝑃 1 (1) = 0.9$ ， $𝑃 2 (0) = 0.9$ ， $𝑃 2 (1) = 0.1$ とする． $𝑛 \geq 1$ とし， $𝜃 = 1$ だと決めつけて例 12.1.4 の符号長の組 $ℓ 𝑛$ （分布 $𝑃 𝑛 1$ についての Shannon 符号語長）をとると

Δ 𝑛 (ℓ 𝑛, 2) \geq 𝐷 (𝑃 2 ∥ 𝑃 1) = 0.8 l o g 2 9 = 2.535 \dots

ビットである．いっぽう $ℓ' 𝑛 (𝑥) : = 𝑛$ （すべての $𝑥 \in X 𝑛$ で $𝑛$ ）とおくと， $ℓ' 𝑛$ も長さ $𝑛$ の符号長の組であり，どちらの $𝜃 \in Θ$ についても

Δ 𝑛 (ℓ' 𝑛, 𝜃) = 1 - 𝐻 𝑏 (0.1) = 0.531 \dots

ビットである（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピーで， $𝐻 𝑏 (0.1) = 0.468 \dots$ である）．したがって $Δ * 𝑛 \leq 0.531 \dots$ ビットがすべての $𝑛 \geq 1$ で成り立つ．

証明. 第 $1$ の主張から見る．4.4 節が既知とした天井関数の性質より $ℓ 𝑛 (𝑥) \geq l o g 2 1 𝑃 𝑛 1 ({𝑥})$ だから

𝑛 Δ 𝑛 (ℓ 𝑛, 2) = \sum 𝑥 𝑃 𝑛 2 ({𝑥}) ℓ 𝑛 (𝑥) - 𝐻 (𝑃 𝑛 2) \geq \sum 𝑥 𝑃 𝑛 2 ({𝑥}) l o g 2 1 𝑃 𝑛 1 ({𝑥}) - 𝐻 (𝑃 𝑛 2)

である．右辺で $𝐻 (𝑃 𝑛 2) = - \sum 𝑥 𝑃 𝑛 2 ({𝑥}) l o g 2 𝑃 𝑛 2 ({𝑥})$ を書き下して二つの和をまとめると，1.6 節の相対エントロピーの定義そのものになり，右辺は $𝐷 (𝑃 𝑛 2 ‖ 𝑃 𝑛 1)$ に等しい． $𝑃 1$ と $𝑃 2$ はどちらも全点で正だから補題 11.4.5 より $𝐷 (𝑃 𝑛 2 ‖ 𝑃 𝑛 1) = 𝑛 𝐷 (𝑃 2 ‖ 𝑃 1)$ であり（この等式は底のとり方に依らない），両辺を $𝑛$ で割ると第 $1$ の不等式を得る．値は

𝐷 (𝑃 2 ∥ 𝑃 1) = 0.9 l o g 2 0.9 0.1 + 0.1 l o g 2 0.1 0.9 = (0.9 - 0.1) l o g 2 9

であり， $l o g 2 9 = 2 l o g 2 3 = 3.1699 \dots$ だから $0.8 \times 3.1699 \dots = 2.5359 \dots$ である．

第 $2$ の主張に移る． $| X 𝑛 | = 2 𝑛$ だから $\sum 𝑥 2 - ℓ' 𝑛 (𝑥) = 2 𝑛 \cdot 2 - 𝑛 = 1$ であり， $ℓ' 𝑛$ は長さ $𝑛$ の符号長の組である．平均符号長は $𝑥$ に依らず $𝑛$ で， $𝑃 𝑛 𝜃$ は分布 $𝑃 𝜃$ の i.i.d. 情報源の長さ $𝑛$ のブロックの分布だから補題 2.3.3 より $𝐻 (𝑃 𝑛 𝜃) = 𝑛 𝐻 (𝑃 𝜃)$ である．どちらの $𝜃$ でも $𝑃 𝜃$ の一方の点の確率が $0.1$ だから，例 1.1.2 より $𝐻 (𝑃 𝜃) = 𝐻 𝑏 (0.1)$ である．よって $Δ 𝑛 (ℓ' 𝑛, 𝜃) = 1 𝑛 (𝑛 - 𝑛 𝐻 𝑏 (0.1)) = 1 - 𝐻 𝑏 (0.1)$ となる．値は $𝐻 𝑏 (0.1) = - 0.1 l o g 2 0.1 - 0.9 l o g 2 0.9 = 0.4689 \dots$ だから $0.5310 \dots$ である．最後に， $ℓ' 𝑛$ は定義 12.1.5 の下限をとる範囲に入っており，そこでの最大は $𝜃$ に依らず $1 - 𝐻 𝑏 (0.1)$ だから， $Δ * 𝑛 \leq 1 - 𝐻 𝑏 (0.1)$ である． $◼$

形式化上の注記

例 12.1.7 は形式化されていない．例 12.1.7 に付した証明が，この主張の保証のすべてである．

決めつけの代償が，二つの意味で大きいことに注目したい．一つめは $𝑛$ との関係である．分布を知っていれば冗長度は $1 / 𝑛$ 未満で， $𝑛$ を大きくすれば消える（例 12.1.4）のに対し， $𝜃 = 1$ と決めつけたときの $2.535 \dots$ ビットは， $𝑛$ をいくら大きくとっても減らない．相対エントロピーが $1$ 文字あたりの量として残るからである．二つめは，この代償が「何も知らないふりをする」ことよりも高くつく点である． $ℓ' 𝑛$ は系列をそのまま $𝑛$ ビットで書き写すだけの符号長の組で，分布についての知識を何も使っていないが，その冗長度は $0.531 \dots$ ビットで，決めつけたときの $4$ 分の $1$ 以下である．この族では，間違った分布を信じるより偏りを使わないほうが良いことになる．

$ℓ' 𝑛$ の冗長度が $𝜃$ に依らないのは，この族の二つの分布のエントロピーがどちらも $𝐻 𝑏 (0.1)$ だからで，族の取り方に依る話である．例 12.1.7 が与えた $Δ * 𝑛 \leq 0.531 \dots$ ビットという上界も，この族についてのものでしかない．次節は $Δ * 𝑛$ の上界を，族の取り方に依らない形で，しかも $𝑛$ とともに $0$ に向かう形で与える．

情報理論入門（Lean による形式証明つき）・GitHub