14.3 相関のある情報源の符号化

第2章は情報源を一つ扱った．列を番号に潰す人が一人いて，番号から列を作り直す人が一人いた．本節では情報源が二つあり，しかも二つは相関している．潰す人は二人に分かれていて，互いの見ているものを知らない．作り直す人は一人で，二つの番号をまとめて受け取り，両方の列を復元する．14.1 節が送り手を二人に分けたのと同じ分け方が，こんどは情報源の側に起きている．通信路は出てこない．本節に現れるのは情報源と符号だけである．

二つの情報源を $𝑋$ と $𝑌$ と書く．二人が相手を見られない以上，それぞれが単独で圧縮するほかないように見える．そうだとすると，第2章定理 2.3.6 を二つの情報源それぞれに当てて， $1$ 文字あたり合計で $𝐻 (𝑋) + 𝐻 (𝑌)$ が要ることになる．ところが節の終わりで借りる達成可能性は，合計を $𝐻 (𝑋, 𝑌)$ の近くまで下げられると言う．相関のぶんの重なり，すなわち定理 1.3.4 が $𝐻 (𝑋) + 𝐻 (𝑌) - 𝐻 (𝑋, 𝑌)$ と書いた $𝐼 (𝑋; 𝑌)$ は，二人が相談しなくても削れるということである．本節はまず下からの評価，つまりどこまでなら下げられないかを三つの形で証明し，そのうえで上からの評価を借りる．

分散符号

定義 14.3.1（相関情報源の分散符号）. $X$ と $Y$ を空でない有限アルファベット， $(𝑋, 𝑌)$ を $X \times Y$ に値をとる確率変数の対とし， $𝑀 𝑋 \geq 1$ ， $𝑀 𝑌 \geq 1$ を整数とする．分散符号 とは，符号化写像 $𝑓 𝑋 : X \to {1, \dots, 𝑀 𝑋}$ ， $𝑓 𝑌 : Y \to {1, \dots, 𝑀 𝑌}$ と 共同復号器 $𝑑 : {1, \dots, 𝑀 𝑋} \times {1, \dots, 𝑀 𝑌} \to X \times Y$ の組である．復号の結果 $𝑑 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))$ の第 $1$ 成分を $ˆ 𝑋$ ，第 $2$ 成分を $ˆ 𝑌$ と書き，三つの 誤り確率 を

𝑃 𝑒 : = P r [(ˆ 𝑋, ˆ 𝑌) \neq (𝑋, 𝑌)], 𝑃 𝑒, 𝑋 : = P r [ˆ 𝑋 \neq 𝑋], 𝑃 𝑒, 𝑌 : = P r [ˆ 𝑌 \neq 𝑌]

で定める．

第2章定義 2.3.1 のブロック情報源符号を二つの情報源に広げた形だが，広げ方は左右で対称ではない．符号化は二本に分かれる． $𝑓 𝑋$ は $𝑋$ だけを見て番号を出し， $𝑌$ の値も相手の出した番号も見ない．いっぽう復号は一本のままで，二つの番号から対を一度に言い当てる．分散と呼ぶのはこの符号化の側の分かれ方を指していて（確率変数のばらつきを測る分散とは別の語である），復号の側は分かれていない．誤り確率を三つ置いたのは，対として当てることと成分ごとに当てることが別の要求だからで，以下の三つの下界はそれぞれ別の誤り確率で書かれる．

長さ $𝑛$ のブロックを扱うときは，定義 14.3.1 の $X$ と $Y$ に $X 𝑛$ と $Y 𝑛$ を，対 $(𝑋, 𝑌)$ に $(𝑋 𝑛, 𝑌 𝑛)$ を置いて読む．そのときレートは $1 𝑛 l o g 𝑀 𝑋$ と $1 𝑛 l o g 𝑀 𝑌$ になる．定義 14.3.1 自体はアルファベットに何の構造も求めないので，この読み替えに断りは要らない．

形式化上の注記. 形式化には符号の三つの写像を束ねた構造体が無く，逆定理の宣言は符号化写像二つと共同復号器を別々の引数として受け取る．誤り確率のほうは二か所にある．全体の誤り確率を長さ $𝑛$ のブロックについて書いた swErrorProb (InformationTheory/Shannon/SlepianWolf/Achievability.lean) と，逆定理の宣言が使う一般の有限アルファベットについての errorProb (InformationTheory/Fano/Measure.lean) で，前者のアルファベットを $X 𝑛$ と $Y 𝑛$ にとれば二つは同じものを測るが，単独の宣言としては別である．

例 14.3.2（二元対称な相関）. $X = Y = {0, 1}$ とし， $𝜌 \in [0, 1]$ とする． $𝑋$ を $X$ 上の一様分布に従う確率変数， $𝑍$ を $𝑋$ と独立で $P r [𝑍 = 1] = 𝜌$ を満たす確率変数とし， $𝑌 : = 𝑋 \oplus 𝑍$ （ $\oplus$ は排他的論理和）とする．このとき $𝑋$ を与えたときの $𝑌$ の条件付き分布は，例 6.1.8 の反転確率 $𝜌$ の二元対称通信路が返す分布であり，

𝐻 (𝑋) = 𝐻 (𝑌) = 1, 𝐻 (𝑋 ∣ 𝑌) = 𝐻 (𝑌 ∣ 𝑋) = 𝐻 𝑏 (𝜌),

𝐻 (𝑋, 𝑌) = 1 + 𝐻 𝑏 (𝜌), 𝐼 (𝑋; 𝑌) = 1 - 𝐻 𝑏 (𝜌)

である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）．また $𝑀 𝑋 : = 2$ ， $𝑀 𝑌 : = 2$ とし， $𝑓 𝑋$ と $𝑓 𝑌$ をどちらも $0 \mapsto 1$ ， $1 \mapsto 2$ で定め， $𝑑 (𝑚 𝑋, 𝑚 𝑌) : = (𝑚 𝑋 - 1, 𝑚 𝑌 - 1)$ と定めると，この組は定義 14.3.1 の分散符号であり，三つの誤り確率はどれも $0$ で， $l o g 𝑀 𝑋 = l o g 𝑀 𝑌 = 1$ である．さらに $𝜌 = 0$ のときにかぎり， $𝑀 𝑋 : = 2$ ， $𝑀 𝑌 : = 1$ とし， $𝑓 𝑋$ を同じ写像， $𝑓 𝑌$ を値が $1$ の定数写像とし， $𝑑 (𝑚 𝑋, 1) : = (𝑚 𝑋 - 1, 𝑚 𝑋 - 1)$ と定めると，この組も定義 14.3.1 の分散符号であり，三つの誤り確率はどれも $0$ で， $l o g 𝑀 𝑋 + l o g 𝑀 𝑌 = 1$ である．

証明. $𝑌$ の分布をまず見る． $𝑋$ と $𝑍$ は独立だから

P r [𝑌 = 1] = P r [𝑋 = 1] P r [𝑍 = 0] + P r [𝑋 = 0] P r [𝑍 = 1] = 12 (1 - 𝜌) + 12 𝜌 = 12

であり， $𝑌$ も $X$ 上の一様分布に従う．よって例 1.1.3 より $𝐻 (𝑋) = 𝐻 (𝑌) = l o g 2 = 1$ である．

条件付き分布と $𝐻 (𝑌 ∣ 𝑋)$ を見る． $𝑥$ を一つ固定する． $𝑍$ は $𝑋$ と独立だから， $𝑋 = 𝑥$ を与えたときの $𝑍$ の条件付き分布はもとの分布のままで， $𝑌 = 𝑥 \oplus 𝑍$ は $𝑥$ と違う値を確率 $𝜌$ ， $𝑥$ を確率 $1 - 𝜌$ でとる．これが例 6.1.8 の反転確率 $𝜌$ の二元対称通信路が入力 $𝑥$ に返す分布である．定義 1.1.1 よりそのエントロピーは $𝑥$ によらず $𝐻 𝑏 (𝜌)$ だから，定義 1.2.2 がそれを平均した値も $𝐻 𝑏 (𝜌)$ である．

残る三つはチェイン則から出る．定理 1.2.3 より $𝐻 (𝑋, 𝑌) = 𝐻 (𝑋) + 𝐻 (𝑌 ∣ 𝑋) = 1 + 𝐻 𝑏 (𝜌)$ であり，同じチェイン則を $𝑌$ の側から読むと $𝐻 (𝑋 ∣ 𝑌) = 𝐻 (𝑋, 𝑌) - 𝐻 (𝑌) = 𝐻 𝑏 (𝜌)$ である．相互情報量は，定理 1.3.4 の $𝐼 (𝑋; 𝑌) = 𝐻 (𝑋) - 𝐻 (𝑋 ∣ 𝑌)$ に二つを入れて $1 - 𝐻 𝑏 (𝜌)$ である．

符号を確かめる． $𝑓 𝑋$ と $𝑓 𝑌$ はどちらも ${0, 1}$ を ${1, 2}$ に写す一対一の写像で， $𝑑$ は各成分にその逆を施すから， $𝑑 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌)) = (𝑋, 𝑌)$ がつねに成り立つ．対として当たっているから成分ごとにも当たっており，三つの誤り確率はどれも $0$ である． $𝑀 𝑋 = 𝑀 𝑌 = 2$ から $l o g 𝑀 𝑋 = l o g 𝑀 𝑌 = 1$ を得る．

$𝜌 = 0$ の符号を確かめる．このとき $𝑍$ は確率 $1$ で $0$ をとるから， $𝑌 = 𝑋 \oplus 𝑍$ は確率 $1$ で $𝑋$ に等しい． $𝑓 𝑋$ は $𝑥$ を $𝑥 + 1$ に写すから $𝑑 (𝑓 𝑋 (𝑋), 1) = (𝑋, 𝑋)$ であり， $𝑓 𝑌$ の値は $1$ しかないので，これが $𝑑 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))$ である．右辺は確率 $1$ で $(𝑋, 𝑌)$ に等しいから，三つの誤り確率はどれも $0$ である． $𝑀 𝑋 = 2$ ， $𝑀 𝑌 = 1$ から $l o g 𝑀 𝑋 + l o g 𝑀 𝑌 = 1 + 0 = 1$ を得る． $◼$

$𝜌$ が相関の強さを動かす． $𝜌 = 0$ なら $𝑍$ は確率 $1$ で $0$ をとるので $𝑌 = 𝑋$ であり， $𝜌 = 1$ なら $𝑌$ は $𝑋$ を裏返したものである．例 1.1.2 のとおり $𝐻 𝑏$ はその両端で $0$ ， $𝜌 = 1 / 2$ で最大値 $l o g 2 = 1$ をとる． $𝜌$ をどこに置いても $𝐻 (𝑋) + 𝐻 (𝑌) = 2$ は動かないのに，対のエントロピー $𝐻 (𝑋, 𝑌) = 1 + 𝐻 𝑏 (𝜌)$ のほうは $1$ から $2$ までを動く．その差が，例 14.3.2 の $𝐼 (𝑋; 𝑌) = 1 - 𝐻 𝑏 (𝜌)$ である．本節の冒頭で「相関のぶんの重なりは二人が相談しなくても削れる」と書いたのは，この差のことである．例 14.3.2 の一つめの符号は合計で $2$ ，すなわち $𝐻 (𝑋) + 𝐻 (𝑌)$ をそのまま使っていて，この差をまだ受け取っていない．いっぽう $𝜌 = 0$ の符号は， $𝑌$ 側の番号が一通りしかない，つまり $𝑌$ 側が何も送っていないのに，合計 $1$ で二つの列をどちらも復元している． $𝐻 (𝑋) + 𝐻 (𝑌) = 2$ より $1$ 少なく，削れた $1$ はこのときの $𝐼 (𝑋; 𝑌) = 1 - 𝐻 𝑏 (0) = 1$ に等しい．相関が完全なので極端な場合だが，二人が相談しないまま重なりのぶんだけ削れる，ということの実物にはなっている．中間の $𝜌$ について合計を $𝐻 (𝑋, 𝑌)$ の近くまで下げられると言うのは節の終わりで借りる達成可能性のほうで，そちらは長さ $𝑛$ のブロックについての主張である．

三つの下界

これから三つの下界を示す．どれもファノの不等式（定理 1.10.1）を使うが，観測の位置に置くのは一つの確率変数ではなく対である．定義 1.2.2 が断ったとおり，条件が複数あるときは対を一つの変数とみなして読めばよいので，定理 1.10.1 が観測に置いている変数にその対を，観測のとる値の集合にその対のとる値の集合を置けば，そのまま当たる．どの対を置くかが三つで違い，それが三つの下界の違いを生む．

定理 14.3.3（分散符号の逆定理・ $𝑋$ 側）. $X$ と $Y$ を空でない有限アルファベットとし， $| X | \geq 2$ とする． $(𝑋, 𝑌)$ を $X \times Y$ に値をとる確率変数の対， $(𝑀 𝑋, 𝑀 𝑌, 𝑓 𝑋, 𝑓 𝑌, 𝑑)$ を定義 14.3.1 の分散符号， $𝑃 𝑒, 𝑋$ をその $𝑋$ 側の誤り確率とすると

l o g 𝑀 𝑋 \geq 𝐻 (𝑋 ∣ 𝑌) - 𝐻 𝑏 (𝑃 𝑒, 𝑋) - 𝑃 𝑒, 𝑋 l o g (| X | - 1)

である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）．

証明. $ˆ 𝑋$ を定義 14.3.1 のとおり $𝑑 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))$ の第 $1$ 成分とする．

$ˆ 𝑋$ が対 $(𝑌, 𝑓 𝑋 (𝑋))$ の写像で書けることをまず見る． $𝑔 : Y \times {1, \dots, 𝑀 𝑋} \to X$ を $𝑔 (𝑦, 𝑚) : = (𝑑 (𝑚, 𝑓 𝑌 (𝑦))) 1$ （第 $1$ 成分）で定めると， $𝑔 (𝑌, 𝑓 𝑋 (𝑋)) = (𝑑 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))) 1 = ˆ 𝑋$ である．この写像の誤り確率 $P r [ˆ 𝑋 \neq 𝑋]$ は定義 14.3.1 の $𝑃 𝑒, 𝑋$ にほかならない．そこでファノの不等式（定理 1.10.1）を，観測に対 $(𝑌, 𝑓 𝑋 (𝑋))$ を，復号器に $𝑔$ を置いて当てる． $| X | \geq 2$ だから

𝐻 (𝑋 ∣ 𝑌, 𝑓 𝑋 (𝑋)) \leq 𝐻 𝑏 (𝑃 𝑒, 𝑋) + 𝑃 𝑒, 𝑋 l o g (| X | - 1)

を得る．

次に， $𝑌$ を知っている人にとって番号 $𝑓 𝑋 (𝑋)$ が $𝑋$ について持つ情報が $l o g 𝑀 𝑋$ を超えないことを見る．エントロピーの差の形（定理 1.4.3）で

𝐼 (𝑋; 𝑓 𝑋 (𝑋) ∣ 𝑌) = 𝐻 (𝑋 ∣ 𝑌) - 𝐻 (𝑋 ∣ 𝑌, 𝑓 𝑋 (𝑋))

である．いっぽう命題 1.4.2 の対称性より $𝐼 (𝑋; 𝑓 𝑋 (𝑋) ∣ 𝑌) = 𝐼 (𝑓 𝑋 (𝑋); 𝑋 ∣ 𝑌)$ であり，定理 1.4.3 をこちらの向きに読むと

𝐼 (𝑓 𝑋 (𝑋); 𝑋 ∣ 𝑌) = 𝐻 (𝑓 𝑋 (𝑋) ∣ 𝑌) - 𝐻 (𝑓 𝑋 (𝑋) ∣ 𝑌, 𝑋)

となる．右辺の第 $2$ 項は条件付きエントロピーだから非負であり（定義 1.2.2 と命題 1.1.4）， $𝐼 (𝑋; 𝑓 𝑋 (𝑋) ∣ 𝑌) \leq 𝐻 (𝑓 𝑋 (𝑋) ∣ 𝑌)$ である．さらに定理 1.2.4 の基本形より $𝐻 (𝑓 𝑋 (𝑋) ∣ 𝑌) \leq 𝐻 (𝑓 𝑋 (𝑋))$ であり， $𝑓 𝑋 (𝑋)$ のとりうる値は $𝑀 𝑋$ 個だから定理 1.1.5 より $𝐻 (𝑓 𝑋 (𝑋)) \leq l o g 𝑀 𝑋$ である．

二つを合わせる．定理 1.4.3 から出した等式を移項すると $𝐻 (𝑋 ∣ 𝑌) = 𝐼 (𝑋; 𝑓 𝑋 (𝑋) ∣ 𝑌) + 𝐻 (𝑋 ∣ 𝑌, 𝑓 𝑋 (𝑋))$ であり，右辺の第 $1$ 項にいま見た $l o g 𝑀 𝑋$ の上界を，第 $2$ 項にファノの不等式から出した上界を当てて

𝐻 (𝑋 ∣ 𝑌) \leq l o g 𝑀 𝑋 + 𝐻 𝑏 (𝑃 𝑒, 𝑋) + 𝑃 𝑒, 𝑋 l o g (| X | - 1)

であり，移項すれば主張を得る． $◼$

形式化: slepian_wolf_converse_X (ソース)

定理 14.3.4（分散符号の逆定理・ $𝑌$ 側）. $X$ と $Y$ を空でない有限アルファベットとし， $| Y | \geq 2$ とする． $(𝑋, 𝑌)$ を $X \times Y$ に値をとる確率変数の対， $(𝑀 𝑋, 𝑀 𝑌, 𝑓 𝑋, 𝑓 𝑌, 𝑑)$ を定義 14.3.1 の分散符号， $𝑃 𝑒, 𝑌$ をその $𝑌$ 側の誤り確率とすると

l o g 𝑀 𝑌 \geq 𝐻 (𝑌 ∣ 𝑋) - 𝐻 𝑏 (𝑃 𝑒, 𝑌) - 𝑃 𝑒, 𝑌 l o g (| Y | - 1)

である．

証明. 定理 14.3.3 の証明で， $𝑋$ と $𝑌$ ， $X$ と $Y$ ， $𝑓 𝑋$ と $𝑓 𝑌$ ， $𝑀 𝑋$ と $𝑀 𝑌$ の役をそれぞれ入れ替え，復号の結果の第 $1$ 成分をとるところを第 $2$ 成分に替えればよい．すなわち $ℎ : X \times {1, \dots, 𝑀 𝑌} \to Y$ を $ℎ (𝑥, 𝑚) : = (𝑑 (𝑓 𝑋 (𝑥), 𝑚)) 2$ で定めると $ℎ (𝑋, 𝑓 𝑌 (𝑌)) = ˆ 𝑌$ であり，その誤り確率は定義 14.3.1 の $𝑃 𝑒, 𝑌$ である．以下の運びは定理 14.3.3 の証明と同じで，ファノの不等式を当てるときに条件に置く対が $(𝑋, 𝑓 𝑌 (𝑌))$ に，最大エントロピー上界を当てる相手が $𝑓 𝑌 (𝑌)$ に替わるだけである． $◼$

形式化: slepian_wolf_converse_Y (ソース)

定理 14.3.5（分散符号の逆定理・和レート）. $X$ と $Y$ を空でない有限アルファベットとし， $| X \times Y | \geq 2$ とする． $(𝑋, 𝑌)$ を $X \times Y$ に値をとる確率変数の対， $(𝑀 𝑋, 𝑀 𝑌, 𝑓 𝑋, 𝑓 𝑌, 𝑑)$ を定義 14.3.1 の分散符号， $𝑃 𝑒$ をその全体の誤り確率とすると

l o g 𝑀 𝑋 + l o g 𝑀 𝑌 \geq 𝐻 (𝑋, 𝑌) - 𝐻 𝑏 (𝑃 𝑒) - 𝑃 𝑒 l o g (| X \times Y | - 1)

である．

証明. 対 $(𝑋, 𝑌)$ を $X \times Y$ に値をとる一つの確率変数とみなし，対 $(𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))$ を ${1, \dots, 𝑀 𝑋} \times {1, \dots, 𝑀 𝑌}$ に値をとる一つの確率変数とみなす．共同復号器 $𝑑$ は後者から前者の推定を作る写像であり，その誤り確率は定義 14.3.1 の $𝑃 𝑒$ である． $| X \times Y | \geq 2$ だから，ファノの不等式（定理 1.10.1）を，当てる対象に $(𝑋, 𝑌)$ を，観測に $(𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))$ を，復号器に $𝑑$ を置いて当てると

𝐻 ((𝑋, 𝑌) ∣ 𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌)) \leq 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (| X \times Y | - 1)

を得る．

番号の対が運べる情報を抑える．定理 1.3.4 のエントロピー表現を二つの対に当てると

𝐼 ((𝑋, 𝑌); (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))) = 𝐻 (𝑋, 𝑌) - 𝐻 ((𝑋, 𝑌) ∣ 𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))

である．同じ定理 1.3.4 を逆向きに読むと，右辺の相互情報量は $𝐻 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌)) - 𝐻 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌) ∣ 𝑋, 𝑌)$ に等しく，第 $2$ 項は条件付きエントロピーだから非負である（定義 1.2.2 と命題 1.1.4）．よって

𝐼 ((𝑋, 𝑌); (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))) \leq 𝐻 (𝑓 𝑋 (𝑋), 𝑓 𝑌 (𝑌))

であり，番号の対のとりうる値は高々 $𝑀 𝑋 𝑀 𝑌$ 個だから定理 1.1.5 より右辺は $l o g (𝑀 𝑋 𝑀 𝑌) = l o g 𝑀 𝑋 + l o g 𝑀 𝑌$ 以下である．

二つを合わせると $𝐻 (𝑋, 𝑌) \leq l o g 𝑀 𝑋 + l o g 𝑀 𝑌 + 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (| X \times Y | - 1)$ であり，移項すれば主張を得る． $◼$

形式化: slepian_wolf_converse_sum (ソース)

三つの下界は別のことを言っている．定理 14.3.3 の右辺にある $𝐻 (𝑋 ∣ 𝑌)$ は， $𝑌$ をまるごと渡されている受け手にとってさえ $𝑋$ に残る不確かさである． $𝑋$ の側のレートはそこより下げられない，ただし誤りを許すぶんだけの余裕が右辺の補正項として付く，と読める．相手の情報源を知っている人を相手にするのだからいちばん甘い要求で，それでも $0$ にはならない．定理 14.3.5 の $𝐻 (𝑋, 𝑌)$ は逆に，二人が示し合わせて一人のように潰したとしても番号の総数はこれだけ要る，という要求である．14.1 節の五角形が，片方の利用者だけについての枠と二人を合わせた枠の二種類を持っていたのと，読み方の構造がそのまま対応している．違うのは向きで，あちらは上界，こちらは下界である．

例 14.3.2 の一つめの符号で三つを確かめておく．誤り確率がどれも $0$ で，例 1.1.2 より $𝐻 𝑏 (0) = 0$ だから，補正項はすべて消える．三つの下界はそれぞれ $l o g 𝑀 𝑋 \geq 𝐻 𝑏 (𝜌)$ ， $l o g 𝑀 𝑌 \geq 𝐻 𝑏 (𝜌)$ ， $l o g 𝑀 𝑋 + l o g 𝑀 𝑌 \geq 1 + 𝐻 𝑏 (𝜌)$ になり，実際の値 $1$ ， $1$ ， $2$ と比べると，どれも $1 - 𝐻 𝑏 (𝜌)$ だけの余裕をもって成り立っている．この値は例 14.3.2 の $𝐼 (𝑋; 𝑌)$ そのもので，三つの余裕がそろってそこに等しい． $𝜌 = 1 / 2$ のとき，すなわち $𝐼 (𝑋; 𝑌) = 0$ のときは，例 1.1.2 より $𝐻 𝑏 (1 / 2) = l o g 2 = 1$ だから余裕が消えて，三つとも等号になる．重なりが無ければこの素直な符号がすでに下界どおりで，削る余地がそもそも無い． $𝜌 = 0$ の符号のほうは， $l o g 𝑀 𝑌 = 0 = 𝐻 (𝑌 ∣ 𝑋)$ と $l o g 𝑀 𝑋 + l o g 𝑀 𝑌 = 1 = 𝐻 (𝑋, 𝑌)$ の二つが等号で，余裕が残るのは $𝑋$ 側の $1 - 𝐻 (𝑋 ∣ 𝑌) = 1$ だけである．削る余地を和については使い切っている．

長さを伸ばす

三つの下界は長さ $1$ の符号にも長さ $𝑛$ のブロックにも当たるが，右辺の $𝐻$ はブロック全体についてのエントロピーである．情報源が i.i.d. なら，それは $1$ 文字あたりの量の $𝑛$ 倍になり， $𝑛$ で割った形，つまりレートについての下界に直せる．

系 14.3.6（レートの下界）. $X$ と $Y$ を空でない有限アルファベットとし， $((𝑋 𝑖, 𝑌 𝑖)) 𝑖 \geq 0$ を， $X \times Y$ に値をとる互いに独立で同分布な確率変数の対の列とする． $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝑌 𝑛 : = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ と書き，各 $𝑛 \geq 1$ について $(𝑀 𝑋, 𝑛, 𝑀 𝑌, 𝑛, 𝑓 𝑋, 𝑛, 𝑓 𝑌, 𝑛, 𝑑 𝑛)$ を，定義 14.3.1 を $X 𝑛$ ， $Y 𝑛$ と対 $(𝑋 𝑛, 𝑌 𝑛)$ に当てた分散符号とし，その全体の誤り確率を $𝑃 𝑒, 𝑛$ と書く． $𝑃 𝑒, 𝑛 \to 0$ ならば次の三つが成り立つ．

$| X | \geq 2$ ならば
$l i m i n f 𝑛 \to \infty 1 𝑛 l o g 𝑀 𝑋, 𝑛 \geq 𝐻 (𝑋 0 ∣ 𝑌 0)$
である．
$| Y | \geq 2$ ならば
$l i m i n f 𝑛 \to \infty 1 𝑛 l o g 𝑀 𝑌, 𝑛 \geq 𝐻 (𝑌 0 ∣ 𝑋 0)$
である．
$| X \times Y | \geq 2$ ならば
$l i m i n f 𝑛 \to \infty 1 𝑛 (l o g 𝑀 𝑋, 𝑛 + l o g 𝑀 𝑌, 𝑛) \geq 𝐻 (𝑋 0, 𝑌 0)$
である．

証明. 第 $1$ の主張を詳しく書き，残りの二つは違うところだけを言う．

三つの誤り確率の関係をまず押さえる． $𝑛$ 番目の符号の $𝑋$ 側と $𝑌$ 側の誤り確率（定義 14.3.1）を $𝑃 𝑒, 𝑋, 𝑛$ ， $𝑃 𝑒, 𝑌, 𝑛$ と書く．復号の結果が対として当たっていれば成分ごとにも当たっているから，どの $𝑛$ でも $𝑃 𝑒, 𝑋, 𝑛 \leq 𝑃 𝑒, 𝑛$ かつ $𝑃 𝑒, 𝑌, 𝑛 \leq 𝑃 𝑒, 𝑛$ である．よって $𝑃 𝑒, 𝑛 \to 0$ から $𝑃 𝑒, 𝑋, 𝑛 \to 0$ と $𝑃 𝑒, 𝑌, 𝑛 \to 0$ も従う．

$𝑛 \geq 1$ を一つとる．第 $1$ の主張の仮定 $| X | \geq 2$ より $| X 𝑛 | = | X | 𝑛 \geq 2$ だから定理 14.3.3 が当たり

l o g 𝑀 𝑋, 𝑛 \geq 𝐻 (𝑋 𝑛 ∣ 𝑌 𝑛) - 𝐻 𝑏 (𝑃 𝑒, 𝑋, 𝑛) - 𝑃 𝑒, 𝑋, 𝑛 l o g (| X | 𝑛 - 1)

である．

右辺の主要項が $𝑛$ 倍になることを見る．定理 1.2.3 のチェイン則より $𝐻 (𝑋 𝑛 ∣ 𝑌 𝑛) = 𝐻 (𝑋 𝑛, 𝑌 𝑛) - 𝐻 (𝑌 𝑛)$ である．対の列 $((𝑋 𝑖, 𝑌 𝑖))$ は $X \times Y$ 上の i.i.d. 情報源だから，補題 2.3.3 をこの情報源に当てて $𝐻 (𝑋 𝑛, 𝑌 𝑛) = 𝑛 𝐻 (𝑋 0, 𝑌 0)$ を得る．成分の列 $(𝑌 𝑖)$ も i.i.d. だから，同じ補題より $𝐻 (𝑌 𝑛) = 𝑛 𝐻 (𝑌 0)$ である．ふたたび定理 1.2.3 より $𝐻 (𝑋 0, 𝑌 0) - 𝐻 (𝑌 0) = 𝐻 (𝑋 0 ∣ 𝑌 0)$ だから， $𝐻 (𝑋 𝑛 ∣ 𝑌 𝑛) = 𝑛 𝐻 (𝑋 0 ∣ 𝑌 0)$ である．

補正項が消えることを見る． $Λ 𝑛 : = 1 𝑛 l o g (| X | 𝑛 - 1)$ とおく． $| X | 𝑛 \geq 2$ より $| X | 𝑛 - 1 \geq 1$ だから $Λ 𝑛 \geq 0$ であり， $| X | 𝑛 - 1 \leq | X | 𝑛$ だから $Λ 𝑛 \leq l o g | X |$ で，列 $(Λ 𝑛)$ は上に有界である． $𝑃 𝑒, 𝑋, 𝑛 \to 0$ と合わせて補題 6.4.7 を当てると

𝐻 𝑏 (𝑃 𝑒, 𝑋, 𝑛) 𝑛 + 𝑃 𝑒, 𝑋, 𝑛 Λ 𝑛 ⟶ 0

である．

極限に移る．上の不等式を $𝑛$ で割ると

1 𝑛 l o g 𝑀 𝑋, 𝑛 \geq 𝐻 (𝑋 0 ∣ 𝑌 0) - ⎛ ⎜ ⎜ ⎝ 𝐻 𝑏 (𝑃 𝑒, 𝑋, 𝑛) 𝑛 + 𝑃 𝑒, 𝑋, 𝑛 Λ 𝑛 ⎞ ⎟ ⎟ ⎠

であり，右辺は $𝐻 (𝑋 0 ∣ 𝑌 0)$ に収束する．左辺はどの $𝑛$ でも右辺以上だから，左辺の下極限は右辺の極限以上であり，第 $1$ の主張を得る．

第 $2$ の主張は， $𝑋$ と $𝑌$ の役を入れ替えて定理 14.3.4 を当てれば同じ運びである（ $| Y 𝑛 | \geq 2$ は $| Y | \geq 2$ から出る）．第 $3$ の主張は定理 14.3.5 を当てる． $| X 𝑛 \times Y 𝑛 | = (| X | | Y |) 𝑛 \geq 2$ であり，主要項は補題 2.3.3 より $𝐻 (𝑋 𝑛, 𝑌 𝑛) = 𝑛 𝐻 (𝑋 0, 𝑌 0)$ で，補正項は $Λ' 𝑛 : = 1 𝑛 l o g ((| X | | Y |) 𝑛 - 1)$ が $0$ 以上 $l o g (| X | | Y |)$ 以下であることと $𝑃 𝑒, 𝑛 \to 0$ から，同じく補題 6.4.7 で消える． $◼$

形式化上の注記. 系 14.3.6 に対応する単独の宣言はない．定理 14.3.3・定理 14.3.4・定理 14.3.5 に紐付けた三つの宣言と，i.i.d. 情報源についての補題 2.3.3 に紐付けた entropy_jointRV_eq_n_smul (InformationTheory/Shannon/AEP/Basic/Converse.lean) を対の列と成分の列に当てたもの，および定理 1.2.3 に紐付けた entropy_pair_eq_entropy_add_condEntropy (InformationTheory/Shannon/Entropy.lean) の合成で得られる．レートの下極限をブロックのエントロピーと結ぶ宣言も，誤り確率が $0$ に向かう符号の族について述べる宣言も，達成できるレートの対の集合を一つの領域として書いた宣言も，分散符号の側には置かれていない．

達成可能性

道具を一つ借りる．Slepian–Wolf の達成可能性，すなわち「三つの下界が真に満たされているレートの対は実際に達成できる」という主張である．使う形を書いておく．

$X$ と $Y$ を空でない有限アルファベットとし， $((𝑋 𝑖, 𝑌 𝑖)) 𝑖 \geq 0$ を $X \times Y$ に値をとる互いに独立で同分布な確率変数の対の列とする．対 $(𝑋 0, 𝑌 0)$ の分布が全点で正であるとする．実数 $𝑅 𝑋$ ， $𝑅 𝑌$ が

𝐻 (𝑋 0 ∣ 𝑌 0) < 𝑅 𝑋, 𝐻 (𝑌 0 ∣ 𝑋 0) < 𝑅 𝑌, 𝐻 (𝑋 0, 𝑌 0) < 𝑅 𝑋 + 𝑅 𝑌

を満たすならば，各 $𝑛 \geq 1$ について定義 14.3.1 を $X 𝑛$ ， $Y 𝑛$ と対 $(𝑋 𝑛, 𝑌 𝑛)$ に当てた分散符号 $(𝑀 𝑋, 𝑛, 𝑀 𝑌, 𝑛, 𝑓 𝑋, 𝑛, 𝑓 𝑌, 𝑛, 𝑑 𝑛)$ がとれて， $1 𝑛 l o g 𝑀 𝑋, 𝑛 \to 𝑅 𝑋$ かつ $1 𝑛 l o g 𝑀 𝑌, 𝑛 \to 𝑅 𝑌$ であり，全体の誤り確率が $0$ に収束する．

当てる対象は定義 14.3.1 の分散符号だけで，依存するのは本節の終わりの地の文と，14.4 節が借りる 副情報つきレート歪みの達成可能性 の筋書きである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．くじで引くのは符号語ではなく 割り振り である． $X 𝑛$ の系列それぞれに ${1, \dots, 𝑀 𝑋, 𝑛}$ の番号を一様に独立に割り当て， $Y 𝑛$ の側も同じように ${1, \dots, 𝑀 𝑌, 𝑛}$ の番号を割り当てる．符号化はその割り当てを引くだけで，系列の中身を見ない．復号器は，受け取った二つの番号に割り当てられている系列の組のうち，結合典型（定義 6.2.3 の同時分布を対 $(𝑋, 𝑌)$ のものに取り替えたもの）である組がちょうど一つならそれを答え，そうでなければ誤る．この作り方を ランダムビニング（random binning）と呼ぶ．誤りの起こり方は 14.1 節で借りた 多元接続通信路の達成可能性 と同じく三種類に分かれ， $𝑋$ の側だけが紛れ込む， $𝑌$ の側だけが紛れ込む，両方が紛れ込む，の三つである．同じ番号に落ちる確率がそれぞれ $1 / 𝑀 𝑋, 𝑛$ ， $1 / 𝑀 𝑌, 𝑛$ ，その積なので，紛れ込みうる系列の本数を数えて掛けたものが $0$ に向かう条件が，三つの不等式そのものになる．

本書はこの主張を証明しない．三種の紛れ込みのうち両方が紛れる場合は，紛れ込みうる組の本数が結合典型な組の全体で抑えられるので，定理 6.2.5 にあたる評価で足りる．ところが $𝑋$ の側だけが紛れる場合に数えるのは， $𝑦 𝑛$ を一つ固定したときにそれと結合典型になる $𝑥 𝑛$ の本数であり，これは結合典型集合の全体ではなくその切り口である．本書はこの切り口の個数を抑える評価を持っていない．

形式化: slepian_wolf_full_rate_region_achievability (ソース)

形式化上の注記. 形式化の宣言は，借りた主張の仮定を細かく分けて受け取る．対の列が互いに独立で同分布であることに加えて，成分の列 $(𝑋 𝑖)$ と $(𝑌 𝑖)$ のそれぞれについても独立と同分布を別の仮定に置き，対の分布が全点で正であることに加えて， $𝑋 0$ の分布と $𝑌 0$ の分布が全点で正であることも別の仮定に置く．成分の列は対の列を成分ごとに写したものであり， $X$ も $Y$ も空でないので，足されたこの四つはどれも対の側の二つから従う．宣言が覆う範囲は借りた形と同じである．そのほかに各 $𝑋 𝑖$ ， $𝑌 𝑖$ が可測であることを求める．三つの不等式は借りた形と同じである．結論の誤り確率は，全体の誤り確率を長さ $𝑛$ のブロックについて書いた swErrorProb (InformationTheory/Shannon/SlepianWolf/Achievability.lean) で測っている．

借りた Slepian–Wolf の達成可能性 が覆うのは三つの不等式が真に成り立つ側，系 14.3.6 が禁じるのは同じ三つが逆向きに破れる側で，境界，すなわちどれかが等号で成り立つレートの対については，どちらも何も言っていない．二つはさらに「達成できる」を別の形で言っていて，借りた側が作るのはレートが目標の対に収束する符号の族，系 14.3.6 が受け取るのは誤り確率が $0$ に向かう符号の族で，返すのはそのレートの下極限についての不等式である．そのため本書は，達成できるレートの対の集合が三つの不等式の定める領域に一致する，という形の主張は述べず，保証できるのは三つの不等式のそれぞれについての片側ずつまでである．

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