12.4 算術符号

補題 12.3.2 は，符号長の組を一つ決めると $X 𝑛$ 上の分布 $𝑞 𝑛$ が定まり，冗長度がその $𝑞 𝑛$ と真の分布との隔たりで書けることを述べていた．本節は逆をたどる． $X 𝑛$ 上の分布 $𝑞 𝑛$ を先に決め，そこから符号長の組を作って，その冗長度を $𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ で上から抑える． $𝑞 𝑛$ を決めるのに真の分布は要らないから，これは万能符号の作り方の一つになる．得られる評価は，補題 12.3.2 が冗長度を下から抑えたのと同じ相対エントロピーの形をしている．定理 12.3.4 の下界と並べれば，ミニマックス冗長度が上下から挟める．

作り方そのものは定義 4.4.1 の Shannon 符号語長とほとんど同じで， $l o g 2 1 𝑞 𝑛 (𝑥)$ を切り上げ，そこに $1$ ビットを足す．足した $1$ ビットは，符号語を累積分布から作るときに効く．本節が定義と主張として述べるのはこの符号語長のほうで，区間を細分して符号語そのものを作る手続きは，地の文で述べるにとどめる．順序立てるため，まず $1$ 文字ごとの符号として調べ，そのあとでアルファベットを $X 𝑛$ にとる．

1 文字ごとの符号語長

定義 12.4.1（Shannon–Fano–Elias 符号語長）. $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑎 \in X$ で $𝑝 (𝑎) > 0$ を満たすものとする． $ℓ S$ を定義 4.4.1 の Shannon 符号語長（ $𝐷 = 2$ ，分布 $𝑝$ ）として

ℓ F E (𝑎) : = ℓ S (𝑎) + 1 = ⌈ l o g 2 1 𝑝 (𝑎) ⌉ + 1

と定め， $ℓ F E (𝑎)$ を $𝑎$ の Shannon–Fano–Elias 符号語長 と呼ぶ．

$ℓ S$ との違いは $1$ ビットだけで，その $1$ ビットは符号語を次のように作ることを見込んで足してある． $X$ の文字に順序を入れ，各文字までの確率を足し上げた値（累積分布）を目盛りとして並べると，区間 $[0, 1)$ が文字ごとに幅 $𝑝 (𝑎)$ の区間に分かれる．文字 $𝑎$ には，その区間の中点を二進小数に展開し，先頭 $ℓ F E (𝑎)$ 桁で打ち切ったものを割り当てる．打ち切りで落ちる量は $2 - ℓ F E (𝑎)$ 未満であり，4.4 節が既知とした天井関数の性質より $ℓ S (𝑎) \geq l o g 2 1 𝑝 (𝑎)$ だから $2 - ℓ F E (𝑎) \leq 𝑝 (𝑎) / 2$ で，打ち切った値は中点から区間の幅の半分より近いところにあって $𝑎$ の区間から出ない．同じ勘定で，打ち切った値に $2 - ℓ F E (𝑎)$ を足しても $𝑎$ の区間の右端を越えない．打ち切った値を語頭にもつ二進小数は，打ち切った値以上で，それに $2 - ℓ F E (𝑎)$ を足した値より小さいものに限るから，どれも $𝑎$ の区間に落ちる．別の文字の符号語は，二進小数として読むとその文字の区間に落ちていて，文字ごとの区間は互いに交わらないから， $𝑎$ の符号語を語頭にもつことはない．これが語頭条件である． $ℓ S$ 桁で打ち切ると同じ見積もりが $𝑝 (𝑎)$ までしか効かず，区間から出ないことがこの勘定からは出てこない．足した $1$ ビットはその差である．符号語を区間の中の数として扱うこの見方が，算術符号という名前の由来である．12.2 節で述べた方針のとおり，この構成も長さの由来を説明したもので，本節が使う符号の存在は系 12.4.4 が定理 4.2.2 から与える．足した $1$ ビットと引き換えに何が得られるかは，アルファベットを $X 𝑛$ にとったところで見る．

形式化: sfeLength (ソース)

形式化上の注記. 形式化は符号語長の組だけを通していて，累積分布を二進小数に展開して符号語を作る構成は避けてある．上に述べた区間による構成に対応する宣言は無い．

命題 12.4.2. $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑎 \in X$ で $𝑝 (𝑎) > 0$ を満たすものとする． $ℓ F E$ を定義 12.4.1 の Shannon–Fano–Elias 符号語長とすると

\sum 𝑎 \in X 2 - ℓ F E (𝑎) \leq 1

である．

証明. $ℓ F E (𝑎) = ℓ S (𝑎) + 1$ だから $2 - ℓ F E (𝑎) = 12 \cdot 2 - ℓ S (𝑎)$ であり，

\sum 𝑎 \in X 2 - ℓ F E (𝑎) = 12 \sum 𝑎 \in X 2 - ℓ S (𝑎)

となる．右辺の和は，命題 4.4.2 を $X$ ， $𝐷 = 2$ ，分布 $𝑝$ に当てて $1$ 以下だから，全体は $12$ 以下で，とくに $1$ 以下である． $◼$

形式化: sfeLength_kraft_le_one (ソース)

$ℓ F E$ の Kraft 和は，命題 12.4.2 の証明で見たとおり $ℓ S$ のときのちょうど半分である．4.2 節の木の言葉でいえば， $1$ ビット足すことで符号語に使える場所が半分になり，残りは少なくとも半分が空いたまま残る．次の定理は，その代わりに平均符号長がどうなるかを，エントロピーとの比較で述べる．

定理 12.4.3. $X$ を空でない有限アルファベット， $𝑋$ を $X$ 上に分布 $𝑝$ をもつ確率変数で，すべての $𝑎 \in X$ で $𝑝 (𝑎) > 0$ を満たすものとする． $ℓ F E$ を定義 12.4.1 の Shannon–Fano–Elias 符号語長とすると

𝐻 (𝑋) \leq \sum 𝑎 \in X 𝑝 (𝑎) ℓ F E (𝑎) \leq 𝐻 (𝑋) + 2

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

証明. 左側を示す． $ℓ S$ は $0$ 以上の整数値をとるから $ℓ F E$ もそうであり，命題 12.4.2 より $ℓ F E$ は $𝐷 = 2$ について Kraft の不等式を満たす．よって定理 4.3.2 を $X$ ， $𝐷 = 2$ ，確率変数 $𝑋$ に当てて $𝐻 2 (𝑋) \leq \sum 𝑎 𝑝 (𝑎) ℓ F E (𝑎)$ を得る．本章は底を $2$ にとっているので $𝐻 2 (𝑋) = 𝐻 (𝑋)$ である．

右側に移る． $\sum 𝑎 𝑝 (𝑎) = 1$ だから

\sum 𝑎 \in X 𝑝 (𝑎) ℓ F E (𝑎) = \sum 𝑎 \in X 𝑝 (𝑎) ℓ S (𝑎) + 1

である．右辺の和に定理 4.4.4 を同じ設定に当てると $𝐻 2 (𝑋) + 1$ 未満だから，全体は $𝐻 2 (𝑋) + 2$ 未満であり，とくに $𝐻 2 (𝑋) + 2$ 以下である． $◼$

形式化: arithmeticCode_expected_length_bounds (ソース)

幅を定理 4.4.4 と比べておく．あちらは Shannon 符号語長について $𝐻 (𝑋)$ 以上 $𝐻 (𝑋) + 1$ 未満という幅 $1$ の評価だった．定理 12.4.3 の幅は $2$ で， $1$ ビット広い．広がったぶんは定義 12.4.1 で足した $1$ ビットそのもので，定理 12.4.3 の証明が見たとおり，平均符号長は $ℓ S$ のときよりつねにちょうど $1$ ビット大きい． $1$ 文字ごとに符号語を作るかぎり，この $1$ ビットは毎回払うことになる．

系 12.4.4. $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑎 \in X$ で $𝑝 (𝑎) > 0$ を満たすものとする．このとき $X$ 上の二元語頭符号で，各 $𝑎 \in X$ の符号語長が定義 12.4.1 の $ℓ F E (𝑎)$ に等しいものが存在する．

証明. $𝑝 (𝑎) \leq 1$ より $l o g 2 1 𝑝 (𝑎) \geq 0$ だから $ℓ S (𝑎) \geq 0$ であり， $ℓ F E (𝑎) = ℓ S (𝑎) + 1$ は $1$ 以上の整数である．命題 12.4.2 と合わせて，定理 4.2.2 を $X$ ， $𝐷 = 2$ ，長さの組 $ℓ F E$ に当てればよい． $◼$

形式化: arithmeticCode_prefix_free (ソース)

足した $1$ ビットのおかげで符号語長がどれも $1$ 以上になるので，系 4.4.3 が Shannon 符号語長について同じことを述べるのに $X$ が $2$ 文字以上であることを要したのに対し，系 12.4.4 はそれを要さない．

系 12.4.5. $X$ を空でない有限アルファベット， $𝑝$ を $X$ 上の分布ですべての $𝑎 \in X$ で $𝑝 (𝑎) > 0$ を満たすものとする．このとき $X$ 上の一意復号可能な二元符号で，各 $𝑎 \in X$ の符号語長が定義 12.4.1 の $ℓ F E (𝑎)$ に等しいものが存在する．

証明. 系 12.4.4 がその長さの二元語頭符号 $𝑐$ を与える． $𝑝 (𝑎) \leq 1$ より $ℓ S (𝑎) \geq 0$ だから $ℓ F E (𝑎) = ℓ S (𝑎) + 1 \geq 1$ であり，定義 4.1.1 より $𝑐 (𝑎)$ はどの $𝑎$ についても空でない．よって命題 4.1.3 より $𝑐$ は一意復号可能である． $◼$

形式化上の注記. 系 12.4.5 に対応する単独の宣言は無い．その長さの語頭符号が存在することは arithmeticCode_prefix_free，語頭で符号語が空でない写像が一意復号可能であることは arithmeticCode_unique_decodable (InformationTheory/Shannon/ArithmeticCoding.lean) が述べていて，前者が与える符号は符号語長が $ℓ F E$ に等しく，それは $1$ 以上だから後者の仮定を満たす．二つを合わせれば系 12.4.5 が得られる．

読む側に要るのは，符号語をつないだ $1$ 本の列から元の文字の列が一つに定まることであって（4.1 節），読みながらその場で区切れることはそれより強い．12.1 節が長さの組だけを見て済ませられる根拠に挙げたのは，その弱いほうの条件まで許しても長さの組は Kraft の不等式を満たすこと（定理 4.5.1）で，系 12.4.5 はその逆向きにあたり， $ℓ F E$ が弱いほうの条件だけで見ても実現されることを言っている．

系列に当てる

ここまでは $1$ 文字ごとの話だった．定義 12.4.1 はアルファベットを何にとってもよいので， $X 𝑛$ を一つのアルファベットと見て，その上の分布 $𝑞 𝑛$ に当てれば，系列 $𝑥 \in X 𝑛$ の全体に一つの符号語が付く．区間の見方でいえば， $[0, 1)$ を最初の文字で分け，その中をさらに次の文字で分け，と $𝑛$ 回細分して得た区間が $𝑥$ に対応し，その区間を指す二進小数が符号語になる．こうすると定理 12.4.3 の $2$ ビットは系列 $1$ 本あたりの量になり， $1$ 文字あたりに直せば $2 / 𝑛$ である． $1$ 文字ごとに符号語を作れば毎回払っていた $1$ ビットも，系列をまとめれば $1$ 文字あたり $1 / 𝑛$ ビットになる．

区間の見方がここで効く．符号語を得る道は二つある．一つは系 12.4.4 を $X 𝑛$ に当てることで，定理 4.2.2 の証明が与える手続きは，アルファベットの文字を符号語長の順に並べ， $𝑥$ より前にあるものすべての寄与を足し上げて $𝑥$ の符号語を決める．アルファベットが $X 𝑛$ のとき，この並べ上げは $| X | 𝑛$ 本の系列にわたる．もう一つが区間による構成で，こちらは $[0, 1)$ を $𝑛$ 回細分するだけで $𝑥$ の区間を決める．各段で要るのは，そこまでに読んだ文字で条件づけた次の文字の確率だけだから， $𝑞 𝑛$ が $1$ 文字ずつの条件付き確率の積の形で与えられていれば， $𝑥$ を先頭から読みながら区間を狭めていける．各段の目盛りを作るのに足し合わせるのは $X$ の文字についての和で， $𝑛$ 段を通しても $𝑛 | X |$ 個の値で済む．定義 12.4.1 で足した $1$ ビットは，この細分で得た区間の中に符号語を収めるための代金であり， $1$ 文字あたりに直せば上に見た $1 / 𝑛$ である．

形式化上の注記（本節共通）. 定義 12.4.1 と命題 12.4.2・定理 12.4.3・系 12.4.4 は，どれも空でない有限アルファベットについて述べてあり，形式化の側も同じ一般性で書かれているので，アルファベットを $X 𝑛$ にとった場合もその宣言が覆っている．系 12.4.5 の合成に使う二つの宣言も同じ一般性で書かれている．いっぽう区間による構成に対応する宣言は，アルファベットを $X 𝑛$ にとった場合にも無い．

ただし定理 12.4.3 が測っているのは，符号を作るのに使った分布そのもので平均した符号長である．万能符号で問題になるのは真の分布 $𝑃 𝑛 𝜃$ で平均した符号長のほうで， $𝑞 𝑛$ が $𝑃 𝑛 𝜃$ と違うと，二つが一致するとはかぎらない．次の定理は，その食い違いのぶんが相対エントロピー $𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ で抑えられることを述べる．

定理 12.4.6（信じた分布で符号化したときの冗長度）. 定義 12.1.1 の設定で $𝑛 \geq 1$ とし， $𝑞 𝑛$ を $X 𝑛$ 上の分布ですべての $𝑥 \in X 𝑛$ で $𝑞 𝑛 (𝑥) > 0$ を満たすものとする．

ℓ 𝑛 (𝑥) : = ⌈ l o g 2 1 𝑞 𝑛 (𝑥) ⌉ + 1 (𝑥 \in X 𝑛)

と定めると， $ℓ 𝑛$ は定義 12.1.1 の意味で長さ $𝑛$ の符号長の組であり，どの $𝜃 \in Θ$ についても

Δ 𝑛 (ℓ 𝑛, 𝜃) \leq 1 𝑛 𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛) + 2 𝑛

である（ $Δ 𝑛$ は定義 12.1.2 の冗長度， $𝐷$ は 1.6 節の相対エントロピー）．

証明. $X$ は空でないから $X 𝑛$ も空でなく， $𝑞 𝑛$ は全点で正だから， $ℓ 𝑛$ はアルファベット $X 𝑛$ と分布 $𝑞 𝑛$ について定義 12.4.1 が定める Shannon–Fano–Elias 符号語長にほかならない． $𝑞 𝑛 (𝑥) \leq 1$ より $l o g 2 1 𝑞 𝑛 (𝑥) \geq 0$ だから切り上げも $0$ 以上で， $ℓ 𝑛 (𝑥)$ は $0$ 以上の整数である．Kraft の不等式は命題 12.4.2 を $X 𝑛$ と $𝑞 𝑛$ に当てて得られる．よって $ℓ 𝑛$ は長さ $𝑛$ の符号長の組である．

冗長度を評価する．4.4 節が既知とした天井関数の性質 $⌈ 𝑡 ⌉ < 𝑡 + 1$ より

ℓ 𝑛 (𝑥) < l o g 2 1 𝑞 𝑛 (𝑥) + 2

である． $𝜃 \in Θ$ をとり，両辺に $𝑃 𝑛 𝜃 ({𝑥})$ を掛けて $𝑥$ について足すと， $\sum 𝑥 𝑃 𝑛 𝜃 ({𝑥}) = 1$ より

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

となる．両辺から $𝐻 (𝑃 𝑛 𝜃) = - \sum 𝑥 𝑃 𝑛 𝜃 ({𝑥}) l o g 2 𝑃 𝑛 𝜃 ({𝑥})$ を引き，右辺の二つの和をまとめる． $𝑃 𝜃$ は全点で正だから $𝑃 𝑛 𝜃$ も全点で正であり， $𝑞 𝑛$ も全点で正だから，対数の中身はつねに正で

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

である．右辺の和は 1.6 節の定義そのもので $𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ に等しい．両辺を $𝑛$ で割ると，定義 12.1.2 より左辺は $Δ 𝑛 (ℓ 𝑛, 𝜃)$ であり，主張の不等式が従う． $◼$

形式化上の注記. 定理 12.4.6 に対応する単独の宣言は無い． $ℓ 𝑛$ が長さ $𝑛$ の符号長の組であるという前半は，sfeLength_kraft_le_one (InformationTheory/Shannon/ArithmeticCoding.lean) をアルファベット $X 𝑛$ と分布 $𝑞 𝑛$ に当てたものである．後半の冗長度の評価に対応する宣言は無い．expectedLength_shannon_lt_entropyD_add_one は符号長を作る分布と平均をとる分布が同じ場合の上界であり，entropyD_le_expectedLength_of_kraft (InformationTheory/Shannon/ShannonCode/Basic.lean) は任意の長さの組についての下界で，どちらも結論に相対エントロピーを含まないからである．

定理 12.4.6 は補題 12.3.2 の裏返しである．補題 12.3.2 は符号長の組から分布を作り，冗長度を下から $1 𝑛 𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ で抑えた．定理 12.4.6 は分布から符号長の組を作り，冗長度を上から $1 𝑛 𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛) + 2 𝑛$ で抑える．行き来する向きが逆で，上乗せの $2 𝑛$ は，切り上げの $1$ ビットと定義 12.4.1 で足した $1$ ビットを $𝑛$ で割ったものである．

系 12.4.7. 定義 12.1.1 の設定で $𝑛 \geq 1$ とすると

𝐶 (𝑊 𝑛) 𝑛 \leq Δ * 𝑛 \leq 1 𝑛 i n f 𝑞 𝑛 m a x 𝜃 \in Θ 𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛) + 2 𝑛

である．下限は $X 𝑛$ 上の全点で正の分布の全体，最大は有限集合 $Θ$ の上でとる（ $Δ * 𝑛$ は定義 12.1.5 のミニマックス冗長度， $𝑊 𝑛$ は定義 12.3.1 の通信路）．

証明. 左側は定理 12.3.4 そのものである．

右側を示す． $𝑞 𝑛$ を $X 𝑛$ 上の全点で正の分布とし，定理 12.4.6 の符号長の組 $ℓ 𝑛$ をとる． $ℓ 𝑛$ は長さ $𝑛$ の符号長の組だから定義 12.1.5 の下限をとる範囲に入り， $Θ$ は有限だから

Δ * 𝑛 \leq m a x 𝜃 \in Θ Δ 𝑛 (ℓ 𝑛, 𝜃) \leq 1 𝑛 m a x 𝜃 \in Θ 𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛) + 2 𝑛

である（第 $2$ の不等号は，定理 12.4.6 の評価を各 $𝜃$ に当てて最大をとったものである）．すなわち，どの $𝑞 𝑛$ についても $𝑛 (Δ * 𝑛 - 2 𝑛) \leq m a x 𝜃 𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ が成り立つ．

下限に移る．右辺の値の集合は空でなく（ $X 𝑛$ 上の一様分布が一つの元を与える），定理 1.6.1 より各元は $0$ 以上だから下に有界であり，下限は実数として定まる．左辺は $𝑞 𝑛$ に依らない定数で，その集合の下界だから，下限はそれ以上である．よって $𝑛 (Δ * 𝑛 - 2 𝑛) \leq i n f 𝑞 𝑛 m a x 𝜃 𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ であり，移項して $𝑛$ で割れば主張を得る． $◼$

上下の差は， $i n f 𝑞 𝑛 m a x 𝜃 𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ と $𝐶 (𝑊 𝑛)$ の差に $2$ を足して $𝑛$ で割ったものである． $2$ のほうは定義 12.4.1 で足した $1$ ビットと切り上げの $1$ ビットから来ていて， $𝑛$ で割れば $𝑛$ を大きくとるにつれて消える．残るのは前の二つの量の差で，どちらも族の分布どうしの離れ具合を測っている．前者は $X 𝑛$ 上の分布を一つ選んで族の全体を代表させたときの最悪の隔たりであり，後者は定理 12.3.4 の証明がその隔たりから取り出した量である．12.3 節で借りた冗長度–容量定理を認めれば，この二つの量は一致する．そのとき系 12.4.7 の左右の端はどちらも $𝐶 (𝑊 𝑛) / 𝑛$ から $2 / 𝑛$ 以内にあり，ミニマックス冗長度は通信路容量で上下から挟まれる．

残るのは $𝑞 𝑛$ をどう選ぶかである．真の $𝜃$ が分からない以上，族のどれか一つを選ぶわけにはいかない．次の例は，族の分布を等しい重みで混ぜたものを $𝑞 𝑛$ にとる．これは補題 12.3.3 の混合 $𝑃 𝑛 𝜋$ を， $𝜋$ が $Θ$ 上の一様分布である場合にとったものにあたる．

例 12.4.8（二つの偏ったコインの混合で作った分布）. 例 12.1.7 の族（ $X = {0, 1}$ ， $Θ = {1, 2}$ ）で $𝑛 \geq 1$ とし，

𝑞 𝑛 (𝑥) : = 12 (𝑃 𝑛 1 ({𝑥}) + 𝑃 𝑛 2 ({𝑥})) (𝑥 \in X 𝑛)

とおく． $𝑞 𝑛$ は $X 𝑛$ 上の全点で正の分布であり， $ℓ 𝑛$ を定理 12.4.6 が $𝑞 𝑛$ から定める符号長の組とすると，どちらの $𝜃 \in Θ$ についても

𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛) \leq 1, Δ 𝑛 (ℓ 𝑛, 𝜃) \leq 3 𝑛

である（どちらもビットで測った値である）．この上界 $3 / 𝑛$ は，どの $𝑛 \geq 1$ でも定理 12.2.4 が同じ族に与える上界より小さく， $𝑛 = 1000$ では $0.003$ ビットである．

証明. $𝑃 𝑛 1$ と $𝑃 𝑛 2$ は $X 𝑛$ 上の全点で正の分布だから， $𝑞 𝑛$ の値は正で，総和は $12 (1 + 1) = 1$ である．よって $𝑞 𝑛$ は $X 𝑛$ 上の全点で正の分布であり，定理 12.4.6 が当たる．

相対エントロピーを抑える． $𝜃 \in Θ$ をとると， $𝑞 𝑛$ の定義の右辺には $12 𝑃 𝑛 𝜃 ({𝑥})$ の項が含まれ，もう一方の項は非負だから $𝑞 𝑛 (𝑥) \geq 12 𝑃 𝑛 𝜃 ({𝑥})$ である．したがって $𝑃 𝑛 𝜃 ({𝑥}) 𝑞 𝑛 (𝑥) \leq 2$ であり，両辺の対数をとって $l o g 2 𝑃 𝑛 𝜃 ({𝑥}) 𝑞 𝑛 (𝑥) \leq 1$ を得る．重み $𝑃 𝑛 𝜃 ({𝑥})$ は非負で総和が $1$ だから，1.6 節の定義より $𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛) \leq 1$ である．これを定理 12.4.6 に入れると $Δ 𝑛 (ℓ 𝑛, 𝜃) \leq 1 𝑛 + 2 𝑛 = 3 𝑛$ となる．

上界どうしを比べる．この族では $| X | = 2$ だから，定理 12.2.4 の右辺は $(2 l o g 2 (𝑛 + 1) + 2) / 𝑛$ である． $𝑛 \geq 1$ より $𝑛 + 1 \geq 2$ で $l o g 2 (𝑛 + 1) \geq 1$ だから，分子は $4$ 以上であり， $3$ より真に大きい．よって $3 / 𝑛$ のほうが小さい．最後に $𝑛 = 1000$ では $3 / 1000 = 0.003$ である． $◼$

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

同じ作り方は，族が二つでなくてもそのまま通る． $Θ$ の元をすべて等しい重みで混ぜればよい．

系 12.4.9. 定義 12.1.1 の設定で $𝑛 \geq 1$ とし，

𝑞 𝑛 (𝑥) : = 1 | Θ | \sum 𝜃 \in Θ 𝑃 𝑛 𝜃 ({𝑥}) (𝑥 \in X 𝑛)

とおく． $ℓ 𝑛$ を定理 12.4.6 が $𝑞 𝑛$ から定める符号長の組とすると，どの $𝜃 \in Θ$ についても

Δ 𝑛 (ℓ 𝑛, 𝜃) \leq l o g 2 | Θ | + 2 𝑛

であり，したがって $Δ * 𝑛 \leq (l o g 2 | Θ | + 2) / 𝑛$ である．さらに，各 $𝑛 \geq 1$ にこの $ℓ 𝑛$ を対応させた列は，族 ${𝑃 𝜃} 𝜃 \in Θ$ に対する万能符号である（定義 12.1.6）．

証明. $Θ$ は空でない有限集合で，各 $𝑃 𝑛 𝜃$ は $X 𝑛$ 上の全点で正の分布だから， $𝑞 𝑛$ の値は正で，総和は $1 | Θ | | Θ | = 1$ である．よって $𝑞 𝑛$ は $X 𝑛$ 上の全点で正の分布であり，定理 12.4.6 が当たる．

相対エントロピーを抑える． $𝜃 \in Θ$ をとると， $𝑞 𝑛$ の定義の右辺には $1 | Θ | 𝑃 𝑛 𝜃 ({𝑥})$ の項が含まれ，残りの項は非負だから $𝑞 𝑛 (𝑥) \geq 1 | Θ | 𝑃 𝑛 𝜃 ({𝑥})$ である．したがって $𝑃 𝑛 𝜃 ({𝑥}) 𝑞 𝑛 (𝑥) \leq | Θ |$ であり，両辺の対数をとって $l o g 2 𝑃 𝑛 𝜃 ({𝑥}) 𝑞 𝑛 (𝑥) \leq l o g 2 | Θ |$ を得る．重み $𝑃 𝑛 𝜃 ({𝑥})$ は非負で総和が $1$ だから，1.6 節の定義より $𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛) \leq l o g 2 | Θ |$ である．これを定理 12.4.6 に入れると，主張の第 $1$ の不等式を得る．

$ℓ 𝑛$ は長さ $𝑛$ の符号長の組だから定義 12.1.5 の下限をとる範囲に入り， $Θ$ は有限だから $Δ * 𝑛 \leq m a x 𝜃 Δ 𝑛 (ℓ 𝑛, 𝜃)$ であり，右辺はいま示した値以下である．

最後の主張に移る． $| Θ |$ は $𝑛$ に依らない有限の数だから $(l o g 2 | Θ | + 2) / 𝑛 \to 0$ であり，命題 12.1.3 より $m a x 𝜃 Δ 𝑛 (ℓ 𝑛, 𝜃) \geq 0$ である．はさみうちにより $m a x 𝜃 Δ 𝑛 (ℓ 𝑛, 𝜃) \to 0$ となり，定義 12.1.6 の条件が満たされる． $◼$

形式化上の注記. 系 12.4.9 に対応する宣言は無い．定理 12.4.6 と同じ理由で，冗長度そのものが形式化されていないからである．

$| Θ | = 2$ ととれば例 12.4.8 の $3 / 𝑛$ が戻る．系 12.4.9 の右辺は族の中身によらず $| Θ |$ だけで書けていて， $𝑛$ に反比例して $0$ に向かう．系 12.2.5 が型による符号に与えた上界 $(| X | l o g 2 (𝑛 + 1) + 2) / 𝑛$ と比べると，族を固定して $𝑛$ を大きくしていったときに $l o g 2 𝑛$ の因子ぶん小さい（族の大きさが $𝑛$ に比べて大きいところでは逆になる． $| X | = 2$ ， $| Θ | = 21000$ ， $𝑛 = 10$ なら，系 12.4.9 の右辺は $100.2$ で，系 12.2.5 の右辺の $0.891 \dots$ より大きい）．12.3 節は，この因子ぶんの隔たりが型による符号の緩みなのか下界の緩みなのかは決まらない，と書いた．本節の評価を足すと決まる．下界は系 12.3.5 より $l o g 2 | Θ | / 𝑛$ を超えず，ミニマックス冗長度そのものも系 12.4.9 より $(l o g 2 | Θ | + 2) / 𝑛$ を超えないから，隔たりは上界の側にある．有限の族に対しては，族を見て混合を作れば $1$ 文字あたりの損が $1 / 𝑛$ の水準まで下がるのだから，系 12.2.5 の上界にある $l o g 2 𝑛$ の因子は，族の中身を見ないことの代金である．いっぽう $l o g 2 | Θ |$ という量は $Θ$ が有限であることに頼っていて，12.1 節が本章では扱わないと断った，偏りが連続に動く族には当てられない．型による符号の上界のほうは族の大きさを見ずに書けているので， $Θ$ がどれだけ大きくても同じ式のままである．

この $𝑞 𝑛$ を作るには族の分布がすべて要る．知らないのは $𝜃$ だけで族そのものは分かっている，という定義 12.1.1 の枠組みには収まっている．この $𝑞 𝑛$ は $1$ 文字ずつの積の形をしていないが，区間による構成に要る条件付き確率は $1$ 文字ずつ出せる．そこまでに読んだ列で条件づけた次の文字の確率は，族の各分布がその文字に与える確率を，そこまでの列に族の各分布が与える値に比例する重みで平均したものだから， $| Θ |$ 個の重みを $1$ 文字ごとに更新していけばよく，族の側から要るのは，各 $𝜃$ と各文字についての $𝑃 𝜃$ の値，すなわち $| Θ | | X |$ 個の値だけである．

ここまでに作った符号は，型によるものも混合によるものも，定義 12.1.1 の枠組みの中で測ってきた．そこに現れる $𝑃 𝑛 𝜃$ は $1$ 文字ずつの積だから，前に出た文字が次の文字の出方に効く情報源は，族の中に初めから入っていない．第3章が扱った定常情報源には，そういう記憶のあるものが入っていて，そこで $1$ 文字あたりの不確かさを測るのはエントロピーではなくエントロピーレートだった（定義 3.2.1）．記憶のある情報源に対して，しかも族を用意せずに， $1$ 文字あたりの符号長をエントロピーレートまで下げる符号はあるだろうか．次節は定義 12.1.1 の枠組みそのものを離れ，分布を持ち出さずに符号を作る方法に移る．

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