9.2 レート歪み関数の性質

9.1 節は $𝑅 (𝐷)$ を，歪みを $𝐷$ 以下に抑えるという制約のもとでの相互情報量の下限として定め，それが最小値でもあること（命題 9.1.8）まで確かめた．値の計算はまだ一つもしていない．本節では，具体的な情報源を決める前に， $𝐷$ の関数として $𝑅 (\cdot)$ がどんな形をしているかを調べる．示すのは四つで， $𝐷$ について非増加であること，凸であること， $𝐷 = 0$ での値，そして $𝑅 (𝐷)$ が $0$ になる $𝐷$ のうち最小のものである．どれも 9.3 節と 9.4 節で具体的な情報源のレート歪み関数を計算するときに，答え合わせに使える．記号は定義 9.1.1 と定義 9.1.5 のものをそのまま引き継ぐ．

歪みを多く許すほど下がる

命題 9.2.1. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．実数 $𝐷 1 \leq 𝐷 2$ について $Q (𝐷 1)$ が空でないならば， $Q (𝐷 1) \subseteq Q (𝐷 2)$ であり， $Q (𝐷 2)$ も空でなく

𝑅 (𝐷 2) \leq 𝑅 (𝐷 1)

である．

証明. $𝑞 \in Q (𝐷 1)$ とすると，その期待歪みは $𝐷 1$ 以下であり， $𝐷 1 \leq 𝐷 2$ だから $𝐷 2$ 以下でもある．よって $𝑞 \in Q (𝐷 2)$ であり，包含が従う．この段は $Q (𝐷 1)$ が空でも通るので，包含だけなら空でないという仮定は要らない． $Q (𝐷 1)$ が空でないので $Q (𝐷 2)$ も空でなく， $𝑅 (𝐷 2)$ が定まる．

$𝑅 (𝐷 2)$ は値の集合 ${𝐼 (𝑝; 𝑞) : 𝑞 \in Q (𝐷 2)}$ の下界である．いま見た包含より ${𝐼 (𝑝; 𝑞) : 𝑞 \in Q (𝐷 1)}$ はその部分集合だから， $𝑅 (𝐷 2)$ は後者の下界でもある．下限は下界のうち最大のものだから $𝑅 (𝐷 2) \leq 𝑅 (𝐷 1)$ である． $◼$

読み方は素直である．歪みを多く許すほど，選べる再現の作り方は増える．増えたぶんだけ小さい値が選べるかもしれず，少なくとも大きくはならない．効いているのは制約集合の包含だけで，相互情報量の性質は一つも使っていない．

形式化: rateDistortionFunction_antitone (ソース)

形式化上の注記. rateDistortionFunction_antitone が述べているのは， $𝑅 (𝐷)$ を測度の言葉で書いた宣言 rateDistortionFunction (InformationTheory/Shannon/RateDistortion/Converse.lean) についての非増加性である．定義 9.1.5 に紐付けた rateDistortionFunctionPmf (InformationTheory/Shannon/RateDistortion/Achievability.lean) とは別の宣言で，二つを結ぶ宣言は無い．あちらは値を拡張非負実数にとり，制約を満たす同時分布が一つも無いときの下限を $\infty$ と定めるので，命題 9.2.1 が置いた「 $Q (𝐷 1)$ が空でない」という仮定を置かずに述べられている．包含 $Q (𝐷 1) \subseteq Q (𝐷 2)$ を述べる宣言は無く，あちらが与えるのは不等式だけである．

凸である

命題 9.2.1 の証明は制約集合の包含だけで通ったが，凸性の証明はそれでは済まない．二つの再現の作り方を混ぜたときに相互情報量がどう動くかが要るので，それを先に切り出しておく．道具は第1章定理 1.7.1 の対数和不等式ひとつである．

補題 9.2.2（条件付き分布についての相互情報量の凸性）. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑞 1$ と $𝑞 2$ を条件付き分布（定義 9.1.5）， $𝜆 \in [0, 1]$ とする． $𝑞 𝜆 (ˆ 𝑥 ∣ 𝑥) : = 𝜆 𝑞 1 (ˆ 𝑥 ∣ 𝑥) + (1 - 𝜆) 𝑞 2 (ˆ 𝑥 ∣ 𝑥)$ で定まる $𝑞 𝜆$ もまた条件付き分布であり

𝐼 (𝑝; 𝑞 𝜆) \leq 𝜆 𝐼 (𝑝; 𝑞 1) + (1 - 𝜆) 𝐼 (𝑝; 𝑞 2)

である．

証明. 筋は，対 $(𝑥, ˆ 𝑥)$ ごとに対数和不等式を当てて，それを足し上げるだけである．先に，確率 $0$ の項が現れない対について本線を書き切り，確率 $0$ の対の扱いは末尾にまとめる．

$𝑞 𝜆$ が条件付き分布であることは，非負の数の非負係数の和が非負であることと，各 $𝑥$ について $\sum ˆ 𝑥 𝑞 𝜆 (ˆ 𝑥 ∣ 𝑥) = 𝜆 + (1 - 𝜆) = 1$ であることによる． $𝜆 = 0$ と $𝜆 = 1$ では両辺が一致するので，以下では $0 < 𝜆 < 1$ とする．

記号を用意する． $𝑗 = 1, 2, 𝜆$ について， $𝑞 𝑗$ に対応する同時分布を $𝜋 𝑗 (𝑥, ˆ 𝑥) : = 𝑝 (𝑥) 𝑞 𝑗 (ˆ 𝑥 ∣ 𝑥)$ ，その第 $2$ 周辺分布を $ˆ 𝑝 𝑗 (ˆ 𝑥) : = \sum 𝑥 𝜋 𝑗 (𝑥, ˆ 𝑥)$ と書く．どの $𝑗$ でも第 $1$ 周辺分布は $𝑝$ である． $𝑞 𝜆$ の定め方から，各 $(𝑥, ˆ 𝑥)$ について $𝜋 𝜆 (𝑥, ˆ 𝑥) = 𝜆 𝜋 1 (𝑥, ˆ 𝑥) + (1 - 𝜆) 𝜋 2 (𝑥, ˆ 𝑥)$ であり，これを $𝑥$ について足して，各 $ˆ 𝑥$ について $ˆ 𝑝 𝜆 (ˆ 𝑥) = 𝜆 ˆ 𝑝 1 (ˆ 𝑥) + (1 - 𝜆) ˆ 𝑝 2 (ˆ 𝑥)$ である．

対 $(𝑥, ˆ 𝑥)$ を一つ固定し，

𝑎 1 : = 𝜆 𝜋 1 (𝑥, ˆ 𝑥), 𝑎 2 : = (1 - 𝜆) 𝜋 2 (𝑥, ˆ 𝑥), 𝑏 1 : = 𝜆 𝑝 (𝑥) ˆ 𝑝 1 (ˆ 𝑥), 𝑏 2 : = (1 - 𝜆) 𝑝 (𝑥) ˆ 𝑝 2 (ˆ 𝑥)

とおく．これらは非負で， $𝑎 1 + 𝑎 2 = 𝜋 𝜆 (𝑥, ˆ 𝑥)$ ， $𝑏 1 + 𝑏 2 = 𝑝 (𝑥) ˆ 𝑝 𝜆 (ˆ 𝑥)$ である． $𝑏 1$ と $𝑏 2$ がどちらも正である対では，定理 1.7.1 の対数和不等式がそのまま当たって

𝜋 𝜆 (𝑥, ˆ 𝑥) l o g 𝜋 𝜆 (𝑥, ˆ 𝑥) 𝑝 (𝑥) ˆ 𝑝 𝜆 (ˆ 𝑥) \leq 𝜆 𝜋 1 (𝑥, ˆ 𝑥) l o g 𝜋 1 (𝑥, ˆ 𝑥) 𝑝 (𝑥) ˆ 𝑝 1 (ˆ 𝑥) + (1 - 𝜆) 𝜋 2 (𝑥, ˆ 𝑥) l o g 𝜋 2 (𝑥, ˆ 𝑥) 𝑝 (𝑥) ˆ 𝑝 2 (ˆ 𝑥)

を得る（対数和不等式の右辺の $𝑎 𝑗 l o g (𝑎 𝑗 / 𝑏 𝑗)$ では， $𝑎 𝑗$ と $𝑏 𝑗$ に掛かる $𝜆$ と $1 - 𝜆$ が対数の中で約分される）．

この不等式がどの対でも成り立てば，あとは足すだけである．定義 1.3.1 の和は同時分布が正である項についてとるもので，同時分布が $0$ である項の寄与は $0$ だから，上の不等式を $X \times ˆ X$ の全体で足し合わせると，左辺は $𝐼 (𝑝; 𝑞 𝜆)$ ，右辺は $𝜆 𝐼 (𝑝; 𝑞 1) + (1 - 𝜆) 𝐼 (𝑝; 𝑞 2)$ になる．

残るのは確率 $0$ の対で，そこでも同じ不等式が成り立つ．まず， $𝑏 𝑗 = 0$ となる $𝑗$ があれば，そこでは $𝑎 𝑗 = 0$ でもある．実際 $0 < 𝜆 < 1$ だから， $𝑏 𝑗 = 0$ は $𝑝 (𝑥) = 0$ または $ˆ 𝑝 𝑗 (ˆ 𝑥) = 0$ を意味する．前者なら $𝜋 𝑗 (𝑥, ˆ 𝑥) = 𝑝 (𝑥) 𝑞 𝑗 (ˆ 𝑥 ∣ 𝑥) = 0$ であり，後者なら $𝜋 𝑗 (𝑥, ˆ 𝑥)$ は非負の数の和 $ˆ 𝑝 𝑗 (ˆ 𝑥)$ の一項だからやはり $0$ である．したがって， $𝑏 𝑗 = 0$ である $𝑗$ を落としても $𝑎 1 + 𝑎 2$ と $𝑏 1 + 𝑏 2$ は変わらない．落とした $𝑗$ については $𝜋 𝑗 (𝑥, ˆ 𝑥) = 0$ だから，定義 1.3.1 の和でこの対が $𝐼 (𝑝; 𝑞 𝑗)$ に与える寄与も $0$ である．そこで $𝑏 𝑗 > 0$ である $𝑗$ だけを残して対数和不等式を当て，落とした $𝑗$ の項を右辺に $0$ として書き足せば，上と同じ不等式を得る．残る $𝑗$ が一つも無ければ $𝑎 1 = 𝑎 2 = 0$ ，すなわち $𝜋 1 (𝑥, ˆ 𝑥) = 𝜋 2 (𝑥, ˆ 𝑥) = 𝜋 𝜆 (𝑥, ˆ 𝑥) = 0$ となり，この対が不等式の両辺に与える寄与はどちらも $0$ である． $◻$

補題 9.2.2 が言っているのは，二つの再現の作り方を混ぜると，情報源との結びつきは混ぜる前の平均より強くならない，ということである．混ぜているのは $𝑞$ だけで，情報源の分布 $𝑝$ は固定していることに注意したい．不等号の向きは，相互情報量を隔たりとして読むと見える．定義 1.3.1 の式をそのまま読めば，相互情報量は同時分布と二つの周辺分布の積との相対エントロピー（1.6 節）であり，情報源と再現が独立からどれだけ離れているかを測っている．証明で対数和不等式を当てた位置を見ると，まとめているのは「どちらの作り方を使ったか」という区別である．対数和不等式が言うのは，区別を捨ててまとめると値が小さくなることだった（定理 1.7.1）．つまり，混ぜて区別を捨てた作り方が独立から隔たっている量は，二つの隔たりを同じ重みで混ぜた値を超えない．

形式化上の注記. 補題 9.2.2 にあたる宣言は無い．形式化は条件付き分布を混ぜる形をとらず，相対エントロピーが二つの引数について同時に凸であるという形（klDiv_joint_convex (InformationTheory/Shannon/RateDistortion/Convexity.lean)）で同じ役割を果たしている．

命題 9.2.3. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．実数 $𝐷 1$ ， $𝐷 2$ について $Q (𝐷 1)$ と $Q (𝐷 2)$ がどちらも空でないならば， $𝜆 \in [0, 1]$ に対して $Q (𝜆 𝐷 1 + (1 - 𝜆) 𝐷 2)$ も空でなく

𝑅 (𝜆 𝐷 1 + (1 - 𝜆) 𝐷 2) \leq 𝜆 𝑅 (𝐷 1) + (1 - 𝜆) 𝑅 (𝐷 2)

である．

証明. 命題 9.1.8 により， $𝐼 (𝑝; \cdot)$ を $Q (𝐷 1)$ の上で最小にする $𝑞 1$ と， $Q (𝐷 2)$ の上で最小にする $𝑞 2$ をとることができ， $𝑅 (𝐷 1) = 𝐼 (𝑝; 𝑞 1)$ ， $𝑅 (𝐷 2) = 𝐼 (𝑝; 𝑞 2)$ である． $𝑞 𝜆 : = 𝜆 𝑞 1 + (1 - 𝜆) 𝑞 2$ を補題 9.2.2 のとおりに定める．

$𝑞 𝜆$ が $Q (𝜆 𝐷 1 + (1 - 𝜆) 𝐷 2)$ に属することを見る．補題 9.2.2 より $𝑞 𝜆$ は条件付き分布である．定義 9.1.5 の期待歪みは $𝑞$ の成分について一次だから

\sum 𝑥, ˆ 𝑥 𝑝 (𝑥) 𝑞 𝜆 (ˆ 𝑥 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥) = 𝜆 \sum 𝑥, ˆ 𝑥 𝑝 (𝑥) 𝑞 1 (ˆ 𝑥 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥) + (1 - 𝜆) \sum 𝑥, ˆ 𝑥 𝑝 (𝑥) 𝑞 2 (ˆ 𝑥 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥)

であり， $𝜆 \geq 0$ と $1 - 𝜆 \geq 0$ より右辺は $𝜆 𝐷 1 + (1 - 𝜆) 𝐷 2$ 以下である．よって $𝑞 𝜆$ は制約を満たし，とくに $Q (𝜆 𝐷 1 + (1 - 𝜆) 𝐷 2)$ は空でない．

$𝑅 (\cdot)$ は値の集合の下限だから $𝑅 (𝜆 𝐷 1 + (1 - 𝜆) 𝐷 2) \leq 𝐼 (𝑝; 𝑞 𝜆)$ であり，補題 9.2.2 より

𝐼 (𝑝; 𝑞 𝜆) \leq 𝜆 𝐼 (𝑝; 𝑞 1) + (1 - 𝜆) 𝐼 (𝑝; 𝑞 2) = 𝜆 𝑅 (𝐷 1) + (1 - 𝜆) 𝑅 (𝐷 2)

である．二つを合わせて主張を得る． $◼$

命題 9.2.3 は，二つの歪みの上限のあいだを線形に補間した点で， $𝑅 (\cdot)$ の値が二つの端を結ぶ弦より下にあることを言っている．証明が使ったのは二つだけで， $𝐷 1$ と $𝐷 2$ で最小を与える作り方を混ぜると，期待歪みは二つの期待歪みを同じ重みで混ぜた値になり（期待歪みが $𝑞$ について一次だから），結びつきは二つの相互情報量の平均より強くならない（補題 9.2.2）ということである．

なぜ弦より下になると期待できるのかは，時間で分けてみると見当がつく．符号を定義するのは 9.5 節なので符号の話としてはまだ言えないが，長さ $𝑛$ のブロックのうち $𝜆$ の割合を歪み $𝐷 1$ 用の符号で，残りを歪み $𝐷 2$ 用の符号で処理したとする．歪みは成分についての平均だから全体で $𝜆 𝐷 1 + (1 - 𝜆) 𝐷 2$ になり， $1$ 文字あたりのレートも同じ重みの平均 $𝜆 𝑅 (𝐷 1) + (1 - 𝜆) 𝑅 (𝐷 2)$ になる．中間の歪みをこれだけのレートで実現する手立てが一つある以上，中間の点で弦より上には行きようがない，というわけである．

形式化: rateDistortionFunction_convexOn (ソース)

形式化上の注記. rateDistortionFunction_convexOn が述べているのも， $𝑅 (𝐷)$ を測度の言葉で書いた宣言 rateDistortionFunction (InformationTheory/Shannon/RateDistortion/Converse.lean) についての凸性で，定義 9.1.5 に紐付けた宣言とは別のものである．二つを結ぶ宣言は無い．あちらが与えるのも不等式だけで，混ぜた歪みの制約集合が空でないという命題 9.2.3 の結論の前半にあたる部分は含まれていない．値を拡張非負実数にとるので，制約を満たす同時分布が一つも無いときにも不等式のほうは成り立つからである．またこの宣言は，情報源の分布を第 $1$ 周辺にもつどの同時分布についても歪みが可積分である，という前提を受け取る．命題 9.2.3 が置いた有限のアルファベットのもとでは， $𝑑$ が有限個の値しかとらないのでこの前提は満たされるが，アルファベットを有限に固定した形の宣言は形式化には無い．

両端

残るは両端である．左の端では歪みをいっさい許さず，右の端では $𝑅 (\cdot)$ が $0$ になる．情報源アルファベットが再現アルファベットに含まれ，かつ歪み尺度が「 $0$ になるのは一致するときだけ」を満たすならば，左の端で $𝑅 (\cdot)$ はエントロピーに戻る．どちらも命題 9.2.4 の仮定に置く．歪み尺度の条件が落とせないことは，命題のあとで見る．

命題 9.2.4. $X$ と $ˆ X$ を空でない有限集合で $X \subseteq ˆ X$ を満たすものとし， $𝑝$ を $X$ 上の分布， $𝑋$ を分布 $𝑝$ に従う $X$ に値をとる確率変数とする．歪み尺度 $𝑑$ （定義 9.1.1）が「 $𝑑 (𝑥, ˆ 𝑥) = 0$ となるのは $ˆ 𝑥 = 𝑥$ のとき，かつそのときに限る」を満たすとし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．このとき $Q (0)$ は空でなく

𝑅 (0) = 𝐻 (𝑋)

である．

証明. $Q (0)$ が空でないことを見る． $X \subseteq ˆ X$ だから， $ˆ 𝑥 = 𝑥$ のとき $𝑞 (ˆ 𝑥 ∣ 𝑥) : = 1$ ，そうでないとき $𝑞 (ˆ 𝑥 ∣ 𝑥) : = 0$ と定めることができ，これは条件付き分布である．仮定より $𝑑 (𝑥, 𝑥) = 0$ だから，その期待歪みは $\sum 𝑥 𝑝 (𝑥) 𝑑 (𝑥, 𝑥) = 0$ であり， $𝑞 \in Q (0)$ である．

次に $Q (0)$ の元がどれも同じ相互情報量をもつことを見る． $𝑞 \in Q (0)$ とすると，期待歪み $\sum 𝑥, ˆ 𝑥 𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥)$ は $0$ 以下であり，各項は非負だから，すべての項が $0$ である．すなわち $𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥) > 0$ ならば $𝑑 (𝑥, ˆ 𝑥) = 0$ であり，仮定によりそれは $ˆ 𝑥 = 𝑥$ を意味する．よって $𝑝 (𝑥) > 0$ である $𝑥$ については， $𝑞 (ˆ 𝑥 ∣ 𝑥) > 0$ となる $ˆ 𝑥$ が $𝑥$ に限られ， $\sum ˆ 𝑥 𝑞 (ˆ 𝑥 ∣ 𝑥) = 1$ と合わせて $𝑞 (𝑥 ∣ 𝑥) = 1$ である．したがって $𝑞$ に対応する同時分布は， $ˆ 𝑥 = 𝑥$ のとき $𝑝 (𝑥)$ ，そうでないとき $0$ であり，第 $2$ 周辺分布は $ˆ 𝑥 \in X$ のとき $𝑝 (ˆ 𝑥)$ ，そうでないとき $0$ である．

その相互情報量を定義 1.3.1 で計算する．同時分布が正になるのは $ˆ 𝑥 = 𝑥$ かつ $𝑝 (𝑥) > 0$ のときだけで，そこでの値は $𝑝 (𝑥)$ ，二つの周辺分布の積は $𝑝 (𝑥) 𝑝 (𝑥)$ だから

𝐼 (𝑝; 𝑞) = \sum 𝑥 : 𝑝 (𝑥) > 0 𝑝 (𝑥) l o g 𝑝 (𝑥) 𝑝 (𝑥) 𝑝 (𝑥) = - \sum 𝑥 : 𝑝 (𝑥) > 0 𝑝 (𝑥) l o g 𝑝 (𝑥) = 𝐻 (𝑋)

である（最後の等号は， $𝑝 (𝑥) = 0$ の項を $0 l o g 0 = 0$ と約束した定義 1.1.1 による）．

値の集合が一点 ${𝐻 (𝑋)}$ なので，その下限は $𝐻 (𝑋)$ である． $◼$

歪み尺度の条件は落とせない．たとえば $𝑑$ が恒等的に $0$ なら，どの条件付き分布も $Q (0)$ に属するので， $ˆ X$ の一点に集中する条件付き分布をとれば，情報源と再現は独立になって相互情報量は $0$ になる．相互情報量は非負（命題 1.3.2）だから，このとき $𝑅 (0) = 0$ である． $𝐻 (𝑋) > 0$ である情報源では，これは命題 9.2.4 の結論と違う値である．落とせないのは条件そのもので，条件を課す範囲のほうには余地がある．証明が歪み尺度の条件を使うのは情報源が正の確率を与える文字についてだけなので，確率 $0$ の文字での条件は落としてよい．

命題 9.2.4 の値は，第2章定理 2.3.6 の $i n f R = 𝐻 (𝑋)$ と同じ $𝐻 (𝑋)$ である．ただし命題 9.2.4 が述べているのは最適化問題の値についてであって，符号については何も言っていない．二つを結ぶには $𝑅 (𝐷)$ が符号のレートの限界であることが要り，それが 9.5 節と 9.6 節の内容である．

形式化上の注記. 命題 9.2.4 にあたる宣言は無い．レート歪み関数とエントロピーを同じ主張の中で結ぶ宣言が形式化には無いためである．

命題 9.2.5（ $𝑅 (\cdot)$ が $0$ になる歪み）. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．

𝐷 m a x : = m i n ˆ 𝑥 \in ˆ X \sum 𝑥 \in X 𝑝 (𝑥) 𝑑 (𝑥, ˆ 𝑥)

とおくと， $Q (𝐷 m a x)$ は空でなく $𝑅 (𝐷 m a x) = 0$ である．さらに， $Q (𝐷)$ が空でない実数 $𝐷$ について， $𝑅 (𝐷) = 0$ となるのは $𝐷 \geq 𝐷 m a x$ のとき，かつそのときに限る．

証明. $ˆ X$ は空でない有限集合だから $𝐷 m a x$ は定まる．最小を与える点を一つとって $ˆ 𝑥 0$ と書き， $ˆ 𝑥 = ˆ 𝑥 0$ のとき $𝑞 0 (ˆ 𝑥 ∣ 𝑥) : = 1$ ，そうでないとき $𝑞 0 (ˆ 𝑥 ∣ 𝑥) : = 0$ と定める．これは条件付き分布であり，その期待歪みは $\sum 𝑥 𝑝 (𝑥) 𝑑 (𝑥, ˆ 𝑥 0) = 𝐷 m a x$ である．

$𝐷 \geq 𝐷 m a x$ ならば $𝑅 (𝐷) = 0$ であることを見る（ $𝐷 = 𝐷 m a x$ を含む）． $𝑞 0$ の期待歪みは $𝐷 m a x \leq 𝐷$ だから $𝑞 0 \in Q (𝐷)$ であり，とくに $Q (𝐷)$ は空でない． $𝑞 0$ に対応する同時分布は， $ˆ 𝑥 = ˆ 𝑥 0$ のとき $𝑝 (𝑥)$ ，そうでないとき $0$ であって，これは第 $1$ 周辺分布 $𝑝$ と， $ˆ 𝑥 0$ に $1$ を置く第 $2$ 周辺分布との積にほかならない．よって $𝑋$ と $ˆ 𝑋$ は独立で，命題 1.3.2 より $𝐼 (𝑝; 𝑞 0) = 0$ である．したがって $𝑅 (𝐷) \leq 0$ である．一方，命題 1.3.2 より $Q (𝐷)$ のどの元でも $𝐼 (𝑝; 𝑞) \geq 0$ だから， $0$ は値の集合の下界であり，下限はそれ以上である．二つを合わせて $𝑅 (𝐷) = 0$ を得る．

逆に， $Q (𝐷)$ が空でなく $𝑅 (𝐷) = 0$ とする．命題 9.1.8 より， $𝐼 (𝑝; 𝑞 *) = 𝑅 (𝐷) = 0$ を満たす $𝑞 * \in Q (𝐷)$ がある．命題 1.3.2 の等号条件より， $𝑞 *$ に対応する対 $(𝑋, ˆ 𝑋)$ は独立であり，同時分布は $𝑝 (𝑥) ˆ 𝑝 (ˆ 𝑥)$ である（ $ˆ 𝑝$ は第 $2$ 周辺分布）．よってその期待歪みは

\sum 𝑥, ˆ 𝑥 𝑝 (𝑥) ˆ 𝑝 (ˆ 𝑥) 𝑑 (𝑥, ˆ 𝑥) = \sum ˆ 𝑥 ˆ 𝑝 (ˆ 𝑥) (\sum 𝑥 𝑝 (𝑥) 𝑑 (𝑥, ˆ 𝑥)) \geq \sum ˆ 𝑥 ˆ 𝑝 (ˆ 𝑥) 𝐷 m a x = 𝐷 m a x

である（不等号は $𝐷 m a x$ が内側の和の最小値で $ˆ 𝑝$ が非負なこと，最後の等号は $\sum ˆ 𝑥 ˆ 𝑝 (ˆ 𝑥) = 1$ による）． $𝑞 * \in Q (𝐷)$ よりこの期待歪みは $𝐷$ 以下だから， $𝐷 \geq 𝐷 m a x$ である． $◼$

命題 9.2.5 により， $𝑅 (𝐷) = 0$ となる $𝐷$ のうち最小のものが $𝐷 m a x$ である．最小のものなのに $𝐷 m a x$ という最大を思わせる名前が付くのは，これが歪みを許す意味のある範囲の右端だからである．ここから先はいくら歪みを許しても値が $0$ のままで，見るべきものが残っていない． $𝑞 0$ のとり方が読み方を与える．情報源を見ずに，あらかじめ決めた一文字 $ˆ 𝑥 0$ をいつも出す，というのが「何も送らない」再現であり，その中でいちばん歪みの小さいものが払う歪みが $𝐷 m a x$ である．それより多くの歪みを許してよいなら，情報源について何も知らなくて済む．

形式化上の注記. 命題 9.2.5 にあたる宣言は無い． $𝐷 m a x$ を定める宣言も，レート歪み関数が $0$ になることを述べる宣言も，形式化には無い．最悪の歪み $m a x 𝑥, ˆ 𝑥 𝑑 (𝑥, ˆ 𝑥)$ を定める distortionMax (InformationTheory/Shannon/RateDistortion/AchievabilityAsymptoticFailureDecay.lean) はあるが，これは命題 9.2.5 の $𝐷 m a x$ とは別の量である．

両端で確かめる. 二値の情報源と Hamming 歪み（例 9.1.3）で，二つの端を見ておく． $X = ˆ X = {0, 1}$ とし， $P r [𝑋 = 1] = 𝜋$ とする．補題 9.2.2 の証明が同時分布を $𝜋 𝑗 (𝑥, ˆ 𝑥)$ と書いていて字が重なるが，あちらはつねに二つの引数をとるので，引数のない $𝜋$ はつねに二値情報源のパラメータである． $X = ˆ X$ であり， $𝑑 𝐻 (𝑥, ˆ 𝑥) = 0$ は $ˆ 𝑥 = 𝑥$ と同値だから，命題 9.2.4 の二つの仮定はどちらも満たされ， $𝑅 (0) = 𝐻 (𝑋) = 𝐻 𝑏 (𝜋)$ である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．右の端は， $ˆ 𝑥 = 0$ に対して $\sum 𝑥 𝑝 (𝑥) 𝑑 𝐻 (𝑥, 0) = 𝜋$ ， $ˆ 𝑥 = 1$ に対して $1 - 𝜋$ だから，命題 9.2.5 より $𝐷 m a x = m i n (𝜋, 1 - 𝜋)$ である．公平なコイン（ $𝜋 = 1 / 2$ ）なら $𝑅 (0) = 1$ ビット， $𝐷 m a x = 1 / 2$ になる．後者は，情報源を見ずにいつも $0$ を出せば文字の半分が食い違う，という勘定と合っている．

本節の四つを並べると， $𝑅 (\cdot)$ のグラフの形はかなり絞られる．命題 9.2.4 の仮定のもとでは， $𝐷 = 0$ で $𝐻 (𝑋)$ から始まり， $𝐷$ が増えるにつれて非増加で（命題 9.2.1）凸（命題 9.2.3）であり， $𝐷 m a x$ で $0$ に達して，その先は $0$ のままである（命題 9.2.5）．残っているのは両端のあいだの形だけで，9.3 節は二値の情報源についてそれを決める．9.4 節はアルファベットが実数値の場合で，本節の枠の外に出て量を定義し直したうえで，同じ形の答えを求める．

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