12.2 型による万能符号

12.1 節は，族のどれが真かを知らずに符号を作る問題を，冗長度という一つの量に落とした．残っているのは，その量を族によらず小さくする符号長の組を実際に作ることである．手がかりは第11章にある．系列 $𝑥$ の型 $ˆ 𝑃 𝑥$ （定義 11.1.1）は $𝑥$ の中で各文字が何回出たかだけから決まり，真の分布を持ち出さずに計算できる．しかも定理 11.1.8 が，型類の要素数を型のエントロピーで測っている．そこで，まず型を送り，次に型類の中で何番目かを送る，という二段構えの符号を考える．受け取る側は，前半で型を知り，後半でその型類の中の位置を知るので，二つを合わせれば系列が復元できる．

この構成のどこにも $𝑃 𝜃$ が現れないことが要点である．符号を作る側が見るのは送る系列だけで，族についての知識は使わない．それでいて，前半の長さは型の個数で決まり（型は多項式個しかない），後半の長さは型類の要素数で決まる（要素数は型のエントロピーで抑えられる）ので，符号長は自動的にその系列の型のエントロピーに近くなる．この節はその見積もりを最後まで書き下す．

第11章の道具を引く前に，底の違いを一度そろえておく．第11章は $l o g$ の底を自然対数にとっているので，定理 11.1.8 の上界は，そこで測ったエントロピーを $e$ の肩に乗せた形をしている．自然対数で測ったエントロピーは，本章の底で測った $𝐻 (𝑃)$ の $l o g e 2$ 倍だから

e 𝑛 𝐻 (𝑃) l o g e 2 = 2 𝑛 𝐻 (𝑃)

であり，本章の底では定理 11.1.8 の上界は $| T 𝑛 (𝑃) | \leq 2 𝑛 𝐻 (𝑃)$ と読める（ $𝐻$ は本章の底で測ったエントロピーである）．底を取り替えても対数の値は正の定数倍しか変わらないので，第11章のほかの評価も同じように読み替えてよい．以下ではこの読み替えを断らずに使う．

二段符号の符号長

定義 12.2.1（型による二段符号の符号長）. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とする． $𝑥 \in X 𝑛$ の型を $ˆ 𝑃 𝑥$ ，長さ $𝑛$ の型 $𝑃$ の型類を $T 𝑛 (𝑃)$ （どちらも定義 11.1.1）と書き，

ℓ T 𝑛 (𝑥) : = ⌈ | X | l o g 2 (𝑛 + 1) ⌉ + ⌈ l o g 2 ∣ T 𝑛 (ˆ 𝑃 𝑥) ∣ ⌉

と定める． $ℓ T 𝑛$ を 型による二段符号の符号長 と呼ぶ．

第 $1$ 項は型そのものを指すための長さである．長さ $𝑛$ の型は $(𝑛 + 1) | X |$ 個以下しかない（命題 11.1.3）ので，型に通し番号を振れば $| X | l o g 2 (𝑛 + 1)$ ビットあまりで書ける．第 $2$ 項は，型が決まったあとに型類の中の位置を指すための長さである．どちらも切り上げてあるのは，符号語長が整数でなければならないからで，天井関数とその性質 $𝑡 \leq ⌈ 𝑡 ⌉ < 𝑡 + 1$ は 4.4 節で既知としたとおりに本節でも使う．第 $1$ 項が $𝑥$ に依らないのは，型を書くための場所を，どの系列についても同じだけ確保しているからである．

形式化上の注記. 型による二段符号の符号長に対応する宣言は無い．型と型類は定義 11.1.1 の形式化がそのまま使えるが，それを符号長に組み上げた宣言は無い．

命題 12.2.2. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とする． $ℓ T 𝑛$ （定義 12.2.1）は定義 12.1.1 の意味で長さ $𝑛$ の符号長の組であり，すべての $𝑥 \in X 𝑛$ で $ℓ T 𝑛 (𝑥) \geq 1$ である．したがって定理 4.2.2 より， $X 𝑛$ 上の二元語頭符号で，各 $𝑥$ の符号語長が $ℓ T 𝑛 (𝑥)$ に等しいものが存在する．

証明. $𝐴 : = ⌈ | X | l o g 2 (𝑛 + 1) ⌉$ と置く． $𝑛 \geq 1$ より $l o g 2 (𝑛 + 1) \geq 1$ であり， $X$ は空でないから $| X | \geq 1$ で， $| X | l o g 2 (𝑛 + 1) \geq 1$ である．天井関数の性質より $𝐴 \geq 1$ であり，第 $2$ 項は $0$ 以上だから $ℓ T 𝑛 (𝑥) \geq 1$ である．値が整数であることも天井関数の定義から従う．

Kraft の不等式に移る．どの $𝑥$ もただ一つの型をもつ（定義 11.1.1）から，長さ $𝑛$ の型の型類は $X 𝑛$ を重なりなく覆う． $𝑥 \in T 𝑛 (𝑃)$ ならば $ˆ 𝑃 𝑥 = 𝑃$ なので，その上で $ℓ T 𝑛 (𝑥) = 𝐴 + ⌈ l o g 2 | T 𝑛 (𝑃) | ⌉$ は一定である．よって $𝑃$ が長さ $𝑛$ の型の全体をわたる和として

\sum 𝑥 \in X 𝑛 2 - ℓ T 𝑛 (𝑥) = 2 - 𝐴 \sum 𝑃 ∣ T 𝑛 (𝑃) ∣ 2 - ⌈ l o g 2 | T 𝑛 (𝑃) | ⌉

と書ける．長さ $𝑛$ の型の型類は空でないから $| T 𝑛 (𝑃) | \geq 1$ であり，天井関数の性質より $⌈ l o g 2 | T 𝑛 (𝑃) | ⌉ \geq l o g 2 | T 𝑛 (𝑃) |$ だから，和の各項は

∣ T 𝑛 (𝑃) ∣ 2 - ⌈ l o g 2 | T 𝑛 (𝑃) | ⌉ \leq ∣ T 𝑛 (𝑃) ∣ 2 - l o g 2 | T 𝑛 (𝑃) | = 1

を満たす．項の個数は命題 11.1.3 より $(𝑛 + 1) | X |$ 以下である．また $𝐴 \geq | X | l o g 2 (𝑛 + 1)$ より $2 - 𝐴 \leq (𝑛 + 1) - | X |$ である．三つを合わせると和は $1$ 以下になる．

最後に定理 4.2.2 を，アルファベット $X 𝑛$ ， $𝐷 = 2$ ，長さの組 $ℓ T 𝑛$ に当てる．値が $1$ 以上の整数であることと Kraft の不等式は上で見たとおりである． $◼$

第 $1$ 項の $𝐴$ が，型の個数を数えた命題 11.1.3 の指数をそのまま切り上げた形になっているのが，Kraft の不等式が閉じる仕組みである．型ごとに $2 - 𝐴$ という同じ大きさの場所を割り当て，その中を型類の要素で分け合う．型の個数が $2 𝐴$ 以下だから，全部足しても $1$ を超えない．なお，節のはじめに述べた二段の手続きそのものが語頭符号を与えることは，本書では確かめない．本章が扱うのは符号語長の組であり，その長さをもつ符号が存在することは定理 4.2.2 に任せる（12.1 節で見たとおり，符号を作る問題は長さの組を選ぶ問題に置き換わっている）．この方針は本章を通じてとるもので，各節で述べる構成は，符号そのものではなく長さの由来を説明したものである．命題 12.2.2 が与えるのも，この長さをもつ二元語頭符号が存在することである．

型のエントロピーの平均

補題 12.2.3. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $𝑃$ を $X$ 上の分布， $𝑃 𝑛$ をその $𝑛$ 重の積分布とする． $𝑥 \in X 𝑛$ の型を $ˆ 𝑃 𝑥$ （定義 11.1.1）と書くと

\sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) 𝐻 (ˆ 𝑃 𝑥) \leq 𝐻 (𝑃)

である（ $𝐻$ は定義 1.1.1 のエントロピー）．

証明. $𝜑 (𝑡) = - 𝑡 l o g 2 𝑡$ （ $𝑡 \geq 0$ ， $𝜑 (0) : = 0$ ）と置くと，定義 1.1.1 より $𝐻 (ˆ 𝑃 𝑥) = \sum 𝑎 \in X 𝜑 (ˆ 𝑃 𝑥 (𝑎))$ である． $X$ も $X 𝑛$ も有限だから和の順序を入れ替えてよく

\sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) 𝐻 (ˆ 𝑃 𝑥) = \sum 𝑎 \in X \sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) 𝜑 (ˆ 𝑃 𝑥 (𝑎))

となる．文字 $𝑎 \in X$ を固定して内側の和を評価する． $𝑃 𝑛$ は $X 𝑛$ 上の分布だから重み $𝑃 𝑛 ({𝑥})$ は非負で総和が $1$ であり，点 $ˆ 𝑃 𝑥 (𝑎)$ は $𝜑$ の定義域 $[0, \infty)$ に入る．1.1 節で認めた $𝜑$ の凹性のもと補題 1.1.9 を当てると

\sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) 𝜑 (ˆ 𝑃 𝑥 (𝑎)) \leq 𝜑 (\sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) ˆ 𝑃 𝑥 (𝑎))

である．

内側の重心を求める．定義 11.1.1 より $ˆ 𝑃 𝑥 (𝑎) = 𝑁 (𝑎 ∣ 𝑥) / 𝑛$ で， $𝑁 (𝑎 ∣ 𝑥)$ は $𝑥 𝑖 = 𝑎$ となる位置 $𝑖$ の個数だから，位置ごとに数えると

\sum 𝑥 \in X 𝑛 𝑃 𝑛 ({𝑥}) 𝑁 (𝑎 ∣ 𝑥) = 𝑛 - 1 \sum 𝑖 = 0 \sum 𝑥 : 𝑥 𝑖 = 𝑎 𝑃 𝑛 ({𝑥}) = 𝑛 - 1 \sum 𝑖 = 0 𝑃 (𝑎) = 𝑛 𝑃 (𝑎)

である（ $𝑃 𝑛$ の第 $𝑖$ 成分の周辺分布は $𝑃$ だから，内側の和は $𝑃 (𝑎)$ に等しい）．よって重心は $𝑃 (𝑎)$ であり，上の不等式の右辺は $𝜑 (𝑃 (𝑎))$ になる． $𝑎$ について足すと，右辺の和は $\sum 𝑎 𝜑 (𝑃 (𝑎)) = 𝐻 (𝑃)$ であり，主張を得る． $◻$

補題 12.2.3 が言っているのは，型のエントロピーは平均すると真の分布のエントロピーを超えない，ということである．長さ $𝑛$ の系列を見て作った型は，真の分布のまわりで揺れている．揺れているぶんだけエントロピーは上にも下にも動きうるが， $𝜑$ が凹であるために，平均をとると下側に寄る．二段符号の後半の長さは型類の要素数で決まり，それが型のエントロピーで抑えられているので，平均符号長を真の分布のエントロピーと比べるときに，この補題がちょうど必要な向きの不等式を与える．

冗長度の評価

定理 12.2.4（型による二段符号の冗長度）. 定義 12.1.1 の設定で $𝑛 \geq 1$ とすると，どの $𝜃 \in Θ$ についても

Δ 𝑛 (ℓ T 𝑛, 𝜃) \leq | X | l o g 2 (𝑛 + 1) + 2 𝑛

である（ $ℓ T 𝑛$ は定義 12.2.1 の符号長の組， $Δ 𝑛$ は定義 12.1.2 の冗長度）．

証明. 天井関数の性質 $⌈ 𝑡 ⌉ < 𝑡 + 1$ を定義 12.2.1 の二つの項に当てると

ℓ T 𝑛 (𝑥) < | X | l o g 2 (𝑛 + 1) + 2 + l o g 2 ∣ T 𝑛 (ˆ 𝑃 𝑥) ∣

である．

型類の要素数を抑える．本章の底で読むと定理 11.1.8 の上界は $| T 𝑛 (𝑃) | \leq 2 𝑛 𝐻 (𝑃)$ である．両辺の $l o g 2$ をとると $l o g 2 | T 𝑛 (𝑃) | \leq 𝑛 𝐻 (𝑃)$ であり， $𝑃 : = ˆ 𝑃 𝑥$ ととって上の評価に入れると

ℓ T 𝑛 (𝑥) < | X | l o g 2 (𝑛 + 1) + 2 + 𝑛 𝐻 (ˆ 𝑃 𝑥)

となる．

$𝜃 \in Θ$ をとり，両辺に $𝑃 𝑛 𝜃 ({𝑥})$ を掛けて $𝑥$ について足す． $\sum 𝑥 𝑃 𝑛 𝜃 ({𝑥}) = 1$ と，補題 12.2.3 を $𝑃 : = 𝑃 𝜃$ に当てた不等式から

\sum 𝑥 \in X 𝑛 𝑃 𝑛 𝜃 ({𝑥}) ℓ T 𝑛 (𝑥) < | X | l o g 2 (𝑛 + 1) + 2 + 𝑛 𝐻 (𝑃 𝜃)

である．いっぽう $𝑃 𝑛 𝜃$ は分布 $𝑃 𝜃$ の i.i.d. 情報源の長さ $𝑛$ のブロックの分布だから，補題 2.3.3 より $𝐻 (𝑃 𝑛 𝜃) = 𝑛 𝐻 (𝑃 𝜃)$ である．これを引いて $𝑛$ で割ると，定義 12.1.2 より

Δ 𝑛 (ℓ T 𝑛, 𝜃) < | X | l o g 2 (𝑛 + 1) + 2 𝑛

となり，主張の不等式が従う． $◼$

形式化上の注記. 定理 12.2.4 に対応する宣言は無い．使う道具のうち，命題 11.1.3 の numTypes_le (InformationTheory/Shannon/Sanov/MultinomialLowerBound.lean) と，定理 11.1.8 の上界を与える typeClassByCount_card_le (InformationTheory/Shannon/Sanov/MultinomialLowerBound.lean)，およびその量を $𝑒 𝑛 𝐻 (𝑃)$ に書き換える pow_div_prod_pow_eq_exp_n_entropyByCount (InformationTheory/Shannon/TypeClassLowerBound.lean) は在庫にあるが，そこから符号長の期待値を評価した宣言は無い．

系 12.2.5. 定義 12.1.1 の設定とする．どの $𝑛 \geq 1$ についても

Δ * 𝑛 \leq | X | l o g 2 (𝑛 + 1) + 2 𝑛

である（ $Δ * 𝑛$ は定義 12.1.5 のミニマックス冗長度）．右辺は $Θ$ にも $𝑃 𝜃$ にも依らず， $𝑛 \to \infty$ で $0$ に収束する．さらに，各 $𝑛 \geq 1$ に $ℓ T 𝑛$ （定義 12.2.1）を対応させた列は，この族に対する万能符号である（定義 12.1.6）．

証明. 命題 12.2.2 より $ℓ T 𝑛$ は長さ $𝑛$ の符号長の組だから，定義 12.1.5 の下限をとる範囲に入る．よって $Δ * 𝑛 \leq m a x 𝜃 Δ 𝑛 (ℓ T 𝑛, 𝜃)$ であり， $Θ$ は有限で，どの $𝜃$ でも定理 12.2.4 の評価が成り立つから，最大も同じ値以下である．

右辺が $Θ$ にも $𝑃 𝜃$ にも依らないことは式の形から見てとれる．収束は補題 11.2.2 から出る．本章の底で読むと $l o g 2 (𝑛 + 1) / 𝑛 \to 0$ であり， $| X |$ は $𝑛$ に依らない有限の数だから第 $1$ 項は $0$ に収束する．第 $2$ 項 $2 / 𝑛$ も $0$ に収束する．

最後の主張に移る．いま見たとおり $m a x 𝜃 Δ 𝑛 (ℓ T 𝑛, 𝜃)$ は右辺以下であり，命題 12.1.3 より $0$ 以上である．右辺は $0$ に収束するから，はさみうちにより $m a x 𝜃 Δ 𝑛 (ℓ T 𝑛, 𝜃) \to 0$ であり，定義 12.1.6 の条件が満たされる． $◼$

万能符号があること（定義 12.1.6）は，三つの主張が合わさって出ている．命題 12.2.2 が， $ℓ T 𝑛$ が長さ $𝑛$ の符号長の組であること，すなわちこの長さをもつ二元語頭符号があることを与える．定理 12.2.4 が，その冗長度を族のどの $𝜃$ についても同じ値で抑える．そして系 12.2.5 が，その値が $𝑛 \to \infty$ で $0$ に収束することを述べ，三つを合わせて定義 12.1.6 の条件を確かめている．族をどう与えても $ℓ T 𝑛$ という一つの符号長の組でこれが言え，しかもその上界は族の中身を見ずに書けている．型による二段符号が代償として払っているのは，例 12.1.7 の決めつけのような定数ではない．分布を知っている場合の冗長度は $1 / 𝑛$ 未満（例 12.1.4）だったから，払っているのはその $1 / 𝑛$ に $l o g 2 𝑛$ の因子を掛けたぶんであり， $1$ 文字あたりで見れば $𝑛$ とともに消える量である．

上界が $0$ に向かうのは $𝑛$ が大きいところでの話で，短い系列では逆になる．両端を見ておく．

例 12.2.6（短い系列に当てる）. $X = {0, 1}$ ， $𝑛 = 4$ ， $𝑥 = 0110$ とすると $ℓ T 4 (𝑥) = 8$ である（ $ℓ T 4$ は定義 12.2.1 の符号長）．

証明. 第 $1$ 項は $⌈ 2 l o g 2 5 ⌉$ である． $24 = 16 < 25 = 52 < 32 = 25$ だから $4 < 2 l o g 2 5 < 5$ であり，切り上げは $5$ である．第 $2$ 項に移る．定義 11.1.1 より $𝑥$ の型は $ˆ 𝑃 𝑥 (0) = ˆ 𝑃 𝑥 (1) = 1 / 2$ であり，その型類は $0$ と $1$ がそれぞれ $2$ 回現れる長さ $4$ の二値系列の全体だから，要素数は $1$ の位置の選び方の数 $6$ である（ $0011$ ， $0101$ ， $0110$ ， $1001$ ， $1010$ ， $1100$ の六つ）． $22 = 4 < 6 \leq 8 = 23$ より $⌈ l o g 2 6 ⌉ = 3$ である．合わせて $5 + 3 = 8$ を得る． $◼$

形式化上の注記. 例 12.2.6 は形式化されていない．例 12.2.6 に付した計算が，この主張の保証のすべてである．

同じ $𝑥$ をそのまま書き写せば $4$ ビットで済む（例 12.1.7 の $ℓ' 𝑛$ ）． $𝑛 = 4$ では，型を指すための $5$ ビットが系列そのものより長い．型による二段符号が得をするのは，この固定費 $⌈ | X | l o g 2 (𝑛 + 1) ⌉$ が $𝑛$ に対して小さくなってからで，定理 12.2.4 の右辺が $𝑛$ で割った形をしているのはそのためである．反対の端を見る．

例 12.2.7（二つの偏ったコイン（型による符号））. 例 12.1.7 の族で $𝑛 = 1000$ とすると，系 12.2.5 の右辺は

2 l o g 2 1001 + 2 1000 = 0.02193 \dots

ビットである．

証明. $| X | = 2$ である． $l o g 2 1001 = 9.9672 \dots$ だから，右辺は $(2 \times 9.9672 \dots + 2) / 1000 = 21.934 \dots / 1000$ である． $◼$

形式化上の注記. 例 12.2.7 は形式化されていない．例 12.2.7 に付した計算が，この主張の保証のすべてである．

数を並べると差がはっきりする．同じ族で， $𝜃 = 1$ と決めつけたときの冗長度は $2.535 \dots$ ビット以上であり（例 12.1.7），系列をそのまま書き写したときは $0.531 \dots$ ビットだった．型による二段符号は， $𝑛 = 1000$ でそのどちらより小さい $0.0219 \dots$ ビット以下に収まる．どの $𝜃$ が真かを知らないまま，知っている場合との差を $0.022$ ビットを下回るところまで詰めたことになる．

上からの評価はこれで得られた．残るのは下からで，冗長度をこれ以上小さくできない理由がどこにあるかである．次節はそれを，族の中の分布どうしの隔たりを測る量として取り出す．

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