9.1 歪みとレート歪み関数

第2章と第3章は，情報源の出した列をそのまま復元できることを求めて，どこまで短く書けるかを問うた．その限界がエントロピーだった．ところが実際に圧縮したいものの多くは，そのまま復元しなくてよい．写真を保存するとき，隣り合う画素の値がもとの値から少しずれても，見る側は同じ写真として受け取る．音声も同じで，人の耳に届かない差は落としてよい．実数値をとる量にいたっては，有限個の符号語のどれかに割り当てる時点で，どこかで値を丸めることになる．そこで本章が問うのは，どれだけの誤りを許せばレートをどこまで下げられるか，である．

許す誤りの量は，情報源の文字と，その代わりに出す文字との組に数を与えて測る．この数を歪みと呼び，歪みの平均を $𝐷$ 以下に抑えるという条件のもとでレートの限界を与える量として，本章はレート歪み関数 $𝑅 (𝐷)$ を立てる．進め方は第8章と同じ二段構えにする．本節で $𝑅 (𝐷)$ を最適化問題の値として定義し，9.2 節から 9.4 節でその性質と具体例を調べ，そのうえで，それが符号についての限界でもあることを 9.5 節と 9.6 節で確かめる．

本章では $l o g$ の底を $2$ にとる．符号語の個数を $2$ の何乗として数える段（9.5 節と 9.6 節）で，指数と対数の底がそろっていると式が読みやすい．記号も一つ断っておく．本章の裸の $𝐷$ はつねに許す歪みの上限を指し，第4章 4.1 節が符号アルファベットの大きさに使う裸の $𝐷$ とも，第1章の相対エントロピー $𝐷 (𝑝 ‖ 𝑞)$ とも別である．

形式化上の注記（本章共通）. 単位は本文と形式化で違う．形式化は $l o g$ を自然対数にとるので，相互情報量もレート歪み関数もナットが単位である．本文が符号語の個数を $2$ の何乗として数えるところは，あちらでは $𝑒$ の何乗として数えることになる．底をそろえれば同じ主張である．

歪み尺度

定義 9.1.1（歪み尺度）. $X$ と $ˆ X$ を空でない有限集合とする．歪み尺度 とは，写像

𝑑 : X \times ˆ X ⟶ [0, \infty)

のことをいう． $X$ を 情報源アルファベット， $ˆ X$ を 再現アルファベット と呼び， $𝑑 (𝑥, ˆ 𝑥)$ を，情報源の文字 $𝑥$ の代わりに $ˆ 𝑥$ を出したときに払う歪みと呼ぶ．

歪み尺度は「どれだけ間違えたか」を数で決める約束である．何を損とみなすかは扱う対象で違うので，本書はその決め方に立ち入らず，決まったものとして受け取る．値が小さいほどよい再現で， $0$ は損がないことを表す． $𝐷$ 以下に抑える，という本章の条件は，この数の平均についての条件である．

距離ではない. 定義 9.1.1 が課しているのは非負であることだけで，対称性も三角不等式も課していない．そもそも二つのアルファベットは違ってよいので， $𝑑 (𝑥, ˆ 𝑥)$ と並べて $𝑑 (ˆ 𝑥, 𝑥)$ を書けるとは限らない．白を黒と読むときの損と，黒を白と読むときの損が等しいことも，定義 9.1.1 は要求しない．

形式化: DistortionFn (ソース)

形式化上の注記. 形式化の DistortionFn は歪みの値を非負の実数の型にとる．定義 9.1.1 が値域を $[0, \infty)$ と書いたのと同じことで，非負性が型から出る．

情報源は $1$ 文字ずつではなく，長さ $𝑛$ のブロックにまとめて扱う．ブロックの歪みは，成分ごとの歪みを平均して定める．

定義 9.1.2（ブロックの歪み）. $X$ ， $ˆ X$ ， $𝑑$ を定義 9.1.1 のとおりとし， $𝑛 \geq 1$ とする．列 $𝑥 𝑛 = (𝑥 0, \dots, 𝑥 𝑛 - 1) \in X 𝑛$ と $ˆ 𝑥 𝑛 = (ˆ 𝑥 0, \dots, ˆ 𝑥 𝑛 - 1) \in ˆ X 𝑛$ に対して，ブロックの歪み を

𝑑 (𝑥 𝑛, ˆ 𝑥 𝑛) : = 1 𝑛 𝑛 - 1 \sum 𝑖 = 0 𝑑 (𝑥 𝑖, ˆ 𝑥 𝑖)

で定める．

足すのではなく平均するのは， $1$ 文字あたりの歪みで測るためである．そうしておくと，ブロックの長さを変えても値の大きさがそろい， $𝑛$ を大きくする議論に乗る． $1$ 文字の歪みとブロックの歪みに同じ記号 $𝑑$ を使うが，引数が文字の対か列の対かで見分けられる．

形式化: blockDistortion (ソース)

例 9.1.3（Hamming 歪み）. $X$ を空でない有限集合とし， $ˆ X = X$ として

𝑑 𝐻 (𝑥, ˆ 𝑥) : = {0 (ˆ 𝑥 = 𝑥) 1 (ˆ 𝑥 \neq 𝑥)

と定める．この $𝑑 𝐻$ は歪み尺度（定義 9.1.1）であり， $𝑛 \geq 1$ と $𝑥 𝑛, ˆ 𝑥 𝑛 \in X 𝑛$ に対して，そのブロックの歪み（定義 9.1.2）は成分が食い違う位置の割合

𝑑 𝐻 (𝑥 𝑛, ˆ 𝑥 𝑛) = 1 𝑛 # {𝑖 \in {0, \dots, 𝑛 - 1} : ˆ 𝑥 𝑖 \neq 𝑥 𝑖}

に等しい．さらに $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ と $ˆ 𝑋 𝑛 = (ˆ 𝑋 0, \dots, ˆ 𝑋 𝑛 - 1)$ を $X 𝑛$ に値をとる確率変数の組とすると

𝔼 [𝑑 𝐻 (𝑋 𝑛, ˆ 𝑋 𝑛)] = 1 𝑛 𝑛 - 1 \sum 𝑖 = 0 P r [ˆ 𝑋 𝑖 \neq 𝑋 𝑖]

である．

証明. $𝑑 𝐻$ の値は $0$ と $1$ だけなので $[0, \infty)$ に入り， $𝑑 𝐻$ は歪み尺度である．定義 9.1.2 の和 $\sum 𝑖 𝑑 𝐻 (𝑥 𝑖, ˆ 𝑥 𝑖)$ は， $ˆ 𝑥 𝑖 \neq 𝑥 𝑖$ である $𝑖$ ごとに $1$ を，そうでない $𝑖$ には $0$ を足したものだから，食い違う位置の個数に等しい．これを $𝑛$ で割ったものが第 $1$ の等式である．

期待値に移る． $𝑑 𝐻 (𝑋 𝑖, ˆ 𝑋 𝑖)$ は事象 ${ˆ 𝑋 𝑖 \neq 𝑋 𝑖}$ の指示変数だから，その期待値は $P r [ˆ 𝑋 𝑖 \neq 𝑋 𝑖]$ である．第 $1$ の等式の右辺は $𝑛$ 個の指示変数の平均なので，期待値の線形性から第 $2$ の等式を得る． $◼$

Hamming 歪みは，一致したか否かだけを見る歪み尺度である．例 9.1.3 の第 $2$ の式が数えているのは成分ごとの食い違いであって，ブロック全体の一致ではない．第2章定義 2.3.1 の誤り確率はブロック全体が一致しない確率で，別の量である．Hamming 歪みを小さくするとは，食い違う文字の割合を小さくすることであって，ブロックをそのまま当てることではない．

形式化上の注記. Hamming 歪みにあたる宣言は無い．形式化には，歪み尺度を具体的にとった実例が一つも置かれていない．例 9.1.3 に付した証明が，この主張の保証のすべてである．

例 9.1.4（ $2$ 乗歪み）. $X = ˆ X = ℝ$ とし， $𝑑 (𝑥, ˆ 𝑥) : = (𝑥 - ˆ 𝑥) 2$ と定める．この $𝑑$ は非負の値をとり，定義 9.1.2 の式をそのまま当てると，ブロックの歪みは平均 $2$ 乗誤差 $1 𝑛 \sum 𝑛 - 1 𝑖 = 0 (𝑥 𝑖 - ˆ 𝑥 𝑖) 2$ になる．

$ℝ$ は有限集合ではないので，例 9.1.4 は定義 9.1.1 の枠の外にある．本節から 9.3 節までの定義と主張は有限のアルファベットについて述べるので， $2$ 乗歪みで測る情報源は 9.4 節で別に扱う．

レート歪み関数

歪み尺度が決まると，再現の良し悪しは数で比べられるようになる．次に決めたいのは，歪みを $𝐷$ 以下に抑えるのに，情報源についてどれだけのことを知る必要があるか，である．必要な量を測る物差しとして，本章は相互情報量をとる．情報源 $𝑋$ と，その再現 $ˆ 𝑋$ を対にして見たとき， $𝐼 (𝑋; ˆ 𝑋)$ は二つがどれだけ強く結びついているかを測る量だった（1.3 節）．再現が情報源と独立なら $𝐼 (𝑋; ˆ 𝑋) = 0$ であり，値が大きいほど強く結びついている（命題 1.3.2）．結びつきが弱いほど，再現の側で区別しなければならない情報源の列は少なく，番号を書き下すのに要るビット数も少なくて済む，というのが物差しにとる見当で，その筋は定義のあとに書く．歪みを $𝐷$ 以下に抑えるという条件を満たす再現の作り方のうち，いちばん弱い結びつきで済むものを探して，その結びつきの強さを $𝑅 (𝐷)$ と定める，というのが次の定義である．

定義 9.1.5（レート歪み関数）. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）， $𝐷$ を実数とする．条件付き分布 とは，各 $𝑥 \in X$ と各 $ˆ 𝑥 \in ˆ X$ に非負の実数 $𝑞 (ˆ 𝑥 ∣ 𝑥)$ を与える組であって，各 $𝑥$ について $\sum ˆ 𝑥 \in ˆ X 𝑞 (ˆ 𝑥 ∣ 𝑥) = 1$ を満たすもののことをいう．条件付き分布 $𝑞$ に対し， $(𝑋, ˆ 𝑋)$ を同時分布が $𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥)$ で与えられる対とし，その相互情報量（定義 1.3.1）を $𝐼 (𝑝; 𝑞)$ と書き，その 期待歪み を

𝔼 [𝑑 (𝑋, ˆ 𝑋)] = \sum 𝑥 \in X \sum ˆ 𝑥 \in ˆ X 𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥)

と書く．期待歪みが $𝐷$ 以下である条件付き分布の全体を $Q (𝐷)$ と書く． $Q (𝐷)$ が空でないとき，レート歪み関数 の値を

𝑅 (𝐷) : = i n f 𝑞 \in Q (𝐷) 𝐼 (𝑝; 𝑞)

で定める．

定義 9.1.5 が動かしているのは $𝑞$ だけである．情報源の分布 $𝑝$ と歪み尺度 $𝑑$ は与えられていて動かせない． $𝑞 (ˆ 𝑥 ∣ 𝑥)$ は「情報源が $𝑥$ を出したときに再現として $ˆ 𝑥$ を出す確率」であり， $\sum 𝑥, ˆ 𝑥 𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥) = \sum 𝑥 𝑝 (𝑥) = 1$ だから， $𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥)$ は確かに $X \times ˆ X$ 上の分布である．期待歪みは，その分布のもとで $𝑑$ を平均したものにほかならない．制約集合 $Q (𝐷)$ は「平均して $𝐷$ 以下の歪みしか出さない再現の作り方」の全体で， $𝑅 (𝐷)$ はその中で情報源と再現の結びつきをいちばん弱くしたときの，結びつきの強さである．記号 $𝐼 (𝑝; 𝑞)$ は第6章定義 6.1.2 の $𝐼 (𝑝; 𝑊)$ にならった．あちらが通信路を置いた位置に，こちらは再現の作り方 $𝑞$ を置く． $𝑞$ を決めるごとに対 $(𝑋, ˆ 𝑋)$ が定まるので， $𝐼 (𝑝; 𝑞)$ は $𝑞$ の関数である．

形式化: rateDistortionFunctionPmf，制約集合 RDConstraint，期待歪み expectedDistortionPmf (ソース)

形式化上の注記. 形式化の rateDistortionFunctionPmf が動かすのは条件付き分布ではなく，情報源の分布を第 $1$ 周辺にもつ $X \times ˆ X$ 上の同時分布である．条件付き分布に情報源の分布を掛けたものはそのような同時分布であり，逆にそのような同時分布はどれもこの形に書ける（情報源の分布が $0$ を与える文字での条件付き分布は一通りには決まらないが，その文字では同時分布のほうが $0$ になる）ので，下限をとる相手の集合は一致する．ただし下限をとる相手の量は，定義 1.3.1 の相互情報量とは別に立てた宣言 mutualInfoPmf (InformationTheory/Shannon/RateDistortion/Achievability.lean) で，エントロピーの差の形（定理 1.3.4 の第 $3$ の表現）で書かれている．両者を結ぶ宣言のうち，外から引けるものは無い（特定の環境測度についてエントロピーの差が mutualInfoPmf に等しいことを述べる宣言 rdAmbient_entropy_diff_eq_mutualInfoPmf (InformationTheory/Shannon/RateDistortion/AchievabilityStrongTypicality/SupportingBounds.lean) と，対の経験分布について mutualInfoPmf が定義 1.3.1 の相互情報量に一致することを述べる補題 mutualInfoPmf_empirical_eq_mutualInfo (InformationTheory/Shannon/WynerZiv/Operational.lean) はあるが，前者は一般の相互情報量とは結ばれておらず，後者はファイルの外から引ける宣言になっていない）．さらに形式化には，同じ $𝑅 (𝐷)$ を測度の言葉で書いた宣言 rateDistortionFunction (InformationTheory/Shannon/RateDistortion/Converse.lean) もある．こちらは値を拡張非負実数にとり，相互情報量を相対エントロピーの形で書く．二つの宣言を結ぶ宣言も無い．

定義 9.1.5 が置いた記号に，いちばん小さい情報源で値を入れてみる．

例 9.1.6（二値情報源での二つの再現の作り方）. $X = ˆ X = {0, 1}$ ， $𝑑$ を例 9.1.3 の Hamming 歪み $𝑑 𝐻$ とし， $𝜋 \in [0, 1]$ について $𝑝$ を $𝑝 (1) = 𝜋$ ， $𝑝 (0) = 1 - 𝜋$ で定まる $X$ 上の分布とする． $Q (\cdot)$ ， $𝐼 (𝑝; \cdot)$ ， $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．どの $𝑥 \in X$ についても $𝑞 0 (0 ∣ 𝑥) : = 1$ ， $𝑞 0 (1 ∣ 𝑥) : = 0$ と定める組 $𝑞 0$ と， $ˆ 𝑥 = 𝑥$ のとき $𝑞 i d (ˆ 𝑥 ∣ 𝑥) : = 1$ ，そうでないとき $𝑞 i d (ˆ 𝑥 ∣ 𝑥) : = 0$ と定める組 $𝑞 i d$ は，どちらも定義 9.1.5 の条件付き分布であり，次の三つが成り立つ（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）．

$𝑞 0$ の期待歪みは $𝜋$ であり， $𝐼 (𝑝; 𝑞 0) = 0$ である．
$𝑞 i d$ の期待歪みは $0$ であり， $𝐼 (𝑝; 𝑞 i d) = 𝐻 𝑏 (𝜋)$ である．
実数 $𝐷$ について， $𝐷 \geq 0$ ならば $Q (𝐷)$ は空でなく $𝑅 (𝐷) \leq 𝐻 𝑏 (𝜋)$ であり，さらに $𝐷 \geq 𝜋$ ならば $𝑅 (𝐷) = 0$ である．

証明. $𝑞 0$ も $𝑞 i d$ も値が非負で，どの $𝑥$ についても $ˆ 𝑥$ にわたる和が $1$ だから，条件付き分布である．

$𝑞 0$ に対応する同時分布は， $ˆ 𝑥 = 0$ のとき $𝑝 (𝑥)$ ， $ˆ 𝑥 = 1$ のとき $0$ である． $𝑑 𝐻 (0, 0) = 0$ と $𝑑 𝐻 (1, 0) = 1$ より，定義 9.1.5 の期待歪みは $𝑝 (1) = 𝜋$ である．この同時分布は，第 $1$ 周辺分布 $𝑝$ と， $0$ に $1$ を置く第 $2$ 周辺分布との積にほかならないから， $𝑞 0$ に対応する対 $(𝑋, ˆ 𝑋)$ は独立であり，命題 1.3.2 より $𝐼 (𝑝; 𝑞 0) = 0$ である．
$𝑞 i d$ に対応する同時分布は， $ˆ 𝑥 = 𝑥$ のとき $𝑝 (𝑥)$ ，そうでないとき $0$ であり，二つの周辺分布はどちらも $𝑝$ である． $𝑑 𝐻 (𝑥, 𝑥) = 0$ だから期待歪みは $0$ である．相互情報量を定義 1.3.1 で計算する．同時分布が正になるのは $ˆ 𝑥 = 𝑥$ かつ $𝑝 (𝑥) > 0$ のときだけで，そこでの値は $𝑝 (𝑥)$ ，二つの周辺分布の積は $𝑝 (𝑥) 𝑝 (𝑥)$ だから

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

である． $𝑝 (𝑥) = 0$ の項を $0 l o g 0 = 0$ と約束した定義 1.1.1 のもとで，右辺は $- 𝜋 l o g 𝜋 - (1 - 𝜋) l o g (1 - 𝜋)$ ，すなわち例 1.1.2 の $𝐻 𝑏 (𝜋)$ に等しい．

$𝑞 i d$ の期待歪みは $0$ だから， $𝐷 \geq 0$ ならば $𝑞 i d \in Q (𝐷)$ であり，とくに $Q (𝐷)$ は空でない． $𝑅 (𝐷)$ は値の集合 ${𝐼 (𝑝; 𝑞) : 𝑞 \in Q (𝐷)}$ の下限で， $𝐻 𝑏 (𝜋) = 𝐼 (𝑝; 𝑞 i d)$ はその元だから $𝑅 (𝐷) \leq 𝐻 𝑏 (𝜋)$ である． $𝐷 \geq 𝜋$ ならば $𝑞 0$ の期待歪みも $𝐷$ 以下だから $𝑞 0 \in Q (𝐷)$ であり，同じ理由で $𝑅 (𝐷) \leq 𝐼 (𝑝; 𝑞 0) = 0$ である．いっぽう命題 1.3.2 よりこの値の集合のどの元も非負だから $0$ はその下界であり，下限は下界のうち最大のものだから $𝑅 (𝐷) \geq 0$ である．二つを合わせて $𝑅 (𝐷) = 0$ を得る．

$◼$

二つは両極である． $𝑞 0$ は情報源を見ずにいつも $0$ を出す作り方で，情報源との結びつきがまったく無い代わりに， $1$ が出るたびに歪みを払う． $𝑞 i d$ は情報源をそのまま写す作り方で，歪みを払わない代わりに，結びつきの強さが情報源のエントロピーいっぱいになる．どちらが $Q (𝐷)$ に入るかは $𝐷$ をどこに置くかで変わり，例 9.1.6 の第 $3$ の主張が言っているのは， $𝐷$ が $𝜋$ 以上なら $𝑞 0$ も入って下限が $0$ まで落ちる，ということである． $𝐷$ をそれより小さくとったときに下限がどこにあるかは，本節では決めない．二値の情報源と Hamming 歪みについての答えは 9.3 節で与える．

なぜ最小にする量が相互情報量なのか，見当だけ先に書いておく．歪みを許さない第2章では，再現は $𝑋$ そのものであり，そのときの結びつきの強さは $𝐼 (𝑋; 𝑋) = 𝐻 (𝑋)$ である（1.3 節）．第2章が要したレートもちょうど $𝐻 (𝑋)$ だった（定理 2.3.6）．再現を $𝑋$ からずらすことを許したとき，同じ量が $𝐼 (𝑋; ˆ 𝑋)$ になる．歪みを許すなら，一つの番号に一つの系列を対応させるのではなく，一本の再現の列に，そこから歪みの小さい情報源の列をまとめて引き受けさせればよく，書き下す番号はそのぶん減る．どれだけ減るかの勘定は 9.6 節で書く．

ここまでは見当であって，符号の話は一つも入っていない．いまのところ $𝑅 (𝐷)$ は最適化問題の値でしかなく，第6章定義 6.1.4 の通信路容量と同じ立場にある．したがって「歪みを $𝐷$ 以下に抑えるには $1$ 文字あたり $𝑅 (𝐷)$ ビットで済む」と言う資格は，9.4 節までの段階ではない．その資格を与えるのが 9.5 節と 9.6 節で，前者は歪みを $𝐷$ 以下に抑える符号のレートが $𝑅 (𝐷)$ を下回れないことを示す．後者は，期待歪みが $𝐷$ より小さい再現の作り方があるかぎり， $𝑅 (𝐷)$ より大きいレートをとれば，長さを十分大きくとって歪みを $𝐷$ 以下に抑える符号が作れることを，一つの主張を借りて確かめる．

$𝐷$ を小さくとりすぎると $Q (𝐷)$ は空になり， $𝑅 (𝐷)$ は定まらない．どこから空でなくなるかは，歪み尺度と情報源で決まる．

命題 9.1.7（制約集合が空でない歪み）. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）とし， $Q (\cdot)$ を定義 9.1.5 のとおりとする．実数 $𝐷$ について， $Q (𝐷)$ が空でないのは

𝐷 \geq \sum 𝑥 \in X 𝑝 (𝑥) m i n ˆ 𝑥 \in ˆ X 𝑑 (𝑥, ˆ 𝑥)

のとき，かつそのときに限る．

証明. $ˆ X$ は空でない有限集合だから，各 $𝑥$ について $ˆ 𝑥 \mapsto 𝑑 (𝑥, ˆ 𝑥)$ の最小値は定まる．右辺の値を $𝐷 *$ と書く．

$𝐷 \geq 𝐷 *$ ならば $Q (𝐷)$ が空でないことを見る．各 $𝑥$ について $𝑑 (𝑥, ˆ 𝑥)$ を最小にする $ˆ 𝑥$ を一つ選び，選んだ点に $1$ を， $ˆ X$ のほかの点に $0$ を与える組を $𝑞$ とする．値は非負で，各 $𝑥$ について $ˆ 𝑥$ にわたる和は $1$ だから， $𝑞$ は定義 9.1.5 の条件付き分布である．定義 9.1.5 の期待歪みの和で残るのは，各 $𝑥$ について選んだ点の項だけだから，その値は各 $𝑥$ での最小値を $𝑝$ で平均したもの，すなわち $𝐷 *$ である． $𝐷 * \leq 𝐷$ だから $𝑞 \in Q (𝐷)$ であり， $Q (𝐷)$ は空でない．

逆に $Q (𝐷)$ が空でないとして， $𝑞 \in Q (𝐷)$ を一つとる．どの対 $(𝑥, ˆ 𝑥)$ についても $𝑑 (𝑥, ˆ 𝑥) \geq m i n ˆ 𝑥' \in ˆ X 𝑑 (𝑥, ˆ 𝑥')$ であり，重み $𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥)$ は非負だから

\sum 𝑥, ˆ 𝑥 𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥) \geq \sum 𝑥, ˆ 𝑥 𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥) m i n ˆ 𝑥' \in ˆ X 𝑑 (𝑥, ˆ 𝑥') = \sum 𝑥 𝑝 (𝑥) m i n ˆ 𝑥' \in ˆ X 𝑑 (𝑥, ˆ 𝑥') = 𝐷 *

である（第 $1$ の等号は，各 $𝑥$ について $\sum ˆ 𝑥 𝑞 (ˆ 𝑥 ∣ 𝑥) = 1$ であることによる）．左辺は $𝑞$ の期待歪みであり， $𝑞 \in Q (𝐷)$ よりこれは $𝐷$ 以下だから， $𝐷 \geq 𝐷 *$ である． $◼$

形式化上の注記. 命題 9.1.7 にあたる宣言は無い．形式化では，制約集合が空でないことは達成可能性の宣言や最小値の存在の宣言が受け取る仮定として現れるだけで，どの $𝐷$ からそれが成り立つかを述べる宣言は無い．

そこで本章の主張は， $Q (𝐷)$ が空でないことを仮定に置くか，そうでないものは空でないこと自体を結論に含める．9.2 節は， $𝐷 = 0$ での値と， $𝑅 (𝐷)$ が $0$ になる歪みの両方を扱う．

下限は最小値である

定義 9.1.5 は $𝑅 (𝐷)$ を下限として定めたが，実際には最小値である．示すには，制約集合が有界閉集合であることと，その上で $𝐼 (𝑝; \cdot)$ が連続であることの二つが要る．前者は制約の書き方から出る．後者は，一次結合・合成・有限和が連続性を保つという微積分の計算規則（これは既知とする）と，1.1 節で認めた $𝜑 (𝑡) = - 𝑡 l o g 𝑡$ の $[0, \infty)$ 上の連続性から組み立てる．そのうえで，最大値の存在を引き出すために次の一つを証明せずに借りる．

Weierstrass の最大値定理を借りる. 借りるのは「有限次元の実ベクトル空間の空でない有界閉集合の上の実数値連続関数は最大値をとる」という形である．当てる相手は，実ベクトル空間 $ℝ X \times ˆ X$ の部分集合である制約集合 $Q (𝐷)$ （定義 9.1.5）の上の，実数値関数 $𝑞 \mapsto - 𝐼 (𝑝; 𝑞)$ である．この借用に依存するのは命題 9.1.8 だけで，以降の節は命題 9.1.8 の結論だけを使う．第6章 6.1 節が通信路容量の達成（定理 6.1.5）のために借りたのと同じ定理である．本書はこの最大値定理を証明しないが，形式化されていないわけではない．命題 9.1.8 の形式化は，Mathlib にある無条件の機械検証済みのこの定理をそのまま呼び出しているからである．

命題 9.1.8. $X$ と $ˆ X$ を空でない有限集合， $𝑝$ を $X$ 上の分布， $𝑑$ を歪み尺度（定義 9.1.1）， $𝐷$ を実数とし， $Q (𝐷)$ ， $𝐼 (𝑝; \cdot)$ ， $𝑅 (𝐷)$ を定義 9.1.5 のとおりとする． $Q (𝐷)$ が空でないならば， $𝐼 (𝑝; \cdot)$ を $Q (𝐷)$ の上で最小にする $𝑞 * \in Q (𝐷)$ が存在し， $𝑅 (𝐷) = 𝐼 (𝑝; 𝑞 *)$ である．

証明. $Q (𝐷)$ の元は各 $(𝑥, ˆ 𝑥)$ に実数を割り当てる組だから， $Q (𝐷)$ は実ベクトル空間 $ℝ X \times ˆ X$ の部分集合である．これが有界閉集合であることを見る．各成分の非負性と，各 $𝑥$ についての $\sum ˆ 𝑥 𝑞 (ˆ 𝑥 ∣ 𝑥) = 1$ から $0 \leq 𝑞 (ˆ 𝑥 ∣ 𝑥) \leq 1$ なので有界である． $Q (𝐷)$ を定める三つの条件（各成分が非負であること，各 $𝑥$ について和が $1$ であること，期待歪みが $𝐷$ 以下であること）は，どれも $𝑞$ の成分の一次式についての等式と不等式だから， $Q (𝐷)$ は閉である．

$𝑞 \mapsto 𝐼 (𝑝; 𝑞)$ が $Q (𝐷)$ の上で連続であることを見る． $𝑞$ に対応する対 $(𝑋, ˆ 𝑋)$ の同時分布は $𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥)$ ，第 $1$ 周辺分布は $𝑝$ ，第 $2$ 周辺分布は $ˆ 𝑥 \mapsto \sum 𝑥 𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥)$ である．これに定理 1.3.4 を当てると $𝐼 (𝑝; 𝑞) = 𝐻 (𝑋) + 𝐻 (ˆ 𝑋) - 𝐻 (𝑋, ˆ 𝑋)$ であり，定義 1.1.1 と定義 1.2.1 により三つの項は

𝐻 (𝑋) = \sum 𝑥 𝜑 (𝑝 (𝑥)), 𝐻 (ˆ 𝑋) = \sum ˆ 𝑥 𝜑 (\sum 𝑥 𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥)), 𝐻 (𝑋, ˆ 𝑋) = \sum 𝑥, ˆ 𝑥 𝜑 (𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥))

と書ける（ $𝜑 (𝑡) = - 𝑡 l o g 𝑡$ は 1.1 節の記号である）．第 $1$ 項は $𝑞$ を含まない定数であり，残る二つはどちらも， $𝑞$ の成分の一次結合に $𝜑$ を合成したものの有限和である．既知とした計算規則と，1.1 節で認めた $𝜑$ の連続性により， $𝑞 \mapsto 𝐼 (𝑝; 𝑞)$ は $Q (𝐷)$ の上で連続である．

最小値の存在に移る． $- 𝐼 (𝑝; \cdot)$ も同じ理由で $Q (𝐷)$ の上で連続だから，空でない有界閉集合の上のこの関数に，借りた Weierstrass の最大値定理を当てると，最大値を与える点 $𝑞 *$ が存在する．そこで $𝐼 (𝑝; \cdot)$ は最小値をとる．

最後に $𝑅 (𝐷) = 𝐼 (𝑝; 𝑞 *)$ を見る． $𝐼 (𝑝; 𝑞 *)$ は値の集合 ${𝐼 (𝑝; 𝑞) : 𝑞 \in Q (𝐷)}$ の下界であり，かつその集合の元でもある．下限は下界のうち最大のものだから，この二つから $𝑅 (𝐷) = 𝐼 (𝑝; 𝑞 *)$ である． $◼$

形式化: rateDistortionFunctionPmf_attained (ソース)

形式化上の注記. rateDistortionFunctionPmf_attained が与えるのは，制約集合の上で最小を与える点が存在するところまでで， $𝑅 (𝐷)$ がその点での値に等しいという命題 9.1.8 の後半に対応する単独の宣言は無い．後半は，最小を与える点の存在（rateDistortionFunctionPmf_attained）と， $𝑅 (𝐷)$ が値の集合の下限として定義されていること（rateDistortionFunctionPmf (InformationTheory/Shannon/RateDistortion/Achievability.lean)）との合成で得られる．また，あちらが動かすのは条件付き分布ではなく，情報源の分布を第 $1$ 周辺にもつ同時分布であり，最小にする量も定義 1.3.1 の相互情報量とは別に立てた宣言である．証明の筋は本文と同じで，制約集合がコンパクトであることと，最小にする量が連続であることを組み合わせている．

命題 9.1.8 により， $Q (𝐷)$ が空でないかぎり，以降は $𝑅 (𝐷)$ を最小値として扱ってよい．そのような $𝐷$ ごとに，最小を与える条件付き分布 $𝑞 *$ が一つとれる，ということでもある．どの $𝑞 *$ がとれるかは $𝐷$ によって違い， $𝐷$ を動かしたときに $𝑅 (𝐷)$ の値がどう動くかが次節の主題である．

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