9.5 逆定理

9.4 節までで，レート歪み関数 $𝑅 (𝐷)$ の値は二つの具体例について決まった．けれどもそれはまだ最適化問題の値であって，そこに符号についての意味を与えるのが本節と 9.6 節である．本節はまず，情報源を圧縮して再現するとはどういう操作かを符号として定義し，そのうえで，期待歪みを $𝐷$ 以下に抑える符号のレートが $𝑅 (𝐷)$ を下回れないことを示す．ここで初めて $𝑅 (𝐷)$ に，符号についての限界という操作的な意味が付きはじめる．

置く符号は，第2章定義 2.3.1 のブロック情報源符号を，歪みを許す形に緩めたものになる．第6章定義 6.2.1 のブロック通信路符号ではなくこちらに近いのは，動かす相手が違うからである．第6章の符号は，こちらが選んだメッセージを符号語に変えて通信路へ送り，出てきたものからメッセージを当てる．第2章の符号は，向こうから来た列を番号に潰し，番号から列を作り直す．本節の符号もこの後者の形で，第2章と違うのは，作り直す先が情報源アルファベットではなく再現アルファベットであることと，要求が「一致する」ではなく「歪みが $𝐷$ 以下」であることの二つだけである．

論証の形も第2章定理 2.3.4 に近いが，一つ落ちる道具がある．ファノの不等式を使わない．第2章の逆定理は，復号に失敗する確率という一つの数を，ファノの不等式で情報量の言葉に翻訳する必要があった．本節では歪みという量が最初から $𝑅 (𝐷)$ の定義（定義 9.1.5）の中に書き込まれているので，その翻訳が要らない．そのぶん結論の形も変わり， $𝑛$ を大きくする極限をとらずに，各 $𝑛$ の符号一つ一つについて不等式が成り立つ．

歪みを許す符号

定義 9.5.1（レート歪み符号）. $X$ と $ˆ X$ を空でない有限集合， $𝑛 \geq 1$ ， $𝑀 \geq 1$ とする．長さ $𝑛$ ，符号語数 $𝑀$ の レート歪み符号 とは，符号化写像 $𝑐 : X 𝑛 \to {1, \dots, 𝑀}$ と復号写像 $𝑔 : {1, \dots, 𝑀} \to ˆ X 𝑛$ の組 $(𝑐, 𝑔)$ のことをいう．その レート を

1 𝑛 l o g 𝑀

で定める．さらに $𝑑$ を歪み尺度（定義 9.1.1）， $𝑋 𝑛$ を $X 𝑛$ に値をとる確率変数の組とするとき，この符号の $𝑋 𝑛$ に対する 期待歪み を

𝔼 [𝑑 (𝑋 𝑛, 𝑔 (𝑐 (𝑋 𝑛)))]

で定める（ $𝑑 (𝑥 𝑛, ˆ 𝑥 𝑛)$ は定義 9.1.2 のブロックの歪みである）．

符号化写像は長さ $𝑛$ のブロックを $𝑀$ 個の番号のどれかに潰し，復号写像はその番号から再現の列を作る．レートの読み方は第2章定義 2.3.1 と同じで，番号を書き下すのに要る $l o g 𝑀$ ビットを $𝑛$ 文字で割った， $1$ 文字あたりの取り分である．期待歪みは，情報源のブロックと，それが番号を経て戻ってきた再現のブロックとのあいだの歪みを平均した値である．定義 9.1.2 のブロックの歪みが成分についての平均だったから，この量も $1$ 文字あたりの歪みになっている．符号化写像も復号写像も確率を使わない．同じブロックには同じ番号が付き，同じ番号からは同じ再現の列が出る．

形式化: LossyCode，期待歪み expectedBlockDistortion (ソース)

形式化上の注記. 形式化の LossyCode は符号化写像と復号写像の組で，定義 9.5.1 と同じ形をしている．レートにあたる宣言は無い．第2章定義 2.3.5 に紐付けた達成可能な符号 IsAchievableCode と達成レートの集合 achievableRates (InformationTheory/Shannon/AEP/Basic/Achievability.lean) にあたるものも，歪みを許す側には用意されていない．符号語数の対数を長さで割った量が，そのまま不等式の右辺に書かれる形になっている．期待歪みの expectedBlockDistortion のほうは，情報源の分布を一つ受け取って，その独立な複製の積測度で積分する形をしている．定義 9.5.1 が一般の $𝑋 𝑛$ に対して期待歪みを定めたのに対し，あちらが覆うのは成分が互いに独立で同じ分布に従う場合だけである．

ブロックを成分に分ける

定理 9.5.4 の証明は，ブロックについての量を成分についての量の和に落とすところで進む．落とし方を先に二つ切り出しておく．一つは相互情報量についてのもので，情報源の成分が互いに独立であることだけを使う．

補題 9.5.2（相互情報量の優加法性）. $X$ と $ˆ X$ を空でない有限集合， $𝑛 \geq 1$ とする． $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ を $X$ に値をとる互いに独立な確率変数の組， $ˆ 𝑋 𝑛 = (ˆ 𝑋 0, \dots, ˆ 𝑋 𝑛 - 1)$ を $ˆ X$ に値をとる確率変数の組とすると

𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; ˆ 𝑋 𝑖) \leq 𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛)

である．

証明. $𝑋 < 𝑖 : = (𝑋 0, \dots, 𝑋 𝑖 - 1)$ と書く．以下， $𝑖 = 0$ については条件にとる組が空であると読み，条件付きの量を無条件の量と読む（定理 1.5.2 の右辺の第 $0$ 項も同じ読み方である）．

まず全体を成分ごとの増分に分ける．定理 1.5.2 を，変数列 $𝑋 0, \dots, 𝑋 𝑛 - 1$ と，相手側の変数を $ˆ 𝑋 𝑛$ として当てると

𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛) = 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; ˆ 𝑋 𝑛 ∣ 𝑋 < 𝑖)

である．

各項を下から抑える． $𝑖$ を一つ固定する．定理 1.4.3 を，条件を $𝑋 < 𝑖$ ，相手を $ˆ 𝑋 𝑛$ ととって当てると

𝐼 (𝑋 𝑖; ˆ 𝑋 𝑛 ∣ 𝑋 < 𝑖) = 𝐻 (𝑋 𝑖 ∣ 𝑋 < 𝑖) - 𝐻 (𝑋 𝑖 ∣ 𝑋 < 𝑖, ˆ 𝑋 𝑛)

である．第 $1$ 項は $𝐻 (𝑋 𝑖)$ に等しい．実際， $𝑋 0, \dots, 𝑋 𝑛 - 1$ は互いに独立だから $𝑋 𝑖$ と $𝑋 < 𝑖$ は独立であり，命題 1.3.2 の等号条件より $𝐼 (𝑋 𝑖; 𝑋 < 𝑖) = 0$ ，これと定理 1.3.4 のエントロピー表現を合わせると $𝐻 (𝑋 𝑖 ∣ 𝑋 < 𝑖) = 𝐻 (𝑋 𝑖)$ となる．

第 $2$ 項を上から抑える．条件を減らしてもエントロピーは減らない（定理 1.2.4）から，条件 $(𝑋 < 𝑖, ˆ 𝑋 𝑛)$ のうち $ˆ 𝑋 𝑖$ だけを残して

𝐻 (𝑋 𝑖 ∣ 𝑋 < 𝑖, ˆ 𝑋 𝑛) \leq 𝐻 (𝑋 𝑖 ∣ ˆ 𝑋 𝑖)

である．定理 1.2.4 を当てる形にするには，条件を $ˆ 𝑋 𝑖$ とそれ以外に分けておけばよい．条件にとる組の成分を並べ替えても，条件の各値のもとでの $𝑋 𝑖$ の条件付き分布は変わらないから，定義 1.2.2 の値も変わらない．そこで $ˆ 𝑋 𝑖$ を先頭に，残りの成分を後ろに並べ替えたうえで， $𝑌 \leftarrow ˆ 𝑋 𝑖$ ， $𝑍 \leftarrow$ 残りの成分を並べた組ととればよい（ $𝑛 = 1$ で残りの成分が無いときは， $𝑍$ を自明な定数にとれば両辺が一致する）．二つを合わせると，ふたたび定理 1.3.4 より

𝐼 (𝑋 𝑖; ˆ 𝑋 𝑛 ∣ 𝑋 < 𝑖) \geq 𝐻 (𝑋 𝑖) - 𝐻 (𝑋 𝑖 ∣ ˆ 𝑋 𝑖) = 𝐼 (𝑋 𝑖; ˆ 𝑋 𝑖)

を得る． $𝑖$ について足し合わせれば主張が従う． $◻$

補題 9.5.2 が言っているのは，ブロックとして見たときの結びつきは，成分ごとに見たときの結びつきの和より弱くならない，ということである．独立性はちょうど一か所， $𝐻 (𝑋 𝑖 ∣ 𝑋 < 𝑖) = 𝐻 (𝑋 𝑖)$ の段で効いている．情報源の成分に相関があれば，先行する成分を知るだけで $𝑋 𝑖$ の不確かさが減るので，この等号が崩れて証明は通らなくなる．結論のほうも落ちる． $𝑛 = 2$ で $𝑋 0$ と $𝑋 1$ がつねに等しく， $ˆ 𝑋 0 = ˆ 𝑋 1 = 𝑋 0$ ととると，左辺は $2 𝐻 (𝑋 0)$ ，右辺は $𝐻 (𝑋 0)$ になり， $𝐻 (𝑋 0) > 0$ なら不等号の向きが逆になるからである．

形式化: mutualInfo_superadditive_of_indep (ソース)

もう一つは，成分ごとの歪みの平均にレート歪み関数を当てる段である．命題 9.2.3 の凸性は $2$ 点についてのものなので， $𝑛$ 点の形にしておく．

補題 9.5.3（レート歪み関数の $𝑛$ 点凸性）. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする． $𝑛 \geq 1$ とし，実数 $𝐷 0, \dots, 𝐷 𝑛 - 1$ について $Q (𝐷 0), \dots, Q (𝐷 𝑛 - 1)$ がどれも空でないとする．このとき $¯ 𝐷 : = 1 𝑛 \sum 𝑛 - 1 𝑖 = 0 𝐷 𝑖$ について $Q (¯ 𝐷)$ は空でなく

𝑅 (¯ 𝐷) \leq 1 𝑛 𝑛 - 1 \sum 𝑖 = 0 𝑅 (𝐷 𝑖)

である．

証明. $Q (𝐷)$ が空でない実数 $𝐷$ の全体を $I$ と書く． $I$ が区間であることを見る． $𝑠 \in I$ と $𝑠 \leq 𝑡$ ならば，命題 9.2.1 より $Q (𝑡)$ も空でないから $𝑡 \in I$ である．よって $I$ は，二つの元をとればそのあいだの実数をすべて含む集合，すなわち区間である．

$¯ 𝐷 \in I$ であることを見る． $𝐷 0, \dots, 𝐷 𝑛 - 1$ の最小値を $𝐷 m i n$ と書くと，平均は最小値以上だから $𝐷 m i n \leq ¯ 𝐷$ である． $𝐷 m i n \in I$ だから，いま見たことより $¯ 𝐷 \in I$ であり，とくに $Q (¯ 𝐷)$ は空でない．

$- 𝑅 (\cdot)$ が $I$ の上で凹であることを見る． $I$ の二つの元 $𝑎$ ， $𝑏$ と $𝜆 \in [0, 1]$ をとると， $Q (𝑎)$ と $Q (𝑏)$ はどちらも空でないから命題 9.2.3 が当たり， $𝑅 (𝜆 𝑎 + (1 - 𝜆) 𝑏) \leq 𝜆 𝑅 (𝑎) + (1 - 𝜆) 𝑅 (𝑏)$ である．両辺の符号を変えれば，これは $- 𝑅 (\cdot)$ についての凹性の $2$ 点形にほかならない．

そこで補題 1.1.9 を，区間 $I$ 上の凹関数 $- 𝑅 (\cdot)$ ，点 $𝐷 0, \dots, 𝐷 𝑛 - 1 \in I$ ，重みをどれも $1 / 𝑛$ ととって当てると

1 𝑛 𝑛 - 1 \sum 𝑖 = 0 (- 𝑅 (𝐷 𝑖)) \leq - 𝑅 (¯ 𝐷)

である．両辺の符号を変えて主張を得る． $◻$

形式化上の注記. 補題 9.5.3 にあたる内容は，定理 9.5.4 の形式化の中で証明の一段として作られているが，外から引ける宣言にはなっていない．

逆定理

定理 9.5.4（レート歪み符号の逆定理）. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする． $𝑛 \geq 1$ ， $𝑀 \geq 1$ とし， $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ を，どの成分も分布 $𝑝$ に従い互いに独立な $X$ に値をとる確率変数の組とする．長さ $𝑛$ ，符号語数 $𝑀$ のレート歪み符号（定義 9.5.1）の $𝑋 𝑛$ に対する期待歪みが実数 $𝐷$ 以下ならば， $Q (𝐷)$ は空でなく

1 𝑛 l o g 𝑀 \geq 𝑅 (𝐷)

である．

証明. 符号を $(𝑐, 𝑔)$ と書き， $ˆ 𝑋 𝑛 : = 𝑔 (𝑐 (𝑋 𝑛))$ とおく．その第 $𝑖$ 成分を $ˆ 𝑋 𝑖$ とし， $𝐷 𝑖 : = 𝔼 [𝑑 (𝑋 𝑖, ˆ 𝑋 𝑖)]$ とおく．

期待歪みは成分ごとの歪みの平均である. 定義 9.1.2 より $𝑑 (𝑋 𝑛, ˆ 𝑋 𝑛) = 1 𝑛 \sum 𝑖 𝑑 (𝑋 𝑖, ˆ 𝑋 𝑖)$ だから，期待値の線形性により，定義 9.5.1 の期待歪みは $1 𝑛 \sum 𝑖 𝐷 𝑖$ に等しい．仮定よりこれは $𝐷$ 以下である．

各成分は制約集合の元を与える. $𝑖$ を一つ固定する． $ˆ X$ は空でないので，その元を一つ選んで $ˆ 𝑥 0$ と書く． $𝑝 (𝑥) > 0$ である $𝑥$ については $𝑞 𝑖 (ˆ 𝑥 ∣ 𝑥) : = P r [ˆ 𝑋 𝑖 = ˆ 𝑥 ∣ 𝑋 𝑖 = 𝑥]$ と定め， $𝑝 (𝑥) = 0$ である $𝑥$ については $ˆ 𝑥 = ˆ 𝑥 0$ のとき $1$ ，そうでないとき $0$ と定める．どちらの場合も値は非負で，各 $𝑥$ について $ˆ 𝑥$ にわたる総和は $1$ だから， $𝑞 𝑖$ は定義 9.1.5 の条件付き分布である． $𝑋 𝑖$ の分布は $𝑝$ だから， $𝑝 (𝑥) > 0$ では $𝑝 (𝑥) 𝑞 𝑖 (ˆ 𝑥 ∣ 𝑥) = P r [𝑋 𝑖 = 𝑥, ˆ 𝑋 𝑖 = ˆ 𝑥]$ であり， $𝑝 (𝑥) = 0$ では両辺とも $0$ である．すなわち $𝑞 𝑖$ に対応する対の同時分布は $(𝑋 𝑖, ˆ 𝑋 𝑖)$ の同時分布そのものだから，定義 9.1.5 より $𝐼 (𝑝; 𝑞 𝑖) = 𝐼 (𝑋 𝑖; ˆ 𝑋 𝑖)$ であり，その期待歪みは $𝔼 [𝑑 (𝑋 𝑖, ˆ 𝑋 𝑖)] = 𝐷 𝑖$ である．よって $𝑞 𝑖 \in Q (𝐷 𝑖)$ であり，とくに $Q (𝐷 𝑖)$ は空でない． $𝑅 (𝐷 𝑖)$ は値の集合 ${𝐼 (𝑝; 𝑞) : 𝑞 \in Q (𝐷 𝑖)}$ の下限だから

𝑅 (𝐷 𝑖) \leq 𝐼 (𝑋 𝑖; ˆ 𝑋 𝑖)

である．

符号語数がブロックの相互情報量を抑える. $ˆ 𝑋 𝑛$ の値は $𝑔$ の値域に属する．その値域の大きさを $𝑘$ と書くと， $𝑀 \geq 1$ だから値域は空でなく $1 \leq 𝑘$ である． $ˆ 𝑋 𝑛$ は大きさ $𝑘$ の集合に値をとる確率変数だから，定理 1.1.5 より $𝐻 (ˆ 𝑋 𝑛) \leq l o g 𝑘$ である． $𝑔$ の定義域は ${1, \dots, 𝑀}$ だから $𝑘 \leq 𝑀$ であり，補題 8.2.5 の単調性より $l o g 𝑘 \leq l o g 𝑀$ である．よって $𝐻 (ˆ 𝑋 𝑛) \leq l o g 𝑀$ である．また定理 1.3.4 を対 $(𝑋 𝑛, ˆ 𝑋 𝑛)$ に当てると $𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛) = 𝐻 (ˆ 𝑋 𝑛) - 𝐻 (ˆ 𝑋 𝑛 ∣ 𝑋 𝑛)$ であり，条件付きエントロピーは非負の量を非負の重みで平均したものだから非負である（定義 1.2.2 と命題 1.1.4）．よって $𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛) \leq 𝐻 (ˆ 𝑋 𝑛) \leq l o g 𝑀$ である．

三つの評価が一つの連鎖になる. 補題 9.5.2 を組 $𝑋 𝑛$ と組 $ˆ 𝑋 𝑛$ に当てると $\sum 𝑖 𝐼 (𝑋 𝑖; ˆ 𝑋 𝑖) \leq 𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛)$ である．ここまでを合わせると

l o g 𝑀 \geq 𝐼 (𝑋 𝑛; ˆ 𝑋 𝑛) \geq 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; ˆ 𝑋 𝑖) \geq 𝑛 - 1 \sum 𝑖 = 0 𝑅 (𝐷 𝑖)

である． $¯ 𝐷 : = 1 𝑛 \sum 𝑖 𝐷 𝑖$ とおくと，各 $Q (𝐷 𝑖)$ が空でないので補題 9.5.3 が当たり， $Q (¯ 𝐷)$ は空でなく $𝑅 (¯ 𝐷) \leq 1 𝑛 \sum 𝑖 𝑅 (𝐷 𝑖)$ である．よって $1 𝑛 l o g 𝑀 \geq 𝑅 (¯ 𝐷)$ である．最後に，期待歪みが成分ごとの歪みの平均であることから得た $¯ 𝐷 \leq 𝐷$ に命題 9.2.1 を当てると， $Q (𝐷)$ は空でなく $𝑅 (𝐷) \leq 𝑅 (¯ 𝐷)$ である．二つを合わせて $1 𝑛 l o g 𝑀 \geq 𝑅 (𝐷)$ を得る． $◼$

形式化: rate_distortion_converse_n_letter_singleLetter (ソース)

形式化上の注記. 形式化の仮定は本文と一つずつ対応している．符号が LossyCode であること，長さが正であること，符号語数が正であること，情報源の成分が互いに独立で同じ分布をもつこと，期待歪みが $𝐷$ 以下であることの五つがそれである．本文に対して真に増えているのは，情報源の各成分・符号化写像・復号写像が可測であることと，相互情報量が有限であることの二つで，どちらもアルファベットが有限であれば自動的に満たされる（後者は命題 1.3.5 による）．独立性と同分布性が落とせないことは，形式化の側にも書き添えてある． $𝑛 = 2$ で $𝑋 0$ と $𝑋 1$ がつねに等しい情報源をとると結論が破れる，という理由つきである．いっぽう宣言が述べているのは不等式だけで， $Q (𝐷)$ が空でないという結論の前半にあたる部分は含まれていない．あちらは値を拡張非負実数にとり，実数に落とすところで無限大を $0$ とみなすので， $Q (𝐷)$ が空のときにも不等式のほうは成り立ってしまう．前半を与えているのは，定理 9.5.4 に付した証明である．

ただし，この宣言が使う $𝑅 (𝐷)$ は， $𝑅 (𝐷)$ を測度の言葉で書いた rateDistortionFunction (InformationTheory/Shannon/RateDistortion/Converse.lean) のほうである．値を拡張非負実数にとり，相互情報量を相対エントロピーの形で書くもので，定義 9.1.5 に紐付けた rateDistortionFunctionPmf (InformationTheory/Shannon/RateDistortion/Achievability.lean) とは別の宣言であり，二つを結ぶ宣言は無い．

左辺が誰のものかを見る. 左辺の $1 𝑛 l o g 𝑀$ は符号を設計する側が決める量で，右辺の $𝑅 (𝐷)$ は情報源の分布と歪み尺度だけで決まる量である．したがって定理 9.5.4 は，設計する側が下げられるところに，情報源の側から下限が置かれている形に読める．裏返して言えば，レートを $𝑅 (𝐷)$ より下げた符号は，期待歪みを $𝐷$ 以下に抑えられない．レートを下げたければ $𝐷$ を大きくとる，すなわち歪みを多く許すことになり，そのぶん右辺は上がらない（命題 9.2.1）．第2章定理 2.3.4 と違うのは，ここに極限が出てこないことである．あちらは誤り確率が $0$ に向かう族についてしか言えず，結論も下極限の形だった．こちらは各 $𝑛$ の符号 $1$ 本ごとに不等式が成り立ち， $𝑛$ を大きくしても限界は緩まない．違いを生んでいるのは，歪みが「 $𝐷$ 以下」という形で最初から符号に課された条件になっていることである．

数で見る

例 9.5.5（ $𝜋 = 1 / 4$ の二値情報源の符号語数）. $X = ˆ X = {0, 1}$ ， $𝑝 (1) = 1 / 4$ ， $𝑝 (0) = 3 / 4$ ， $𝑑 = 𝑑 𝐻$ （例 9.1.3）とし， $𝑋 100$ を，どの成分も分布 $𝑝$ に従い互いに独立な $100$ 個の確率変数の組とする．長さ $100$ のレート歪み符号（定義 9.5.1）の符号語数を $𝑀$ とし， $𝑋 100$ に対する期待歪みを考える．期待歪みが $0$ ならば $l o g 𝑀 \geq 100 𝑅 (0)$ であり，右辺は約 $81.13$ である．期待歪みが $0.05$ 以下ならば $l o g 𝑀 \geq 100 𝑅 (0.05)$ であり，右辺は約 $52.49$ である．さらに，期待歪みが $0$ ならば $l o g 𝑀 \geq 100$ である．

証明. $m i n (1 / 4, 3 / 4) = 1 / 4$ であり $0 \leq 0.05 < 1 / 4$ だから，定理 9.3.4 の第 $1$ の場合が $𝐷 = 0$ と $𝐷 = 0.05$ のどちらにも当たり， $Q (0)$ と $Q (0.05)$ はどちらも空でない．期待歪みが $0$ のときは定理 9.5.4 を $𝑛 = 100$ ， $𝐷 = 0$ に当て，期待歪みが $0.05$ 以下のときは同じ定理を $𝑛 = 100$ ， $𝐷 = 0.05$ に当てて，どちらも両辺を $100$ 倍すれば主張の不等式を得る．二つの右辺の値は，例 9.3.5 が求めた $𝑅 (0)$ と $𝑅 (0.05)$ の値のちょうど $100$ 倍である．

最後の主張は定理 9.5.4 を通さずに直接見る．符号を $(𝑐, 𝑔)$ と書く．歪み尺度の値は非負（定義 9.1.1）だからブロックの歪み $𝑑 (𝑋 100, 𝑔 (𝑐 (𝑋 100)))$ も非負であり，その期待値は非負の値を非負の重みで足し合わせたものだから，期待歪みが $0$ になるのは，正の確率をもつどの列でもブロックの歪みが $0$ のときである． $𝑝 (0)$ と $𝑝 (1)$ はどちらも正だから $𝑋 100$ はどの列も正の確率でとり，よってどの $𝑥 100 \in X 100$ についてもブロックの歪みは $0$ である． $𝑑 𝐻$ の値が $0$ になるのは二つの文字が一致するときに限る（例 9.1.3）から，成分ごとに一致して $𝑔 (𝑐 (𝑥 100)) = 𝑥 100$ である．したがって $𝑐$ は単射で $𝑀 \geq 2100$ であり，補題 8.2.5 の単調性より $l o g 𝑀 \geq 100$ である． $◼$

形式化上の注記. 例 9.5.5 に対応する宣言は形式化されていない．形式化には歪み尺度を具体的にとった実例が一つも置かれていないので，Hamming 歪みについて値を述べる宣言も無い．

規模感. 例 9.5.5 の情報源を素朴に $1$ 文字 $1$ ビットで書けば，長さ $100$ のブロックに番号は $2100$ 通り要り， $l o g 𝑀$ は $100$ である．歪みをいっさい許さないなら，例 9.5.5 より $l o g 𝑀$ は約 $81.13$ を下回れない．ただし同じ例が示しているとおり，この場合に実際に要るのは $l o g 𝑀 = 100$ で，素朴なやり方から $1$ ビットも減らせない．定理 9.5.4 の下界は，各 $𝑛$ で最良の値を与えるものではない，ということである．第2章の下界にも同じ開きがあった．定理 2.3.4 が与えるのは，誤り確率を $0$ に向かわせる族について $𝐻 (𝑋)$ という値までで，誤りをいっさい許さない族についても，それより強い下界は与えない．歪みを $0$ ちょうどに固定したときに定理 9.5.4 が $𝑅 (0)$ までしか与えないのと，同じ格好である．文字の $5$ パーセントの食い違いまで許すと，限界が約 $52.49$ まで下がり，素朴なやり方の半分ほどになる．ただし例 9.5.5 が言っているのは限界だけで，この本数の符号語で実際に歪みを $0.05$ 以下に抑えられるかは，まだ何も言っていない．下界と実際に要る量の開きが縮むかどうかも，長さを大きくしたときに何が言えるかによる．

定理 9.5.4 は片側だけの主張である． $𝑅 (𝐷)$ より小さいレートでは期待歪みを $𝐷$ 以下に抑えられないことは言えたが， $𝑅 (𝐷)$ より大きいレートで実際に抑えられるかは，まだ問うていない．それが 9.6 節の内容で，そこで初めて $𝑅 (𝐷)$ の両側がそろう．

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