14.6 通信路のクラスと UV 外界

定理 14.5.8 は劣化を仮定していた．劣化は強い条件である．定義 14.5.4 が求めているのは二つの出力の同時分布についての等式で，受け手 $2$ の出力が受け手 $1$ の出力から作り直せることまで言っている．ところが通信の問題として本当に効くのは，二人がそれぞれ自分の出力から何を読めるか，すなわち出力の周辺だけである．定義 14.5.2 の誤り確率は，受け手 $𝑗$ の復号器が自分の出力 $𝑦 𝑛 𝑗$ だけを見て決まる量である．相手の出力について和をとってしまえば残るのは周辺通信路 $𝑊 𝑗$ だから，符号の良し悪しを測る二つの量は $𝑊 1$ と $𝑊 2$ だけで決まり，同時分布は現れない．そこで本節では，周辺だけを見る条件を二つ置き，劣化がそのどちらも含意することを見る．

そのうえで，二人の性能を比べる条件を一切置かない外界を用意する．こちらは補助変数を二つ使い，五つ組の同時分布ひとつごとに四つの不等式が切る領域を作って，それを全部合わせた形に書かれる．本節の到達点は，三つのクラスでは容量領域がこの外界にちょうど一致する，という形にまとまる．

二つのクラス

定義 14.6.1（雑音がより少ない）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする．受け手 $1$ が受け手 $2$ より 雑音がより少ない（less noisy）とは，空でない有限アルファベット $U$ ， $U$ 上の分布 $𝑝 𝑈$ ， $U$ を入力・ $X$ を出力とする通信路 $𝐾$ （第6章定義 6.1.1）をどうとっても，同時分布が $𝑝 𝑈 (𝑢) 𝐾 (𝑥 ∣ 𝑢) 𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥)$ である四つ組 $(𝑈, 𝑋, 𝑌 1, 𝑌 2)$ について

𝐼 (𝑈; 𝑌 2) \leq 𝐼 (𝑈; 𝑌 1)

が成り立つことをいう．

補助変数 $𝑈$ を入力の手前に置いて，そこから通信路に流し込む．そういう流し込み方をどう選んでも， $𝑈$ について受け手 $1$ の側に届く情報が受け手 $2$ の側に届く情報を下回らない，というのが条件の中身である． $𝑈$ を動かすので，これは入力分布を一つ動かすより強い要求になっている．いっぽう見ているのは $𝐼 (𝑈; 𝑌 1)$ と $𝐼 (𝑈; 𝑌 2)$ という周辺どうしの量で，二つの出力の同時分布は現れない．

形式化: IsBCLessNoisy (ソース)

形式化上の注記（定義 14.6.1 と命題 14.6.5 に共通）. どちらの宣言も，動かす補助アルファベットを入力アルファベットと同じ型の階層のものに限っている．有限型はどれもその階層の型と対応がつき，相互情報量は文字の付け替えで変わらないので，限ったことは制限になっていない．この階層に入力アルファベット自身が入っていることが，定理 14.6.4 の証明で $U : = X$ ととれる理由でもある．

定義 14.6.2（能力がより高い）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とし， $𝑊 1$ ， $𝑊 2$ をその周辺通信路とする．受け手 $1$ が受け手 $2$ より 能力がより高い（more capable）とは， $X$ 上のどの分布 $𝑝$ についても

𝐼 (𝑝; 𝑊 2) \leq 𝐼 (𝑝; 𝑊 1)

が成り立つことをいう（ $𝐼 (𝑝; \cdot)$ は第6章定義 6.1.2 の通信路の相互情報量）．

こちらは補助変数を挟まず，入力分布を直に動かすだけである．定義 14.6.1 で $𝑈$ として入力そのものをとった場合にあたり，要求が弱い．名前のとおり，どの入力分布のもとでも受け手 $1$ のほうが多く運べる，という意味である．定義 6.1.4 の容量は $𝐼 (𝑝; \cdot)$ を入力分布について上限をとった値だから，この条件は容量の大小 $𝐶 (𝑊 2) \leq 𝐶 (𝑊 1)$ を含んでいる．逆向き，すなわち容量どうしの比較から定義 14.6.2 が出るかどうかは本書では扱わない．容量の比較は最大化した値を一つずつ比べるもので，同じ入力分布のもとでの比較にはなっていない．

形式化: IsBCMoreCapable (ソース)

定理 14.6.3. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする． $𝑊$ が定義 14.5.4 の意味で物理的に劣化しているなら，受け手 $1$ は受け手 $2$ より定義 14.6.1 の意味で雑音がより少ない．

証明. $U$ ， $𝑝 𝑈$ ， $𝐾$ をとり，四つ組 $(𝑈, 𝑋, 𝑌 1, 𝑌 2)$ を定義 14.6.1 のとおりとする．劣化の因子を $𝑊 2 ∣ 1$ と書く．

$𝑌 1$ を与えたとき $𝑈$ と $𝑌 2$ が条件付き独立であることを示す．四つ組の同時分布は，劣化の等式より

𝑝 (𝑢, 𝑥, 𝑦 1, 𝑦 2) = 𝑝 𝑈 (𝑢) 𝐾 (𝑥 ∣ 𝑢) 𝑊 1 (𝑦 1 ∣ 𝑥) 𝑊 2 ∣ 1 (𝑦 2 ∣ 𝑦 1)

である． $𝑥$ について和をとると $𝑝 (𝑢, 𝑦 1, 𝑦 2) = 𝑊 2 ∣ 1 (𝑦 2 ∣ 𝑦 1) \sum 𝑥 𝑝 𝑈 (𝑢) 𝐾 (𝑥 ∣ 𝑢) 𝑊 1 (𝑦 1 ∣ 𝑥)$ であり，右辺の和は $𝑝 (𝑢, 𝑦 1)$ にほかならない． $𝑝 (𝑦 1) > 0$ である $𝑦 1$ を固定して両辺を $𝑝 (𝑦 1)$ で割ると $𝑝 (𝑢, 𝑦 2 ∣ 𝑦 1) = 𝑊 2 ∣ 1 (𝑦 2 ∣ 𝑦 1) 𝑝 (𝑢 ∣ 𝑦 1)$ である．さらに $𝑢$ について和をとると $𝑝 (𝑦 2 ∣ 𝑦 1) = 𝑊 2 ∣ 1 (𝑦 2 ∣ 𝑦 1)$ だから

𝑝 (𝑢, 𝑦 2 ∣ 𝑦 1) = 𝑝 (𝑢 ∣ 𝑦 1) 𝑝 (𝑦 2 ∣ 𝑦 1)

であり，これが定義 1.8.3 の条件である．すなわち $𝑌 2 \to 𝑌 1 \to 𝑈$ はマルコフ連鎖をなす（定義 1.8.3 は両端について対称なので，同じことを $𝑈 \to 𝑌 1 \to 𝑌 2$ とも書ける）．

この連鎖にデータ処理不等式（定理 1.8.4）を当てると $𝐼 (𝑌 2; 𝑈) \leq 𝐼 (𝑌 1; 𝑈)$ である．命題 1.3.3 の対称性で向きをそろえれば主張を得る． $◼$

形式化: IsBCDegraded.isBCLessNoisy (ソース)

定理 14.6.4. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする．受け手 $1$ が受け手 $2$ より定義 14.6.1 の意味で雑音がより少ないなら，定義 14.6.2 の意味で能力がより高い．

証明. $X$ 上の分布 $𝑝$ をとる．定義 14.6.1 を， $U : = X$ ， $𝑝 𝑈 : = 𝑝$ ， $𝐾$ として入力をそのまま通す通信路（ $𝐾 (𝑥' ∣ 𝑢) = 1$ が $𝑥' = 𝑢$ のとき，それ以外で $0$ ）にとって当てる．この四つ組では $𝑋 = 𝑈$ が確率 $1$ で成り立つので， $𝐼 (𝑈; 𝑌 𝑗) = 𝐼 (𝑋; 𝑌 𝑗)$ である（ $𝑗 = 1, 2$ ）．いっぽう $(𝑋, 𝑌 𝑗)$ の同時分布は $𝑝 (𝑥) 𝑊 𝑗 (𝑦 𝑗 ∣ 𝑥)$ だから，命題 6.1.3 より $𝐼 (𝑋; 𝑌 𝑗) = 𝐼 (𝑝; 𝑊 𝑗)$ である．よって定義 14.6.1 の不等式がそのまま $𝐼 (𝑝; 𝑊 2) \leq 𝐼 (𝑝; 𝑊 1)$ になる． $◼$

形式化: IsBCLessNoisy.isBCMoreCapable (ソース)

二つの含意を合わせると，例 14.5.5 の通信路は三つのクラスのどれにも入る．あの例で定義 14.5.4 の意味の劣化を確かめてあるので，定理 14.6.3 と定理 14.6.4 がそのまま当たる． $0 < 𝜌 1 < 1$ かつ $0 < 𝜌 2 < 1$ にとれば， $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥)$ は正の数二つの積になって全点で正だから，全点で正であることまで求める主張にも当てられる．

二つの含意の逆向きが成り立つかどうかは，本書では扱わない．落ちるときに何を捨てているかは見ておける．劣化から雑音がより少ないへ落ちるところでは，同時分布についての条件を周辺どうしの比較に読み替えて，同時分布の情報を捨てている．雑音がより少ないから能力がより高いへ落ちるところでは，動かす対象を補助変数から入力そのものに狭めている．以下では三つの条件を，劣化がいちばん強く能力がより高いがいちばん弱いものとして扱う．次の命題は，真ん中の条件が重ね合わせ符号化にとって何をしてくれるかを述べたものである．

命題 14.6.5. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とし，受け手 $1$ は受け手 $2$ より定義 14.6.1 の意味で雑音がより少ないとする．空でない有限アルファベット $U$ ， $U$ 上の分布 $𝑝 𝑈$ ， $U$ を入力・ $X$ を出力とする通信路 $𝐾$ をとり，四つ組 $(𝑈, 𝑋, 𝑌 1, 𝑌 2)$ を定義 14.6.1 のとおりとすると

𝐼 (𝑋; 𝑌 1 ∣ 𝑈) + 𝐼 (𝑈; 𝑌 2) \leq 𝐼 ((𝑈, 𝑋); 𝑌 1)

である．

証明. 対 $(𝑈, 𝑋)$ から $𝑈$ を先に取り出すチェイン則（定理 1.5.1）で

𝐼 ((𝑈, 𝑋); 𝑌 1) = 𝐼 (𝑈; 𝑌 1) + 𝐼 (𝑋; 𝑌 1 ∣ 𝑈)

である．定義 14.6.1 より $𝐼 (𝑈; 𝑌 2) \leq 𝐼 (𝑈; 𝑌 1)$ だから，右辺の第 $1$ 項をこれで下から置き換えれば主張を得る． $◼$

形式化: bc_lessNoisy_infoJoint_ge (ソース)

14.5 節で借りた 重ね合わせ符号化の達成可能性 は，一般の形では三本の枠 $𝑅 1 < 𝐼 (𝑋; 𝑌 1 ∣ 𝑈)$ ， $𝑅 2 < 𝐼 (𝑈; 𝑌 2)$ ， $m a x (𝑅 1, 0) + 𝑅 2 < 𝐼 ((𝑈, 𝑋); 𝑌 1)$ を課し，劣化していてレートがどちらも正の場合にかぎって三本目を落としてよい，という形をしていた．三本目が要るのは，受け手 $1$ が雲と衛星の両方を読むので，その二つを合わせた量を超えては読めないからである．命題 14.6.5 が言っているのは，雑音がより少ないかぎりこの三本目が最初の二本から自動的に従う，ということである．劣化した通信路で三本目を落とせるのは，定理 14.6.3 によりそこが雑音のより少ない場合に含まれているからである．

UV 外界

二人の性能を比べる条件を置かないまま外側から抑えたい．定理 14.5.8 の $𝑈 𝑖$ は受け手 $2$ のメッセージと過去の出力を束ねたものだったが，二人に優劣がないなら受け手 $1$ の側にも同じ役の補助変数を用意しなければならない．そこで補助変数を二つ使う．記号を一つ断っておく．次の定義の $𝜈$ は五つ組の同時分布である．第8章 8.6 節は注水の水位を，第3章 3.1 節は力学系の測度を $𝜈$ と書いているが，本節の $𝜈$ はそのどちらとも別である．どれも引数をとらないので，章をまたいで読むときは気をつけたい．

定義 14.6.6（通信路の法と UV 外界）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする．可算集合 $U$ ， $V$ に値をとる変数の対 $(𝑈, 𝑉)$ を加えた五つ組 $(𝑈, 𝑉, 𝑋, 𝑌 1, 𝑌 2)$ の同時分布 $𝜈$ が $𝑊$ の 通信路の法 であるとは， $(𝑈, 𝑉, 𝑋)$ を与えたときの $(𝑌 1, 𝑌 2)$ の条件付き分布が $𝑋$ だけで決まって $𝑊 (\cdot, \cdot ∣ 𝑋)$ に等しいことをいう．通信路の法 $𝜈$ に対し，四つの不等式

𝑅 1 \leq 𝐼 (𝑉; 𝑌 1), 𝑅 2 \leq 𝐼 (𝑈; 𝑌 2), 𝑅 1 + 𝑅 2 \leq 𝐼 (𝑈; 𝑌 2) + 𝐼 (𝑋; 𝑌 1 ∣ 𝑈), 𝑅 1 + 𝑅 2 \leq 𝐼 (𝑉; 𝑌 1) + 𝐼 (𝑋; 𝑌 2 ∣ 𝑉)

をすべて満たす実数の対 $(𝑅 1, 𝑅 2)$ の集合を $U V (𝜈)$ と書く．通信路の法すべてにわたる $U V (𝜈)$ の合併の閉包を $𝑊$ の UV 外界 と呼び， $O 𝑈 𝑉 (𝑊)$ と書く．

補助アルファベットを可算にとったのは，外界をできるだけ広くとるためである．外界は広いほど主張として弱いので，合併を可算まで広げておけば抑えとしては安全側であり，そのぶん系 14.6.7 の一致は強い主張になる．

条件が二つの補助変数について対称でないことに注意する． $𝑈$ は受け手 $2$ の側の， $𝑉$ は受け手 $1$ の側の粗い層で，最初の二本は 14.5 節の二つの枠をそれぞれの受け手について書いたものである．和レートの枠が二本あるのは，どちらの受け手を先に読むかで別の抑えが出るからで，二本とも課す．通信路の法という条件は落とせない．四つの情報量は五つ組の同時分布だけで決まって $𝑊$ を名指していないので，条件を外すと合併の書き方から $𝑊$ が一切消える．入力を出力にそのまま写す同時分布のように， $𝑊$ を通さずに出力を作る同時分布まで入り込むからで，そうなると外界は二つの通信路を区別しない．

可算の補助変数を条件に置いたので，四つの情報量の読み方を断っておく．第1章の定義は有限アルファベットについてのものだから，四つの情報量はその定義をそのまま当てるのではなく，出力のエントロピーからの差の形（定理 1.3.4 と定理 1.4.3 の表現を，出力の側を第 $1$ 引数にとって読んだもの）で読む． $𝑌 1$ と $𝑌 2$ は有限アルファベットに値をとるので，条件の側に可算の変数を置いた条件付きエントロピーは，非負の項からなる可算個の和として 13.4 節の約束のとおりに定まる．各項は定理 1.1.5 により $l o g | Y 𝑗 |$ 以下の値に重みを掛けたものだから，和も $l o g | Y 𝑗 |$ 以下で，差はつねに定まる．

形式化: 同時分布ひとつごとの領域 uvRegion，合併の閉包 bcOuterRegionUV (ソース)

形式化上の注記. 通信路の法にあたる述語は IsUVChannelLaw（同じファイル）で，条件付き分布についての言い方ではなく，五つ組の同時分布を $(𝑈, 𝑉, 𝑋)$ の周辺と通信路との合成に等しいと書いた一本の等式として置かれている．また宣言は二つの補助アルファベットをどちらも自然数全体に固定している．可算集合はどれも自然数全体の部分集合と対応がつくので，これで可算な補助変数すべてを動かしたことになる．

道具を二つ借りる．どちらも定義 14.5.3 の容量領域と定義 14.6.6 の UV 外界を結ぶもので，向きが違う．

一つめは UV 外界は容量領域を含む，すなわち「達成できるレート対は四つの不等式を満たす法をもつ」という主張である．使う形を書いておく．

$𝑊$ をブロードキャスト通信路とする（二人の性能を比べる条件も，全点で正であることも求めない）．このとき $C (𝑊) \subseteq O 𝑈 𝑉 (𝑊)$ である．

当てる対象は定義 14.5.3 の容量領域と定義 14.6.6 の UV 外界だけで，依存するのは次に借りる 能力がより高い通信路の容量領域 の筋書きと，14.7 節の地の文である．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．骨格は定理 14.5.8 のものを二つの補助変数に広げたものである．長さ $𝑛$ の符号を一つとり，時刻 $𝑖$ ごとに $𝑈 𝑖 : = (M s g 2, 𝑌 < 𝑖 2)$ ， $𝑉 𝑖 : = (M s g 1, 𝑌 < 𝑖 1)$ とおく．受け手ごとの二本の枠は，定理 14.5.8 の受け手 $2$ の側の議論を，受け手 $1$ についても同じ形で行えば出る．和レートの二本は，二人ぶんのメッセージをまとめて抑えてから時刻ごとにほどくときに，どちらの補助変数を先に置くかで二通り出る．最後に時刻を一様に選ぶ変数を束ねて一文字あたりの形に直し，誤り確率を $0$ に送る．

本書はこの主張を証明しない．劣化を使えないので補題 14.5.7 の第 $3$ の主張にあたる評価が立たず，かわりに二つの和レートの枠を突き合わせる勘定が要るからである．

形式化: bc_capacity_subset_uv (ソース)

二つめは 能力がより高い通信路の容量領域，すなわち「能力がより高いなら外界がそのまま答えになる」という主張である．使う形を書いておく．

$𝑊$ をブロードキャスト通信路とし， $𝑊$ が全点で正，すなわち $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) > 0$ がすべての $𝑥$ ， $𝑦 1$ ， $𝑦 2$ で成り立つとする．受け手 $1$ が受け手 $2$ より定義 14.6.2 の意味で能力がより高いなら

C (𝑊) = O 𝑈 𝑉 (𝑊)

である．

当てる対象は定義 14.5.3 の容量領域と定義 14.6.6 の UV 外界だけで，依存するのは系 14.6.7 の証明と，その直後の地の文と，14.7 節の地の文である．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく． $\subseteq$ は一つめの借用 UV 外界は容量領域を含む そのものである． $\supseteq$ を出すには，補助変数を二つ使う定義 14.6.6 の点を，14.5 節で借りた 重ね合わせ符号化の達成可能性 が使う三本の枠 $𝑅 1 < 𝐼 (𝑋; 𝑌 1 ∣ 𝑈)$ ， $𝑅 2 < 𝐼 (𝑈; 𝑌 2)$ ， $m a x (𝑅 1, 0) + 𝑅 2 < 𝐼 ((𝑈, 𝑋); 𝑌 1)$ の内側へ移し，そこで届かせる（残すのは受け手 $2$ の側の $𝑈$ で，消すのは $𝑉$ のほうである）．能力がより高いことが効くのは三本目の枠を出すところで，定義 14.6.6 の和レートの枠の右辺が，この仮定のもとで $𝐼 ((𝑈, 𝑋); 𝑌 1)$ 以下に収まる．

14.5 節の借用を，劣化を仮定した形で引いてはいないことに注意する．引いているのは三本の枠を課した一般の形のほうである．劣化していない通信路で三本目を落とせるとは，本書は言えない．命題 14.6.5 が三本目を最初の二本から出してくれるのは雑音がより少ない場合までで，能力がより高いだけではそこまで言えないからである．

本書はこの主張を証明しない． $𝑉$ を消したうえで 14.5 節の借用が使える形にそろえるには，可算の補助変数を有限のアルファベットへ切り詰める段と，補助変数の分布と $𝐾$ を全点で正に直すために一様分布のほうへずらす段とが要り，最後にその二つの誤差を $0$ に送る極限で戻すことになるからである．

形式化: bc_moreCapable_capacity_eq_uv (ソース)

系 14.6.7. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とし， $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) > 0$ がすべての $𝑥 \in X$ ， $𝑦 1 \in Y 1$ ， $𝑦 2 \in Y 2$ で成り立つとする．受け手 $1$ が受け手 $2$ より定義 14.6.1 の意味で雑音がより少ないか，または $𝑊$ が定義 14.5.4 の意味で物理的に劣化しているなら

C (𝑊) = O 𝑈 𝑉 (𝑊)

である．

証明. 雑音がより少ない場合は，定理 14.6.4 より能力がより高いので，借りた 能力がより高い通信路の容量領域 がそのまま当たる．物理的に劣化している場合は，定理 14.6.3 より雑音がより少なく，いま示した場合に帰着する． $◼$

形式化: 雑音がより少ない場合 bc_lessNoisy_capacity_eq_uv (ソース)，劣化している場合 bc_degraded_capacity_eq_uv (ソース)

系 14.6.7 と，その手前で借りた 能力がより高い通信路の容量領域 を合わせると，全点で正な通信路については，三つのクラスで容量領域が決まったことになる．劣化・雑音がより少ない・能力がより高いの三つはこの順に弱くなるので，実際に内容があるのはいちばん弱い三つめで，前の二つはそこへの帰着である．どのクラスでも答えが同じ $O 𝑈 𝑉 (𝑊)$ になる，つまり二人の受け手に優劣があるかぎり，優劣の付き方によらず同じ形の式が容量領域を与える．

外界が具体的にどんな集合になるかを，例 14.5.5 の通信路で一度書き下しておく．補助変数は，受け手 $2$ の側の $𝑈$ に雲の層を，受け手 $1$ の側の $𝑉$ に入力そのものをとる． $𝑉$ は受け手 $1$ の側の粗い層だが，劣化した通信路で受け手 $1$ のほうが良い出力を見るのだから，粗くする理由がない．入力そのものにとると定義 14.6.6 の第 $4$ の不等式の右辺の第 $2$ 項が $0$ になり，この例ではその一本が第 $3$ の不等式に吸収されて，残る三本だけで領域が書ける．

例 14.6.8（二段の二元対称通信路で外界の点をとる）. 例 14.5.5 の通信路を $𝑊$ と書き， $𝜌 1 = 0.1$ ， $𝜌 2 = 0.2$ とする． $𝑈$ を ${0, 1}$ 上の一様分布に従う変数， $𝐵$ を $𝑈$ と独立で $P r [𝐵 = 1] = 0.1$ を満たす ${0, 1}$ 値の変数とし， $𝑋 : = 𝑈 \oplus 𝐵$ ， $𝑉 : = 𝑋$ とおいて， $𝑌 1 : = 𝑋 \oplus 𝑍 1$ ， $𝑌 2 : = 𝑌 1 \oplus 𝑍 2$ を例 14.5.5 のとおり作る（ $𝑍 1$ ， $𝑍 2$ は互いに独立で $(𝑈, 𝐵)$ とも独立とする）．このとき五つ組 $(𝑈, 𝑉, 𝑋, 𝑌 1, 𝑌 2)$ の同時分布 $𝜈$ は定義 14.6.6 の意味の通信路の法であり， $U V (𝜈)$ は三つの不等式

𝑅 1 \leq 1 - 𝐻 𝑏 (0.1), 𝑅 2 \leq 1 - 𝐻 𝑏 (0.308), 𝑅 1 + 𝑅 2 \leq 𝐻 𝑏 (0.18) - 𝐻 𝑏 (0.1) + 1 - 𝐻 𝑏 (0.308)

が切る領域である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．右辺の値はそれぞれおよそ $0.531$ ， $0.109$ ， $0.320$ である．さらに $U V (𝜈) \subseteq C (𝑊)$ である．

証明. 通信路の法であることを見る． $𝑉 = 𝑋$ だから $(𝑈, 𝑉, 𝑋)$ の値を与えれば $𝑋$ の値が決まる． $𝑌 1$ と $𝑌 2$ は $𝑋$ と $(𝑍 1, 𝑍 2)$ だけから作られ， $(𝑍 1, 𝑍 2)$ は $(𝑈, 𝐵)$ と独立だから， $(𝑈, 𝑉, 𝑋)$ を与えたときの $(𝑌 1, 𝑌 2)$ の条件付き分布は $𝑋$ だけで決まって例 14.5.5 の $𝑊 (\cdot, \cdot ∣ 𝑋)$ に等しい．これが定義 14.6.6 の条件である．

四つの情報量を計算する． $𝑈$ が一様で $𝐵$ が $𝑈$ と独立だから $𝑋$ も一様であり， $𝑌 1$ と $𝑌 2$ も一様である．例 14.5.5 より $𝑊 1$ は反転確率 $0.1$ の， $𝑊 2$ は反転確率 $0.1 \cdot 0.8 + 0.9 \cdot 0.2 = 0.26$ の二元対称通信路である．

第 $1$ の量は $𝐼 (𝑉; 𝑌 1) = 𝐼 (𝑋; 𝑌 1)$ である．定理 1.3.4 と命題 1.3.3 より $𝐼 (𝑋; 𝑌 1) = 𝐻 (𝑌 1) - 𝐻 (𝑌 1 ∣ 𝑋)$ であり， $𝑌 1$ が一様だから定理 1.1.5 の等号条件より $𝐻 (𝑌 1) = 1$ ， $𝑋 = 𝑥$ を与えると $𝑌 1$ が $𝑥$ と違う確率は $0.1$ だから例 1.1.2 より $𝐻 (𝑌 1 ∣ 𝑋) = 𝐻 𝑏 (0.1)$ である．

第 $2$ の量は $𝐼 (𝑈; 𝑌 2) = 𝐻 (𝑌 2) - 𝐻 (𝑌 2 ∣ 𝑈)$ である． $𝐻 (𝑌 2) = 1$ である． $𝑈 = 𝑢$ を与えると $𝑌 2 = 𝑢 \oplus 𝐵 \oplus 𝑍 1 \oplus 𝑍 2$ で， $𝐵$ と $𝑍 1$ の重なりが反転確率 $0.1 \cdot 0.9 + 0.9 \cdot 0.1 = 0.18$ ，そこに $𝑍 2$ が重なって $0.18 \cdot 0.8 + 0.82 \cdot 0.2 = 0.308$ である．よって $𝐻 (𝑌 2 ∣ 𝑈) = 𝐻 𝑏 (0.308)$ である．

第 $3$ の量は，定理 1.4.3 と命題 1.4.2 より $𝐼 (𝑋; 𝑌 1 ∣ 𝑈) = 𝐻 (𝑌 1 ∣ 𝑈) - 𝐻 (𝑌 1 ∣ 𝑈, 𝑋)$ である． $𝑈 = 𝑢$ を与えると $𝑌 1 = 𝑢 \oplus 𝐵 \oplus 𝑍 1$ で反転確率は $0.18$ だから $𝐻 (𝑌 1 ∣ 𝑈) = 𝐻 𝑏 (0.18)$ であり， $(𝑈, 𝑋)$ を与えると $𝑌 1 = 𝑋 \oplus 𝑍 1$ だから $𝐻 (𝑌 1 ∣ 𝑈, 𝑋) = 𝐻 𝑏 (0.1)$ である．

第 $4$ の量は $0$ である．定理 1.4.3 と命題 1.4.2 より $𝐼 (𝑋; 𝑌 2 ∣ 𝑉) = 𝐻 (𝑌 2 ∣ 𝑉) - 𝐻 (𝑌 2 ∣ 𝑉, 𝑋)$ であり， $𝑉 = 𝑋$ だから二つの項はどちらも $𝐻 (𝑌 2 ∣ 𝑋)$ で，差は $0$ である．

定義 14.6.6 の四つの不等式にこれらを入れる．第 $4$ の不等式の右辺は $1 - 𝐻 𝑏 (0.1)$ でおよそ $0.531$ であり，第 $3$ の不等式の右辺のおよそ $0.320$ 以上だから，第 $3$ を課せば第 $4$ は自動的に満たされる．残る三本が主張の三本である．値は $𝐻 𝑏 (0.1) = 0.4689 \dots$ ， $𝐻 𝑏 (0.18) = 0.6800 \dots$ ， $𝐻 𝑏 (0.308) = 0.8908 \dots$ から読める．

最後に包含を見る． $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥)$ は， $𝑌 1$ が $𝑥$ から反転確率 $0.1$ で， $𝑌 2$ が $𝑌 1$ から反転確率 $0.2$ で作られる確率の積だから，四つの組のどれでも正である．例 14.5.5 より $𝑊$ は劣化しているから系 14.6.7 が当たって $C (𝑊) = O 𝑈 𝑉 (𝑊)$ である． $U V (𝜈)$ は定義 14.6.6 の合併に含まれ，合併は自分の閉包に含まれるから， $U V (𝜈) \subseteq O 𝑈 𝑉 (𝑊) = C (𝑊)$ である． $◼$

$𝐵$ の反転確率を動かすと，二人の取り分が入れ替わる． $1 / 2$ にとると $𝑋$ が $𝑈$ と独立になって $𝐼 (𝑈; 𝑌 2) = 0$ ， $𝐼 (𝑋; 𝑌 1 ∣ 𝑈) = 𝐼 (𝑋; 𝑌 1)$ になり， $𝑅 1$ の枠が受け手 $1$ の側の容量 $1 - 𝐻 𝑏 (0.1) \approx 0.531$ いっぱいまで伸びて $𝑅 2$ の枠が $0$ に潰れる． $0$ にとると $𝑋 = 𝑈$ で $𝐼 (𝑋; 𝑌 1 ∣ 𝑈) = 0$ ， $𝐼 (𝑈; 𝑌 2) = 1 - 𝐻 𝑏 (0.26) \approx 0.173$ になり，今度は和の枠が $0.173$ まで縮む．上の $0.1$ はそのあいだの取り引きで， $𝑅 2$ に $0.109$ を渡すかわりに和の枠が $0.320$ に落ちている．雲の層を厚くするほど受け手 $2$ に回り，薄くするほど受け手 $1$ に回る．

協力外界

外界をもう一つ作る．こちらは補助変数を使わず，第6章の一人用の逆定理だけから出る．道具立てが軽いぶん抑えも粗いが，本書が自前で証明できる唯一の外界である．土台になる評価を先に切り出しておく．

補題 14.6.9. $𝐺$ を通信路（第6章定義 6.1.1）， $𝑅$ を実数とする．任意の $𝜁 > 0$ に対してある $𝑁 \geq 1$ があって， $𝑁 \leq 𝑛$ を満たすすべての $𝑛$ について，長さ $𝑛$ のブロック通信路符号（定義 6.2.1）で $1 𝑛 l o g 𝑀 \geq 𝑅$ かつ平均誤り確率が $𝜁$ 未満のものが存在するとする．このとき $𝑅 \leq 𝐶 (𝐺)$ （定義 6.1.4）である．

証明. $𝑅 \leq 0$ のときは命題 6.1.6 より $0 \leq 𝐶 (𝐺)$ だから主張が成り立つ．以下 $𝑅 > 0$ とする．

$𝜁 \in (0, 1)$ を一つとり，仮定の与える $𝑁$ をとる． $𝑁 \leq 𝑛$ を満たす $𝑛$ を一つ固定し，そこで得られる符号を $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛)$ と書く．メッセージが ${1, \dots, 𝑀 𝑛}$ 上の一様分布に従うとして議論する．これは符号に置く追加の仮定ではなく，評価のためにこちらが選ぶ分布である．このとき $𝑃 𝑛 : = P r [𝑑 𝑛 (𝑌 𝑛) \neq M s g]$ は平均誤り確率に等しく， $𝑃 𝑛 < 𝜁$ である． $1 𝑛 l o g 𝑀 𝑛 \geq 𝑅 > 0$ より $𝑀 𝑛 \geq 2$ でもある．

定理 6.4.5 の仮定を確かめる．符号語 $𝑋 𝑛 = 𝑐 𝑛 (M s g)$ を通信路に通すのだから， $𝑋 𝑛$ を与えたときの $𝑌 𝑛$ の条件付き分布は $\prod 𝑖 𝐺 (𝑦 𝑖 ∣ 𝑥 𝑖)$ であって $M s g$ にはよらない． $M s g$ によらないことが定義 1.8.3 の条件付き独立そのものだから $M s g \to 𝑋 𝑛 \to 𝑌 𝑛$ はマルコフ連鎖であり，積の形から補題 6.4.6 より $𝑋 𝑛$ と $𝑌 𝑛$ は各時刻で記憶がなく（定義 6.4.4）， $𝑋 𝑖$ の分布を $𝑝 𝑖$ と書けば対 $(𝑋 𝑖, 𝑌 𝑖)$ の同時分布は $𝑝 𝑖 (𝑥) 𝐺 (𝑦 ∣ 𝑥)$ である．よって定理 6.4.5 より

l o g 𝑀 𝑛 \leq 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; 𝑌 𝑖) + 𝐻 𝑏 (𝑃 𝑛) + 𝑃 𝑛 l o g (𝑀 𝑛 - 1)

である．命題 6.1.3 より $𝐼 (𝑋 𝑖; 𝑌 𝑖) = 𝐼 (𝑝 𝑖; 𝐺)$ であり，定義 6.1.4 の上限より $𝐼 (𝑝 𝑖; 𝐺) \leq 𝐶 (𝐺)$ だから，和は $𝑛 𝐶 (𝐺)$ 以下である．例 1.1.2 より $𝐻 𝑏 (𝑃 𝑛) \leq l o g 2 = 1$ であり， $𝑀 𝑛 \geq 2$ より $0 \leq l o g (𝑀 𝑛 - 1) \leq l o g 𝑀 𝑛$ だから， $𝑃 𝑛 < 𝜁$ と合わせて $𝑃 𝑛 l o g (𝑀 𝑛 - 1) \leq 𝜁 l o g 𝑀 𝑛$ である．三つを入れて移項すると

(1 - 𝜁) l o g 𝑀 𝑛 \leq 𝑛 𝐶 (𝐺) + 1

であり， $𝑛$ で割り $1 𝑛 l o g 𝑀 𝑛 \geq 𝑅$ と $1 - 𝜁 > 0$ を使うと $(1 - 𝜁) 𝑅 \leq 𝐶 (𝐺) + 1 𝑛$ である．

これが $𝑁 \leq 𝑛$ を満たすすべての $𝑛$ で成り立つので， $𝑛 \to \infty$ として $(1 - 𝜁) 𝑅 \leq 𝐶 (𝐺)$ を得る． $𝜁$ は $(0, 1)$ の任意の数だったから， $𝜁 \to 0$ として $𝑅 \leq 𝐶 (𝐺)$ を得る． $◻$

形式化上の注記（補題 14.6.9 と命題 14.6.10 に共通）. どちらにも同じ形の宣言がある．補題 14.6.9 には channelCoding_operational_rate_le_capacity (InformationTheory/Shannon/ChannelCoding/StrongConverseAsymptotic.lean)，命題 14.6.10 には同じ包含を述べる bc_capacity_subset_coop (InformationTheory/Shannon/BroadcastChannel/OuterBound.lean) である．どちらにもポインタは付けない．形式化はこの不等式を強逆定理（第6章定理 6.6.11）の対偶として出しており，そのため通信路ごとに，容量を達成する入力分布の存在と，その入力分布が生む出力分布が全点で正であることとを仮定に持つからである（命題 14.6.10 の側では，三つの通信路それぞれについて一組ずつ持つ）．本文の証明は第6章定理 6.4.5 の弱い逆定理だけを使うので，これらを仮定に置かない．宣言のほうが強い仮定をもつ形になる．命題 14.6.10 が抑えている集合そのものは bcOuterRegionCoop（bc_capacity_subset_coop と同じファイル）として置かれている．

命題 14.6.10（協力外界）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）， $𝑊 1$ ， $𝑊 2$ をその周辺通信路とし， $Y 1 \times Y 2$ を一つの出力アルファベットとみなした $𝑊$ を，第6章定義 6.1.1 の意味の通信路として読む． $𝐶$ を定義 6.1.4 の通信路容量とし，

O c o o p (𝑊) : = {(𝑅 1, 𝑅 2) \in ℝ 2 : 𝑅 1 \leq 𝐶 (𝑊 1), 𝑅 2 \leq 𝐶 (𝑊 2), 𝑅 1 + 𝑅 2 \leq 𝐶 (𝑊)}

とおく．このとき $C (𝑊) \subseteq O c o o p (𝑊)$ である（ $C (𝑊)$ は定義 14.5.3 の容量領域）．

証明. まず，達成可能な対（定義 14.5.3）が三つの不等式を満たすことを示す．三つとも補題 14.6.9 に帰着させる．そのために，ブロードキャスト符号から一人用のブロック通信路符号を三通りに作る．

受け手 $1$ の取り分は，相手のメッセージを一つ固定した符号に補題 14.6.9 を当てて出る. $𝜁 > 0$ をとり，定義 14.5.3 の与える $𝑁$ をとる． $𝑁 \leq 𝑛$ を満たす $𝑛$ を固定し，そこで得られる符号を $(𝑀 1, 𝑀 2, 𝑐, 𝑑 1, 𝑑 2)$ と書く． $𝑚 2$ を一つ固定するごとに，符号化写像 $𝑚 1 \mapsto 𝑐 (𝑚 1, 𝑚 2)$ と復号器 $𝑑 1$ の組は， $𝑊 1$ についての長さ $𝑛$ のブロック通信路符号（定義 6.2.1）である．定義 14.5.1 の積の形で $𝑦 𝑛 2$ について和をとると， $𝑥 𝑛$ を与えたときの $𝑌 𝑛 1$ の条件付き分布が $\prod 𝑖 𝑊 1 (\cdot ∣ 𝑥 𝑖)$ になるからである．この符号の平均誤り確率は $1 𝑀 1 \sum 𝑚 1 𝑃 𝑒, 1 (𝑚 1, 𝑚 2)$ であり，これを $𝑚 2$ について一様に平均したものが定義 14.5.2 の $¯ 𝑃 𝑒, 1$ にほかならない．平均以下の値をとる項が少なくとも一つあるので， $1 𝑀 1 \sum 𝑚 1 𝑃 𝑒, 1 (𝑚 1, 𝑚 2) \leq ¯ 𝑃 𝑒, 1 < 𝜁$ を満たす $𝑚 2$ がとれる．メッセージ数は $𝑀 1$ でレートは $1 𝑛 l o g 𝑀 1 \geq 𝑅 1$ だから， $𝜁$ と $𝑁$ の対応はそのまま補題 14.6.9 の仮定になり， $𝑅 1 \leq 𝐶 (𝑊 1)$ を得る．

受け手 $2$ の取り分は，添字を入れ替えた同じ論法で出る. 定義 14.5.1 の積の形で今度は $𝑦 𝑛 1$ について和をとれば $𝑊 2$ が残り，あとは上と同じである．

二人の合計は，二人の出力を並べたものを一つの出力とみなした符号から出る. $𝜁 > 0$ をとり，定義 14.5.3 を目標の誤り確率 $𝜁 / 2$ に対して使って $𝑁$ をとる． $𝑁 \leq 𝑛$ を満たす $𝑛$ を固定し，符号を $(𝑀 1, 𝑀 2, 𝑐, 𝑑 1, 𝑑 2)$ とする．メッセージの対 $(𝑚 1, 𝑚 2)$ を一つのメッセージとみなし，復号器を $(𝑦 𝑛 1, 𝑦 𝑛 2) \mapsto (𝑑 1 (𝑦 𝑛 1), 𝑑 2 (𝑦 𝑛 2))$ とすると，この組は $Y 1 \times Y 2$ を出力とする $𝑊$ についての長さ $𝑛$ のブロック通信路符号であり，メッセージ数は $𝑀 1 𝑀 2$ である．対として当てそこなうのは少なくとも一方を当てそこなうときだから， $(𝑚 1, 𝑚 2)$ での誤り確率は $𝑃 𝑒, 1 (𝑚 1, 𝑚 2) + 𝑃 𝑒, 2 (𝑚 1, 𝑚 2)$ 以下である．メッセージの対について平均すると，平均誤り確率は $¯ 𝑃 𝑒, 1 + ¯ 𝑃 𝑒, 2 < 𝜁$ である．レートは $1 𝑛 l o g (𝑀 1 𝑀 2) = 1 𝑛 l o g 𝑀 1 + 1 𝑛 l o g 𝑀 2 \geq 𝑅 1 + 𝑅 2$ だから，補題 14.6.9 より $𝑅 1 + 𝑅 2 \leq 𝐶 (𝑊)$ を得る．

三つの不等式は，閉包に移しても保たれる. $O c o o p (𝑊)$ は三つの半平面の共通部分である．半平面はどれも閉集合である．そこに属する対からなる収束列をとると，各不等式の両辺が極限に移って同じ不等式が成り立つので，14.2 節で借りた 平面の閉集合と閉包の基本性質 の第二により閉である．同じ基本性質の第一により，三つの共通部分も閉である．いま示したことから，達成可能な対全体は $O c o o p (𝑊)$ に含まれる．閉包はその集合を含む最小の閉集合だから（14.2 節の借用の第一）， $C (𝑊) \subseteq O c o o p (𝑊)$ である． $◼$

同じ $𝑊$ について $C (𝑊)$ と $𝐶 (𝑊)$ の二つが現れるが，前者は定義 14.5.3 の容量領域という平面の部分集合，後者は定義 6.1.4 の通信路容量という実数で，別の記号である．14.2 節例 14.2.6 も同じ書き分けをしている．

三本目の読み方を確かめておく． $Y 1 \times Y 2$ を一つの出力とみなすのは，二人の受け手が出力を持ち寄って協力し，二人ぶんのメッセージを一緒に言い当てる，という設定に相当する．協力してよいのだから，できることは増えるだけである．したがって協力した場合の限界 $𝐶 (𝑊)$ は，協力しない場合の和レートの限界でもある．名前はこの読み方から来ている．

協力外界が具体的にどんな数になるかを，例 14.6.8 と同じ通信路で見ておく．

例 14.6.11（二段の二元対称通信路で協力外界を書き下す）. 例 14.6.8 の通信路 $𝑊$ ，すなわち例 14.5.5 で $𝜌 1 = 0.1$ ， $𝜌 2 = 0.2$ としたものをとる．このとき

𝐶 (𝑊 1) = 1 - 𝐻 𝑏 (0.1), 𝐶 (𝑊 2) = 1 - 𝐻 𝑏 (0.26), 𝐶 (𝑊) = 1 - 𝐻 𝑏 (0.1)

である（ $𝐶$ は定義 6.1.4 の通信路容量， $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．したがって命題 14.6.10 の $O c o o p (𝑊)$ は，三つの不等式

𝑅 1 \leq 1 - 𝐻 𝑏 (0.1), 𝑅 2 \leq 1 - 𝐻 𝑏 (0.26), 𝑅 1 + 𝑅 2 \leq 1 - 𝐻 𝑏 (0.1)

が切る領域であり，右辺の値はそれぞれおよそ $0.531$ ， $0.173$ ， $0.531$ である．

証明. 例 14.5.5 より $𝑊 1$ は反転確率 $0.1$ の， $𝑊 2$ は反転確率 $0.1 \cdot 0.8 + 0.9 \cdot 0.2 = 0.26$ の二元対称通信路だから，前の二つは例 6.1.8 そのものである．

三つめに移る． $X$ 上の分布 $𝑝$ をとり， $𝑋$ が $𝑝$ に従い， $𝑋$ を与えたときの $(𝑌 1, 𝑌 2)$ の条件付き分布が $𝑊 (\cdot, \cdot ∣ 𝑋)$ であるような三つ組をとる．対 $(𝑌 1, 𝑌 2)$ から $𝑌 1$ を先に取り出すチェイン則（定理 1.5.1）を当て，命題 1.3.3 の対称性で向きをそろえると

𝐼 (𝑋; (𝑌 1, 𝑌 2)) = 𝐼 (𝑋; 𝑌 1) + 𝐼 (𝑌 2; 𝑋 ∣ 𝑌 1)

である．

第 $2$ 項が $0$ であることを示す．劣化の因子 $𝑊 2 ∣ 1$ を例 14.5.5 の証明のとおりにとる． $𝜌 1 = 0.1$ だから $𝑊 1$ は全点で正であり，定義 14.5.4 の等式を $𝑊 1 (𝑦 1 ∣ 𝑥)$ で割ると， $(𝑋, 𝑌 1) = (𝑥, 𝑦 1)$ を与えたときの $𝑌 2$ の条件付き分布は $𝑊 2 ∣ 1 (\cdot ∣ 𝑦 1)$ である．右辺は $𝑦 1$ だけの関数だから，補題 14.5.6 を， $𝐴$ に $𝑌 2$ ， $𝐵$ に対 $(𝑋, 𝑌 1)$ ， $𝑔$ にその値から $𝑌 1$ の値を与える対応と読み替えて当てると $P r [𝑌 2 = 𝑦 2 ∣ 𝑌 1] = 𝑊 2 ∣ 1 (𝑦 2 ∣ 𝑌 1)$ を得る．条件付き確率のチェイン則に二つを入れると $P r [𝑋 = 𝑥, 𝑌 2 = 𝑦 2 ∣ 𝑌 1] = P r [𝑋 = 𝑥 ∣ 𝑌 1] P r [𝑌 2 = 𝑦 2 ∣ 𝑌 1]$ であり，これが定義 1.8.3 の条件だから，命題 1.4.2 の等号条件より第 $2$ 項は $0$ である．

よって $𝐼 (𝑋; (𝑌 1, 𝑌 2)) = 𝐼 (𝑋; 𝑌 1)$ である．命題 6.1.3 より左辺は $𝐼 (𝑝; 𝑊)$ ，右辺は $𝐼 (𝑝; 𝑊 1)$ だから， $𝑝$ を動かして定義 6.1.4 の上限をとると $𝐶 (𝑊) = 𝐶 (𝑊 1)$ を得る．値は $𝐻 𝑏 (0.1) = 0.4689 \dots$ ， $𝐻 𝑏 (0.26) = 0.8267 \dots$ から読める． $◼$

例 14.6.8 の法が切る三本 $0.531$ ， $0.109$ ， $0.320$ と並べると，協力外界の効き目が見える． $𝑅 1$ の枠はどちらも $0.531$ で同じ値である． $𝑅 2$ の枠の $0.173$ は，上で $𝐵$ の反転確率を $0$ にとったときに例 14.6.8 の法が与えた値と同じで， $0.109$ より緩い．いちばん開くのは和の枠で， $0.531$ に対して $0.320$ である．協力外界は $𝑅 2$ を正にとっても和の枠を $0.531$ のままにしているのに対し，例 14.6.8 の法は $𝑅 2$ に $0.109$ を渡すかわりに和を $0.320$ に切っている．二人の取り分のあいだの取り引きは協力外界には現れず，そこを言い当てるのは定義 14.6.6 の合併のほうである．

本章はこれで，容量領域を二つの外界で抑えたことになる．借用の与えた $O 𝑈 𝑉 (𝑊)$ と，命題 14.6.10 の与える $O c o o p (𝑊)$ である．本書はこの二つの大小を比べない．どちらも容量領域を含むことしか示しておらず，一方が他方に含まれることを述べる主張は本書にも形式化にもないからである．系 14.6.7 と，その手前の借用とが覆う三つのクラスでは前者が容量領域そのものなので，そこでは前者のほうが後者に含まれる．クラスの外でどうなるかは本書の範囲にない．

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