12.3 ミニマックス冗長度と通信路容量

前節はミニマックス冗長度を上から抑えた．下からはどうか．例 12.1.7 が示しているのは，族の中の二つの分布が互いに離れていると，一方に合わせた符号が他方で大きく損をする，ということだった．族が離れているほど，一つの符号ですべてを賄うのは苦しくなるはずである．その離れ具合は，次のように読み替えれば第6章の道具で測れる．

つながりの見当は次のようにつく． $𝜃$ を送りたいものと見て， $𝜃$ を選ぶと長さ $𝑛$ の系列 $𝑥$ が分布 $𝑃 𝑛 𝜃$ に従って現れる，という仕組みを一つの通信路と読む．入力は $Θ$ の元，出力は $X 𝑛$ の元である．この通信路の容量が大きいということは，出てきた系列から $𝜃$ がよく分かるということ，すなわち族の分布どうしが離れているということである．そして符号を作る側は $𝜃$ を知らないまま一つの分布を信じるしかないので，離れているぶんがそのまま損になる．族の離れ具合を測る量として，第6章の通信路容量がそのまま使えることになる．本節はこの見当を， $Δ * 𝑛 \geq 𝐶 (𝑊 𝑛) / 𝑛$ という形の不等式にする．本節が証明するのはこの下界までである．上下がちょうど一致することを述べる等式は，本節の末で借りるだけで，証明しない．

本節では $Θ$ 上の分布を $𝜋$ と書く．本節の $𝜋$ はつねに $Θ$ の元を引数にとって $𝜋 (𝜃)$ の形で現れるもので，第6章 6.1 節と第9章が二値の情報源のパラメータに使う裸の $𝜋$ とも，第7章以降が円周率に使う裸の $𝜋$ とも別である（本章には円周率も二値のパラメータも現れない）．通信路のほうは $𝑊 𝑛$ と書く．本章の $𝑊$ はつねに添字 $𝑛$ を持ち，第6章の通信路と同じ意味で使う（第5章の倍加率 $𝑊$ とも，第8章 8.5 節の帯域幅 $𝑊$ とも別である）．

パラメータから系列への通信路

定義 12.3.1（パラメータから系列への通信路）. 定義 12.1.1 の設定で $𝑛 \geq 1$ とする．各 $𝜃 \in Θ$ と $𝑥 \in X 𝑛$ に対し

𝑊 𝑛 (𝑥 ∣ 𝜃) : = 𝑃 𝑛 𝜃 ({𝑥})

と定める． $𝑃 𝑛 𝜃$ は $X 𝑛$ 上の分布だから，値は非負で，各 $𝜃$ について $\sum 𝑥 \in X 𝑛 𝑊 𝑛 (𝑥 ∣ 𝜃) = 1$ である．すなわち $𝑊 𝑛$ は，入力アルファベット $Θ$ ，出力アルファベット $X 𝑛$ の通信路（定義 6.1.1）である．その通信路容量を $𝐶 (𝑊 𝑛)$ （定義 6.1.4）と書く．

同じ式を通信路と読むところが，本節の仕掛けのすべてである．第6章では $𝑊 (𝑦 ∣ 𝑥)$ が雑音を表していて，送り手にはどうにもできないものだった．ここでは $𝑊 𝑛 (𝑥 ∣ 𝜃)$ が情報源の族そのものであり，「どの $𝜃$ が真か」という知りたいことが入力，「実際に出てきた系列」が出力である． $Θ$ は空でない有限集合， $X 𝑛$ は有限集合なので，定義 6.1.1 が要求する有限性はどちらも満たされている．

形式化上の注記. $𝜃$ から $X 𝑛$ への通信路そのものを定めた宣言は無い．通信路と容量の側は定義 6.1.1 の形式化 Channel (InformationTheory/Shannon/ChannelCoding/Basic.lean) と定義 6.1.4 の形式化 capacity (InformationTheory/Shannon/ChannelCoding/ShannonTheorem.lean) がそのまま当たる．ただし形式化の capacity は対数を自然対数にとるので単位はナットで，その値は本章がビットで書く $𝐶 (𝑊 𝑛)$ に $l o g e 2$ を掛けたものである．

冗長度を相対エントロピーで書き直す

補題 12.3.2. 定義 12.1.1 の設定で， $𝑛 \geq 1$ ， $ℓ 𝑛$ を長さ $𝑛$ の符号長の組とし， $𝐾 : = \sum 𝑥 \in X 𝑛 2 - ℓ 𝑛 (𝑥)$ と置く．このとき $0 < 𝐾 \leq 1$ であり，

𝑞 𝑛 (𝑥) : = 2 - ℓ 𝑛 (𝑥) 𝐾 (𝑥 \in X 𝑛)

は $X 𝑛$ 上の全点で正の分布である．さらに，どの $𝜃 \in Θ$ についても

𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃) = 𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛) + l o g 2 1 𝐾 \geq 𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛)

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. $X$ は空でないから $X 𝑛$ も空でなく，和の各項は正だから $𝐾 > 0$ である． $ℓ 𝑛$ は符号長の組だから $𝐾 \leq 1$ である． $𝑞 𝑛$ の値は正で総和は $1$ だから， $𝑞 𝑛$ は $X 𝑛$ 上の全点で正の分布である．

$𝜃 \in Θ$ をとる．定義 12.1.2 より

𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃) = \sum 𝑥 𝑃 𝑛 𝜃 ({𝑥}) (ℓ 𝑛 (𝑥) + l o g 2 𝑃 𝑛 𝜃 ({𝑥})) = \sum 𝑥 𝑃 𝑛 𝜃 ({𝑥}) l o g 2 𝑃 𝑛 𝜃 ({𝑥}) 2 - ℓ 𝑛 (𝑥)

である（ $𝑃 𝜃$ は全点で正だから $𝑃 𝑛 𝜃$ も全点で正で，対数の中身はつねに正である）． $2 - ℓ 𝑛 (𝑥) = 𝐾 𝑞 𝑛 (𝑥)$ を入れ， $l o g 2$ の中の積を和に分け， $\sum 𝑥 𝑃 𝑛 𝜃 ({𝑥}) = 1$ を使うと

𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃) = \sum 𝑥 𝑃 𝑛 𝜃 ({𝑥}) l o g 2 𝑃 𝑛 𝜃 ({𝑥}) 𝑞 𝑛 (𝑥) + l o g 2 1 𝐾

となり，第 $1$ 項は 1.6 節の定義そのもので $𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛)$ である． $0 < 𝐾 \leq 1$ より $l o g 2 1 𝐾 \geq 0$ だから，不等式も従う． $◻$

記号を一つ断っておく． $𝑞 𝑛$ はつねに添字 $𝑛$ を持ち， $X 𝑛$ 上の分布を指す（第6章 6.1 節が出力分布に使った裸の $𝑞$ とは別である）．

補題 12.3.2 は定理 4.3.2 の証明と同じ分解である．あちらは差が非負であることだけを結論にしていたが，本節は等式の形で使うので，改めて書いた．読み方も同じで，符号長の組を選ぶことは分布 $𝑞 𝑛$ を信じることに対応し，冗長度は「信じ違いのぶん」と「場所を余らせたぶん」の和になる． $𝜃$ に依存しているのは第 $1$ 項だけであり， $𝑞 𝑛$ は $𝜃$ を知らずに決めなければならない．次の補題は，この一つの $𝑞 𝑛$ が族の全体に対してどれだけの損を強いられるかを，二つに分ける．

ここから $𝜃$ を確率変数として扱う．統計では未知パラメータを定数とみなすが，相互情報量 $𝐼 (𝜃; 𝑋 𝑛)$ は同時分布に対して定まる量なので， $𝜃$ 自身に分布がなければ書けない．1.9 節と同じく， $Θ$ 上に分布 $𝜋$ を一つ与え， $(𝜃, 𝑋 𝑛)$ を同時分布をもつ対として扱う．この確率変数と $Θ$ をわたる添字とを分けるため，補題 12.3.3 と定理 12.3.4 の証明では，和や最大の添字に $𝜃'$ を使い，裸の $𝜃$ はこの確率変数だけを指すことにする．

補題 12.3.3（平均した相対エントロピーの分解）. 定義 12.1.1 の設定で $𝑛 \geq 1$ とする． $𝜋$ を $Θ$ 上の分布， $𝑞 𝑛$ を $X 𝑛$ 上の全点で正の分布とし，

𝑃 𝑛 𝜋 ({𝑥}) : = \sum 𝜃' \in Θ 𝜋 (𝜃') 𝑃 𝑛 𝜃' ({𝑥}) (𝑥 \in X 𝑛)

と置く． $(𝜃, 𝑋 𝑛)$ を， $Θ \times X 𝑛$ の点 $(𝜃', 𝑥)$ に確率 $𝜋 (𝜃') 𝑃 𝑛 𝜃' ({𝑥})$ を与える同時分布に従う対とすると

\sum 𝜃' \in Θ 𝜋 (𝜃') 𝐷 (𝑃 𝑛 𝜃' ∥ 𝑞 𝑛) = 𝐼 (𝜃; 𝑋 𝑛) + 𝐷 (𝑃 𝑛 𝜋 ∥ 𝑞 𝑛)

である（ $𝐼$ は定義 1.3.1 の相互情報量， $𝐷$ は 1.6 節の相対エントロピー）．

証明. $𝜋 (𝜃') = 0$ の項は左辺で $0$ であり，同時分布もその $𝜃'$ の上で $0$ なので定義 1.3.1 の和にも寄与しない．以下 $𝜋 (𝜃') > 0$ の $𝜃'$ だけを見る． $𝑃 𝜃'$ は全点で正だから $𝑃 𝑛 𝜃'$ も全点で正で，したがって $𝑃 𝑛 𝜋$ も全点で正である（ $𝜋$ は少なくとも一点で正である）． $𝑞 𝑛$ も全点で正だから，以下に現れる対数の中身はすべて正である．

各 $𝜃'$ について，対数の中身を二つに分ける．

𝐷 (𝑃 𝑛 𝜃' ∥ 𝑞 𝑛) = \sum 𝑥 𝑃 𝑛 𝜃' ({𝑥}) l o g 2 𝑃 𝑛 𝜃' ({𝑥}) 𝑃 𝑛 𝜋 ({𝑥}) + \sum 𝑥 𝑃 𝑛 𝜃' ({𝑥}) l o g 2 𝑃 𝑛 𝜋 ({𝑥}) 𝑞 𝑛 (𝑥)

である．両辺に $𝜋 (𝜃')$ を掛けて $𝜃'$ について足す．

第 $1$ の和を見る．対 $(𝜃, 𝑋 𝑛)$ の同時分布は点 $(𝜃', 𝑥)$ で $𝜋 (𝜃') 𝑃 𝑛 𝜃' ({𝑥})$ であり，その二つの周辺分布は $𝜋 (𝜃')$ と $𝑃 𝑛 𝜋 ({𝑥})$ である．よって

𝜋 (𝜃') 𝑃 𝑛 𝜃' ({𝑥}) 𝜋 (𝜃') 𝑃 𝑛 𝜋 ({𝑥}) = 𝑃 𝑛 𝜃' ({𝑥}) 𝑃 𝑛 𝜋 ({𝑥})

だから， $\sum 𝜃', 𝑥 𝜋 (𝜃') 𝑃 𝑛 𝜃' ({𝑥}) l o g 2 𝑃 𝑛 𝜃' ({𝑥}) 𝑃 𝑛 𝜋 ({𝑥})$ は定義 1.3.1 の右辺そのもので， $𝐼 (𝜃; 𝑋 𝑛)$ に等しい．

第 $2$ の和を見る．こちらは対数の中身が $𝜃'$ に依らないので， $𝜃'$ について先に足すと

\sum 𝑥 (\sum 𝜃' 𝜋 (𝜃') 𝑃 𝑛 𝜃' ({𝑥})) l o g 2 𝑃 𝑛 𝜋 ({𝑥}) 𝑞 𝑛 (𝑥) = \sum 𝑥 𝑃 𝑛 𝜋 ({𝑥}) l o g 2 𝑃 𝑛 𝜋 ({𝑥}) 𝑞 𝑛 (𝑥)

となり，これは $𝐷 (𝑃 𝑛 𝜋 ‖ 𝑞 𝑛)$ である．二つを足せば主張を得る． $◻$

左辺は，族の各分布に対する損を事前分布 $𝜋$ で平均したものである．それが二つに割れた．第 $2$ 項は，混合 $𝑃 𝑛 𝜋$ と符号が信じる $𝑞 𝑛$ との隔たりで， $𝑞 𝑛$ を $𝑃 𝑛 𝜋$ そのものにとれば定理 1.6.1 の等号条件により $0$ になる．いっぽう第 $1$ 項には $𝑞 𝑛$ が現れない．相対エントロピーは非負だから（定理 1.6.1），左辺は $𝑞 𝑛$ の選び方によらず $𝐼 (𝜃; 𝑋 𝑛)$ 以上である．平均した損の下界が相互情報量として書けたことになる． $𝜋$ を動かしてこれを最大にすれば，第6章の容量が出てくる．

下界

定理 12.3.4（ミニマックス冗長度の下界）. 定義 12.1.1 の設定で $𝑛 \geq 1$ とすると

Δ * 𝑛 \geq 𝐶 (𝑊 𝑛) 𝑛

である（ $Δ * 𝑛$ は定義 12.1.5 のミニマックス冗長度， $𝑊 𝑛$ は定義 12.3.1 の通信路）．

証明. $ℓ 𝑛$ を長さ $𝑛$ の符号長の組とし，補題 12.3.2 の $𝑞 𝑛$ をとる． $𝜋$ を $Θ$ 上の任意の分布とする． $𝜋$ は総和 $1$ の非負の重みだから，加重平均は最大以下であり，続いて補題 12.3.2 の不等式を各 $𝜃'$ に当てると

m a x 𝜃' \in Θ 𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃') \geq \sum 𝜃' 𝜋 (𝜃') 𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃') \geq \sum 𝜃' 𝜋 (𝜃') 𝐷 (𝑃 𝑛 𝜃' ∥ 𝑞 𝑛)

である． $𝑞 𝑛$ は $X 𝑛$ 上の全点で正の分布だから，右辺に補題 12.3.3 を当てると $𝐼 (𝜃; 𝑋 𝑛) + 𝐷 (𝑃 𝑛 𝜋 ‖ 𝑞 𝑛)$ になり，第 $2$ 項は定理 1.6.1 より $0$ 以上だから

m a x 𝜃' \in Θ 𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃') \geq 𝐼 (𝜃; 𝑋 𝑛)

を得る．ここで $(𝜃, 𝑋 𝑛)$ は，点 $(𝜃', 𝑥)$ で $𝜋 (𝜃') 𝑊 𝑛 (𝑥 ∣ 𝜃')$ となる同時分布に従う対だから，命題 6.1.3 を通信路 $𝑊 𝑛$ と入力分布 $𝜋$ に当てて $𝐼 (𝜃; 𝑋 𝑛) = 𝐼 (𝜋; 𝑊 𝑛)$ （定義 6.1.2 の意味）である．

$𝜋$ は任意だったので，定理 6.1.5 を $𝑊 𝑛$ に当て， $𝐼 (\cdot; 𝑊 𝑛)$ を最大にする入力分布 $𝜋 *$ をとる． $𝜋 : = 𝜋 *$ として上の評価を使うと

m a x 𝜃' \in Θ 𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃') \geq 𝐼 (𝜋 *; 𝑊 𝑛) = 𝐶 (𝑊 𝑛)

である．左辺の $ℓ 𝑛$ は長さ $𝑛$ の符号長の組として任意だったから， $𝐶 (𝑊 𝑛)$ は定義 12.1.5 の下限をとる値の集合の下界であり，下限はそれ以上である．すなわち $𝑛 Δ * 𝑛 \geq 𝐶 (𝑊 𝑛)$ であり，両辺を $𝑛$ で割れば主張を得る． $◼$

形式化上の注記. 定理 12.3.4 に対応する宣言は無い．冗長度とミニマックス冗長度そのものが形式化されていないからである．使う部品のうち，容量が最大値として達成されることは exists_capacity_achiever (InformationTheory/Shannon/ChannelCoding/ShannonTheorem.lean) にある．

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

𝐶 (𝑊 𝑛) \leq l o g 2 | Θ |

である（ $𝑊 𝑛$ は定義 12.3.1 の通信路）．したがって定理 12.3.4 の下界 $𝐶 (𝑊 𝑛) / 𝑛$ は $l o g 2 | Θ | / 𝑛$ を超えない．

証明. 定義 12.3.1 より $𝑊 𝑛$ は入力アルファベット $Θ$ ，出力アルファベット $X 𝑛$ の通信路である．命題 6.1.7 をこの通信路に当てると $𝐶 (𝑊 𝑛) \leq l o g 2 m i n (| Θ |, | X 𝑛 |)$ であり， $m i n (| Θ |, | X 𝑛 |) \leq | Θ |$ だから $𝐶 (𝑊 𝑛) \leq l o g 2 | Θ |$ を得る．両辺を $𝑛 > 0$ で割れば後半が従う． $◼$

形式化上の注記. 系 12.3.5 に対応する宣言は無い．引いている命題 6.1.7 も形式化されていない．

系 12.3.5 は，下界そのものの大きさに天井を与えている．族が有限であるかぎり，定理 12.3.4 から読み取れる $1$ 文字あたりの損は多くとも $l o g 2 | Θ | / 𝑛$ で， $𝑛$ に反比例して消える水準である．いっぽう系 12.2.5 の上界は $| X | l o g 2 (𝑛 + 1) / 𝑛$ の水準だった．二つのあいだには $l o g 2 𝑛$ の因子ぶんの隔たりがあり，それが型による符号の緩みなのか下界の緩みなのかは，本節の道具では決まらない．

冗長度–容量定理を借りる. 借りるのは，定義 12.1.1 の設定で

i n f 𝑞 𝑛 m a x 𝜃 \in Θ 𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛) = 𝐶 (𝑊 𝑛)

が成り立つ，という形である（下限は $X 𝑛$ 上の全点で正の分布の全体，最大は $Θ$ の上でとる）．当てる相手は，本章の有限な $Θ$ と有限な $X$ の場合だけである．二つの側に分けて見る．一方の

i n f 𝑞 𝑛 m a x 𝜃 \in Θ 𝐷 (𝑃 𝑛 𝜃 ∥ 𝑞 𝑛) \geq 𝐶 (𝑊 𝑛)

は，定理 12.3.4 の証明がたどった道がそのまま覆っている．その証明で $𝑞 𝑛$ が符号長の組から作られていることを使うのは，補題 12.3.2 を当てる最初の一歩だけで，そこから先の評価は $X 𝑛$ 上の全点で正の分布ならどれでも通るからである．借りるのは反対の

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

のほうだけである．本書はこれを証明しない． $𝜃$ 側の最大と $𝑞 𝑛$ 側の下限の順序を入れ替えるミニマックス定理が要り，本書はそれを用意していないからである．この借用に依存するのは，本節の地の文で定理 12.3.4 の下界の意味を説明するところと，12.4 節が系 12.4.7 のあとで上下の評価を突き合わせるところだけで，本章のどの主張の証明にも使わない．

形式化上の注記. 借りている側，すなわち $i n f 𝑞 𝑛 m a x 𝜃 𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛) \leq 𝐶 (𝑊 𝑛)$ に対応する単独の宣言は無いが，二つの宣言の合成で得られる．容量を達成する入力分布の存在を無条件に与えるのが exists_capacity_achiever (InformationTheory/Shannon/ChannelCoding/ShannonTheorem.lean) で，その入力分布の出力分布が全点で正であるとき，どの入力記号についても出力分布への相対エントロピーが容量以下であることを与えるのが klDiv_channel_le_capacity (InformationTheory/Shannon/ChannelCoding/StrongConverseAsymptotic.lean) である．出力分布を下限の候補にとれば，二つを合わせて借りている側が出る．全点で正であるという仮定は，定義 12.1.1 が族に課した全点正値性から従う．宣言が測る単位はナットだが，底を取り替えると不等式の両辺が同じ正の定数倍で変わるので，向きは変わらない．等式そのものをまとめた宣言と，本章の $𝑊 𝑛$ を通信路として与えた宣言は無い．なお形式化の証明が通る道は容量の鞍点条件で，本文が挙げたミニマックス定理は使わない．

補題 12.3.2 の等式と借りた定理を並べると，下界の意味がはっきりする．補題 12.3.2 は $𝑛 Δ 𝑛 (ℓ 𝑛, 𝜃) = 𝐷 (𝑃 𝑛 𝜃 ‖ 𝑞 𝑛) + l o g 2 1 𝐾$ だったから，場所を余らせない符号長の組（ $𝐾 = 1$ ）に限れば，冗長度の $𝑛$ 倍はちょうど相対エントロピーである．すなわち $𝑛 Δ * 𝑛$ は，借りた定理の左辺を， $𝑞 𝑛$ が符号長の組から作れるものに限って測り，さらに場所を余らせたぶんを足した量である．定理 12.3.4 はその二つの制限を落として得た下界で，借りた定理は，制限を落とした側の値がちょうど $𝐶 (𝑊 𝑛)$ であることを述べている．

例 12.3.6（二つの偏ったコイン（容量））. 例 12.1.7 の族で $𝑛 = 1$ とすると，定義 12.3.1 の通信路 $𝑊 1$ の容量は

𝐶 (𝑊 1) = 1 - 𝐻 𝑏 (0.1) = 0.531 \dots

ビットであり， $Δ * 1 = 0.531 \dots$ ビットである（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．

証明. まず容量を求める．定義 12.3.1 より $𝑊 1 (0 ∣ 1) = 0.1$ ， $𝑊 1 (1 ∣ 1) = 0.9$ ， $𝑊 1 (0 ∣ 2) = 0.9$ ， $𝑊 1 (1 ∣ 2) = 0.1$ である．入力の名前を $1 \mapsto 1$ ， $2 \mapsto 0$ と付け替えると，これは例 6.1.8 の反転確率 $0.1$ の二元対称通信路の遷移確率と一致する．定義 6.1.2 の右辺に現れるのは入力分布の値と遷移確率の値だけで，入力の名前は現れないから，付け替えても $𝐼 (𝑝; 𝑊)$ のとりうる値の集合は変わらず，定義 6.1.4 の上限も変わらない．よって例 6.1.8 より $𝐶 (𝑊 1) = 1 - 𝐻 𝑏 (0.1)$ である．

下からは定理 12.3.4 を $𝑛 = 1$ に当てて $Δ * 1 \geq 𝐶 (𝑊 1)$ である．上からは例 12.1.7 が $Δ * 1 \leq 1 - 𝐻 𝑏 (0.1)$ を与えている．二つを合わせて $Δ * 1 = 1 - 𝐻 𝑏 (0.1)$ であり，例 1.1.2 より $𝐻 𝑏 (0.1) = 0.4689 \dots$ だから，値は $0.5310 \dots$ である． $◼$

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

$𝑛 = 1$ では下界がそのまま達成されている．いっぽう系 12.2.5 の上界は $𝑛 = 1$ で $4$ ビットで，ずいぶん緩い．型を送るための $⌈ | X | l o g 2 (𝑛 + 1) ⌉$ ビットが， $𝑛 = 1$ では $1$ 文字あたり丸ごと $2$ ビットの負担になるからである．上界と下界が近づくのは $𝑛$ が大きいところで，そこでは上界が $| X | l o g 2 (𝑛 + 1) / 𝑛$ の水準まで落ちる．

下界は補題 12.3.2 を通して，符号が信じる分布 $𝑞 𝑛$ と真の分布との相対エントロピーの形で出てきた．上からの評価を同じ形で書ければ，上下が直接比べられる．次節は，符号長の組を型から作るのではなく， $𝑞 𝑛$ を先に決めてそこから作る，という道筋をとり，その冗長度を相対エントロピーで抑える．

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