14.7 Marton の内界

14.6 節は三つのクラスで容量領域を決めた．どのクラスも二人の受け手に優劣が付いていることを求めている．どのクラスにも入らない通信路，すなわち入力の選び方によって有利な受け手が入れ替わるような通信路については，容量領域は分かっていない．そういう通信路が本当にあることは，本節の終わりに例 14.7.6 として一つ書き下す．そこで内側と外側から挟む．外側からの評価は 14.6 節の UV 外界が与えた．本節は内側からの評価を置く． $𝑊$ が全点で正であれば，そこに置いた集合の点はどれも確かに達成できる．

道具立ては 14.5 節と同じ補助変数だが，置き方が違う．重ね合わせ符号化は補助変数を一つだけ置いて，それを二人に共通で見える粗い層にした．優劣が付かないなら共通の層をとる理由がないので，受け手ごとに一つずつ補助変数を置く．二つの符号帳を別々に作り，送る直前に組み合わせる，という作り方がそれにあたる．

本節は二つの補助変数を $𝑉 1$ ， $𝑉 2$ と書く． $𝑉$ の字は本書ですでに三通りに使われていて，第6章 6.6 節が強逆定理の証明で対数尤度比 $𝑉 𝑖$ に，第8章 8.3 節がガウス通信路の受信列 $𝑉$ に，第9章 9.4 節が情報源と再現の食い違い $𝑉$ に使っている．本節の $𝑉 1$ ， $𝑉 2$ はそのどれでもなく，情報量の引数に置かれる補助変数である．添字が付いているが，第6章のものにも添字が付くので見分けの根拠にはならない．直前の 14.6 節の $𝑉$ は，これと同じ役の補助変数である．定義 14.6.6 の $𝑈$ と $𝑉$ が本節の $𝑉 2$ と $𝑉 1$ にそれぞれ対応することは，下の定理 14.7.5 の証明が使う読み替えでもある．

四辺形

定義 14.7.1（Marton の四辺形）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする．空でない有限アルファベット $V 1$ ， $V 2$ と， $V 1 \times V 2$ 上の分布 $𝑝 𝑉$ ，および $V 1 \times V 2$ を入力・ $X$ を出力とする通信路 $𝐾$ （第6章定義 6.1.1）をとる．五つ組 $(𝑉 1, 𝑉 2, 𝑋, 𝑌 1, 𝑌 2)$ を，同時分布が

𝑝 𝑉 (𝑣 1, 𝑣 2) 𝐾 (𝑥 ∣ 𝑣 1, 𝑣 2) 𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥)

であるような確率変数の組とする．三つの不等式

𝑅 1 \leq 𝐼 (𝑉 1; 𝑌 1), 𝑅 2 \leq 𝐼 (𝑉 2; 𝑌 2), 𝑅 1 + 𝑅 2 \leq 𝐼 (𝑉 1; 𝑌 1) + 𝐼 (𝑉 2; 𝑌 2) - 𝐼 (𝑉 1; 𝑉 2)

をすべて満たす実数の対 $(𝑅 1, 𝑅 2)$ の集合を Marton の四辺形 と呼び， $M (𝑝 𝑉, 𝐾)$ と書く．

前の二本は，受け手ごとの粗い層がその受け手にどれだけ届くかを言っているだけで，14.5 節の枠と同じ形である．目新しいのは三本目の $- 𝐼 (𝑉 1; 𝑉 2)$ で，二つの補助変数が独立でないぶんだけ和レートから引かれている． $𝐼 (𝑉 1; 𝑉 2) = 0$ ，すなわち二つが独立なら三本目は前の二本から従うので，四辺形は長方形に戻る．四辺形と呼ぶが，定義 14.5.3 と同じくレートの非負性を課していないので左下には限りがない．呼び名は第一象限で見える形から来ている．

わざと相関をもたせたい理由は，送れる入力列が一本しかないところにある． $𝑉 1$ の側の符号語と $𝑉 2$ の側の符号語は $𝐾$ を通して一本の入力列に合わさるので，二つをまったく無関係に引くと，出来上がった入力列がどちらの受け手にも中途半端になりうる．二つの補助変数に相関を許せば，受け手ごとに合わせた符号語どうしのうち相性のよい組だけを選んで合わせられる．前の二本の右辺 $𝐼 (𝑉 1; 𝑌 1)$ と $𝐼 (𝑉 2; 𝑌 2)$ は，そうして選んだ組についての量になる．選ぶために余分な符号語を用意するぶんが $𝐼 (𝑉 1; 𝑉 2)$ で，三本目の和レートから引かれる．損が和レートの一本だけに掛かり，前の二本には掛からないところが，この取り引きの要である．どちらのとり方が得かは通信路による．定義 14.7.2 の内界は $(𝑝 𝑉, 𝐾)$ のとり方すべてにわたる合併なので，独立にとった長方形も相関をもたせた四辺形もどちらも入っており，得なほうが自動的に拾われる．余分な符号語がなぜちょうど $𝐼 (𝑉 1; 𝑉 2)$ のぶんで足り，しかもその損が和レートの一本だけに掛かるのかは，下で道具を借りたあとに数える．

形式化: martonRegion (ソース)

形式化上の注記. 形式化の三つの情報量は， $𝐼 (𝑉 1; 𝑌 1)$ ， $𝐼 (𝑉 2; 𝑌 2)$ ， $𝐼 (𝑉 1; 𝑉 2)$ をエントロピーの差の形（定理 1.3.4 の表現）で書いた martonInfo₁，martonInfo₂，martonInfoV₁V₂ (InformationTheory/Shannon/BroadcastChannel/Marton/Setup.lean) である．値は同じでも，宣言としては別の式である．

道具を一つ借りる．Marton の内界の達成可能性，すなわち「四辺形はまるごと達成できる」という主張である．使う形を書いておく．

$𝑊$ をブロードキャスト通信路とし， $𝑊$ が全点で正，すなわち $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) > 0$ がすべての $𝑥 \in X$ ， $𝑦 1 \in Y 1$ ， $𝑦 2 \in Y 2$ で成り立つとする．このとき，空でない有限アルファベットの対と $𝑝 𝑉$ ， $𝐾$ をどう選んでも

M (𝑝 𝑉, 𝐾) \subseteq C (𝑊)

である（ $C (𝑊)$ は定義 14.5.3 の容量領域）．

当てる対象は定義 14.7.1 の四辺形と定義 14.5.3 の容量領域だけで，依存するのは定理 14.7.3 の証明だけである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．受け手ごとに別の符号帳を引く． $𝑉 1$ の側の符号帳から $𝑚 1$ のための行を一本， $𝑉 2$ の側から $𝑚 2$ のための行を一本選び，その二本が結合典型になる組み合わせを探して，見つかった対を $𝐾$ に通して入力列を作る．二本の符号語をこうして噛み合わせるには，行ごとに符号語を何本か余分に用意しておかなければならない．余分に要る本数がちょうど $2 𝑛 𝐼 (𝑉 1; 𝑉 2)$ ほどで，それが和レートから引かれる．引き算の正体は，二本の符号語を噛み合わせる手間である．受け手 $1$ は $𝑉 1$ の符号帳だけを，受け手 $2$ は $𝑉 2$ の符号帳だけを読むので，前の二本の枠はそれぞれの読み取りが通る条件になっている．

本書はこの主張を証明しない．噛み合う組が確かに見つかることを言う段（この段は相互被覆と呼ばれる）が，第2章・第6章の典型性の道具の外にあるからである．さらに，補助変数の分布と $𝐾$ に全点で正であることを課さずに済ませる段が要る．そこは 14.2 節が借りた 五角形の包含 の筋書きと同じ形で，補助変数の側を一様分布のほうへわずかにずらして全点で正にし，三つの情報量が連続的に動くことを確かめて，ずらし幅を $0$ にする極限で戻す．

形式化: marton_region_subset_capacity_of_channel_fullSupport (ソース)

余分に要る本数を，筋書きよりもう一段細かく数えておく．勘定そのものは第6章定理 6.2.7 と同じである．あの定理が測ったのは，たがいに独立に引いた二本の列が結合典型になる確率で，二本の相互情報量を $𝐼$ と書けば $2 - 𝑛 𝐼$ ほどだった．第6章 6.3 節はこれを，誤って選びうる符号語の本数に掛けて $0$ に向かわせる向きに使い，符号帳の大きさの上限を出した．ここで要るのは逆向きである．メッセージ $𝑚 1$ ごとに $𝑉 1$ の側の候補を $2 𝑛 𝑅' 1$ 本， $𝑚 2$ ごとに $𝑉 2$ の側の候補を $2 𝑛 𝑅' 2$ 本用意すると，噛み合わせる相手の組は $2 𝑛 (𝑅' 1 + 𝑅' 2)$ 通りある．一組が噛み合う確率が $2 - 𝑛 𝐼 (𝑉 1; 𝑉 2)$ ほどだから，噛み合う組が見つかることを期待するには $𝑅' 1 + 𝑅' 2 > 𝐼 (𝑉 1; 𝑉 2)$ が要る．いっぽう受け手 $𝑗$ （ $𝑗 = 1, 2$ ）が読み分けるのは自分の側の符号帳の全体，すなわち $2 𝑛 (𝑅 𝑗 + 𝑅' 𝑗)$ 本だから，読み取りが通る条件は $𝑅 𝑗 + 𝑅' 𝑗 < 𝐼 (𝑉 𝑗; 𝑌 𝑗)$ である．この二本を足すと $𝑅 1 + 𝑅 2 < 𝐼 (𝑉 1; 𝑌 1) + 𝐼 (𝑉 2; 𝑌 2) - (𝑅' 1 + 𝑅' 2)$ になり， $𝑅' 1 + 𝑅' 2$ を $𝐼 (𝑉 1; 𝑉 2)$ のすぐ上にとれば定義 14.7.1 の三本目が出る．損が和レートの一本だけに掛かるのは，余分な本数を $𝑉 1$ の側と $𝑉 2$ の側にどう割り振るかがこちらの自由だからである．片側に寄せて $𝑅' 1 = 0$ ととれば，受け手 $1$ の側の条件は $𝑅 1 < 𝐼 (𝑉 1; 𝑌 1)$ のままで，余分のぶんは受け手 $2$ の側だけが払う．寄せ先を受け手ごとに選べるので，前の二本の枠はそれぞれ $𝐼 (𝑉 𝑗; 𝑌 𝑗)$ まで届く．

内界

定義 14.7.2（Marton の内界）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする．空でない有限アルファベットの対と $𝑝 𝑉$ ， $𝐾$ のとり方すべてにわたる Marton の四辺形（定義 14.7.1）の合併の閉包を Marton の内界 と呼び， $I 𝑀 (𝑊)$ と書く．

補助アルファベットの大きさに上限を置いていないので，合併は無限個の四辺形にわたる．閉包をとる理由は定義 14.2.1 や定義 14.5.3 と同じで，比べたい相手がどれも閉集合だからである．閉包は 14.2 節で借りた 平面の閉集合と閉包の基本性質 の意味でとる．

形式化: martonRegionUnion (ソース)

形式化上の注記. 宣言は補助アルファベットを ${1, \dots, 𝑘 + 1}$ の形のものに固定して $𝑘$ を動かす．空でない有限の補助アルファベットについての四辺形がどれもこの合併に含まれることは，形式化の側に martonRegion_subset_union（同じファイル）として置かれている．

定理 14.7.3. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とし， $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) > 0$ がすべての $𝑥 \in X$ ， $𝑦 1 \in Y 1$ ， $𝑦 2 \in Y 2$ で成り立つとする．このとき

I 𝑀 (𝑊) \subseteq C (𝑊)

である．

証明. 借りた Marton の内界の達成可能性 より，どの $(𝑝 𝑉, 𝐾)$ についても $M (𝑝 𝑉, 𝐾) \subseteq C (𝑊)$ だから，四辺形の合併も $C (𝑊)$ に含まれる． $C (𝑊)$ は定義 14.5.3 により達成可能な対全体の閉包であり，14.2 節で借りた 平面の閉集合と閉包の基本性質 の第一より，閉包は閉集合である．同じ第一により，合併の閉包 $I 𝑀 (𝑊)$ は合併を含む最小の閉集合だから， $C (𝑊)$ に含まれる． $◼$

形式化: martonRegionUnion_subset_capacity (ソース)

内界は外界に含まれる

内界と外界は，どちらも容量領域を挟むために別々に定めたものだから，両端どうしが直につながるかどうかは改めて確かめることになる．結論からいえばつながり，しかも定理 14.7.3 と違って $𝑊$ が全点で正であることは要らない．道具を一つ用意しておく．第1章定理 1.8.4 のデータ処理不等式は，条件を置かない形で述べられていた．以下で要るのは，何かを知っている人から見た形である．

補題 14.7.4（条件付きデータ処理不等式）. $𝐴$ ， $𝐵$ ， $𝐶$ ， $𝐷$ を有限集合に値をとる確率変数とする（どれも確率変数の組を一つにまとめたものでよい）．対 $(𝐷, 𝐴)$ ，対 $(𝐷, 𝐶)$ ， $𝐵$ がこの順にマルコフ連鎖（定義 1.8.3）をなすとする．このとき

𝐼 (𝐴; 𝐵 ∣ 𝐷) \leq 𝐼 (𝐶; 𝐵 ∣ 𝐷)

である．

証明. 対 $(𝐷, 𝐴)$ と対 $(𝐷, 𝐶)$ からそれぞれ $𝐷$ を先に取り出すチェイン則（定理 1.5.1）で $𝐼 ((𝐷, 𝐴); 𝐵) = 𝐼 (𝐷; 𝐵) + 𝐼 (𝐴; 𝐵 ∣ 𝐷)$ と $𝐼 ((𝐷, 𝐶); 𝐵) = 𝐼 (𝐷; 𝐵) + 𝐼 (𝐶; 𝐵 ∣ 𝐷)$ である．いっぽう仮定のマルコフ連鎖にデータ処理不等式（定理 1.8.4）を当てると $𝐼 ((𝐷, 𝐴); 𝐵) \leq 𝐼 ((𝐷, 𝐶); 𝐵)$ である． $𝐵$ のとりうる値の集合を $B$ と書くと，定理 1.1.5 より $𝐻 (𝐵) \leq l o g | B |$ であり，定理 1.2.4 より $𝐻 (𝐵 ∣ 𝐷) \leq 𝐻 (𝐵)$ だから，定理 1.3.4 の表す $𝐼 (𝐷; 𝐵) = 𝐻 (𝐵) - 𝐻 (𝐵 ∣ 𝐷)$ は有限の実数である．よって二つの等式を不等式に入れ，両辺から $𝐼 (𝐷; 𝐵)$ を引けば主張を得る． $◻$

形式化: condMutualInfo_le_of_markov_joint (ソース)

形式化上の注記. 宣言は有限集合に値をとる確率変数に限らず一般の空間について述べられており，そのぶん $𝐼 (𝐷; 𝐵)$ が有限であることを仮定に置いている．本文が有限アルファベットから引いた有限性が，そこに当たる．余分な仮定をもつ宣言にポインタを付けてよいかどうかは，その仮定が本文の主張の仮定から正則性として出るかどうかで決まる．ここでは補題 14.7.4 が置いた有限集合という仮定だけから有限性が出るので，宣言は本文の主張をそのまま覆っている．14.4 節命題 14.4.6 の注記が同じ形の余分な仮定にポインタを付けないと決めているのは，あちらの余分な仮定（値の集合が下に有界であること）が補題 14.4.4 という別の主張を経由してはじめて出るもので，宣言だけでは本文の主張に届かないからである．

定理 14.7.5. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする（全点で正であることは求めない）．このとき

I 𝑀 (𝑊) \subseteq O 𝑈 𝑉 (𝑊)

である（ $O 𝑈 𝑉 (𝑊)$ は定義 14.6.6 の UV 外界）．

証明. 空でない有限アルファベットの対と $𝑝 𝑉$ ， $𝐾$ を一組固定し，五つ組 $(𝑉 1, 𝑉 2, 𝑋, 𝑌 1, 𝑌 2)$ を定義 14.7.1 のとおりとする．成分を並べ替えた五つ組 $(𝑉 2, 𝑉 1, 𝑋, 𝑌 1, 𝑌 2)$ の同時分布を $𝜈$ と書く．つまり定義 14.6.6 の $𝑈$ に $𝑉 2$ を， $𝑉$ に $𝑉 1$ を当てる．以下，条件付き確率を $P r [\cdot ∣ \cdot]$ と書き，条件の側が正の確率をもつ点で考える．

$𝜈$ は通信路の法である. 定義 14.7.1 の同時分布で $(𝑉 2, 𝑉 1, 𝑋) = (𝑣 2, 𝑣 1, 𝑥)$ を与えると， $(𝑌 1, 𝑌 2)$ の条件付き分布は残る因子 $𝑊 (\cdot, \cdot ∣ 𝑥)$ である．これは $𝑥$ だけで決まるから，定義 14.6.6 の条件がそのまま成り立つ．有限アルファベットは可算なので，補助アルファベットについての条件も満たされている．

相関を引いた残りは，補助変数を条件に置いた入力の情報量で抑えられる. 二つの評価

𝐼 (𝑉 1; 𝑌 1) - 𝐼 (𝑉 1; 𝑉 2) \leq 𝐼 (𝑋; 𝑌 1 ∣ 𝑉 2), 𝐼 (𝑉 2; 𝑌 2) - 𝐼 (𝑉 1; 𝑉 2) \leq 𝐼 (𝑋; 𝑌 2 ∣ 𝑉 1)

を示す．前者を二段で出す．第一段は，相関を条件に移すところである．対 $(𝑉 2, 𝑌 1)$ から先に取り出すほうを二通りにとるチェイン則（定理 1.5.1）を当て，どちらも命題 1.3.3 と命題 1.4.2 の対称性で向きをそろえると， $𝐼 (𝑉 1; (𝑉 2, 𝑌 1)) = 𝐼 (𝑉 1; 𝑉 2) + 𝐼 (𝑉 1; 𝑌 1 ∣ 𝑉 2)$ と $𝐼 (𝑉 1; (𝑌 1, 𝑉 2)) = 𝐼 (𝑉 1; 𝑌 1) + 𝐼 (𝑉 1; 𝑉 2 ∣ 𝑌 1)$ である．左辺は対の並べ方によらないので二つの右辺は等しく，命題 1.4.2 より $𝐼 (𝑉 1; 𝑉 2 ∣ 𝑌 1) \geq 0$ だから $𝐼 (𝑉 1; 𝑌 1) - 𝐼 (𝑉 1; 𝑉 2) \leq 𝐼 (𝑉 1; 𝑌 1 ∣ 𝑉 2)$ である．

第二段は，補助変数を入力に取り替えるところである．補題 14.7.4 を，その $𝐴$ に $𝑉 1$ ， $𝐵$ に $𝑌 1$ ， $𝐶$ に $𝑋$ ， $𝐷$ に $𝑉 2$ と読み替えて当てる．仮定を確かめる．条件の側に $𝑉 2$ が入っているので，対 $(𝑉 2, 𝑉 1)$ と $𝑌 1$ の条件付き独立は， $𝑉 1$ と $𝑌 1$ の条件付き独立と同じことである．そこで $(𝑉 2, 𝑋)$ を与えたとき $𝑉 1$ と $𝑌 1$ が条件付き独立であることを示す．定義 14.7.1 の同時分布で $(𝑉 1, 𝑉 2, 𝑋) = (𝑣 1, 𝑣 2, 𝑥)$ を与えると $(𝑌 1, 𝑌 2)$ の条件付き分布は $𝑊 (\cdot, \cdot ∣ 𝑥)$ だから，第 $1$ 成分についての周辺をとって $P r [𝑌 1 = 𝑦 1 ∣ 𝑉 1, 𝑉 2, 𝑋] = 𝑊 1 (𝑦 1 ∣ 𝑋)$ である（ $𝑊 1$ は定義 14.5.1 の周辺通信路）．右辺は $(𝑉 2, 𝑋)$ の値から読めるので，補題 14.5.6 を， $𝐴$ に $𝑌 1$ ， $𝐵$ に三つ組 $(𝑉 1, 𝑉 2, 𝑋)$ ， $𝑔$ にその値から $(𝑉 2, 𝑋)$ の値を与える対応， $𝑓$ に「 $𝑌 1$ の値 $𝑦 1$ と $(𝑉 2, 𝑋)$ の値の対から，そこに含まれる $𝑋$ の値 $𝑥$ を読んで $𝑊 1 (𝑦 1 ∣ 𝑥)$ を返す写像」と読み替えて当てると $P r [𝑌 1 = 𝑦 1 ∣ 𝑉 2, 𝑋] = 𝑊 1 (𝑦 1 ∣ 𝑋)$ を得る．条件付き確率のチェイン則に二つを入れると $P r [𝑉 1 = 𝑣 1, 𝑌 1 = 𝑦 1 ∣ 𝑉 2, 𝑋] = P r [𝑉 1 = 𝑣 1 ∣ 𝑉 2, 𝑋] P r [𝑌 1 = 𝑦 1 ∣ 𝑉 1, 𝑉 2, 𝑋] = P r [𝑉 1 = 𝑣 1 ∣ 𝑉 2, 𝑋] P r [𝑌 1 = 𝑦 1 ∣ 𝑉 2, 𝑋]$ であり，これが定義 1.8.3 の条件である．よって補題 14.7.4 より $𝐼 (𝑉 1; 𝑌 1 ∣ 𝑉 2) \leq 𝐼 (𝑋; 𝑌 1 ∣ 𝑉 2)$ であり，第一段と合わせて前者を得る．後者は， $(𝑉 1, 𝑌 1)$ と $(𝑉 2, 𝑌 2)$ を入れ替えた五つ組に同じ議論を当てれば出る．入れ替えた組の同時分布も定義 14.7.1 の形をしている（ $𝑝 𝑉$ の二つの成分を入れ替え， $𝐾$ の引数も入れ替え， $𝑊$ の二つの出力を入れ替えたものをとればよい）． $𝐼 (𝑉 1; 𝑉 2)$ が入れ替えで変わらないことは命題 1.3.3 による．

四辺形は $U V (𝜈)$ に含まれる. $(𝑅 1, 𝑅 2) \in M (𝑝 𝑉, 𝐾)$ をとる．定義 14.7.1 の第 $1$ と第 $2$ の不等式は，読み替えのもとで定義 14.6.6 の第 $1$ と第 $2$ の不等式そのものである．第 $3$ の不等式の右辺に，いま示した二つの評価をそれぞれ当てると

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

であり，これが定義 14.6.6 の第 $3$ と第 $4$ の不等式である．よって $M (𝑝 𝑉, 𝐾) \subseteq U V (𝜈)$ である．

合併と閉包に移しても包含は保たれる. $𝜈$ は通信路の法だから $U V (𝜈)$ は定義 14.6.6 の合併に含まれ，合併はその閉包 $O 𝑈 𝑉 (𝑊)$ に含まれる． $(𝑝 𝑉, 𝐾)$ は任意だったから，四辺形の合併が $O 𝑈 𝑉 (𝑊)$ に含まれる．14.2 節で借りた 平面の閉集合と閉包の基本性質 の第一より $O 𝑈 𝑉 (𝑊)$ は閉集合であり，同じ第一により合併の閉包 $I 𝑀 (𝑊)$ は合併を含む最小の閉集合だから， $O 𝑈 𝑉 (𝑊)$ に含まれる． $◼$

形式化: martonRegionUnion_subset_uv (ソース)

形式化上の注記. 定理 14.7.5 の証明は $(𝑝 𝑉, 𝐾)$ を一組固定するところから始まるが，形式化にもその段に対応する単独の宣言 marton_region_subset_uv (InformationTheory/Shannon/BroadcastChannel/OuterBoundUV/MartonBridge.lean) がある．ただしその結論は，証明が途中で示す $M (𝑝 𝑉, 𝐾) \subseteq U V (𝜈)$ ではなく，一組の四辺形が UV 外界そのものに含まれること，すなわち合併と閉包に移す段まで済ませた形である．宣言が合併の中で名指す法も，本文の $𝜈$ そのものではなく， $𝜈$ の二つの補助アルファベットを自然数へ付け替えたものである（定義 14.6.6 の合併が自然数を補助アルファベットとする法をわたることは，14.6 節の注記で断ったとおりである）．この宣言にも， $𝑝 𝑉$ ・ $𝐾$ ・ $𝑊$ が全点で正であることは求められていない．

挟み込み

定理 14.7.3 と，14.6 節で借りた UV 外界は容量領域を含む を並べると， $𝑊$ が全点で正であるかぎり

I 𝑀 (𝑊) \subseteq C (𝑊) \subseteq O 𝑈 𝑉 (𝑊)

である．定理 14.7.5 は，この両端を真ん中を経由せずに直につないでいる．真ん中が左の端と一致するのかどうかも，右の端と一致するのかどうかも，本書も形式化も述べない．一般のブロードキャスト通信路の容量領域は分かっていない，というのが現在の状況である．分かっていないというのは，領域を与える式がまだ見つかっていないという意味であって，そういう式が存在しえないことが示されているわけではない．

14.6 節の三つのクラスでは，右の二つが一致する（系 14.6.7 と，そこで借りた 能力がより高い通信路の容量領域）．左がそれに一致するかどうかは，そのクラスの中でも本書は述べない．内界が容量領域を超えないという向きは定理 14.7.3 が与えるが，逆向き，すなわち容量領域の点がどれも四辺形の合併の閉包に入ることを述べる主張は，本書にも形式化にもない．挟み込みで言えているのは，左と右のあいだに真ん中があるというところまでである．

外側からの評価は命題 14.6.10 の協力外界にもう一つあり， $𝑊$ が全点で正なら定理 14.7.3 と命題 14.6.10 を容量領域でつないで $I 𝑀 (𝑊) \subseteq O c o o p (𝑊)$ も出る．協力外界と UV 外界のどちらが小さいかは，14.6 節の終わりで断ったとおり本書は述べないので，外側からの評価は二つ並んだままである．

どのクラスにも入らない通信路

本節の出発点は，14.6 節の三つのクラスのどれにも入らない通信路がある，というところだった．そういう通信路を一つ書き下しておく．二人の受け手に別の種類の雑音を割り当てれば，入力の選び方で有利な受け手が入れ替わる．

例 14.7.6（対称な雑音と消失を並べる）. $X = {0, 1}$ ， $Y 1 = {0, 1}$ ， $Y 2 = {0, 1, *}$ とし， $𝑊 1$ を反転確率 $0.1$ の二元対称通信路（例 6.1.8）， $𝑊 2$ を消失確率 $0.5$ の二元消失通信路（例 6.1.9）として，

𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) : = 𝑊 1 (𝑦 1 ∣ 𝑥) 𝑊 2 (𝑦 2 ∣ 𝑥)

で定まる対応を $𝑊$ とする．このとき $𝑊$ は定義 14.5.1 の意味でブロードキャスト通信路であり，その二つの周辺通信路は $𝑊 1$ ， $𝑊 2$ である． $X$ 上の分布 $𝑝$ が $𝑝 (1) = 1 / 2$ を満たすなら $𝐼 (𝑝; 𝑊 2) < 𝐼 (𝑝; 𝑊 1)$ であり， $𝑝 (1) = 0.05$ を満たすなら $𝐼 (𝑝; 𝑊 1) < 𝐼 (𝑝; 𝑊 2)$ である（ $𝐼 (𝑝; \cdot)$ は第6章定義 6.1.2 の通信路の相互情報量）．したがって受け手 $1$ が受け手 $2$ より定義 14.6.2 の意味で能力がより高いことはなく，受け手の番号を入れ替えても同じである． $𝑊$ は 14.6 節の三つのクラスのどれにも，どちらの向きにも入らない．

証明. 通信路であることと周辺通信路を確かめる． $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) \geq 0$ であり， $\sum 𝑦 1, 𝑦 2 𝑊 1 (𝑦 1 ∣ 𝑥) 𝑊 2 (𝑦 2 ∣ 𝑥)$ は二つの和の積 $1 \cdot 1$ に等しい．定義 14.5.1 の周辺は， $𝑦 2$ について和をとると $𝑊 1 (𝑦 1 ∣ 𝑥)$ ， $𝑦 1$ について和をとると $𝑊 2 (𝑦 2 ∣ 𝑥)$ である．

二つの量を入力分布の式で書く． $𝜋 : = 𝑝 (1)$ とおく（例 6.1.8 と例 6.1.9 が置く $𝜋$ と同じである）．消失通信路の側は，例 6.1.9 が一般の入力分布について与える式に消失確率 $𝜂 = 0.5$ を入れて $𝐼 (𝑝; 𝑊 2) = 𝐻 𝑏 (𝜋) / 2$ である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．対称通信路の側は，例 6.1.8 が与える同じ形の式に反転確率 $𝜌 = 0.1$ を入れて $𝐼 (𝑝; 𝑊 1) = 𝐻 𝑏 (0.9 𝜋 + 0.1 (1 - 𝜋)) - 𝐻 𝑏 (0.1)$ である．

値を入れる． $𝜋 = 1 / 2$ では $0.9 𝜋 + 0.1 (1 - 𝜋) = 1 / 2$ だから $𝐼 (𝑝; 𝑊 1) = 1 - 𝐻 𝑏 (0.1)$ で， $𝐻 𝑏 (0.1) = 0.4689 \dots$ よりおよそ $0.531$ である．いっぽう $𝐼 (𝑝; 𝑊 2) = 𝐻 𝑏 (1 / 2) / 2 = 1 / 2$ だから， $𝐼 (𝑝; 𝑊 2) < 𝐼 (𝑝; 𝑊 1)$ である． $𝜋 = 0.05$ では $0.9 \cdot 0.05 + 0.1 \cdot 0.95 = 0.14$ だから $𝐼 (𝑝; 𝑊 1) = 𝐻 𝑏 (0.14) - 𝐻 𝑏 (0.1)$ で， $𝐻 𝑏 (0.14) = 0.5842 \dots$ よりおよそ $0.115$ である．いっぽう $𝐼 (𝑝; 𝑊 2) = 𝐻 𝑏 (0.05) / 2$ で， $𝐻 𝑏 (0.05) = 0.2863 \dots$ よりおよそ $0.143$ だから， $𝐼 (𝑝; 𝑊 1) < 𝐼 (𝑝; 𝑊 2)$ である．

クラスの外にあることを見る．定義 14.6.2 が求めているのは，どの入力分布についても $𝐼 (𝑝; 𝑊 2) \leq 𝐼 (𝑝; 𝑊 1)$ が成り立つことである． $𝜋 = 0.05$ の分布がこれを破るので，受け手 $1$ は受け手 $2$ より能力がより高くない．定理 14.6.4 の対偶より受け手 $1$ は受け手 $2$ より定義 14.6.1 の意味で雑音がより少なくもなく，定理 14.6.3 の対偶より $𝑊$ は定義 14.5.4 の意味で物理的に劣化してもいない．番号を入れ替えた向きは，出力の対の二つの成分を入れ替えて得られるブロードキャスト通信路に同じ議論を当てる．その周辺通信路は順に $𝑊 2$ ， $𝑊 1$ なので，定義 14.6.2 がそちらに求めるのはどの入力分布についても $𝐼 (𝑝; 𝑊 1) \leq 𝐼 (𝑝; 𝑊 2)$ が成り立つことであり， $𝜋 = 1 / 2$ の分布がこれを破る．あとは同じ二つの対偶による． $◼$

一様な入力では，反転確率 $0.1$ の二元対称通信路のほうが消失確率 $0.5$ の二元消失通信路より多く運べる．これは第6章 6.1 節が計算した二つの容量 $1 - 𝐻 𝑏 (0.1)$ と $1 - 0.5$ の比較そのものである．ところが入力を $0$ の側へ偏らせると，対称通信路の側では出力の偏りが雑音で薄められて $𝐻 𝑏 (0.14)$ までしか下がらず，そこから $𝐻 𝑏 (0.1)$ を引くと残りが小さい．消失通信路の側は届いたビットがそのまま信用できるので， $𝐻 𝑏 (0.05)$ に $1 / 2$ を掛けるだけで済む．その差が $𝜋 = 0.05$ では大小をひっくり返す．

どちらの受け手に合わせて入力を選ぶかで優劣が入れ替わるので，14.6 節の三つのクラスはどれも当たらず，系 14.6.7 も，そこで借りた 能力がより高い通信路の容量領域 も，この $𝑊$ には当てられない．内側からの評価も，この $𝑊$ にはそのままでは当てられない．定理 14.7.3 は $𝑊$ が全点で正であることを求めるが，消失通信路の側に $𝑊 2 (1 - 𝑥 ∣ 𝑥) = 0$ があるので，この $𝑊$ はそれを満たさないからである．残るのは全点で正であることを求めない三つ，すなわち定理 14.7.5 と，14.6 節で借りた UV 外界は容量領域を含む と，命題 14.6.10 の協力外界である．内界と容量領域を直に結ぶ向きは，この $𝑊$ には残らない．

内界と外界がそれぞれどのあたりにあるかを，一点ずつ数で見ておく．

例 14.7.7（内界の二点と協力外界の枠）. 例 14.7.6 の通信路 $𝑊$ をとる．対 $(1 - 𝐻 𝑏 (0.1), 0)$ と対 $(0, 1 / 2)$ はどちらも定義 14.7.2 の Marton の内界 $I 𝑀 (𝑊)$ に属する．いっぽう定義 14.5.3 の容量領域 $C (𝑊)$ に属する対 $(𝑅 1, 𝑅 2)$ はどれも

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

を満たす．二つの右辺の値はおよそ $0.531$ と $0.5$ である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．

証明. 内界の二点から見る． $V 1 : = {0, 1}$ ， $V 2 : = {0}$ とし， $𝑝 𝑉$ を第 $1$ 成分について一様な分布， $𝐾$ を対 $(𝑣 1, 𝑣 2)$ を $𝑣 1$ に写す通信路にとる．このとき確率 $1$ で $𝑋 = 𝑉 1$ であり， $𝑋$ は一様である． $𝑉 2$ は定数だから，定義 1.1.1 より $𝐻 (𝑉 2) = 0$ であり，定義 1.2.2 の条件付きエントロピー $𝐻 (𝑉 2 ∣ 𝑌 2)$ と $𝐻 (𝑉 2 ∣ 𝑉 1)$ も $0$ である．命題 1.3.3 で向きをそろえて定理 1.3.4 を読むと $𝐼 (𝑉 2; 𝑌 2) = 𝐻 (𝑉 2) - 𝐻 (𝑉 2 ∣ 𝑌 2) = 0$ と $𝐼 (𝑉 1; 𝑉 2) = 𝐻 (𝑉 2) - 𝐻 (𝑉 2 ∣ 𝑉 1) = 0$ を得る．確率 $1$ で $𝑋 = 𝑉 1$ だから $𝐼 (𝑉 1; 𝑌 1) = 𝐼 (𝑋; 𝑌 1)$ であり， $𝑋$ の分布を $𝑝$ と書くと対 $(𝑋, 𝑌 1)$ の同時分布は $𝑝 (𝑥) 𝑊 1 (𝑦 1 ∣ 𝑥)$ だから命題 6.1.3 より $𝐼 (𝑋; 𝑌 1) = 𝐼 (𝑝; 𝑊 1)$ である．例 6.1.8 の一般の入力分布についての式に $𝜋 = 1 / 2$ と $𝜌 = 0.1$ を入れると $𝐼 (𝑝; 𝑊 1) = 𝐻 𝑏 (1 / 2) - 𝐻 𝑏 (0.1) = 1 - 𝐻 𝑏 (0.1)$ である．よって定義 14.7.1 の三つの不等式は $𝑅 1 \leq 1 - 𝐻 𝑏 (0.1)$ ， $𝑅 2 \leq 0$ ， $𝑅 1 + 𝑅 2 \leq 1 - 𝐻 𝑏 (0.1)$ となり，一つめの対はこれをすべて満たす．四辺形は定義 14.7.2 の合併に含まれ，合併はその閉包に含まれるから，この対は $I 𝑀 (𝑊)$ に属する．二つめの対は，二つの補助変数の役を入れ替えて同じことをする． $V 1 : = {0}$ ， $V 2 : = {0, 1}$ ととると $𝐼 (𝑉 1; 𝑌 1) = 0$ と $𝐼 (𝑉 1; 𝑉 2) = 0$ が同じ理由で出て，例 6.1.9 の式に $𝜋 = 1 / 2$ と $𝜂 = 1 / 2$ を入れると $𝐼 (𝑉 2; 𝑌 2) = 𝐼 (𝑋; 𝑌 2) = 𝐼 (𝑝; 𝑊 2) = 𝐻 𝑏 (1 / 2) / 2 = 1 / 2$ である．

外側は命題 14.6.10 による．例 6.1.8 より $𝐶 (𝑊 1) = 1 - 𝐻 𝑏 (0.1)$ ，例 6.1.9 より $𝐶 (𝑊 2) = 1 - 1 / 2 = 1 / 2$ であり，これが $O c o o p (𝑊)$ を定める三つの不等式のうち最初の二本である．命題 14.6.10 より $C (𝑊) \subseteq O c o o p (𝑊)$ だから，容量領域の点もこの二本を満たす．値は $𝐻 𝑏 (0.1) = 0.4689 \dots$ から読める． $◼$

内界に入れた二点は，協力外界が $𝑅 1$ と $𝑅 2$ のそれぞれに置いた枠にちょうど乗っている．つまりどちらの軸の上でも，Marton の内界が届く値と，容量領域に外から置かれた枠とが一致する．和の向きは比べられない．協力外界の三本目に現れる $𝐶 (𝑊)$ ，すなわち二人の受け手が出力を持ち寄ったときの容量を，本書は計算していないからである．軸の上の一致から，容量領域が軸の上でどこまで届くかが決まる，とまでは言えない．この $𝑊$ には定理 14.7.3 が当てられないので，内界の点が達成できるかどうかを本書は述べていないからである．

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