14.4 副情報つきレート歪み

第9章は，情報源 $𝑋$ を歪み $𝐷$ 以下で再現する符号のレートが $𝑅 (𝐷)$ を下回れないこと（定理 9.5.4）と， $𝐷$ より小さい歪みで済む再現の作り方があるなら $𝑅 (𝐷)$ より大きいレートでそういう符号がとれること（系 9.6.1）を見た（ $𝑅 (𝐷)$ の定義は定義 9.1.5）．本節はそこに， $𝑋$ と相関する別の情報源 $𝑌$ を持ち込む．ただし $𝑌$ を見られるのは復号する側だけで，符号化する側は見られない．前節は二つの情報源をどちらもそのまま復元することを求めたが，ここでは片方の $𝑌$ を圧縮せずに復号器へ渡し，もう片方の $𝑋$ を歪みを許して再現する．問うのは， $𝑌$ が復号側にあるぶんレートをどこまで下げられるか，である．

本節はまず，この設定に対応する量 $𝑅 W Z (𝐷)$ を，第9章定義 9.1.5 と同じく最適化問題の値として立てる．そのうえで，それが符号についての限界でもあることを，逆定理と達成可能性の二つを借りて確かめる．第9章の $𝑅 (𝐷)$ との関係は命題 14.4.7 で述べる．

記号を二つ断っておく．第一に，本節は補助変数として $𝑈$ を置く． $𝑈$ の字は本書ですでに三通りに使われていて，第7章例 7.3.5 が区間 $[0, 1]$ 上の一様分布に従う確率変数に，第9章 9.6 節が第6章の通信路の入力を表す確率変数に，第10章 10.1 節と第11章 11.2 節・11.6 節が一様分布そのものに使っている．三つめは分布であって確率変数ではないが，前の二つは本節の $𝑈$ と同じく確率変数で，しかも第7章のものは微分エントロピー $ℎ (\cdot)$ の，第9章のものは相互情報量の引数に置かれるので，引数の形では見分けられない．二つともそれぞれの節の中で閉じた記号であり，本節の $𝑈$ はそのどれでもなく，定義 14.4.3 が置く補助変数である．第13章の万能機械 $U$ は字体が違う（その字体は 14.5 節と 14.6 節が，補助変数のとるアルファベットの名前に使う）．第二に，本節の $𝑑$ は第9章定義 9.1.1 から引き継いだ歪み尺度であって，14.1 節と 14.3 節が共同復号器に使った $𝑑$ とは別である．本節では符号の復号写像を，第9章定義 9.5.1 にならって $𝑔$ と書く．

副情報つき符号

定義 14.4.1（副情報つき符号）. $X$ ， $Y$ ， $ˆ X$ を空でない有限集合， $𝑑$ を $X \times ˆ X$ の上の歪み尺度（定義 9.1.1）， $𝑛 \geq 1$ ， $𝑀 \geq 1$ とする．長さ $𝑛$ ，符号語数 $𝑀$ の 副情報つき符号 とは，符号化写像 $𝑐 : X 𝑛 \to {1, \dots, 𝑀}$ と復号写像 $𝑔 : {1, \dots, 𝑀} \times Y 𝑛 \to ˆ X 𝑛$ の組 $(𝑐, 𝑔)$ のことをいう．その レート を $1 𝑛 l o g 𝑀$ で定める．さらに $𝑝$ を $X \times Y$ 上の分布とし， $((𝑋 𝑖, 𝑌 𝑖)) 0 \leq 𝑖 < 𝑛$ をどれも $𝑝$ に従い互いに独立な対の組として $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝑌 𝑛 : = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ と書くとき，この符号の 期待ブロック歪み を

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

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

第9章定義 9.5.1 のレート歪み符号との違いは一つだけである．あちらの復号写像は番号だけを受け取ったが，こちらは番号と $𝑌 𝑛$ の両方を受け取る．符号化写像のほうは $𝑋 𝑛$ しか受け取らず， $𝑌 𝑛$ を見ない．この非対称が本節の主題で，圧縮する人は副情報を持たず，復元する人だけが持つ．期待ブロック歪みを定めるところで情報源を i.i.d. に限っている点も違う．第9章定義 9.5.1 は，成分の分布に条件を置かない一般の $𝑋 𝑛$ に対して期待歪みを定めていた．

形式化: 符号 WynerZivCode，期待ブロック歪み expectedBlockDistortion (ソース)

定義 14.4.2（達成可能なレート）. $X$ ， $Y$ ， $ˆ X$ ， $𝑑$ を定義 14.4.1 のとおりとし， $𝑝$ を $X \times Y$ 上の分布， $𝑅$ と $𝐷$ を実数とする． $𝑅$ が歪み $𝐷$ で 達成可能 であるとは，各 $𝑛 \geq 1$ について符号語数 $𝑀 𝑛 \geq 1$ の長さ $𝑛$ の副情報つき符号（定義 14.4.1）がとれて，次の二つが成り立つことをいう．第一に $1 𝑛 l o g 𝑀 𝑛 \to 𝑅$ である．第二に，任意の $𝜀 > 0$ に対してある $𝑁 \geq 1$ があって， $𝑁 \leq 𝑛$ を満たすすべての $𝑛$ で，その長さの符号の期待ブロック歪みが $𝐷 + 𝜀$ 以下である．

歪みの側に $𝜀$ の余裕が付いているのは，第9章 9.6 節が借りた レート歪み理論の達成可能性 と同じ形である．レートのほうは $𝑅$ 以上ではなく $𝑅$ への収束を求めていて，14.1 節定義 14.1.3 が $1 𝑛 l o g 𝑀 𝑗 \geq 𝑅 𝑗$ と書いたのとは形が違う．符号の族に対して定めている点は定義 14.1.3 と同じである．

形式化: WynerZivAchievable (ソース)

副情報つきレート歪み関数

第9章定義 9.1.5 は，情報源から再現への条件付き分布 $𝑞 (ˆ 𝑥 ∣ 𝑥)$ を動かして，歪みの制約のもとで $𝐼 (𝑝; 𝑞)$ をいちばん小さくした．同じことを副情報つきの設定でやりたいが， $𝑞$ をそのまま動かすわけにはいかない．符号化する側は $𝑌$ を見られないので，再現を直接作らせるとその制約が落ちてしまう．そこで，符号化する側が作れるものと，復号する側が作れるものを二段に分ける．前者が補助変数で， $𝑋$ だけから作る．後者が再現で，補助変数と副情報の両方から作る．

定義 14.4.3（副情報つきレート歪み関数）. $X$ ， $Y$ ， $ˆ X$ ， $𝑑$ を定義 14.4.1 のとおりとし， $𝑝$ を $X \times Y$ 上の分布， $𝐷$ を実数とする．正の整数 $𝑘$ と， $X$ から ${1, \dots, 𝑘}$ への条件付き分布 $𝑞$ （定義 9.1.5 の意味で，各 $𝑥$ について $𝑞 (𝑢 ∣ 𝑥) \geq 0$ かつ $\sum 𝑘 𝑢 = 1 𝑞 (𝑢 ∣ 𝑥) = 1$ ）と，再現関数 $𝑓 : {1, \dots, 𝑘} \times Y \to ˆ X$ の三つ組 $(𝑘, 𝑞, 𝑓)$ を考える．この三つ組が定める $X \times Y \times {1, \dots, 𝑘}$ 上の分布を

𝑝 (𝑥, 𝑦, 𝑢) : = 𝑝 (𝑥, 𝑦) 𝑞 (𝑢 ∣ 𝑥)

とし， $(𝑋, 𝑌, 𝑈)$ をこの分布に従う三つ組とする．三つ組 $(𝑘, 𝑞, 𝑓)$ が 実行可能 であるとは

𝔼 [𝑑 (𝑋, 𝑓 (𝑈, 𝑌))] \leq 𝐷

が成り立つことをいう．三つ組を一つ決めるごとに実数 $𝐼 (𝑋; 𝑈) - 𝐼 (𝑌; 𝑈)$ が定まる（定義 1.3.1）．実行可能な三つ組が少なくとも一つあるとき，副情報つきレート歪み関数 の値 $𝑅 W Z (𝐷)$ を，この実数の実行可能な三つ組すべてにわたる下限として定め，実行可能な三つ組が一つも無いときは $𝑅 W Z (𝐷) : = 0$ と約束する．

定義 14.4.3 が動かしているのは三つ組 $(𝑘, 𝑞, 𝑓)$ だけである．情報源の分布 $𝑝$ と歪み尺度 $𝑑$ は与えられていて動かせない．三つ組が定める分布の $(𝑥, 𝑦)$ についての周辺は，各 $𝑥$ について $\sum 𝑢 𝑞 (𝑢 ∣ 𝑥) = 1$ だから $𝑝 (𝑥, 𝑦)$ そのものであり，同じ記号 $𝑝$ を引数の並びで使い分ける定義 1.2.2 の慣用と食い違わない．実行可能な三つ組があるとき，その下限が実数として定まるのは目的の値が $0$ を下回らないからで，それを与えるのは次の補題 14.4.4 である．

条件付き分布 $𝑞 (𝑢 ∣ 𝑥)$ が $𝑦$ によらないところに，符号化する側が $𝑌$ を見られないことが書き込まれている．補助変数 $𝑈$ は $𝑋$ だけから作られる．いっぽう再現関数 $𝑓 (𝑢, 𝑦)$ は $𝑦$ を引数にとるので，復号する側が副情報を持つことは $𝑓$ の側に書き込まれている．目的の値の第 $1$ 項 $𝐼 (𝑋; 𝑈)$ は，第9章定義 9.1.5 が歪みの制約のもとで最小にした相互情報量と同じ立場の量で， $𝑋$ について送る量を測る．第 $2$ 項が副情報のぶんの値引きで， $𝑈$ のうち $𝑌$ からも分かってしまう部分は送らなくてよい，と読める．値引きがちょうど $𝐼 (𝑌; 𝑈)$ なのはなぜか，という問いには，本節の終わりで借りる 副情報つきレート歪みの達成可能性 の筋書きが答える．そこでは，補助変数の側の符号語の番号を箱に投げ込み，箱の中から $𝑌 𝑛$ に合う一本を復号器に選ばせる段として出てくる．

実行可能な三つ組が一つも無いときに置いた $0$ は，下限の値ではない．下限をとる相手の集合が空で下限が定まらないので，値を一つ決めておくための約束である．したがってその場合の $𝑅 W Z (𝐷)$ を「歪み $𝐷$ で済ませるのに要るレート」と読んではいけない．命題 14.4.5 はこの場合も込みで述べるが，そこで示すのは約束の値が $0$ 以上だということだけである．レートの大きさを実際に問う命題 14.4.6，命題 14.4.7，例 14.4.8，例 14.4.10，および本節の終わりで借りる達成可能性は，どれも実行可能な三つ組があることを仮定に置くか結論に含めるかしている．

形式化: wynerZivRate (ソース)

形式化上の注記（本節共通）. 形式化は補助変数のとる値の集合を ${1, \dots, 𝑘}$ の形のものに限り， $𝑘$ を $0$ も含めて動かす． $𝑘 = 0$ のときは各 $𝑥$ についての和が $1$ になる条件付き分布がとれないので実行可能な三つ組が無く，下限をとる相手の集合には何も加わらない．したがって下限をとる範囲は定義 14.4.3 と同じである．また，目的の値の二つの項は，定義 1.3.1 の相互情報量とは別に立てた宣言 wzMutualInfoXU，wzMutualInfoYU (InformationTheory/Shannon/WynerZiv/Basic.lean) で，エントロピーの差の形（定理 1.3.4 の第 $3$ の表現）に書かれている．第9章定義 9.1.5 の側でも，下限をとる相手の相互情報量は同じくエントロピーの差の形で書かれた別の宣言である．以下で本節が名指しする宣言のうち，目的の値を扱うものはどれもこの二つの量で書かれている．

補題 14.4.4. $X$ と $Y$ を空でない有限集合， $𝑝$ を $X \times Y$ 上の分布， $𝑘$ を正の整数， $𝑞$ を $X$ から ${1, \dots, 𝑘}$ への条件付き分布（定義 9.1.5）とし， $(𝑋, 𝑌, 𝑈)$ を定義 14.4.3 の分布 $𝑝 (𝑥, 𝑦) 𝑞 (𝑢 ∣ 𝑥)$ に従う三つ組とする．このとき $𝑌 \to 𝑋 \to 𝑈$ はマルコフ連鎖（定義 1.8.3）であり，

𝐼 (𝑌; 𝑈) \leq 𝐼 (𝑋; 𝑈)

である．

証明. マルコフ連鎖であることを見る．定義 1.8.3 は $𝑌 \to 𝑋 \to 𝑈$ を， $𝑋$ を与えたときの $𝑌$ と $𝑈$ の条件付き独立として定めている． $𝑋$ の周辺分布 $𝑝 (𝑥) = \sum 𝑦 𝑝 (𝑥, 𝑦)$ が正であるような $𝑥$ を一つ固定する．三つ組の分布の作り方から

𝑝 (𝑦, 𝑢 ∣ 𝑥) = 𝑝 (𝑥, 𝑦) 𝑞 (𝑢 ∣ 𝑥) 𝑝 (𝑥) = 𝑝 (𝑦 ∣ 𝑥) 𝑞 (𝑢 ∣ 𝑥)

である．この等式を $𝑦$ について足すと，各 $𝑥$ について $\sum 𝑦 𝑝 (𝑦 ∣ 𝑥) = 1$ だから $𝑝 (𝑢 ∣ 𝑥) = 𝑞 (𝑢 ∣ 𝑥)$ を得る．これを上の等式に戻すと $𝑝 (𝑦, 𝑢 ∣ 𝑥) = 𝑝 (𝑦 ∣ 𝑥) 𝑝 (𝑢 ∣ 𝑥)$ であり，これが定義 1.8.3 の条件そのものである．

不等式に移る．いま示した連鎖 $𝑌 \to 𝑋 \to 𝑈$ にデータ処理不等式（定理 1.8.4）を当てると $𝐼 (𝑌; 𝑈) \leq 𝐼 (𝑋; 𝑈)$ である． $◻$

形式化: マルコフ連鎖であること wzFactorizable_isMarkovChain，不等式 wzObjective_nonneg_of_factorizable (ソース)

定義 1.8.3 は両端について対称だから， $𝑌 \to 𝑋 \to 𝑈$ は $𝑈 \to 𝑋 \to 𝑌$ とも書ける．後者の向きで読むと，補助変数が $𝑌$ とつながるのは $𝑋$ を通ってだけである，という定義 14.4.3 の作り方がそのまま絵になる．不等式のほうは， $𝑈$ が $𝑋$ について持っている情報のうち $𝑌$ に届くのはその一部だけだ，と読める．目的の値 $𝐼 (𝑋; 𝑈) - 𝐼 (𝑌; 𝑈)$ が負にならないのはこのためで，次の命題はそれを $𝑅 W Z$ の側へ移したものである．

命題 14.4.5. $X$ ， $Y$ ， $ˆ X$ ， $𝑑$ を定義 14.4.1 のとおりとし， $𝑝$ を $X \times Y$ 上の分布， $𝐷$ を実数とする． $𝑅 W Z (\cdot)$ を定義 14.4.3 のとおりとすると $0 \leq 𝑅 W Z (𝐷)$ である．

証明. 実行可能な三つ組が一つも無いときは，定義 14.4.3 の約束により $𝑅 W Z (𝐷) = 0$ だから主張が成り立つ．少なくとも一つあるときは，補題 14.4.4 よりどの三つ組でも目的の値 $𝐼 (𝑋; 𝑈) - 𝐼 (𝑌; 𝑈)$ が $0$ 以上だから， $0$ は値の集合の下界であり，下限は下界のうち最大のものだから $𝑅 W Z (𝐷) \geq 0$ である． $◼$

形式化: wynerZivRate_nonneg (ソース)

命題 14.4.6. $X$ ， $Y$ ， $ˆ X$ ， $𝑑$ を定義 14.4.1 のとおりとし， $𝑝$ を $X \times Y$ 上の分布とする． $𝑅 W Z (\cdot)$ を定義 14.4.3 のとおりとし，実数 $𝐷$ ， $𝐷'$ が $𝐷 \leq 𝐷'$ を満たすとする．歪み $𝐷$ で実行可能な三つ組（定義 14.4.3）が少なくとも一つあるならば

𝑅 W Z (𝐷') \leq 𝑅 W Z (𝐷)

である．

証明. 歪み $𝐷$ で実行可能な三つ組は，期待歪みが $𝐷$ 以下，したがって $𝐷'$ 以下だから，歪み $𝐷'$ でも実行可能である．よって $𝐷'$ についての値の集合は $𝐷$ についての値の集合を含み，仮定より後者が空でないから前者も空でない．どちらの集合も補題 14.4.4 より $0$ を下界にもつので， $𝑅 W Z (𝐷)$ も $𝑅 W Z (𝐷')$ も定義 14.4.3 の約束ではなく実際の下限である．

広いほうの下限は広いほうのどの元以下でもあり，狭いほうの元はどれも広いほうの元だから，広いほうの下限は狭いほうの下界である．下限は下界のうち最大のものだから $𝑅 W Z (𝐷') \leq 𝑅 W Z (𝐷)$ である． $◼$

歪み $𝐷$ で実行可能な三つ組があるという仮定は落とせない．それが無いと $𝑅 W Z (𝐷)$ の値は下限ではなく定義 14.4.3 の約束で決まり，命題 14.4.6 の証明は集合の包含から下限の大小へ移るところで途切れる．仮定はその場合を主張の外に置くために要る．

形式化上の注記. 命題 14.4.6 と同じ不等式を述べる宣言 wynerZivRate_antitone (InformationTheory/Shannon/WynerZiv/FactorizableRate.lean) があるが，仮定が二つある．一つは命題 14.4.6 と同じ「歪みが小さいほうで実行可能な三つ組があること」で，もう一つは「歪みが大きいほうの値の集合が下に有界であること」である．本文は後者を補題 14.4.4 から出して仮定に置かない．あちらは情報源の分布が確率分布であることを求めない形で書かれているので，この有界性を仮定として受け取る必要がある．宣言のほうが強い仮定をもつ形になるので，ポインタは付けない．

命題 14.4.7. $X$ ， $Y$ ， $ˆ X$ ， $𝑑$ を定義 14.4.1 のとおりとし， $𝑝$ を $X \times Y$ 上の分布， $𝐷$ を実数とする． $X$ 上の分布 $𝑝 X (𝑥) : = \sum 𝑦 \in Y 𝑝 (𝑥, 𝑦)$ について $Q (\cdot)$ ， $𝐼 (𝑝 X; \cdot)$ ， $𝑅 (\cdot)$ を定義 9.1.5 のとおりとし， $𝑅 W Z (\cdot)$ を定義 14.4.3 のとおりとする． $Q (𝐷)$ が空でないならば，歪み $𝐷$ で実行可能な三つ組が少なくとも一つあり，かつ

𝑅 W Z (𝐷) \leq 𝑅 (𝐷)

である．

証明. $Q (𝐷)$ の元 $𝑞 0$ を一つとる．

この $𝑞 0$ から実行可能な三つ組を作る． $ˆ X$ は空でない有限集合だから，その元に $1$ から $𝑘 : = | ˆ X |$ までの番号を一対一につけられる．番号 $𝑢$ の元を $ˆ 𝑥 𝑢$ と書き， $𝑞 (𝑢 ∣ 𝑥) : = 𝑞 0 (ˆ 𝑥 𝑢 ∣ 𝑥)$ ， $𝑓 (𝑢, 𝑦) : = ˆ 𝑥 𝑢$ と定める．番号づけが一対一だから，各 $𝑥$ について $\sum 𝑘 𝑢 = 1 𝑞 (𝑢 ∣ 𝑥) = \sum ˆ 𝑥 𝑞 0 (ˆ 𝑥 ∣ 𝑥) = 1$ であり，値は非負だから $𝑞$ は $X$ から ${1, \dots, 𝑘}$ への条件付き分布である． $𝑓$ も定義 14.4.3 の再現関数の形をしている．

この三つ組の期待歪みを計算する． $(𝑋, 𝑌, 𝑈)$ を定義 14.4.3 の分布に従う三つ組とすると， $𝑓 (𝑢, 𝑦)$ が $𝑦$ によらないので

𝔼 [𝑑 (𝑋, 𝑓 (𝑈, 𝑌))] = \sum 𝑥, 𝑦, 𝑢 𝑝 (𝑥, 𝑦) 𝑞 (𝑢 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥 𝑢) = \sum 𝑥, 𝑢 𝑝 X (𝑥) 𝑞 0 (ˆ 𝑥 𝑢 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥 𝑢)

である（第 $2$ の等号は $𝑦$ について先に和をとったもので， $\sum 𝑦 𝑝 (𝑥, 𝑦) = 𝑝 X (𝑥)$ による）．番号づけが一対一だから，右辺は $\sum 𝑥, ˆ 𝑥 𝑝 X (𝑥) 𝑞 0 (ˆ 𝑥 ∣ 𝑥) 𝑑 (𝑥, ˆ 𝑥)$ に等しく，これは定義 9.1.5 が $𝑞 0$ に対応させる期待歪みそのものである． $𝑞 0 \in Q (𝐷)$ よりこれは $𝐷$ 以下だから， $(𝑘, 𝑞, 𝑓)$ は実行可能である．とくに実行可能な三つ組が少なくとも一つある．

この三つ組の目的の値を上から抑える．対 $(𝑋, 𝑈)$ の同時分布は $\sum 𝑦 𝑝 (𝑥, 𝑦) 𝑞 (𝑢 ∣ 𝑥) = 𝑝 X (𝑥) 𝑞 0 (ˆ 𝑥 𝑢 ∣ 𝑥)$ であり，これは定義 9.1.5 が $𝑞 0$ に対応させる対の同時分布を番号で書き直したものだから， $𝐼 (𝑋; 𝑈) = 𝐼 (𝑝 X; 𝑞 0)$ である．命題 1.3.2 より $𝐼 (𝑌; 𝑈) \geq 0$ だから

𝐼 (𝑋; 𝑈) - 𝐼 (𝑌; 𝑈) \leq 𝐼 (𝑋; 𝑈) = 𝐼 (𝑝 X; 𝑞 0)

である．

下限に移る．実行可能な三つ組が少なくとも一つあり，補題 14.4.4 より値の集合は $0$ を下界にもつから， $𝑅 W Z (𝐷)$ は実際の下限である．下限は下界だから，いま作った三つ組の目的の値以下であり，上の不等式と合わせて $𝑅 W Z (𝐷) \leq 𝐼 (𝑝 X; 𝑞 0)$ を得る．左辺は $𝑞 0$ の選び方によらないので， $𝑅 W Z (𝐷)$ は値の集合 ${𝐼 (𝑝 X; 𝑞) : 𝑞 \in Q (𝐷)}$ の下界である．下限は下界のうち最大のものだから， $𝑅 W Z (𝐷) \leq 𝑅 (𝐷)$ である． $◼$

命題 14.4.5 と命題 14.4.7 を並べると， $Q (𝐷)$ が空でないかぎり $0 \leq 𝑅 W Z (𝐷) \leq 𝑅 (𝐷)$ である．二つの端は矛盾しない． $𝑅 (𝐷)$ が下限をとる値の集合の元はどれも命題 1.3.2 より非負で， $𝑅 (𝐷)$ 自身も $0$ 以上だからである．上からの評価が言っているのは，副情報を持つ復号器を相手にするなら第9章の $𝑅 (𝐷)$ より多く送る必要はない，ということである．どれだけ少なくて済むかは $𝐼 (𝑌; 𝑈)$ の大きさで決まる．証明で作った三つ組は補助変数を再現そのものにとり，再現関数が $𝑦$ を捨てているので，副情報をまったく使っていない． $𝑦$ を実際に使う再現関数をとれば $𝐼 (𝑌; 𝑈)$ のぶんの値引きが目的の値に効く，というのが $𝑅 W Z$ を $𝑅$ より小さくしうる仕組みである．

形式化上の注記. 命題 14.4.7 に対応する単独の宣言はない．第9章定義 9.1.5 の $𝑅 (𝐷)$ を書いた宣言と定義 14.4.3 の $𝑅 W Z (𝐷)$ を書いた宣言を結ぶ宣言も，形式化には置かれていない．命題 14.4.7 に付した証明が，この主張の保証のすべてである．

値引きがいちばん効く場合と，まったく効かない場合を見ておく．どちらも補助変数を退化させた設定で，数行で閉じる．

例 14.4.8（副情報が情報源そのものである場合）. $X = Y = ˆ X = {0, 1}$ とし， $𝑑$ を例 9.1.3 の Hamming 歪み $𝑑 𝐻$ とする． $𝑝$ を $𝑝 (1, 1) = 1 / 4$ ， $𝑝 (0, 0) = 3 / 4$ ， $𝑝 (0, 1) = 𝑝 (1, 0) = 0$ で定まる $X \times Y$ 上の分布とし， $𝑅 W Z (\cdot)$ を定義 14.4.3 のとおりとする．このとき $𝐷 \geq 0$ を満たすどの実数 $𝐷$ についても，歪み $𝐷$ で実行可能な三つ組があり， $𝑅 W Z (𝐷) = 0$ である．

証明. $𝑘 : = 1$ とし，どの $𝑥 \in X$ についても $𝑞 (1 ∣ 𝑥) : = 1$ と定め， $𝑓 (1, 𝑦) : = 𝑦$ と定める．各 $𝑥$ について $\sum 1 𝑢 = 1 𝑞 (𝑢 ∣ 𝑥) = 1$ で値は非負だから $𝑞$ は定義 14.4.3 の条件付き分布であり， $𝑓$ は ${1} \times Y$ から $ˆ X$ への写像だから再現関数の形をしている．

期待歪みを見る． $(𝑋, 𝑌, 𝑈)$ を定義 14.4.3 の分布に従う三つ組とする． $𝑝 (0, 1) = 𝑝 (1, 0) = 0$ だから $P r [𝑌 \neq 𝑋] = 0$ であり， $𝑓 (𝑈, 𝑌) = 𝑌$ だから例 9.1.3 より $𝑑 𝐻 (𝑋, 𝑓 (𝑈, 𝑌))$ は確率 $1$ で $0$ をとる．よって期待歪みは $0$ で， $𝐷 \geq 0$ ならば $(1, 𝑞, 𝑓)$ は歪み $𝐷$ で実行可能である．

目的の値を見る． $𝑈$ は確率 $1$ で $1$ をとるから， $𝑈$ と $𝑋$ の同時分布も $𝑈$ と $𝑌$ の同時分布も，それぞれの周辺分布の積に等しい．命題 1.3.2 の等号条件より $𝐼 (𝑋; 𝑈) = 𝐼 (𝑌; 𝑈) = 0$ であり，この三つ組の目的の値は $0$ である．実行可能な三つ組があり，補題 14.4.4 より値の集合は $0$ を下界にもつから， $𝑅 W Z (𝐷)$ は実際の下限である．下限は下界だから，いま作った三つ組の目的の値 $0$ 以下であり，命題 14.4.5 と合わせて $𝑅 W Z (𝐷) = 0$ を得る． $◼$

この分布の $X$ についての周辺は例 9.3.5 の二値情報源そのもので，例 9.3.5 が与えた $𝑅 (0)$ は約 $0.8113$ ビットである．副情報が $𝑋$ をそのまま渡してくるので，符号化する側は何も送らなくてよい．命題 14.4.7 が置いた $𝑅 W Z (𝐷) \leq 𝑅 (𝐷)$ を $𝐷 = 0$ で読むと，左辺が $0$ ，右辺が約 $0.8113$ ビットで，値引きが右辺をすべて消している．

例 14.4.9（副情報が情報源と独立である場合）. $X$ ， $Y$ ， $ˆ X$ を空でない有限集合とし， $𝑝 X$ を $X$ 上の分布， $𝑝 Y$ を $Y$ 上の分布として $𝑝 (𝑥, 𝑦) : = 𝑝 X (𝑥) 𝑝 Y (𝑦)$ とする．正の整数 $𝑘$ と， $X$ から ${1, \dots, 𝑘}$ への条件付き分布 $𝑞$ （定義 9.1.5）と，再現関数 $𝑓 : {1, \dots, 𝑘} \times Y \to ˆ X$ （定義 14.4.3）の三つ組 $(𝑘, 𝑞, 𝑓)$ を任意にとり， $(𝑋, 𝑌, 𝑈)$ を定義 14.4.3 の分布 $𝑝 (𝑥, 𝑦) 𝑞 (𝑢 ∣ 𝑥)$ に従う三つ組とする．このとき $𝐼 (𝑌; 𝑈) = 0$ であり，この三つ組の目的の値は $𝐼 (𝑋; 𝑈)$ に等しい．

証明. 三つ組が定める分布は $𝑝 X (𝑥) 𝑝 Y (𝑦) 𝑞 (𝑢 ∣ 𝑥)$ である．対 $(𝑌, 𝑈)$ の同時分布はこれを $𝑥$ について足したもので

\sum 𝑥 𝑝 X (𝑥) 𝑝 Y (𝑦) 𝑞 (𝑢 ∣ 𝑥) = 𝑝 Y (𝑦) \sum 𝑥 𝑝 X (𝑥) 𝑞 (𝑢 ∣ 𝑥)

である．いっぽう $𝑌$ の周辺分布は，各 $𝑥$ について $\sum 𝑢 𝑞 (𝑢 ∣ 𝑥) = 1$ であることと $\sum 𝑥 𝑝 X (𝑥) = 1$ とから $𝑝 Y (𝑦)$ であり， $𝑈$ の周辺分布は $\sum 𝑦 𝑝 Y (𝑦) = 1$ から $\sum 𝑥 𝑝 X (𝑥) 𝑞 (𝑢 ∣ 𝑥)$ である．よって上の右辺は二つの周辺分布の積にほかならない．命題 1.3.2 の等号条件より $𝐼 (𝑌; 𝑈) = 0$ であり，目的の値 $𝐼 (𝑋; 𝑈) - 𝐼 (𝑌; 𝑈)$ は $𝐼 (𝑋; 𝑈)$ に等しい． $◼$

補助変数は $𝑋$ だけから作られるので， $𝑌$ が $𝑋$ と独立なら $𝑈$ とも独立になる．値引きの項が消えて，副情報を渡しても目的の値は下がらない．例 14.4.8 とちょうど逆の端である．ただしこのとき $𝑅 W Z (𝐷)$ が第9章の $𝑅 (𝐷)$ に一致する，とまでは本書は述べない．再現関数 $𝑓 (𝑢, 𝑦)$ は $𝑦$ を引数にとってよいので， $𝑦$ を使わない形に直す段が要り，本節はその段を置いていない．

両端のあいだにある例を一つ置く．補助変数を退化させず，入力そのものにとる．情報源には 14.3 節の例 14.3.2 の対をそのまま使う．

例 14.4.10（二元対称な相関で補助変数を入力にとる）. $X = Y = ˆ X = {0, 1}$ とし， $𝑑$ を例 9.1.3 の Hamming 歪み $𝑑 𝐻$ とする． $𝜌 \in [0, 1]$ をとり， $𝑝$ を例 14.3.2 の対 $(𝑋, 𝑌)$ の同時分布，すなわち $𝑝 (0, 0) = 𝑝 (1, 1) = (1 - 𝜌) / 2$ ， $𝑝 (0, 1) = 𝑝 (1, 0) = 𝜌 / 2$ とし， $𝑅 W Z (\cdot)$ を定義 14.4.3 のとおりとする． $𝑘 : = 2$ とし，各 $𝑥 \in X$ について $𝑞 (𝑥 + 1 ∣ 𝑥) : = 1$ ， $𝑢 \neq 𝑥 + 1$ では $𝑞 (𝑢 ∣ 𝑥) : = 0$ と定め， $𝑓 (𝑢, 𝑦) : = 𝑢 - 1$ と定めると，三つ組 $(2, 𝑞, 𝑓)$ は $𝐷 \geq 0$ を満たすどの実数 $𝐷$ についても実行可能であり，その目的の値は $𝐻 𝑏 (𝜌)$ である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．したがって $𝐷 \geq 0$ ならば $𝑅 W Z (𝐷) \leq 𝐻 𝑏 (𝜌)$ である．

証明. 三つ組の形を確かめる．各 $𝑥 \in {0, 1}$ について $𝑥 + 1 \in {1, 2}$ であり， $\sum 2 𝑢 = 1 𝑞 (𝑢 ∣ 𝑥) = 1$ で値は非負だから， $𝑞$ は $X$ から ${1, 2}$ への条件付き分布である． $𝑓$ は ${1, 2} \times Y$ から $ˆ X$ への写像だから，定義 14.4.3 の再現関数の形をしている．

実行可能であることを見る． $(𝑋, 𝑌, 𝑈)$ を定義 14.4.3 の分布 $𝑝 (𝑥, 𝑦) 𝑞 (𝑢 ∣ 𝑥)$ に従う三つ組とすると， $𝑞$ の作り方から $𝑈 = 𝑋 + 1$ が確率 $1$ で成り立ち， $𝑓 (𝑈, 𝑌) = 𝑈 - 1 = 𝑋$ である．例 9.1.3 より $𝑑 𝐻 (𝑋, 𝑋) = 0$ だから期待歪みは $0$ で， $𝐷 \geq 0$ ならばこの三つ組は実行可能である．

目的の値を出す．定理 1.3.4 の $𝐼 (𝑋; 𝑈) = 𝐻 (𝑈) - 𝐻 (𝑈 ∣ 𝑋)$ で， $𝑋$ を与えると $𝑈$ は一点に決まるから定義 1.1.1 と定義 1.2.2 より第 $2$ 項は $0$ であり， $𝑈$ の分布は $𝑋$ の分布の値を付け替えただけだから，例 14.3.2 と合わせて $𝐻 (𝑈) = 𝐻 (𝑋) = 1$ である．よって $𝐼 (𝑋; 𝑈) = 1$ である．いっぽう対 $(𝑌, 𝑈)$ の同時分布は対 $(𝑌, 𝑋)$ の同時分布を第 $2$ 成分の番号で書き直したものだから $𝐼 (𝑌; 𝑈) = 𝐼 (𝑌; 𝑋)$ であり，例 14.3.2 の $𝐼 (𝑋; 𝑌) = 1 - 𝐻 𝑏 (𝜌)$ と命題 1.3.3 の対称性より $𝐼 (𝑌; 𝑈) = 1 - 𝐻 𝑏 (𝜌)$ である．よって目的の値は $1 - (1 - 𝐻 𝑏 (𝜌)) = 𝐻 𝑏 (𝜌)$ である．

下限に移る．実行可能な三つ組があり，補題 14.4.4 より値の集合は $0$ を下界にもつから， $𝑅 W Z (𝐷)$ は実際の下限である．下限は下界だから，いま作った三つ組の目的の値 $𝐻 𝑏 (𝜌)$ 以下である． $◼$

例 14.4.8 では値引きが例 9.3.5 の $𝑅 (0)$ を丸ごと消し，例 14.4.9 では値引きが $0$ だった．例 14.4.10 はそのあいだにある．この三つ組では $𝐼 (𝑋; 𝑈) = 1$ ， $𝐼 (𝑌; 𝑈) = 1 - 𝐻 𝑏 (𝜌)$ で，副情報がちょうど例 14.3.2 の $𝐼 (𝑋; 𝑌)$ のぶんだけ値引きし， $𝐻 𝑏 (𝜌)$ が残る． $𝜌$ が $0$ ， $1 / 2$ ， $1$ のどれでもなければ $0 < 𝐻 𝑏 (𝜌) < 1$ だから，値引きは効いているが全部を消してはいない．残った $𝐻 𝑏 (𝜌)$ は，同じ対について 14.3 節の定理 14.3.3 が $𝑋$ 側のレートに置いた下界の，誤り確率が $0$ のときの値 $𝐻 (𝑋 ∣ 𝑌)$ と同じである． $𝑌$ をまるごと渡されている受け手を相手に $𝑋$ を届ける，という要求が，14.3 節では二人で圧縮する設定の $𝑋$ 側の枠として，本節では副情報つきの目的の値として，同じ量で現れている．ただし例 14.4.10 が与えるのは上からの評価だけで， $𝑅 W Z (𝐷)$ がこの値に等しいことまでは本書も形式化も述べない．

逆定理と達成可能性

道具を二つ借りる．どちらも定義 14.4.2 の達成可能性と定義 14.4.3 の $𝑅 W Z$ を結ぶもので，向きが逆である．

一つめは 副情報つきレート歪みの逆定理，すなわち「達成可能なレートは $𝑅 W Z (𝐷)$ を下回らない」という主張である．使う形を書いておく．

$X$ ， $Y$ ， $ˆ X$ ， $𝑑$ を定義 14.4.1 のとおりとし， $𝑝$ を $X \times Y$ 上の分布， $𝑅$ と $𝐷$ を実数とする． $𝑅$ が歪み $𝐷$ で達成可能（定義 14.4.2）ならば $𝑅 W Z (𝐷) \leq 𝑅$ である．

当てる対象は定義 14.4.1 の副情報つき符号だけで，情報源の分布にも歪み尺度にも定義 14.4.1 が置いた以上の条件を加えない．依存するのは本節の終わりの地の文だけである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．長さ $𝑛$ の符号を一つとり，符号化写像の出す番号を $𝐽 : = 𝑐 (𝑋 𝑛)$ と書く．時刻 $𝑖$ ごとに，番号と，時刻 $𝑖$ 以外のすべての副情報とを束ねた $𝑈 𝑖 : = (𝐽, (𝑌 𝑗) 𝑗 \neq 𝑖)$ を補助変数とする．情報源が対ごとに独立であることから $𝑌 𝑖 \to 𝑋 𝑖 \to 𝑈 𝑖$ がマルコフ連鎖になり， $𝑈 𝑖$ は定義 14.4.3 の補助変数として通る．再現関数は，復号写像の出す列の第 $𝑖$ 成分をとったものである．そのうえで $l o g 𝑀$ を時刻ごとの $𝐼 (𝑋 𝑖; 𝑈 𝑖) - 𝐼 (𝑌 𝑖; 𝑈 𝑖)$ の和で下から抑え，時刻を一様に選ぶ変数をもう一段の補助変数として束ねて $1$ 文字あたりの形に直し，最後に $𝑛$ を大きくして歪みの余裕を $0$ に送る．

本書はこの主張を証明しない．時刻ごとにほどく段が，第6章定理 6.4.5 や第9章定理 9.5.4 のものをそのまま当てるのでは済まないからである．あちらで和に分けたのは相互情報量一つだったが，こちらで分けるのは差 $𝐼 (𝑋 𝑛; 𝐽) - 𝐼 (𝑌 𝑛; 𝐽)$ で，二つの項を同じ時刻の切り方でそろえる段が要る．そのうえ束ねた $𝑈 𝑖$ は時刻 $𝑖$ の前後の両側の副情報を含んでいる．片側だけにすると定義 14.4.3 の再現関数が作れない．復号写像の出す列の第 $𝑖$ 成分は $𝑌 𝑛$ の全体を引数にとるので，時刻 $𝑖$ の再現を対 $(𝑈 𝑖, 𝑌 𝑖)$ だけの写像として書くには， $𝑈 𝑖$ が時刻 $𝑖$ 以外の副情報を両側とも含んでいなければならないからである．そのぶん重くなった $𝑈 𝑖$ を扱う道具が要る．

形式化: wyner_ziv_converse (ソース)

二つめは 副情報つきレート歪みの達成可能性，すなわち「 $𝑅 W Z (𝐷)$ より大きいレートは実際に達成できる」という主張である．使う形を書いておく．

$X$ ， $Y$ ， $ˆ X$ ， $𝑑$ を定義 14.4.1 のとおりとし， $𝑝$ を $X \times Y$ 上の分布， $𝑅$ と $𝐷$ を実数とする．歪み $𝐷$ で実行可能な三つ組（定義 14.4.3）が少なくとも一つあり， $𝑅 W Z (𝐷) < 𝑅$ ならば， $𝑅$ は歪み $𝐷$ で達成可能である（定義 14.4.2）．

当てる対象は定義 14.4.1 の副情報つき符号だけで，依存するのは本節の終わりの地の文だけである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．二つの道具を組み合わせる．一つめは覆いで，第9章 9.6 節が借りた レート歪み理論の達成可能性 と同じく，補助変数の側の符号語を $2 𝑛 𝐼 (𝑋; 𝑈)$ 本ほど引いて $𝑋 𝑛$ を覆う．ここまでなら要るレートは $𝐼 (𝑋; 𝑈)$ である．二つめがビニングで，14.3 節が借りた Slepian–Wolf の達成可能性 と同じく，覆った符号語の番号をさらに $2 𝑛 (𝐼 (𝑋; 𝑈) - 𝐼 (𝑌; 𝑈))$ 個の箱に投げ込み，送るのは箱の番号だけにする．復号器は $𝑌 𝑛$ を持っているので，受け取った箱の中から $𝑌 𝑛$ と結合典型な符号語を探せばよく，一つの箱に紛れる本数が $2 𝑛 𝐼 (𝑌; 𝑈)$ ほどまでなら一本に絞れる．差し引き $𝐼 (𝑋; 𝑈) - 𝐼 (𝑌; 𝑈)$ が送るレートになる，という勘定である．覆いとビニングという，本書のここまでで別々に現れた二つの道具が一つの構成の中で噛み合うのが，この設定の眼目である．

本書はこの主張を証明しない．覆いの側は第9章 9.6 節で，ビニングの側は 14.3 節で，どちらも借りたままだから，組み合わせる段で当てる相手が本書には無い．しかも足りない道具は 14.3 節で足りなかったものと同じで， $𝑌 𝑛$ を一つ固定したときにそれと結合典型になる補助変数の側の系列の本数，すなわち結合典型集合の切り口の個数を抑える評価が，一つの箱に紛れ込む本数を数えるところで要る．

形式化: wyner_ziv_achievability (ソース)

形式化上の注記. 形式化の宣言の仮定は，借りた主張の仮定と一つずつ対応している．歪み $𝐷$ で実行可能な三つ組があることと， $𝑅 W Z (𝐷)$ がレートより真に小さいことの二つで，これがすべてである．結論も定義 14.4.2 の達成可能性そのものである．

二つの借用を並べると， $𝑅 W Z (𝐷)$ が達成可能なレートの境目にあることが見える．副情報つきレート歪みの逆定理より， $𝑅 W Z (𝐷)$ より小さい実数は一つも達成可能でない．副情報つきレート歪みの達成可能性より，歪み $𝐷$ で実行可能な三つ組があるかぎり， $𝑅 W Z (𝐷)$ より大きい実数はすべて達成可能である．境目の $𝑅 = 𝑅 W Z (𝐷)$ そのものが達成可能かどうかは，どちらの借用も述べておらず，本書も形式化も述べない．14.2 節が定義 14.2.1 で境界のレート対を閉包で拾ったのに対し，本節は境目をそのまま切れ目として残している．

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