14.2 多元接続通信路の容量領域

14.1 節は入力分布の対を一つ固定して，そこから五角形を作った． $𝑊$ と入力分布の対がどれも全点で正なら，14.1 節で借りた 多元接続通信路の達成可能性 により，その五角形の内側の対はどれも達成可能である．固定を外すと届く先は広がる．入力分布の対を取り替えれば別の五角形が出るからというだけではない．二つの符号を時間で分けて使えば，二つの五角形から一点ずつとった対の中間にも，いくらでも近いところまで届いてしまう．

本節は，この広がりを二つの操作で言い当てる．一つは時間で分ける操作で，レート対の凸結合を作る．もう一つは極限をとる操作で，境界に届く対を拾う． $𝑊$ が全点で正のとき，容量領域と第一象限の共通部分は，ちょうど五角形の合併の閉凸包になる．

平面の閉集合と閉包の基本性質を借りる. $ℝ 2$ の部分集合についての次の三つを既知とする．第一に，閉集合の族の共通部分はふたたび閉集合である．したがって $𝑆 \subseteq ℝ 2$ に対し， $𝑆$ を含む閉集合すべての共通部分は $𝑆$ を含む最小の閉集合になる．これを $𝑆$ の閉包と呼び $―― 𝑆$ と書く．第二に， $𝐾 \subseteq ℝ 2$ が閉集合であることと， $𝐾$ の点からなる収束列の極限がつねに $𝐾$ に属することとは，同じことである．第三に， $―― 𝑆$ の点はどれも $𝑆$ の点からなる収束列の極限として書ける．本節から先，容量領域や内界・外界を閉包で定めるところも，それらについての証明も，この宣言の意味で閉包を使う．

容量領域と閉凸包

定義 14.2.1（容量領域）. $𝑊$ を多元接続通信路（定義 14.1.1）とする．達成可能なレート対（定義 14.1.3）全体の集合を $A (𝑊)$ と書き，その閉包

C (𝑊) : = ―――― A (𝑊)

を $𝑊$ の 容量領域 と呼ぶ．

$A (𝑊)$ そのものではなく閉包を容量領域と呼ぶのは，達成可能性が与えるのがつねに「不等式が真に成り立つ側」だからである．14.1 節で借りた形がまさにそれで，五角形の境界の上の対については何も言っていない．境界の対が一つずつ達成可能かどうかを問うかわりに，極限で届く対まで含めて領域と呼ぶ．第6章も同じところで手当てをしていて，達成レートの集合 $R (𝑊)$ （定義 6.2.2）そのものではなく，その上限が容量に一致することを主定理にしていた（定理 6.4.9）．答えが 1 つの数から対の集合に変わったぶん，上限をとる操作のかわりに閉包をとる操作が出てくる．

形式化: macCapacityRegion (ソース)

定義 14.2.2（閉凸包）. $𝑆 \subseteq ℝ 2$ に対し， $𝑆$ を含む閉凸集合すべての共通部分を $𝑆$ の 閉凸包 と呼び， $―――― c o n v 𝑆$ と書く．

$ℝ 2$ 自身が $𝑆$ を含む閉凸集合なので，共通部分をとる先の族は空でない．借りた 平面の閉集合と閉包の基本性質 の第一が閉包に与えた作り方と同じで，集める集合に凸という条件を足しただけである．

時分割

記号を一つ引いておく．実数 $𝑡$ に対する床関数 $⌊ 𝑡 ⌋$ ，すなわち $𝑡$ 以下の最大の整数と，その性質 $⌊ 𝑡 ⌋ \leq 𝑡 < ⌊ 𝑡 ⌋ + 1$ は，第12章 12.5 節で既知としたとおりに本節でも使う．

命題 14.2.3. $𝑊$ を多元接続通信路（定義 14.1.1）とする．その容量領域 $C (𝑊)$ （定義 14.2.1）は閉集合であり，かつ凸集合である．

証明. 閉であることは定義から出る． $C (𝑊)$ は $A (𝑊)$ の閉包であり，平面の閉集合と閉包の基本性質の第一により閉包は閉集合である．

凸であることを二段に分けて示す．第一段では，達成可能な二つの対の凸結合に真に下から近い対が達成可能であることを見る．すなわち， $(𝑎 1, 𝑎 2)$ と $(𝑏 1, 𝑏 2)$ が達成可能で， $𝜆 \in [0, 1]$ と実数の対 $(𝑅 1, 𝑅 2)$ が $𝑅 𝑗 < 𝜆 𝑎 𝑗 + (1 - 𝜆) 𝑏 𝑗$ （ $𝑗 = 1, 2$ ）を満たすなら， $(𝑅 1, 𝑅 2)$ は達成可能である．

はじめに，達成可能性が成分について単調であることに注意する． $(𝑎 1, 𝑎 2)$ が達成可能で $𝑅 𝑗 \leq 𝑎 𝑗$ なら，定義 14.1.3 が与える符号がそのまま $(𝑅 1, 𝑅 2)$ についての条件を満たす．これで $𝜆 = 1$ と $𝜆 = 0$ の場合は済むので，以下 $0 < 𝜆 < 1$ とする．

$𝜁 > 0$ をとる．達成可能性を目標の誤り確率 $𝜁 / 2$ に対して二つの対それぞれに使い， $(𝑎 1, 𝑎 2)$ の側で得られる長さの下限を $𝑁 𝑎$ ， $(𝑏 1, 𝑏 2)$ の側のものを $𝑁 𝑏$ とする．長さ $𝑛$ に対し $𝑛 𝑎 : = ⌊ 𝜆 𝑛 ⌋$ ， $𝑛 𝑏 : = 𝑛 - 𝑛 𝑎$ とおく．床関数の性質より $𝜆 𝑛 - 1 < 𝑛 𝑎 \leq 𝜆 𝑛$ であり， $0 < 𝜆 < 1$ だから $𝑛 𝑎 \to \infty$ かつ $𝑛 𝑏 \geq (1 - 𝜆) 𝑛 \to \infty$ である．よって，ある $𝑁 0$ から先のすべての $𝑛$ で $𝑁 𝑎 \leq 𝑛 𝑎$ と $𝑁 𝑏 \leq 𝑛 𝑏$ がともに成り立ち，しかも $𝑛 𝑎$ と $𝑛 𝑏$ はどちらも $1$ 以上である．

そのような $𝑛$ を一つとる．長さ $𝑛 𝑎$ の多元接続符号で $1 𝑛 𝑎 l o g 𝑀 𝑎 𝑗 \geq 𝑎 𝑗$ （ $𝑗 = 1, 2$ ）と平均誤り確率 $𝜁 / 2$ 未満を満たすものと，長さ $𝑛 𝑏$ の多元接続符号で $1 𝑛 𝑏 l o g 𝑀 𝑏 𝑗 \geq 𝑏 𝑗$ と平均誤り確率 $𝜁 / 2$ 未満を満たすものをとる．この二つを時間でつないで，長さ $𝑛$ の符号を作る．利用者 $𝑗$ のメッセージを対 $(𝑢, 𝑣) \in {1, \dots, 𝑀 𝑎 𝑗} \times {1, \dots, 𝑀 𝑏 𝑗}$ で番号づけ，その符号語を，前半の符号語のうしろに後半の符号語をつないだものとする．復号器は，受け取った $𝑦 𝑛$ の前半 $𝑛 𝑎$ 文字を前半の符号の復号器に，後半 $𝑛 𝑏$ 文字を後半の符号の復号器に渡し，返ってきた二つの対から利用者ごとに番号を組み立てる．

つないだ符号のメッセージ数は $𝑀 𝑗 = 𝑀 𝑎 𝑗 𝑀 𝑏 𝑗$ だから

1 𝑛 l o g 𝑀 𝑗 = 𝑛 𝑎 𝑛 \cdot 1 𝑛 𝑎 l o g 𝑀 𝑎 𝑗 + 𝑛 𝑏 𝑛 \cdot 1 𝑛 𝑏 l o g 𝑀 𝑏 𝑗 \geq 𝑛 𝑎 𝑛 𝑎 𝑗 + 𝑛 𝑏 𝑛 𝑏 𝑗

である．誤り確率のほうは，定義 14.1.1 の積の形により，前半 $𝑛 𝑎$ 文字の出力の分布が前半の入力だけで決まる長さ $𝑛 𝑎$ のものになり，後半についても同様で，しかも二つは独立である．つないだ符号が誤るのは前半か後半の少なくとも一方で誤るときだから，どのメッセージの対についても誤り確率は二つの符号の対応する誤り確率の和以下である．メッセージの対について平均すると，前半の平均誤り確率と後半の平均誤り確率の和で抑えられるので， $¯ 𝑃 𝑒 < 𝜁 / 2 + 𝜁 / 2 = 𝜁$ である．

最後に $𝑛$ を大きくする． $𝑛 𝑎 / 𝑛 \to 𝜆$ かつ $𝑛 𝑏 / 𝑛 \to 1 - 𝜆$ だから，上の右辺は $𝜆 𝑎 𝑗 + (1 - 𝜆) 𝑏 𝑗$ に収束する． $𝑅 𝑗$ はこの値より真に小さいので， $𝑁 0$ を大きくとり直せば， $𝑁 0 \leq 𝑛$ を満たすすべての $𝑛$ で $1 𝑛 l o g 𝑀 𝑗 \geq 𝑅 𝑗$ が $𝑗 = 1, 2$ の両方について成り立つ． $𝜁$ に対する $𝑁$ としてこの $𝑁 0$ がとれたから， $(𝑅 1, 𝑅 2)$ は達成可能である．

第二段で凸性を出す． $𝑥$ ， $𝑦$ を $C (𝑊)$ の点， $𝜆 \in [0, 1]$ とし， $𝑧 : = 𝜆 𝑥 + (1 - 𝜆) 𝑦$ とおく．平面の閉集合と閉包の基本性質の第三により， $A (𝑊)$ の点からなる列 $𝑎 (𝑘)$ ， $𝑏 (𝑘)$ で $𝑎 (𝑘) \to 𝑥$ ， $𝑏 (𝑘) \to 𝑦$ となるものがとれる． $𝑘 \geq 1$ に対し

𝑧 (𝑘) : = 𝜆 𝑎 (𝑘) + (1 - 𝜆) 𝑏 (𝑘) - (1 𝑘, 1 𝑘)

とおくと，成分ごとに $𝑧 (𝑘) 𝑗 < 𝜆 𝑎 (𝑘) 𝑗 + (1 - 𝜆) 𝑏 (𝑘) 𝑗$ だから，第一段より $𝑧 (𝑘)$ は達成可能である．いっぽう $𝑧 (𝑘) \to 𝜆 𝑥 + (1 - 𝜆) 𝑦 = 𝑧$ である． $A (𝑊) \subseteq C (𝑊)$ であり $C (𝑊)$ は閉集合だから，平面の閉集合と閉包の基本性質の第二により極限 $𝑧$ も $C (𝑊)$ に属する． $◼$

形式化: 閉であること mac_capacityRegion_isClosed，凸であること mac_capacityRegion_convex (ソース)

第一段が時分割である． $𝑛$ 回の使用のうち先頭の $𝜆$ 割を一つ目の符号に，残りを二つ目の符号に割り当てた．2 人が同じ割り当てを知っていることは要る（そうでなければ後半の符号語を前半に送ってしまう）が，互いのメッセージを知る必要はないので，定義 14.1.2 の枠の中に収まっている．レートが凸結合になるのは，メッセージ数が掛け算で増え，対数が足し算に変わるからである．誤りのほうは足し算のまま増えるので，目標を半分ずつに割っておけば間に合う．

五角形の合併から容量領域へ

道具をもう一つ借りる．五角形の包含，すなわち「どの入力の対がつくる五角形も容量領域に含まれる」という主張である．使う形を書いておく．

$𝑊$ を多元接続通信路とし， $𝑊$ が全点で正，すなわち $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) > 0$ がすべての $𝑥 1 \in X 1$ ， $𝑥 2 \in X 2$ ， $𝑦 \in Y$ で成り立つとする．このとき， $X 1$ 上の分布 $𝑝 1$ と $X 2$ 上の分布 $𝑝 2$ のどの対についても $P (𝑝 1, 𝑝 2) \subseteq C (𝑊)$ である．

当てる対象は定義 14.1.5 の五角形と定義 14.2.1 の容量領域だけで，依存するのは定理 14.2.4 の証明と，14.7 節が借りる Marton の内界の達成可能性 の筋書きである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．五角形の内側で両方のレートが正である対は，14.1 節で借りた 多元接続通信路の達成可能性 がそのまま与える．残るのは二つで，一つは五角形の境界と軸の上の対，もう一つは入力分布が全点で正でない場合である．前者は容量領域が閉包であることから拾える．後者は，入力分布を一様分布のほうへわずかにずらして全点で正にし，ずらし幅を $0$ に近づける極限で戻す．

本書はこの主張を証明しない．いま述べた二段をどちらも扱わないからである．前者が見かけほど簡単でないのは，五角形が潰れることがあるからである．14.1 節の借用が届くのは両方のレートが真に正である対だけなので，枠の一つが $0$ になる入力の対では届く対が一つも無く，境界の対を内側からの極限としては拾えない．出力が一方の入力にしかよらない通信路では，どちらの入力分布を全点で正にとってもこれが起きる．後者，すなわち入力分布をずらして戻す段では，ずらし幅を $0$ に近づけたときに三つの枠が連続的に動くことを確かめる必要がある．

形式化: mac_pentagon_subset_capacityRegion_allprob (ソース)

定理 14.2.4. $𝑊$ を多元接続通信路（定義 14.1.1）とし， $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) > 0$ がすべての $𝑥 1 \in X 1$ ， $𝑥 2 \in X 2$ ， $𝑦 \in Y$ で成り立つとする．このとき

―――― c o n v (⋃ 𝑝 1, 𝑝 2 P (𝑝 1, 𝑝 2)) \subseteq C (𝑊)

である．ここで合併は， $X 1$ 上の分布 $𝑝 1$ と $X 2$ 上の分布 $𝑝 2$ の対すべてにわたる．

証明. 借りた五角形の包含より，どの対 $(𝑝 1, 𝑝 2)$ についても $P (𝑝 1, 𝑝 2) \subseteq C (𝑊)$ だから，合併も $C (𝑊)$ に含まれる．命題 14.2.3 より $C (𝑊)$ は閉集合であり凸集合である．したがって $C (𝑊)$ は，定義 14.2.2 で共通部分をとる先の族，すなわち合併を含む閉凸集合の族に属する．共通部分はその族のどの元にも含まれるから，左辺は $C (𝑊)$ に含まれる． $◼$

形式化: mac_achievability_region_allprob (ソース)

左辺を合併ではなく閉凸包にしてあるのは，時分割で届く対が合併の中に収まらないからである．二つの入力の対 $(𝑝 1, 𝑝 2)$ と $(𝑝' 1, 𝑝' 2)$ をとり，それぞれの五角形から一点ずつ選ぶと，借りた五角形の包含が言うのは二点が $C (𝑊)$ に属することまでで，二点を結ぶ線分がどちらかの五角形に入っているとは限らない．その線分が $C (𝑊)$ に収まることを与えるのが命題 14.2.3 の凸性であり，閉凸包はこの線分をはじめから含んでいる．時分割の議論は，命題 14.2.3 の凸性を経由してここで働いている．

容量領域の特徴づけ

逆向き，すなわち容量領域が閉凸包より広くならないことを見る．ここでも道具を借りる．多元接続通信路の逆定理，すなわち「達成可能で第一象限にあるレート対は，五角形の合併の閉凸包に属する」という主張である．使う形を書いておく．

$𝑊$ を多元接続通信路とする（全点で正であることは求めない）．実数の対 $(𝑅 1, 𝑅 2)$ が定義 14.1.3 の意味で達成可能で， $𝑅 1 \geq 0$ かつ $𝑅 2 \geq 0$ なら，

(𝑅 1, 𝑅 2) \in ―――― c o n v (⋃ 𝑝 1, 𝑝 2 P (𝑝 1, 𝑝 2))

である．合併は定理 14.2.4 と同じく分布の対すべてにわたる．

当てる対象は定義 14.1.3 の達成可能性と定義 14.1.5 の五角形だけで，依存するのは定理 14.2.5 の証明だけである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．長さ $𝑛$ の符号を一つとり，メッセージの対が一様に選ばれるとして，ファノの不等式（定理 1.10.1）を三通りに当てる．利用者 1 のメッセージを利用者 2 のメッセージと出力から推定する形，利用者 2 について同じ形，そして対をまとめて推定する形の三つで， $l o g 𝑀 1$ ， $l o g 𝑀 2$ ， $l o g 𝑀 1 + l o g 𝑀 2$ の上界がそれぞれ出る．第6章定理 6.4.5 と同じように通信路の記憶のなさで時刻ごとにほどくと，右辺は時刻ごとの入力の対が定める五角形の枠の，時刻についての平均になる．平均で抑えられた対を，時刻ごとの五角形から一点ずつとった凸結合として書き直すと，五角形の合併の凸包に入る．最後に誤り確率を $0$ に送るとファノの項が消えて，閉包の側に落ちる．

本書はこの主張を証明しない．済ませなければならない段が二つあって，どちらも本書が用意していないものである．一つは時刻ごとにほどく段で，第6章のものをそのまま当てるのでは済まない．あちらは入力が 1 本だったので条件付き相互情報量の和に分ければ終わったが，こちらは三つの不等式それぞれで条件に置くものが違うので，三通りに分け直すことになる．もう一つは，ほどいた先で得られるのが三つの枠の時刻についての平均による評価でしかない，というところである．平均で抑えられた対を，時刻ごとの五角形から一点ずつとった凸結合として書き直す段が要る．書き直せるのは，時刻ごとの三つ組が命題 14.1.4 の形をしているおかげである．メッセージの対が一様で，各利用者の符号語は自分のメッセージだけで決まるので，時刻ごとの入力の対は独立なのである．

形式化: mac_timesharing_converse (ソース)

定理 14.2.5（容量領域の特徴づけ）. $𝑊$ を多元接続通信路（定義 14.1.1）とし， $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) > 0$ がすべての $𝑥 1 \in X 1$ ， $𝑥 2 \in X 2$ ， $𝑦 \in Y$ で成り立つとする． $𝑄 : = {(𝑅 1, 𝑅 2) \in ℝ 2 : 𝑅 1 \geq 0, 𝑅 2 \geq 0}$ とおくと

C (𝑊) \cap 𝑄 = ―――― c o n v (⋃ 𝑝 1, 𝑝 2 P (𝑝 1, 𝑝 2))

である．合併は定理 14.2.4 と同じく， $X 1$ 上の分布と $X 2$ 上の分布の対すべてにわたる．

証明. 右辺を $𝐾$ と書く．

$𝐾 \subseteq C (𝑊) \cap 𝑄$ を示す． $𝐾 \subseteq C (𝑊)$ は定理 14.2.4 である． $𝐾 \subseteq 𝑄$ を見るには， $𝑄$ が合併を含む閉凸集合であることを言えばよい（定義 14.2.2 の共通部分はその族のどの元にも含まれる）．五角形はどれも定義 14.1.5 の最初の二つの不等式により $𝑄$ に含まれるから，合併も $𝑄$ に含まれる． $𝑄$ の点の凸結合は成分がふたたび非負だから $𝑄$ は凸であり， $𝑄$ の点からなる収束列の極限も成分が非負だから，平面の閉集合と閉包の基本性質の第二により $𝑄$ は閉である．

$C (𝑊) \cap 𝑄 \subseteq 𝐾$ を示す． $(𝑅 1, 𝑅 2) \in C (𝑊) \cap 𝑄$ をとる．定義 14.2.1 より $C (𝑊)$ は $A (𝑊)$ の閉包だから，平面の閉集合と閉包の基本性質の第三により，達成可能な対からなる列 $𝑎 (𝑘) \to (𝑅 1, 𝑅 2)$ がとれる．各 $𝑘$ について $𝑏 (𝑘) : = (m a x (𝑎 (𝑘) 1, 0), m a x (𝑎 (𝑘) 2, 0))$ とおく．これは三つのことを満たす．第一に $𝑏 (𝑘)$ は達成可能である．定義 14.1.3 はメッセージ数に $𝑀 𝑗 \geq 1$ を求めているので $1 𝑛 l o g 𝑀 𝑗 \geq 0$ であり， $𝑎 (𝑘) 𝑗$ を $0$ に取り替えても条件は満たされたままだからである．第二に $𝑏 (𝑘) \in 𝑄$ である．第三に $𝑏 (𝑘) \to (𝑅 1, 𝑅 2)$ である．実数 $𝑠$ ， $𝑡$ について $| m a x (𝑠, 0) - m a x (𝑡, 0) | \leq | 𝑠 - 𝑡 |$ が成り立ち（ $𝑠$ と $𝑡$ の大小で場合を分ければ確かめられる）， $𝑅 𝑗 \geq 0$ より $m a x (𝑅 𝑗, 0) = 𝑅 𝑗$ だからである．

借りた多元接続通信路の逆定理を各 $𝑏 (𝑘)$ に当てると $𝑏 (𝑘) \in 𝐾$ を得る． $𝐾$ は定義 14.2.2 により閉集合の共通部分だから，平面の閉集合と閉包の基本性質の第一により閉集合である．よって平面の閉集合と閉包の基本性質の第二により，極限 $(𝑅 1, 𝑅 2)$ も $𝐾$ に属する． $◼$

形式化: mac_timesharing_capacity_region (ソース)

定理 14.2.5 が述べているのは，容量領域そのものではなく第一象限との共通部分についてである．定義 14.1.3 の達成可能性は負のレートを禁じていない．レートに求めているのは $1 𝑛 l o g 𝑀 𝑗 \geq 𝑅 𝑗$ という下からの不等式だけなので， $𝑅 𝑗$ を負にとれば条件はそれだけ緩くなる．いっぽう右辺の閉凸包は第一象限に収まる．五角形はどれも定義 14.1.5 の最初の二つの不等式により第一象限に含まれ，第一象限は閉凸集合だからである（定理 14.2.5 の証明の第一段がその確認である）．負のレートは符号の取り分としては読めないので， $C (𝑊)$ の側を第一象限で切ってから特徴づけを述べている．

例 14.2.6（片方を黙らせる）. $𝑊$ を多元接続通信路とし， $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) > 0$ がすべての $𝑥 1$ ， $𝑥 2$ ， $𝑦$ で成り立つとする． $𝑥 2 \in X 2$ を一つ固定し， $𝑊 𝑥 2 (𝑦 ∣ 𝑥 1) : = 𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2)$ とおく．これは第6章定義 6.1.1 の意味の通信路である． $𝑝 2$ を $𝑥 2$ に集中した一点分布にとると， $X 1$ 上のどの分布 $𝑝 1$ についても，命題 14.1.4 の三つ組の三つの量は

𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2) = 𝐼 (𝑝 1; 𝑊 𝑥 2), 𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1) = 0, 𝐼 ((𝑋 1, 𝑋 2); 𝑌) = 𝐼 (𝑝 1; 𝑊 𝑥 2)

であり，五角形 $P (𝑝 1, 𝑝 2)$ は線分 ${(𝑅 1, 0) : 0 \leq 𝑅 1 \leq 𝐼 (𝑝 1; 𝑊 𝑥 2)}$ に潰れる． $𝑝 1$ を動かしてこれらを合わせると線分 ${(𝑅 1, 0) : 0 \leq 𝑅 1 \leq 𝐶 (𝑊 𝑥 2)}$ になり（ $𝐶$ は定義 6.1.4 の通信路容量），定理 14.2.5 よりこれは $C (𝑊)$ に含まれる．

証明. $𝑝 2$ が $𝑥 2$ に集中しているので，三つ組の同時分布は $𝑥' 2 \neq 𝑥 2$ で $0$ であり， $𝑥' 2 = 𝑥 2$ では $𝑝 1 (𝑥 1) 𝑊 𝑥 2 (𝑦 ∣ 𝑥 1)$ である．

まず $𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1) = 0$ を見る． $𝑥 1$ を固定すると，条件付き分布のもとで $𝑋 2$ は $𝑥 2$ をとる確率が $1$ だから， $𝑝 (𝑥' 2, 𝑦 ∣ 𝑥 1) = 𝑝 (𝑥' 2 ∣ 𝑥 1) 𝑝 (𝑦 ∣ 𝑥 1)$ がすべての $(𝑥' 2, 𝑦)$ で成り立つ（ $𝑥' 2 \neq 𝑥 2$ では両辺とも $0$ ， $𝑥' 2 = 𝑥 2$ では $𝑝 (𝑥 2 ∣ 𝑥 1) = 1$ である）．命題 1.4.2 の等号条件より $𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1) = 0$ である．

次に $𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2)$ を計算する．定義 1.4.1 より，これは $𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2 = 𝑥' 2)$ を $𝑥' 2$ について平均したものであり，重みが $0$ でない項は $𝑥' 2 = 𝑥 2$ の一つだけである． $𝑋 2 = 𝑥 2$ のもとでの $(𝑋 1, 𝑌)$ の条件付き同時分布は $𝑝 1 (𝑥 1) 𝑊 𝑥 2 (𝑦 ∣ 𝑥 1)$ だから，命題 6.1.3 よりその相互情報量は $𝐼 (𝑝 1; 𝑊 𝑥 2)$ である．

三つめに移る．対 $(𝑋 2, 𝑋 1)$ から $𝑋 2$ を先に取り出すチェイン則（定理 1.5.1）で $𝐼 ((𝑋 2, 𝑋 1); 𝑌) = 𝐼 (𝑋 2; 𝑌) + 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2)$ である． $𝑋 2$ は確率 $1$ で $𝑥 2$ をとるから，上と同じ理由で $𝑝 (𝑥' 2, 𝑦) = 𝑝 (𝑥' 2) 𝑝 (𝑦)$ がすべての $(𝑥' 2, 𝑦)$ で成り立ち，命題 1.3.2 の等号条件より $𝐼 (𝑋 2; 𝑌) = 0$ である．対の成分をどちらの順に並べても情報量は変わらないので， $𝐼 ((𝑋 1, 𝑋 2); 𝑌) = 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2)$ である．

五角形の形を見る．三つの枠が $𝐼 (𝑝 1; 𝑊 𝑥 2)$ ， $0$ ， $𝐼 (𝑝 1; 𝑊 𝑥 2)$ だから，定義 14.1.5 の五つの条件は $0 \leq 𝑅 1 \leq 𝐼 (𝑝 1; 𝑊 𝑥 2)$ と $𝑅 2 = 0$ に同値である（ $0 \leq 𝑅 2 \leq 0$ から $𝑅 2 = 0$ が出て，和の条件は第 1 の条件に吸収される）．

最後に $𝑝 1$ を動かす．どの $𝑝 1$ についても $𝐼 (𝑝 1; 𝑊 𝑥 2) \leq 𝐶 (𝑊 𝑥 2)$ だから，合わせたものは主張の線分に含まれる．逆に，定理 6.1.5 より $𝐼 (\cdot; 𝑊 𝑥 2)$ を最大にする入力分布 $𝑝 *$ があって $𝐼 (𝑝 *; 𝑊 𝑥 2) = 𝐶 (𝑊 𝑥 2)$ だから， $𝑝 1 = 𝑝 *$ の線分が主張の線分そのものである．これは定理 14.2.5 の右辺の合併に含まれ，定義 14.2.2 で共通部分をとる先の集合はどれも合併を含むから閉凸包も合併を含む．よって定理 14.2.5 より $C (𝑊)$ に含まれる． $◼$

片方の利用者を黙らせると，残った側から見た通信路は第6章の 1 人用の通信路にほかならない．例 14.2.6 は，その容量が多元接続の容量領域の $𝑅 2 = 0$ の辺として現れることを言っている．第6章の $𝐶 (𝑊 𝑥 2)$ は，こうして領域の一部として読み直せる．黙らせる文字を $𝑥 2$ ごとに取り替えれば別の $𝐶 (𝑊 𝑥 2)$ が出るので，辺の長さは黙らせ方のうちいちばん良いものまで伸びる．

形式化上の注記. 例 14.2.6 に対応する単独の宣言はない．片方の入力を一点分布にとった五角形について述べる宣言も，それを第6章の通信路容量と結ぶ宣言も形式化には無く，定理 14.2.5 に紐付けた宣言と，第6章の容量についての宣言を突き合わせて得られる．

本節はここまで，領域を集合の操作だけで書いてきた．最後に，全点で正な通信路を一つとって三つの枠を数で出し，領域の形を見ておく．

例 14.2.7（雑音のある二元加算多元接続通信路）. $X 1 = X 2 = {0, 1}$ ， $Y = {0, 1, 2}$ とし， $𝑊$ を

𝑊 (𝑥 1 + 𝑥 2 ∣ 𝑥 1, 𝑥 2) = 0.9, 𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) = 0.05 (𝑦 \neq 𝑥 1 + 𝑥 2)

で定まる通信路とする．例 14.1.6 の加算通信路で，出力が確率 $0.1$ で残りの二つの値のどちらかに化ける，と読める．この $𝑊$ は全点で正である．入力分布 $𝑝 1$ ， $𝑝 2$ をどちらも一様，すなわち $𝑝 1 (0) = 𝑝 1 (1) = 𝑝 2 (0) = 𝑝 2 (1) = 1 / 2$ にとると，命題 14.1.4 の三つ組について

𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2) = 𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1) = 1720 + 𝐻 𝑏 (0.05) - 𝐻 𝑏 (0.1), 𝐼 ((𝑋 1, 𝑋 2); 𝑌) = 1740 + 𝐻 𝑏 (0.475) - 𝐻 𝑏 (0.1)

である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．五角形 $P (𝑝 1, 𝑝 2)$ は定理 14.2.4 より $C (𝑊)$ に含まれる．

証明. 各対についての総和が $0.9 + 0.05 + 0.05 = 1$ だから， $𝑊$ は定義 14.1.1 の多元接続通信路である．値が $0.9$ と $0.05$ の二通りしかないので全点で正でもある．

$𝐻 (𝑌 ∣ 𝑋 1, 𝑋 2)$ を計算する．入力の対を固定すると $𝑌$ は三つの値を確率 $0.9$ ， $0.05$ ， $0.05$ でとるから，定義 1.1.1 より，そのエントロピーは対によらず

- 0.9 l o g 0.9 - 2 \cdot 0.05 l o g 0.05 = - 0.9 l o g 0.9 - 0.1 l o g 0.1 + 0.1 = 𝐻 𝑏 (0.1) + 0.1

である（ $l o g 0.05 = l o g 0.1 - 1$ を使った）．定義 1.2.2 はこれを平均したものだから $𝐻 (𝑌 ∣ 𝑋 1, 𝑋 2) = 𝐻 𝑏 (0.1) + 0.1$ である．

$𝐻 (𝑌 ∣ 𝑋 2)$ に移る． $𝑋 1$ と $𝑋 2$ は独立だから， $𝑋 2 = 𝑥 2$ のもとで $𝑋 1$ は一様である． $𝑥 1$ が動くと入力の和は $𝑥 2$ と $𝑥 2 + 1$ の二つの値をそれぞれ確率 $1 / 2$ でとるので， $𝑌$ の条件付き分布はその二つの値をそれぞれ確率 $12 (0.9 + 0.05) = 0.475$ でとり，残る一つの値を確率 $0.05$ でとる．定義 1.1.1 より，そのエントロピーは $𝑥 2$ によらず

- 2 \cdot 0.475 l o g 0.475 - 0.05 l o g 0.05 = - 0.95 l o g 0.95 - 0.05 l o g 0.05 + 0.95 = 𝐻 𝑏 (0.05) + 0.95

である（ $l o g 0.475 = l o g 0.95 - 1$ を使った）．よって $𝐻 (𝑌 ∣ 𝑋 2) = 𝐻 𝑏 (0.05) + 0.95$ である．

一つめの量を出す．出力の側をエントロピーの差に開く形（定理 1.4.3）で $𝐼 (𝑌; 𝑋 1 ∣ 𝑋 2) = 𝐻 (𝑌 ∣ 𝑋 2) - 𝐻 (𝑌 ∣ 𝑋 2, 𝑋 1)$ であり，命題 1.4.2 の対称性より左辺は $𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2)$ に等しい．上の二つを引くと $𝐻 𝑏 (0.05) + 0.95 - 𝐻 𝑏 (0.1) - 0.1$ で，これが主張の値である． $𝑊$ は $𝑥 1$ と $𝑥 2$ の入れ替えで変わらず，入力分布も同じだから， $𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1)$ も同じ値である．

和のほうに移る． $𝑋 1$ と $𝑋 2$ が独立な一様分布だから，入力の和は $0$ ， $1$ ， $2$ をそれぞれ確率 $1 / 4$ ， $1 / 2$ ， $1 / 4$ でとる．よって $𝑌$ は $0$ と $2$ をそれぞれ確率 $14 \cdot 0.9 + 34 \cdot 0.05 = 0.2625$ でとり， $1$ を確率 $12 \cdot 0.9 + 12 \cdot 0.05 = 0.475$ でとる．定義 1.1.1 より

𝐻 (𝑌) = - 2 \cdot 0.2625 l o g 0.2625 - 0.475 l o g 0.475 = 𝐻 𝑏 (0.475) + 0.525

である（ $l o g 0.2625 = l o g 0.525 - 1$ を使って第 1 項を $- 0.525 l o g 0.525 + 0.525$ に直した）．定理 1.3.4 の $𝐼 (𝑋; 𝑌) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋)$ を，対 $(𝑋 1, 𝑋 2)$ を 1 つの変数とみなして当てると $𝐼 ((𝑋 1, 𝑋 2); 𝑌) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋 1, 𝑋 2)$ だから，これは $𝐻 𝑏 (0.475) + 0.525 - 𝐻 𝑏 (0.1) - 0.1$ で，やはり主張の値である．

最後に包含を見る． $𝑊$ は全点で正だから定理 14.2.4 が当たる．五角形は合併に含まれ，定義 14.2.2 で共通部分をとる先の集合はどれも合併を含むから閉凸包も合併を含み，その閉凸包が $C (𝑊)$ に含まれる． $◼$

数で見ると，1 人ぶんの枠はどちらも約 $0.667$ ，和の枠は約 $0.954$ である．例 14.1.6 の雑音のない加算通信路では $1$ ， $1$ ， $3 / 2$ だったから， $10$ 回に $1$ 回の化けが三つの枠をこれだけ削ったことになる．和の枠は 1 人ぶんの枠の $2$ 倍（約 $1.33$ ）に届いていないので，五角形は辺が潰れておらず，二つの折れ点は約 $(0.667, 0.287)$ と約 $(0.287, 0.667)$ にある．一様な入力分布から出るのはこの五角形一つで， $C (𝑊) \cap 𝑄$ を言い当てるには，定理 14.2.5 のとおり入力分布の対すべてにわたる合併の閉凸包をとることになる．

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