2.3 情報源符号化定理

前節の終わりに述べた見通しを，定理の形にする．典型集合はおよそ $2 𝑛 𝐻$ 個しか元をもたず（定理 2.2.5），ブロックはほぼ確実にその中に落ちる（定理 2.2.3）．ならば典型系列に通し番号を振り，番号だけを送ればよい．番号を書き下すのに必要なのは1 文字あたり約 $𝐻 (𝑋)$ ビットで，典型集合から外れたときだけ復号に失敗するが，その確率は 0 に向かう．

これで「1 文字あたり $𝐻 (𝑋)$ ビットあれば送れる」までは言える．本節の主題は，その先の「 $𝐻 (𝑋)$ ビットより少なくては送れない」のほうである．前者は符号を一つ作れば済む存在の主張だが，後者はどんな符号を設計してもという全称の主張であり，構成では歯が立たない．ここで第1章のファノの不等式（定理 1.10.1）が唯一の橋になる．二つを合わせると，圧縮率の下限がちょうどエントロピーに一致する．

本節では $X$ は 2 文字以上とする（ファノの不等式がそれを要求する）．前節の記法はそのまま引き継ぐ．

定義

定義 2.3.1（ブロック情報源符号）. 長さ $𝑛$ の ブロック情報源符号 とは，符号語数 $𝑀 𝑛 \geq 1$ と，符号化写像 $𝑐 𝑛 : X 𝑛 \to {1, \dots, 𝑀 𝑛}$ ，復号写像 $𝑑 𝑛 : {1, \dots, 𝑀 𝑛} \to X 𝑛$ の組である．その レート と誤り確率 を

𝑅 𝑛 : = 1 𝑛 l o g 𝑀 𝑛, 𝑃 (𝑛) 𝑒 : = P r [𝑑 𝑛 (𝑐 𝑛 (𝑋 𝑛)) \neq 𝑋 𝑛]

で定める．

レート $𝑅 𝑛$ は「1 文字あたり何ビット使ったか」である．番号 $𝑐 𝑛 (𝑋 𝑛)$ を書き下すのに $l o g 𝑀 𝑛$ ビット要り，それで $𝑛$ 文字を運んでいるから，割り算がそのまま 1 文字あたりの費用になる（正確には整数ビットに切り上げる必要があるが，差は高々 1 ビットで， $𝑛$ で割れば消える）． $𝑀 𝑛$ を小さくすればレートは下がるが，番号の数が足りなくなれば別々の系列を同じ番号に潰さざるをえず，そこで復号に失敗して $𝑃 (𝑛) 𝑒$ が上がる．この二つの綱引きが本節の全体である．

符号は $𝑛$ ごとに 1 個ずつ，族として考える．「レート $𝑅$ の符号」と言うときに意味があるのは， $𝑛$ を大きくしたときのレートの極限であって，特定の $𝑛$ での値ではない．

達成可能性

定理 2.3.2. $𝑅 > 𝐻 (𝑋)$ とする．このときブロック情報源符号の族 $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛) 𝑛 \geq 1$ で，

𝑅 𝑛 ⟶ 𝑅, 𝑃 (𝑛) 𝑒 ⟶ 0

を満たすものが存在する．

証明. $𝜀 : = (𝑅 - 𝐻 (𝑋)) / 2 > 0$ とおき， $𝑀 𝑛 : = ⌈ 2 𝑛 𝑅 ⌉$ とする．

符号を構成する． $𝐻 (𝑋) + 𝜀 < 𝑅$ だから，定理 2.2.5 の上界より

∣ 𝑇 (𝑛) 𝜀 ∣ \leq 2 𝑛 (𝐻 (𝑋) + 𝜀) \leq 2 𝑛 𝑅 \leq 𝑀 𝑛

であり，典型集合から ${1, \dots, 𝑀 𝑛}$ への単射がとれる． $𝑐 𝑛$ を， $𝑇 (𝑛) 𝜀$ の上ではこの単射， $𝑇 (𝑛) 𝜀$ の外では定数 $1$ と定める． $𝑑 𝑛$ は， $𝑐 𝑛$ が典型系列に与えた番号についてはその典型系列を返し，残りの番号については $X 𝑛$ の元を任意に一つ決めて返すものとする．

誤り確率を抑える． $𝑥 \in 𝑇 (𝑛) 𝜀$ なら $𝑐 𝑛$ は単射なので $𝑑 𝑛 (𝑐 𝑛 (𝑥)) = 𝑥$ となり，誤りは起きない．したがって誤りが起きるのは $𝑋 𝑛 \notin 𝑇 (𝑛) 𝜀$ のときに限られ，

𝑃 (𝑛) 𝑒 \leq P r [𝑋 𝑛 \notin 𝑇 (𝑛) 𝜀]

である．右辺は定理 2.2.3 より 0 に収束する．

レートを計算する． $𝑅 > 𝐻 (𝑋) \geq 0$ （命題 1.1.4）だから $2 𝑛 𝑅 \geq 1$ であり，天井関数の定義から $2 𝑛 𝑅 \leq 𝑀 𝑛 < 2 𝑛 𝑅 + 1$ ．両辺の $l o g$ をとって $𝑛$ で割ると

𝑅 \leq 𝑅 𝑛 < 𝑅 + 1 𝑛 l o g (1 + 2 - 𝑛 𝑅)

となる．右端の補正項は $𝑛 \to \infty$ で 0 に収束するので $𝑅 𝑛 \to 𝑅$ ． $◼$

工夫は典型集合の側にある. 圧縮方式そのものは「典型集合に番号を振り，外れたらあきらめる」だけで，工夫らしい工夫はない．効いているのはすべて前節の性質のほうで，要素数の上界（定理 2.2.5）がレートを，確率の収束（定理 2.2.3）が誤り確率を担っている．前節で典型集合を「確率 $\times$ 個数の釣り合いを捉える集合」と述べたが，その釣り合いの二つの側が，ここでちょうどレートと誤り確率に対応している．

数で見る. 例 2.2.2 の偏ったコイン（ $𝐻 (𝑋) \approx 0.469$ ビット）を $𝑛 = 100$ 文字ずつ区切って送るとする．素朴に 1 文字 1 ビットで書けば 100 ビットだが， $𝑅 = 0.5$ をとれば $𝑀 100 = ⌈ 250 ⌉$ 通りの番号で足り，50 ビットで済む．半分である．このとき捨てているのは典型集合の外の系列で，その確率は $𝑛$ とともに 0 に向かう．例 2.2.2 で見た「 $1$ ばかりの系列はいちばん確率が高いのに典型ではない」という系列も，ここでは捨てられる側にいる．それでも全体としてはほぼ確実に復号できる．

形式化: source_coding_achievability (ソース)

逆定理

逆向きの評価には，ブロック全体のエントロピーが必要になる．i.i.d. の場合にそれが1 文字あたりのエントロピーの $𝑛$ 倍になることを，先に確かめておく．

補題 2.3.3. i.i.d. 情報源に対し， $𝑛 \geq 1$ ならば $𝐻 (𝑋 𝑛) = 𝑛 𝐻 (𝑋)$ ．

証明（ $𝑛$ についての数学的帰納法）. 以下，上付きの $𝑋 𝑛$ は先頭 $𝑛$ 文字のブロック，下付きの $𝑋 𝑛$ は次に来る 1 文字である（添字が $0$ 始まりなので， $𝑋 𝑛$ の次の文字がちょうど $𝑋 𝑛$ になる）．

$𝑛 = 1$ のときは両辺とも $𝐻 (𝑋 0) = 𝐻 (𝑋)$ である． $𝑛$ で成り立つとして $𝑛 + 1$ の場合を見る．エントロピーのチェイン則（定理 1.2.3）を $𝑋 𝑛$ と $𝑋 𝑛$ の組に適用すると

𝐻 (𝑋 𝑛 + 1) = 𝐻 (𝑋 𝑛, 𝑋 𝑛) = 𝐻 (𝑋 𝑛) + 𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) .

第 2 項を評価する．独立性より $𝑋 𝑛$ は $𝑋 𝑛$ と独立だから，命題 1.3.2 の等号条件により $𝐼 (𝑋 𝑛; 𝑋 𝑛) = 0$ ．定理 1.3.4 のエントロピー表現 $𝐼 (𝑋 𝑛; 𝑋 𝑛) = 𝐻 (𝑋 𝑛) - 𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛)$ と合わせて $𝐻 (𝑋 𝑛 ∣ 𝑋 𝑛) = 𝐻 (𝑋 𝑛)$ であり，同分布性からこれは $𝐻 (𝑋)$ に等しい．帰納法の仮定 $𝐻 (𝑋 𝑛) = 𝑛 𝐻 (𝑋)$ と足し合わせて $𝐻 (𝑋 𝑛 + 1) = (𝑛 + 1) 𝐻 (𝑋)$ を得る． $◻$

補題 2.3.3 の証明で独立性が効いているのは 1 か所， $𝑋 𝑛$ が先行するブロック全体と独立だという点である． $𝑋 𝑛$ が各 $𝑋 𝑖$ と個別に独立であるだけでは足りない．

形式化: entropy_jointRV_eq_n_smul (ソース)

定理 2.3.4（弱逆定理）. ブロック情報源符号の族 $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛) 𝑛 \geq 1$ が $𝑃 (𝑛) 𝑒 \to 0$ を満たし，かつレートの列 $(𝑅 𝑛)$ が上に有界なら

𝐻 (𝑋) \leq l i m i n f 𝑛 \to \infty 𝑅 𝑛 .

証明. $ˆ 𝑋 𝑛 : = 𝑑 𝑛 (𝑐 𝑛 (𝑋 𝑛))$ とおく．これは $𝑋 𝑛$ の推定値であり， $P r [ˆ 𝑋 𝑛 \neq 𝑋 𝑛] = 𝑃 (𝑛) 𝑒$ である．

ブロックのエントロピーを二つに分ける. 定理 1.3.4 のエントロピー表現を $(𝑋 𝑛, ˆ 𝑋 𝑛)$ に適用すると

𝐻 (𝑋 𝑛) = 𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛) + 𝐻 (𝑋 𝑛 ∣ ˆ 𝑋 𝑛) .

左辺は補題 2.3.3 より $𝑛 𝐻 (𝑋)$ である．右辺の 2 項をそれぞれ上から抑える．

第 1 項：符号語数で抑える. ふたたび定理 1.3.4 より $𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛) = 𝐻 (ˆ 𝑋 𝑛) - 𝐻 (ˆ 𝑋 𝑛 ∣ 𝑋 𝑛) \leq 𝐻 (ˆ 𝑋 𝑛)$ である（条件付きエントロピーは非負量の平均なので非負．定義 1.2.2 と命題 1.1.4）． $ˆ 𝑋 𝑛$ は $𝑑 𝑛$ の値域に属し，高々 $𝑀 𝑛$ 個の値しかとらないから，最大エントロピー上界（定理 1.1.5）より $𝐻 (ˆ 𝑋 𝑛) \leq l o g 𝑀 𝑛$ ．

第 2 項：ファノの不等式で抑える. 定理 1.10.1 は「観測から対象を当てる」という形をしていたが，当てる操作が済んだ対にもそのまま使える．観測そのものを推定値とみなし，復号器として何もしない写像をとればよい．そこで対象を $𝑋 𝑛$ ，観測を $ˆ 𝑋 𝑛$ ，復号器を恒等写像として適用する． $𝑋 𝑛$ のとりうる値は $| X | 𝑛 \geq 2$ 個，誤り確率は $𝑃 (𝑛) 𝑒$ だから

𝐻 (𝑋 𝑛 ∣ ˆ 𝑋 𝑛) \leq 𝐻 𝑏 (𝑃 (𝑛) 𝑒) + 𝑃 (𝑛) 𝑒 l o g (| X | 𝑛 - 1) \leq 𝐻 𝑏 (𝑃 (𝑛) 𝑒) + 𝑃 (𝑛) 𝑒 𝑛 l o g | X | .

三つを合わせると，各 $𝑛$ について

𝑛 𝐻 (𝑋) \leq l o g 𝑀 𝑛 + 𝐻 𝑏 (𝑃 (𝑛) 𝑒) + 𝑃 (𝑛) 𝑒 𝑛 l o g | X |

であり， $𝑛$ で割って

𝐻 (𝑋) \leq 𝑅 𝑛 + 𝐻 𝑏 (𝑃 (𝑛) 𝑒) 𝑛 + 𝑃 (𝑛) 𝑒 l o g | X | ⏟_____⏟_____⏟ = : 𝛿 𝑛 .

仮定 $𝑃 (𝑛) 𝑒 \to 0$ と，定義 1.1.1 で置いた $𝑝 l o g 𝑝 \to 0$ （ $𝑝 ↓ 0$ ）の約束から $𝐻 𝑏 (𝑃 (𝑛) 𝑒) \to 0$ であり， $𝛿 𝑛 \to 0$ ．したがって $𝐻 (𝑋) - 𝛿 𝑛 \leq 𝑅 𝑛$ の両辺で下極限をとれば主張を得る． $◼$

橋の使い方. ファノの不等式は $𝐻 (𝑋 𝑛 ∣ ˆ 𝑋 𝑛)$ を誤り確率で上から抑える形をしているが，ここでの使い道は裏返しである．左辺のブロックのエントロピー $𝑛 𝐻 (𝑋)$ は情報源だけで決まって動かせない．それを「符号語数の項」と「誤り確率の項」の和で上から抑えたのだから，誤り確率の項を 0 に押しつぶすと，残った符号語数の項が $𝑛 𝐻 (𝑋)$ を支えきらなければならなくなる． $𝑃 (𝑛) 𝑒 \to 0$ という仮定が，そのまま $l o g 𝑀 𝑛$ への下からの圧力に変換されている．1.10 節では，この不等式を裏返して誤り確率の下界として使うのが実際の用途だと述べた．ここでの使い方はその変種で， $𝑃 (𝑛) 𝑒$ を下から押すかわりに， $𝑃 (𝑛) 𝑒 \to 0$ を仮定して誤り確率の項を消し，残った符号語数の項に $𝑛 𝐻 (𝑋)$ を支えさせている．どちらも，情報量の言明から確率や符号語数の言明へ渡るという橋の役目は同じである．

$l i m i n f$ である理由. 結論が $l i m$ ではなく $l i m i n f$ なのは，レートが収束するとは仮定していないからである． $𝑅 𝑛$ は振動してよく，主張しているのは「どんな部分列をとっても $𝐻 (𝑋)$ を下回る値に張り付くことはない」ということである．

形式化: 弱逆定理 source_coding_converse，三つの評価を合わせた 1 ブロックごとの不等式source_coding_per_n_bound (ソース)

両側を合わせる

定義 2.3.5（達成レート）. ブロック情報源符号の族 $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛) 𝑛 \geq 1$ が 達成可能 であるとは， $𝑃 (𝑛) 𝑒 \to 0$ であり，かつレートの列 $(𝑅 𝑛)$ が上に有界なことをいう．このとき $l i m i n f 𝑛 𝑅 𝑛$ をその族の 達成レート と呼び，達成レート全体の集合を $R$ と書く．

上に有界という条件は，符号語数が $𝑛$ について指数を超える速さで増える族を除くために置く．実数列の下極限は上に有界でなければ実数として定まらないので，この条件がないと「達成レート」という値そのものが決まらない．除いても失うものはない．そういう族はレートがいくらでも大きいのだから，下限の値には関わらない．実用上の符号（ $𝑀 𝑛$ が $2 𝑛 𝑅$ 程度のもの）ではつねに満たされる．

定理 2.3.6（情報源符号化定理）.

i n f R = 𝐻 (𝑋) .

証明. $𝐻 (𝑋) \leq i n f R$ . 達成可能な族は定義 2.3.5 より $𝑃 (𝑛) 𝑒 \to 0$ とレートの上界の両方を満たすから，定理 2.3.4 よりその達成レートは $𝐻 (𝑋)$ 以上である．すなわち $𝐻 (𝑋)$ は $R$ の下界であり，下限は下界以上だから $𝐻 (𝑋) \leq i n f R$ ．

$i n f R \leq 𝐻 (𝑋)$ . $𝑅 > 𝐻 (𝑋)$ を任意にとる．定理 2.3.2 の族は $𝑅 𝑛 \to 𝑅$ を満たすので，収束列として上に有界であり， $𝑃 (𝑛) 𝑒 \to 0$ も満たす．よって達成可能で，その達成レートは $l i m i n f 𝑛 𝑅 𝑛 = 𝑅$ である．ゆえに $𝑅 \in R$ で，とくに $R$ は空でなく $i n f R \leq 𝑅$ ． $𝑅$ は $𝐻 (𝑋)$ より大きい任意の実数だったから $i n f R \leq 𝐻 (𝑋)$ ．

二つを合わせて等号を得る． $◼$

定理 2.3.6 は，第1章で「平均驚き量」として定義した量が，圧縮という操作上の問いに対する答えでもあることを述べている． $𝐻 (𝑋)$ は分布から決まる数にすぎず，符号の話は一切していなかった．それが，あらゆる符号にわたる下限としてふたたび現れる．エントロピーが情報の量の尺度として正しいという主張の，最初の裏づけがこれである．

なお， $i n f$ が達成されるかどうかは本定理の主張に含まれない． $𝑅 = 𝐻 (𝑋)$ ちょうどのレートで誤り確率が 0 に収束する符号族があるかは，ここでは問わない．

形式化: 達成可能な符号 IsAchievableCode，達成レートの集合 achievableRates，情報源符号化定理source_coding_theorem (ソース)

形式化上の注記. 形式化の達成レートの定義 IsAchievableCode も，誤り確率の消失とレートの一様上界の2 条件を課している．本文が定義 2.3.1 に置いた $𝑀 𝑛 \geq 1$ も，番号の型を空にしないために同じ構造体に取り込まれている．

独立性の仮定は定理ごとに強さが違う．前節の確率収束（定理 2.2.3）と定理 2.1.4 は対独立で足りるが，本節の逆定理は補題 2.3.3 を経由するため，どの有限個をとっても同時に独立という意味の 相互独立（iIndepFun）を要求する．本文の補題 2.3.3 の証明で「 $𝑋 𝑛$ が先行ブロック全体と独立」を使った箇所が，そのまま形式化での仮定の強さの違いになっている．達成可能性 source_coding_achievability の宣言も相互独立を受けているが，こちらは証明の冒頭で対独立に落としているだけで，点ごとの確率評価は経由しない．

弱逆定理の証明ルートは本文と一つずれる．本文は観測を $ˆ 𝑋 𝑛$ （復号結果）にとり，復号器を恒等写像としてファノの不等式を当てた．形式化は観測を符号語 $𝑌 𝑛 = 𝑐 𝑛 (𝑋 𝑛)$ にとり，復号器 $𝑑 𝑛$ とともに $(𝑋 𝑛, 𝑌 𝑛)$ へ当てる．符号語数の項も $𝐻 (ˆ 𝑋 𝑛)$ を経由せず， $𝑌 𝑛$ の値域の大きさから最大エントロピー上界で直接出す．到達する不等式は本文と同じである．誤り確率は測度論的に $𝑃 𝑒 = 𝜇 {𝜔 : 𝑋 𝑛 (𝜔) \neq 𝑑 𝑛 (𝑐 𝑛 (𝑋 𝑛 (𝜔)))}$ として定義され（errorProb），ファノの不等式は第1章と同じ測度論版を用いる．

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