9.6 達成可能性

定理 9.5.4 は，期待歪みを $𝐷$ 以下に抑える符号のレートを下から押さえた．残るのは逆向きで， $𝑅 (𝐷)$ より大きいレートなら実際に符号が作れるか，という問いである．第2章定理 2.3.2 と第6章 6.3 節で答えたのと同じ形の問いで，答えも同じく肯定である．本節はその達成可能性を借用として置く．借りる形には歪みの側に小さな余裕が付いていて，レートを $𝑅 (𝐷)$ より大きくとれば，どの $𝜀 > 0$ についても，長さを十分大きくとって期待歪みを $𝐷 + 𝜀$ 以下に抑えられる，という形をしている．そのうえで，期待歪みが $𝐷$ より小さい再現の作り方があるときには，この余裕を落として期待歪みを $𝐷$ 以下に抑えられることを見る．

記号を一つ断っておく．本節は符号のレートの値を $𝑅$ と書く．本章は定義 9.1.5 のレート歪み関数をつねに $𝑅 (𝐷)$ や $𝑅 (\cdot)$ のように引数を添えて書くので，引数の有無で二つを見分けられる．

本節はまず，なぜ $𝑅 (𝐷)$ という数がここに現れるのかを，再現の列で情報源の典型系列を覆うという勘定で見る．そのうえで達成可能性を借用として置き，逆定理と突き合わせて本章の主定理に至る．次に長さ $2$ の符号を二つ作って数を見る．最後に，第6章と本章で得た二つの符号化定理を並べて，向きの違いを見る．

覆う勘定

第2章の圧縮は，典型集合（定義 2.2.1）に番号を振ることで働いた．情報源のブロックはほぼ確実に典型集合に落ち（定理 2.2.3），その元の個数は $2 𝑛 𝐻 (𝑋)$ をわずかに上回るところまでで抑えられる（定理 2.2.5）から，番号を書き下すのに $1$ 文字あたり $𝐻 (𝑋)$ ビットあれば足りた．歪みを許すと，番号の数をもっと減らせるはずである．一つの番号に一つの系列を対応させるのではなく，一本の再現の列に，そこから歪みの小さい情報源の列をまとめて引き受けさせればよい．

ここから先は見当である．条件付き分布 $𝑞$ を一つ固定し，対 $(𝑋, ˆ 𝑋)$ をその同時分布に従うものとして，その独立な複製を $𝑛$ 組並べたものを $(𝑋 𝑛, ˆ 𝑋 𝑛)$ と書く．再現の列 $ˆ 𝑥 𝑛$ を一本決めたとき，それが引き受けられる情報源の列は， $ˆ 𝑋 𝑛 = ˆ 𝑥 𝑛$ を知ったあとの世界で典型な列だから，その個数はおよそ $2 𝑛 𝐻 (𝑋 ∣ ˆ 𝑋)$ である，と読む．肩に $𝐻 (𝑋 ∣ ˆ 𝑋)$ が来るのは，定理 2.2.5 の勘定をこの条件つきの世界に当てるからである．あちらで肩に乗っていたのは情報源の $1$ 文字あたりの不確かさ $𝐻 (𝑋)$ で，いまは $ˆ 𝑥 𝑛$ を知ったぶんだけそれが減り，平均すると $𝐻 (𝑋 ∣ ˆ 𝑋)$ になる．覆いたい相手はおよそ $2 𝑛 𝐻 (𝑋)$ 個あるから，要る本数はその比

2 𝑛 𝐻 (𝑋) 2 𝑛 𝐻 (𝑋 ∣ ˆ 𝑋) = 2 𝑛 𝐼 (𝑋; ˆ 𝑋)

ほどになる（指数の差が相互情報量になるのは定理 1.3.4 による）．本数を少なくしたければ $𝐼 (𝑋; ˆ 𝑋)$ を小さくすればよく，歪みの制約のもとでいちばん小さくした値が $𝑅 (𝐷)$ にほかならない（定義 9.1.5）．本書はこの勘定を主張としては述べない．「 $ˆ 𝑥 𝑛$ を知ったあとの典型な列」にあたる集合を，本書は用意していないからである．一本の再現の列が実際に何本を引き受けるかは，長さ $2$ の場合を例 9.6.2 で数える．

第8章 8.4 節の勘定と，数の出方が同じであることも見ておく．あちらは，半径 $\sqrt 𝑛 (𝑃 + 𝑁)$ の球の中に半径 $\sqrt 𝑛 𝑁$ の球をいくつ詰められるかを，体積の比として数えた（命題 8.4.1）．こちらは，情報源の典型集合が一本の再現の列でどれだけ覆えるかを，個数の比として数えている．違うのは，詰めるのか覆うのかという向きだけである．

借りる道具

解析の事実を一つ借りる．区間の上で定義された凸関数は，その区間の内点で連続であるという事実である．当てる相手は，実数の区間の上の実数値関数として見た $𝑅 (\cdot)$ だけで，この借用に依存するのは系 9.6.1 の第 $2$ の主張の証明だけである．本書はこの事実を証明しないが，形式化されていないわけではない．Mathlib に無条件の機械検証済みの定理として置かれている．

道具をもう一つ借りる．レート歪み理論の達成可能性，すなわち「レートが $𝑅 (𝐷)$ を上回っているかぎり，期待歪みを $𝐷$ にいくらでも近いところまで抑える符号がある」という主張である．使う形を書いておく．

$X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．実数 $𝐷$ について $Q (𝐷)$ が空でないとし，実数 $𝑅$ が $𝑅 > 𝑅 (𝐷)$ を満たし， $𝜀 > 0$ とする．このとき番号 $𝑛 0$ があって， $𝑛 \geq 𝑛 0$ を満たすどの $𝑛$ についても，符号語数 $𝑀$ が $𝑀 \leq 2 𝑛 𝑅 + 1$ を満たす長さ $𝑛$ のレート歪み符号（定義 9.5.1）で，どの成分も分布 $𝑝$ に従い互いに独立な $X$ に値をとる $𝑛$ 個の確率変数の組 $𝑋 𝑛$ に対する期待歪みが $𝐷 + 𝜀$ 以下であるものが存在する．

当てる対象は，情報源アルファベットと再現アルファベットがどちらも空でない有限集合であるときの，定義 9.5.1 のレート歪み符号だけである．情報源の分布 $𝑝$ には， $X$ 上の分布であること以外の条件を置かない．この借用を主張の根拠として当てるのは系 9.6.1 の証明だけである．第14章 14.4 節がこの名前を二度引くが，どちらも当てているのではない．一度は定義 14.4.2 が歪みに $𝜀$ の余裕を付ける形をここと同じだと言うところ，もう一度は同節が借りる「副情報つきレート歪みの達成可能性」の筋書きが，覆いの段をここと同じ作り方だと言うところである．

本書がこの主張を証明しないのは，第6章 6.3 節のランダム符号化に使う部品のうち，二つを用意していないからである．一つは，結合典型集合（定義 6.2.3）に落ちる確率を下から抑える評価である．第6章が要ったのは，無関係な対がたまたま結合典型になる確率を上から抑えること（定理 6.2.7）で，そちらは誤りを小さくするために使う．覆う議論で要るのはその逆向き，すなわち独立に引いた再現の列が情報源の列と結合典型になる確率を下から抑えることで，一本も当たらない確率を $(1 - その確率) 𝑀$ の形で押さえるのに使う．本書はこの下界を持っていない．もう一つは，結合典型であることからブロックの歪みが期待歪みの近くにあることを引き出す段である．これには第2章 2.4 節の強典型性（定義 2.4.1）を，一つの情報源についてではなく対について立てる必要があり，本書はその形を用意していない．「本書で証明しない」ことと「形式化されていない」ことは別である．本節が借りた主張は，本書が証明を載せないだけで，無条件の機械検証済みの定理として形式化されている．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．符号帳は設計するのではなく，くじで引く．命題 9.1.8 により $𝐼 (𝑝; \cdot)$ を $Q (𝐷)$ の上で最小にする条件付き分布 $𝑞 *$ をとり，それが定める再現の側の分布を $ˆ 𝑝$ と書く．一本の再現の列は，各成分を独立に $ˆ 𝑝$ から引いて作り，それを $𝑀$ 本ぶん独立に繰り返す．符号化は，情報源の列 $𝑥 𝑛$ に対して，対 $(𝑥 𝑛, ˆ 𝑥 𝑛)$ が 歪み典型 である符号語 $ˆ 𝑥 𝑛$ を探し，見つかればその番号を出し，一本も見つからなければ番号 $1$ を出す，というものである．ここで歪み典型とは，結合典型（定義 6.2.3 を $𝑞 *$ の定める同時分布に当てたもの）であって，かつブロックの歪み（定義 9.1.2）が期待歪みの近くにあることをいう．第6章 6.3 節の復号器が結合典型な符号語を探したのと，探す規則は同じで，探す側が復号から符号化へ移っている．

見当のとおり，一本の符号語が当たる確率はおよそ $2 - 𝑛 𝐼 (𝑝; 𝑞 *) = 2 - 𝑛 𝑅 (𝐷)$ で， $𝑀$ 本のうち一本も当たらない確率はおよそ $(1 - 2 - 𝑛 𝑅 (𝐷)) 𝑀$ である． $𝑀$ が $2 𝑛 𝑅$ ほどあって $𝑅 > 𝑅 (𝐷)$ なら，これは $𝑛$ とともに $0$ に向かう（ $0 \leq 𝑥 \leq 1$ のとき $(1 - 𝑥) 𝑀 \leq 𝑒 - 𝑥 𝑀$ であり， $𝑥 = 2 - 𝑛 𝑅 (𝐷)$ ， $𝑀 = 2 𝑛 𝑅$ とおくと肩の $𝑥 𝑀 = 2 𝑛 (𝑅 - 𝑅 (𝐷))$ が発散するからである）．当たったときのブロックの歪みは，歪み典型の定め方から期待歪みの近く，すなわち $𝐷$ の近くにある．当たらなかったときの歪みは，アルファベットが有限なので $m a x 𝑥, ˆ 𝑥 𝑑 (𝑥, ˆ 𝑥)$ で抑えられ，その場合の確率が $0$ に向かうので，期待歪みへの寄与も $0$ に向かう．二つを合わせると， $𝑛$ を十分大きくとれば期待歪みは $𝐷 + 𝜀$ 以下に収まる．最後に，引いた符号帳について平均した期待歪みがこの評価を満たすので，少なくとも一つの符号帳が同じ評価を満たす．第6章 6.3 節も最後に同じ形の議論を通った．

形式化: rate_distortion_achievability_operational_general (ソース)

形式化上の注記. 形式化の宣言の仮定は，借りた主張と一つずつ対応している．情報源の分布が確率分布であること，制約集合が空でないこと（本文の「 $Q (𝐷)$ が空でない」にあたる），レートが $𝑅 (𝐷)$ より真に大きいこと， $𝜀$ が正であることの四つで，これがすべてである．結論も同じ形で，ある番号から先のすべての長さについて，符号語数が上の不等式を満たすレート歪み符号があり，その期待歪みが $𝐷 + 𝜀$ 以下である，という形をしている．ただし宣言は符号語数について， $2 𝑛 𝑅$ を切り上げた整数以上であるという下からの評価も与える．本文が使うのは符号語数が正であることだけで，それは定義 9.5.1 から出るので，借りる形からはこの評価を落としてある．筋書きに書いた歪み典型は，あちらでは distortionTypicalSet (InformationTheory/Shannon/RateDistortion/AchievabilityJointTypicalEncoder.lean) として，結合典型集合と，ブロックの歪みについての条件との共通部分に定めてある．ただし探索の規則は本文の筋書きと違う．形式化の符号化器 jointStronglyTypicalLossyEncoder (InformationTheory/Shannon/RateDistortion/AchievabilityJointStrongTypicality.lean) が探すのは，強典型性（定義 2.4.1）の意味で結合典型な符号語である．ブロックの歪みが期待歪みの近くにあることは，探索の規則からではなく，そこから distortionTypicalSet への包含 jts_subset_dts_of_dist_slack (InformationTheory/Shannon/RateDistortion/AchievabilityUnconditional.lean) を経て出る．

レート歪み定理

これから置く系のうち，達成可能性の側の証明は二段の余裕とりで動くので，筋を先に言っておく．借りた達成可能性が返してくるのは期待歪み $𝐷 + 𝜀$ 以下の符号なので，その余裕をあらかじめ差し引いておく．すなわち $𝐷$ より少し小さい歪み $𝐷 ″$ に借用を当て，余裕のほうを $𝐷 - 𝐷 ″$ にとれば，合わせてちょうど $𝐷$ になる．そう縮めても借用が使える，つまり $𝑅 (𝐷 ″) < 𝑅$ がなお成り立つ，というところに借りた凸関数の連続性が要る．レートの側にも同じ形の差し引きがあって，借用のレートを $𝑅$ より少し小さい $𝑅'$ にとることで，符号語数を整数にするぶんの増加を吸収する．

系 9.6.1（レート歪み定理）. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．実数 $𝐷$ について $Q (𝐷)$ が空でないとし，各 $𝑛 \geq 1$ について $𝑋 𝑛$ を，どの成分も分布 $𝑝$ に従い互いに独立な $𝑛$ 個の $X$ に値をとる確率変数の組とする．実数 $𝑅$ について次の二つが成り立つ．

$𝑅 < 𝑅 (𝐷)$ ならば，どの $𝑛 \geq 1$ についても，レートが $𝑅$ 以下で $𝑋 𝑛$ に対する期待歪みが $𝐷$ 以下である長さ $𝑛$ のレート歪み符号（定義 9.5.1）は存在しない．
$𝑅 > 𝑅 (𝐷)$ で，かつ $Q (𝐷')$ が空でない実数 $𝐷' < 𝐷$ が存在するならば，番号 $𝑛 *$ があって， $𝑛 \geq 𝑛 *$ を満たすどの $𝑛$ についても，レートが $𝑅$ 以下で $𝑋 𝑛$ に対する期待歪みが $𝐷$ 以下である長さ $𝑛$ のレート歪み符号が存在する．

証明.

そのような符号があったとし，その符号語数を $𝑀$ とする．期待歪みが $𝐷$ 以下だから定理 9.5.4 が当たり $1 𝑛 l o g 𝑀 \geq 𝑅 (𝐷)$ である．いっぽうレートが $𝑅$ 以下という仮定は $1 𝑛 l o g 𝑀 \leq 𝑅$ だから $𝑅 \geq 𝑅 (𝐷)$ となり， $𝑅 < 𝑅 (𝐷)$ に反する．
まず， $Q (𝑡)$ が空でないどの実数 $𝑡$ についても $𝑅 (𝑡) \geq 0$ であることを見る．定義 9.1.5 の $𝑅 (𝑡)$ は値の集合 ${𝐼 (𝑝; 𝑞) : 𝑞 \in Q (𝑡)}$ の下限であり，命題 1.3.2 よりどの値も非負だから $0$ はこの集合の下界である．下限は下界のうち最大のものだから $𝑅 (𝑡) \geq 0$ である．

歪みの側に余裕を作る．仮定より $Q (𝐷')$ が空でない実数 $𝐷' < 𝐷$ がある．命題 9.2.1 より $𝐷'$ 以上のどの実数 $𝑡$ についても $Q (𝑡)$ は空でないから， $𝑅 (\cdot)$ は区間 $[𝐷', \infty)$ の上で定まり，命題 9.2.3 よりその上で凸である． $𝐷' < 𝐷$ だから $𝐷$ はこの区間の内点であり，区間の上で定義された凸関数はその区間の内点で連続だから， $𝑅 (\cdot)$ は $𝐷$ で連続である． $𝑅 - 𝑅 (𝐷) > 0$ にこの連続性を当てると， $𝛿 > 0$ があって， $[𝐷', \infty)$ の点 $𝑡$ が $| 𝑡 - 𝐷 | < 𝛿$ を満たすかぎり $𝑅 (𝑡) < 𝑅$ である．そこで $𝐷 ″ : = m a x (𝐷', 𝐷 - 𝛿 / 2)$ とおくと $𝐷' \leq 𝐷 ″ < 𝐷$ かつ $𝑅 (𝐷 ″) < 𝑅$ であり， $𝑅' : = 12 (𝑅 (𝐷 ″) + 𝑅)$ とおくと $𝑅 (𝐷 ″) < 𝑅' < 𝑅$ である．

借りたレート歪み理論の達成可能性を，歪みの上限 $𝐷 ″$ ，レート $𝑅'$ ，余裕 $𝐷 - 𝐷 ″$ に当てて番号 $𝑛 0$ を得る． $1 / 𝑛 1 \leq 𝑅 - 𝑅'$ を満たす番号 $𝑛 1$ をとり， $𝑛 * : = m a x (𝑛 0, 𝑛 1)$ とおく． $𝑛 \geq 𝑛 *$ とすると，符号語数 $𝑀$ が $𝑀 \leq 2 𝑛 𝑅' + 1$ を満たし， $𝑋 𝑛$ に対する期待歪みが $𝐷 ″ + (𝐷 - 𝐷 ″) = 𝐷$ 以下である長さ $𝑛$ のレート歪み符号がとれる．

レートを評価する． $𝑅' > 𝑅 (𝐷 ″) \geq 0$ と $𝑛 \geq 1$ より $2 𝑛 𝑅' \geq 1$ だから $𝑀 \leq 2 𝑛 𝑅' + 1 \leq 2 \cdot 2 𝑛 𝑅' = 2 𝑛 𝑅' + 1$ である．また定義 9.5.1 より $𝑀 \geq 1$ である．補題 8.2.5 より $l o g$ は単調だから， $𝑀 \leq 2 𝑛 𝑅' + 1$ の対数をとって $𝑛$ で割ると

1 𝑛 l o g 𝑀 \leq 𝑅' + 1 𝑛

である． $𝑛 \geq 𝑛 1$ より $1 𝑛 \leq 1 𝑛 1 \leq 𝑅 - 𝑅'$ だから，レートは $𝑅$ 以下である． $◼$

形式化上の注記. 系 9.6.1 に対応する単独の宣言は無い．しかも片側ずつの機械検証は，同じ $𝑅 (𝐷)$ についてのものになっていない．第 $2$ の主張に使った達成可能性の宣言が下限をとる相手は，定義 9.1.5 に紐付けた rateDistortionFunctionPmf (InformationTheory/Shannon/RateDistortion/Achievability.lean) である．いっぽう第 $1$ の主張が経由する定理 9.5.4 の宣言が使うのは， $𝑅 (𝐷)$ を測度の言葉で書いた rateDistortionFunction (InformationTheory/Shannon/RateDistortion/Converse.lean) で，値を拡張非負実数にとり，相互情報量を相対エントロピーの形で書く．二つの値はどちらも定義 9.1.5 の $𝑅 (𝐷)$ にあたるが，単独の宣言としては別のもので，両者を結ぶ宣言は無い．したがって，本文が一つの $𝑅 (𝐷)$ について述べている両側の主張は，形式化では別々の量についての二つの主張になっている．

系 9.6.1 の二つは $𝑅 (𝐷)$ を境として向かい合っている．第 $1$ の主張は，レートが $𝑅 (𝐷)$ より小さければ期待歪みを $𝐷$ 以下に抑える符号がどの長さにも無いと言う．第 $2$ の主張は， $𝑅 (𝐷)$ より大きく，しかも期待歪みが $𝐷$ より小さい再現の作り方があるなら，長さを十分大きくとってそういう符号がとれると言う．一行で言えば，歪み $𝐷$ を許した圧縮に要るレートの限界は $𝑅 (𝐷)$ で，境目のすぐ上とすぐ下とで符号の有無が入れ替わる．第6章定理 6.4.9 と第8章系 8.4.2 で達成可能性と逆定理が噛み合ったのと，同じ形である．

第 $2$ の主張だけが余分に置いた条件は， $𝐷$ より小さい歪みで済む再現の作り方がある，ということである．借りた達成可能性がそのまま与えるのは期待歪みが $𝐷 + 𝜀$ 以下までで，そこから $𝜀$ を落とすのに使ったのが，この条件と， $𝑅 (\cdot)$ の非増加性（命題 9.2.1）・凸性（命題 9.2.3）と，借りた凸関数の連続性である．歪みをいっさい許さない $𝐷 = 0$ は，どの情報源でもこの条件から外れる．歪み尺度の値は非負（定義 9.1.1）だから， $𝐷 < 0$ では $Q (𝐷)$ が空だからである．外したのは書きぶりの都合ではない．例 9.5.5 の情報源で，レートを $𝑅 (0)$ と $1$ のあいだにとってみる（例 9.3.5 より $𝑅 (0)$ は約 $0.8113$ ビットだから，そういうレートはある）．期待歪みを $0$ にするには，例 9.5.5 の最後の段と同じ理由で符号化写像が単射でなければならず，符号語数は $2 𝑛$ 以上，すなわちレートは $1$ 以上になる．長さ $𝑛$ を何にとってもそうだから，どれだけ長くとってもそういう符号は存在しない．

数で見る

例 9.6.2（ $𝜋 = 1 / 4$ の二値情報源の長さ $2$ の符号）. $X = ˆ X = {0, 1}$ ， $𝑝 (1) = 1 / 4$ ， $𝑝 (0) = 3 / 4$ ， $𝑑 = 𝑑 𝐻$ （例 9.1.3）とし， $𝑋 2 = (𝑋 0, 𝑋 1)$ を，どちらの成分も分布 $𝑝$ に従い互いに独立な確率変数の組とする．長さ $2$ のレート歪み符号（定義 9.5.1）を二つ考える．

符号語数 $𝑀 = 1$ で，復号写像が番号 $1$ に $(0, 0)$ を返すもの．そのレートは $0$ で， $𝑋 2$ に対する期待歪みは $1 / 4$ である．
符号語数 $𝑀 = 2$ で，復号写像が番号 $1$ に $(0, 0)$ ，番号 $2$ に $(1, 1)$ を返し，符号化写像が $(1, 1)$ に番号 $2$ を，残りの三つの列に番号 $1$ を割り当てるもの．そのレートは $1 / 2$ ビットで， $𝑋 2$ に対する期待歪みは $3 / 16$ である．

さらに，定理 9.5.4 が期待歪み $3 / 16$ に置く下界 $𝑅 (3 / 16)$ は約 $0.1151$ ビットであり，第 $2$ の符号のレート $1 / 2$ はその $4$ 倍を超える．

証明. 成分が互いに独立だから， $𝑋 2$ の分布は $P r [𝑋 2 = (0, 0)] = 9 / 16$ ， $P r [𝑋 2 = (0, 1)] = P r [𝑋 2 = (1, 0)] = 3 / 16$ ， $P r [𝑋 2 = (1, 1)] = 1 / 16$ である．また例 9.1.3 より，長さ $2$ のブロックの歪みは成分が食い違う位置の割合，すなわち食い違った成分の個数の半分である．

レートは $12 l o g 1 = 0$ である．再現の列は $(0, 0)$ の一本だけだから，ふたたび例 9.1.3 より期待歪みは $12 (P r [𝑋 0 \neq 0] + P r [𝑋 1 \neq 0]) = 12 (14 + 14) = 14$ である．
レートは $12 l o g 2 = 12$ ビットである．四つの列それぞれについてブロックの歪みを数える． $(0, 0)$ と $(1, 1)$ は自分と同じ再現の列に移るから歪みは $0$ ， $(0, 1)$ と $(1, 0)$ は番号 $1$ を経て $(0, 0)$ に戻り，食い違う成分が一つだから歪みは $1 / 2$ である．よって期待歪みは $316 \cdot 12 + 316 \cdot 12 = 316$ である．

最後の主張を見る． $3 / 16 < 1 / 4$ より，定理 9.3.4 の第 $1$ の場合が $𝐷 = 3 / 16$ に当たるから， $Q (3 / 16)$ は空でなく，その値も同じ場合の式で直接求まる． $l o g 2 3 = 1.5849 \dots$ ， $l o g 2 13 = 3.7004 \dots$ だから $l o g 2 316 = - 2.4150 \dots$ ， $l o g 2 1316 = - 0.2995 \dots$ であり

𝐻 𝑏 (316) = 316 \times 2.4150 \dots + 1316 \times 0.2995 \dots = 0.4528 \dots + 0.2433 \dots = 0.6962 \dots

である． $𝐻 𝑏 (1 / 4)$ は例 9.3.5 の $𝑅 (0)$ そのもので約 $0.8113$ ビットだから， $𝑅 (3 / 16) = 𝐻 𝑏 (1 / 4) - 𝐻 𝑏 (3 / 16)$ は約 $0.8113 - 0.6962 = 0.1151$ ビットである．レート $1 / 2$ をこの値で割ると $4.34 \dots$ だから，レートは下界の $4$ 倍を超えている． $◼$

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

二つを見比べると，覆うという言葉に実体が入る．第 $1$ の符号は再現の列を一本しか持たず，その一本が $X 2$ の四つの列すべてを引き受けている．レートは $0$ で番号を書き下す手間がいっさい要らない代わりに， $1$ が出るたびにそのぶんの歪みを払うので，期待歪みは $1$ の出る割合そのものになる．第 $2$ の符号は $(1, 1)$ をもう一本足し，四つのうち $(1, 1)$ の一つだけをそちらへ移した．一本が引き受ける本数が減ったぶん期待歪みは $3 / 16$ まで下がり，代わりにレートが $1 / 2$ ビットに上がる．レートと歪みの交換は，こういう形で起きている．

第 $1$ の符号のレート $0$ は，定理 9.5.4 が期待歪み $1 / 4$ に置く下界 $𝑅 (1 / 4)$ にちょうど等しい（例 9.3.5 より $𝑅 (1 / 4) = 0$ ）．歪みを $1 / 4$ まで許すなら，長さ $2$ でも符号語一本で足りるということである．第 $2$ の符号のレートのほうは，例 9.6.2 の最後の主張のとおり，下界 $𝑅 (3 / 16)$ の $4$ 倍を超えたところにある．長さ $2$ では再現の列の置き場所が四か所しかないので，この粗さが残る．この情報源では， $0.1 < 1 / 4$ より定理 9.3.4 の第 $1$ の場合が $𝐷 = 0.1$ にも当たって $Q (0.1)$ が空でなく，しかも $0.1 < 3 / 16$ だから，系 9.6.1 の第 $2$ の主張が $𝐷 = 3 / 16$ に当たる．長さを大きくとれば，レートを $𝑅 (3 / 16)$ のすぐ上まで下げても期待歪みを $3 / 16$ 以下に抑えられる，ということである．

覆うことと詰めること

第6章と本章で符号化定理を二つ得た．二つを並べると，同じ道具立てが向きを変えて使われていることが見える．以下は前半の勘定と同じく見当の言葉で書く．記号を一つ置く．第6章の通信路の入力を $𝑈$ ，出力を $𝑌$ と書く．本章の $𝑋$ と $ˆ 𝑋$ はどちらも情報源の側の記号なので，通信路の側には別の字を当てる．例 7.3.5 が一様分布の確率変数に使った $𝑈$ とは別である．

通信路符号化（第6章定理 6.4.9）が作るのは，入力アルファベットの列に置いた符号語の集まりである．一本の符号語を送ると，出てくる列はその符号語と結合典型な列のどれかで，およそ $2 𝑛 𝐻 (𝑌 ∣ 𝑈)$ 個の広がりをもつ．二本の符号語の広がりが重なると復号を誤るから，設計の目標は符号語をなるべく重ならないように 散らす ことである．全体の入れ物である出力側の典型集合はおよそ $2 𝑛 𝐻 (𝑌)$ 個だから，散らせる本数はその比 $2 𝑛 𝐼 (𝑈; 𝑌)$ ほどで，本数を多くしたければ $𝐼 (𝑈; 𝑌)$ を大きくすればよい．入力分布を動かして $𝐼 (𝑈; 𝑌)$ を最大にした値が容量である（定義 6.1.4）．

情報源符号化（系 9.6.1）が作るのは，再現アルファベットの列 $ˆ X 𝑛$ に置いた再現の列の集まりである．一本の再現の列は，それと歪み典型な情報源の列を引き受け，およそ $2 𝑛 𝐻 (𝑋 ∣ ˆ 𝑋)$ 個の広がりをもつ．引き受けそこねた列があるとそこで歪みが大きくなるから，設計の目標は情報源の典型集合をなるべく少ない本数で覆うことである．覆う相手はおよそ $2 𝑛 𝐻 (𝑋)$ 個だから，要る本数はその比 $2 𝑛 𝐼 (𝑋; ˆ 𝑋)$ ほどで，本数を少なくしたければ $𝐼 (𝑋; ˆ 𝑋)$ を小さくすればよい．条件付き分布を動かして $𝐼 (𝑋; ˆ 𝑋)$ を最小にした値がレート歪み関数である（定義 9.1.5）．

三つの向きがそろって裏返っている．散らすことと覆うこと，最大化と最小化，そして符号のレートに対する不等号の向きである．通信路では，達成レートが容量を超えられない（系 6.4.8）ので容量が上からの限界になり，情報源では，レートが $𝑅 (𝐷)$ を下回れない（定理 9.5.4）ので $𝑅 (𝐷)$ が下からの限界になる．相互情報量を肩に乗せた同じ形の数が，一方では詰められる本数の上限として，他方では覆うのに要る本数の下限として現れている．

本書は，この対比が定理として成り立つことを示さない．示したのは二つの符号化定理であって，一方から他方を導く主張ではない．並べて見えるのは，二つの証明が同じ部品（典型集合と相互情報量）を使っていて，最適化の向きだけが違う，という事実までである．

形式化上の注記. 形式化の側でも二つの定義は鏡になっていて，容量 capacity (InformationTheory/Shannon/ChannelCoding/ShannonTheorem.lean) が相互情報量の上限，レート歪み関数 rateDistortionFunctionPmf (InformationTheory/Shannon/RateDistortion/Achievability.lean) が相互情報量の下限として書かれている．ただし上限と下限をとる相手は別の宣言である．あちらは通信路についての相互情報量 mutualInfoOfChannel (InformationTheory/Shannon/ChannelCoding/Basic.lean)，こちらは同時分布についての相互情報量 mutualInfoPmf (InformationTheory/Shannon/RateDistortion/Achievability.lean) で，二つを同じ主張の中で結ぶ宣言は無い．

第1章で分布から決まる数として定義した相互情報量が，これで二度，符号についての意味を得たことになる．第6章では入力分布を動かして最大にした値が， $1$ 回の使用あたり運べるビット数の限界として現れた．本章では条件付き分布を動かして最小にした値が， $1$ 文字あたり記録に要するビット数の限界として現れた．運ぶことと記録することは別の操作だが，限界を決めている量は同じ一つである．

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