14.5 ブロードキャスト通信路と重ね合わせ符号化

14.1 節は送り手が二人で受け手が一人だった．本節はその裏返しで，送り手が一人，受け手が二人である．送り手は一本の入力列を流し込み，二人の受け手はそれぞれ自分の側の出力列だけを見て，別々のメッセージを取り出す．無線の基地局が複数の端末に同時に配信する場面がこれにあたる．

答えの形は 14.1 節と同じくレート対の集合になるが，取り引きの中身は違う．多元接続では二人が同じ出力に混ざり込むことが制約だったのに対し，ここでは送れる入力列が一本しかないことが制約である．一本の列に二人ぶんのメッセージを載せるので，片方に合わせて作ると他方には読みにくいものが届く．二人の受け手の性能に差があるとき，この対立をどう調停するかが本節の主題である．

通信路と符号

定義 14.5.1（ブロードキャスト通信路）. $X$ ， $Y 1$ ， $Y 2$ をどれも空でない有限アルファベットとする．ブロードキャスト通信路（broadcast channel）とは，入力 $𝑥 \in X$ ごとに $Y 1 \times Y 2$ 上の分布 $𝑊 (\cdot, \cdot ∣ 𝑥)$ を与える対応である．すなわち $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) \geq 0$ であって，各 $𝑥$ について $\sum 𝑦 1, 𝑦 2 𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) = 1$ を満たす．その二つの 周辺通信路 を

𝑊 1 (𝑦 1 ∣ 𝑥) : = \sum 𝑦 2 \in Y 2 𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥), 𝑊 2 (𝑦 2 ∣ 𝑥) : = \sum 𝑦 1 \in Y 1 𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥)

で定める．長さ $𝑛$ の入力 $𝑥 𝑛 = (𝑥 0, \dots, 𝑥 𝑛 - 1)$ に対する出力の対の分布を

𝑊 𝑛 (𝑦 𝑛 1, 𝑦 𝑛 2 ∣ 𝑥 𝑛) : = 𝑛 - 1 \prod 𝑖 = 0 𝑊 (𝑦 1, 𝑖, 𝑦 2, 𝑖 ∣ 𝑥 𝑖)

で定める．

$𝑊 1$ ， $𝑊 2$ はどちらも第6章定義 6.1.1 の意味の通信路で，受け手 $1$ ，受け手 $2$ が自分の出力だけを見るかぎり相手にしているのはこの二つである．ところが通信路の側はそれ以上のもの，すなわち二つの出力の同時分布まで決めている．同じ周辺をもつ $𝑊$ は何通りもあり，どれを選ぶかで二人の出力の相関が変わる．以下で劣化という条件を置くときに効くのが，まさにこの同時分布のほうである．

形式化: BCChannel (ソース)

定義 14.5.2（ブロードキャスト符号）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とし， $𝑛 \geq 1$ とする．長さ $𝑛$ の ブロードキャスト符号 とは，メッセージ数 $𝑀 1 \geq 1$ ， $𝑀 2 \geq 1$ と，符号化写像 $𝑐 : {1, \dots, 𝑀 1} \times {1, \dots, 𝑀 2} \to X 𝑛$ ，および受け手ごとの復号器 $𝑑 1 : Y 𝑛 1 \to {1, \dots, 𝑀 1}$ ， $𝑑 2 : Y 𝑛 2 \to {1, \dots, 𝑀 2}$ の組である．メッセージの対 $(𝑚 1, 𝑚 2)$ を送ったときの受け手 $𝑗$ の 誤り確率 と，対について平均した受け手 $𝑗$ の 平均誤り確率 を

𝑃 𝑒, 𝑗 (𝑚 1, 𝑚 2) : = \sum 𝑦 𝑛 1, 𝑦 𝑛 2 : 𝑑 𝑗 (𝑦 𝑛 𝑗) \neq 𝑚 𝑗 𝑊 𝑛 (𝑦 𝑛 1, 𝑦 𝑛 2 ∣ 𝑐 (𝑚 1, 𝑚 2)), ¯ 𝑃 𝑒, 𝑗 : = 1 𝑀 1 𝑀 2 𝑀 1 \sum 𝑚 1 = 1 𝑀 2 \sum 𝑚 2 = 1 𝑃 𝑒, 𝑗 (𝑚 1, 𝑚 2)

で定める（ $𝑗 = 1, 2$ ）．

14.1 節の定義 14.1.2 と左右が入れ替わっている．あちらは符号化が二本に分かれて復号が一本だったが，こちらは符号化が一本で復号が二本である．一本になった符号化写像は二つのメッセージの対を受け取るので，送り手は両方を知っている．分かれたのは読む側で，受け手 $1$ は $𝑦 𝑛 1$ しか見ず，受け手 $2$ は $𝑦 𝑛 2$ しか見ない．誤りも受け手ごとに数える．自分のメッセージさえ当たっていればその受け手にとっては誤りでないので，誤り確率は二つある．

形式化: 符号 BroadcastCode，メッセージの対ごとの誤り確率 errorProbAt₁，errorProbAt₂，受け手ごとの平均誤り確率 averageErrorProb₁，averageErrorProb₂ (ソース)

定義 14.5.3（達成可能なレート対と容量領域）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする．実数の対 $(𝑅 1, 𝑅 2)$ が 達成可能 であるとは，任意の $𝜁 > 0$ に対してある $𝑁 \geq 1$ があって， $𝑁 \leq 𝑛$ を満たすすべての $𝑛$ について，長さ $𝑛$ のブロードキャスト符号（定義 14.5.2）で

1 𝑛 l o g 𝑀 1 \geq 𝑅 1, 1 𝑛 l o g 𝑀 2 \geq 𝑅 2, ¯ 𝑃 𝑒, 1 < 𝜁, ¯ 𝑃 𝑒, 2 < 𝜁

を満たすものが存在することをいう．達成可能な対全体の集合の閉包を $𝑊$ の 容量領域 と呼び， $C (𝑊)$ と書く．

14.1 節定義 14.1.3 と同じ形で，誤り確率についての条件が二人ぶんに増えただけである．閉包をとる理由も 14.2 節定義 14.2.1 と同じで，達成可能性が与えるのはつねに不等式が真に成り立つ側だから，境界の対を極限で拾っておく．閉包は 14.2 節で借りた 平面の閉集合と閉包の基本性質 の意味でとる．

この定義はレートの符号を問うていない．14.2 節の定理 14.2.5 が第一象限との共通部分について述べたのに対し，ここでは容量領域を第一象限で切らない．定義 14.5.3 がレートに求めているのは $1 𝑛 l o g 𝑀 𝑗 \geq 𝑅 𝑗$ という下からの不等式だけなので， $𝑅 𝑗$ を負にとれば条件はそれだけ緩くなる．以下で置く内界も外界も同じく第一象限で切らないので，三つの領域はそのまま比べられる．

形式化: 達成可能性 BCAchievable，容量領域 bcCapacityRegion (ソース)

劣化

二人の受け手の性能に差があるという状況を，通信路の側の条件として書く．いちばん強い書き方は，一方の出力がもう一方の出力をさらに雑音に通したものになっている，というものである．

定義 14.5.4（物理的に劣化している）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）とする． $𝑊$ が 物理的に劣化している とは， $Y 1$ を入力， $Y 2$ を出力とする通信路 $𝑊 2 ∣ 1$ （第6章定義 6.1.1）があって，すべての $𝑥$ ， $𝑦 1$ ， $𝑦 2$ について

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

が成り立つことをいう．

右辺を読むと，入力から出るのは $𝑦 1$ だけで， $𝑦 2$ はそこからさらに $𝑊 2 ∣ 1$ を通して作られている．つまり受け手 $2$ は，受け手 $1$ が見たものを又聞きしているにすぎない．これは同時分布についての条件であって，周辺だけでは決まらない． $𝑊 2$ が $𝑊 1$ より雑音が多いという言い方は周辺どうしの比較だが，定義 14.5.4 が求めているのは，同じ確率空間の上で $𝑋 \to 𝑌 1 \to 𝑌 2$ という順に情報が流れていることである．14.6 節では，周辺だけを見る弱い条件を二つ置いて，劣化していればそのどちらも満たされることを見る．

形式化: IsBCDegraded (ソース)

例 14.5.5（二元対称通信路を二段つなぐ）. $𝜌 1, 𝜌 2 \in [0, 1]$ とし， $X = Y 1 = Y 2 = {0, 1}$ とする． $𝑍 1$ ， $𝑍 2$ を互いに独立で $P r [𝑍 1 = 1] = 𝜌 1$ ， $P r [𝑍 2 = 1] = 𝜌 2$ を満たす確率変数とし，入力 $𝑥$ に対する出力の対を $𝑌 1 : = 𝑥 \oplus 𝑍 1$ ， $𝑌 2 : = 𝑌 1 \oplus 𝑍 2$ （ $\oplus$ は排他的論理和）で定める．このとき定まるブロードキャスト通信路 $𝑊$ は定義 14.5.4 の意味で物理的に劣化しており， $𝑊 1$ は反転確率 $𝜌 1$ の二元対称通信路（例 6.1.8）， $𝑊 2$ は反転確率 $𝜌 1 (1 - 𝜌 2) + (1 - 𝜌 1) 𝜌 2$ の二元対称通信路である．

証明. まず劣化を見る． $𝑊 2 ∣ 1$ を反転確率 $𝜌 2$ の二元対称通信路，すなわち $𝑊 2 ∣ 1 (𝑦 1 \oplus 1 ∣ 𝑦 1) = 𝜌 2$ かつ $𝑊 2 ∣ 1 (𝑦 1 ∣ 𝑦 1) = 1 - 𝜌 2$ とする． $𝜌 1$ が $0$ または $1$ のときは， $𝑥$ に対して $𝑌 1$ のとりうる値が一つに決まる．そこで先に， $𝑊 1 (𝑦 1 ∣ 𝑥) = 0$ である組 $(𝑥, 𝑦 1)$ を片づけておく．定義 14.5.1 の和より $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) \leq 𝑊 1 (𝑦 1 ∣ 𝑥)$ だから，この組では示すべき等式の両辺がどちらも $0$ である．以下 $𝑊 1 (𝑦 1 ∣ 𝑥) > 0$ ，すなわち条件の側が正の確率をもつ組で考える． $𝑍 2$ が $𝑍 1$ と独立で，したがって $(𝑥, 𝑌 1)$ とも独立だから， $𝑌 1 = 𝑦 1$ を与えたときの $𝑌 2$ の条件付き分布は $𝑊 2 ∣ 1 (\cdot ∣ 𝑦 1)$ である．よって

𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) = P r [𝑌 1 = 𝑦 1 ∣ 𝑥] P r [𝑌 2 = 𝑦 2 ∣ 𝑥, 𝑌 1 = 𝑦 1] = 𝑊 1 (𝑦 1 ∣ 𝑥) 𝑊 2 ∣ 1 (𝑦 2 ∣ 𝑦 1)

であり，これが定義 14.5.4 の条件である． $𝑊 1$ のほうは $𝑌 1 = 𝑥 \oplus 𝑍 1$ から直に読める． $𝑍 1 = 1$ の確率が $𝜌 1$ なので， $𝑌 1$ が $𝑥$ と違う確率は $𝜌 1$ である．

$𝑊 2$ を計算する． $𝑌 2 = 𝑥 \oplus 𝑍 1 \oplus 𝑍 2$ だから， $𝑌 2$ が $𝑥$ と違うのは $𝑍 1 \oplus 𝑍 2 = 1$ のとき，すなわち $𝑍 1$ と $𝑍 2$ のちょうど一方が $1$ のときである．二つは独立だから，その確率は $𝜌 1 (1 - 𝜌 2) + (1 - 𝜌 1) 𝜌 2$ である．この値は $𝑥$ によらないので， $𝑊 2$ は反転確率がこの値の二元対称通信路である． $◼$

反転確率を二つ重ねると反転しやすくなる．つないだ通信路の反転確率と $𝜌 1$ の差は $𝜌 2 (1 - 2 𝜌 1)$ で， $𝜌 1 < 1 / 2$ かつ $0 < 𝜌 2 < 1 / 2$ ならこれは正であり，つないだ反転確率は $1 / 2$ を超えない． $𝐻 𝑏$ は $[0, 1 / 2]$ の上で減らない（補題 9.3.1 の第 $3$ の主張）ので，例 6.1.8 の容量 $1 - 𝐻 𝑏 (𝜌)$ をこの二つの反転確率で読むと，受け手 $2$ の側が受け手 $1$ の側を上回らないことが見てとれる（単調性は非狭義なので，真に小さいとまでは読めない）．劣化という言葉はこの「後ろに置かれたほうが不利になる」という関係を，容量の比較ではなく通信路の作り方として書いたものである．

重ね合わせ符号化

道具を一つ借りる．重ね合わせ符号化の達成可能性，すなわち「補助変数を一つ挟んで測った情報量の内側のレート対が実際に達成できる」という主張である．使う形を書いておく．

$𝑊$ をブロードキャスト通信路（定義 14.5.1）とする（二人の性能を比べる条件は求めない）．空でない有限アルファベット $U$ 上の分布 $𝑝 𝑈$ と， $U$ を入力， $X$ を出力とする通信路 $𝐾$ （第6章定義 6.1.1）をとり， $𝑝 𝑈$ ， $𝐾$ ， $𝑊$ がどれも全点で正，すなわち $𝑝 𝑈 (𝑢) > 0$ ， $𝐾 (𝑥 ∣ 𝑢) > 0$ ， $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) > 0$ がすべての $𝑢 \in U$ ， $𝑥 \in X$ ， $𝑦 1 \in Y 1$ ， $𝑦 2 \in Y 2$ で成り立つとする．四つ組 $(𝑈, 𝑋, 𝑌 1, 𝑌 2)$ を，同時分布が $𝑝 𝑈 (𝑢) 𝐾 (𝑥 ∣ 𝑢) 𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥)$ であるような確率変数の組とする．実数の対 $(𝑅 1, 𝑅 2)$ が

𝑅 1 < 𝐼 (𝑋; 𝑌 1 ∣ 𝑈), 𝑅 2 < 𝐼 (𝑈; 𝑌 2), m a x (𝑅 1, 0) + 𝑅 2 < 𝐼 ((𝑈, 𝑋); 𝑌 1)

を満たすならば， $(𝑅 1, 𝑅 2)$ は定義 14.5.3 の意味で達成可能である．レートの符号は問わない．三本目に $m a x (𝑅 1, 0)$ を置いてあるのはそのためで， $𝑅 1$ が正のときはこの枠は $𝑅 1 + 𝑅 2 < 𝐼 ((𝑈, 𝑋); 𝑌 1)$ と同じ式である．さらに $𝑊$ が定義 14.5.4 の意味で物理的に劣化していて，しかも $0 < 𝑅 1$ ， $0 < 𝑅 2$ であるなら，三本目を落として最初の二本だけを課しても同じ結論が成り立つ．

当てる対象は定義 14.5.2 のブロードキャスト符号だけで，劣化を仮定した形に依存するのが本節の終わりの地の文，三本の枠を課した形に依存するのが 14.6 節命題 14.6.5 の直後の地の文と，同じ節が借りる 能力がより高い通信路の容量領域 の筋書きである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．符号語を二段に作る．まず補助変数の側の符号語 $𝑈 𝑛 (𝑚 2)$ を $𝑝 𝑈$ の $𝑛$ 重積から $𝑀 2$ 本引き，その一本ごとに，入力の側の符号語 $𝑋 𝑛 (𝑚 1, 𝑚 2)$ を $𝐾 (\cdot ∣ 𝑈 𝑛 (𝑚 2))$ の各文字からの積で $𝑀 1$ 本引く．一本目の層を雲，その周りに散らした二本目の層を衛星と呼ぶ．受け手 $2$ は雲の符号語だけを読み，それが $𝑚 2$ を教える．受け手 $1$ は，まず雲を読んで $𝑚 2$ を当て，そのうえで雲に付いた衛星の中から $𝑚 1$ を読む． $𝑈$ は二人に共通で見える粗い層， $𝑋$ は受け手 $1$ だけが見分けられる細かい層にあたり，二つの情報量 $𝐼 (𝑈; 𝑌 2)$ と $𝐼 (𝑋; 𝑌 1 ∣ 𝑈)$ がそれぞれの層で運べる量である．三本目の枠が出るのはここからで，受け手 $1$ は雲と衛星の両方を読むのだから，二つを合わせた $𝐼 ((𝑈, 𝑋); 𝑌 1)$ を超えては読めない．劣化しているときにこの三本目を落とせる理由は，14.6 節命題 14.6.5 とその直後の地の文で見る．

本書はこの主張を証明しない．二段の符号帳についてのランダム符号化で，14.1 節で借りたものと同じ段，すなわち三通りに分かれる誤りの勘定と，符号帳についての平均から良い一組を取り出す段が要る．そのうえ雲と衛星が入れ子になっているので，第6章 6.3 節の一本の符号帳についての議論をそのまま二度使うのでは済まない．

形式化: 三本の枠を課した形 bc_achievability_of_rate_lt，劣化を仮定した形 bc_achievability (ソース)

形式化上の注記. 形式化の宣言は，目標の誤り確率を結論の中で全称にとらず，仮定の側に置いた形で書かれている．定義 14.5.3 はその全称を達成可能性の定義の中に入れているので，書き方が違うだけで述べていることは同じである．三本の枠を課した宣言はレートの符号を問わず，劣化を仮定した宣言だけが二つのレートを正にとる．借りた形の書き分けはこれに合わせてある．

形式化上の注記（本節と 14.6 節に共通）. 三つの情報量は，形式化では相互情報量としてではなくエントロピーの差の形で書かれている． $𝐼 (𝑋; 𝑌 1 ∣ 𝑈)$ と $𝐼 (𝑈; 𝑌 2)$ を定理 1.4.3 と定理 1.3.4 の表現で書いたものが bcInfo₁，bcInfo₂ (InformationTheory/Shannon/BroadcastChannel/Achievability/Setup.lean)， $𝐼 ((𝑈, 𝑋); 𝑌 1)$ を同じ形で書いたものが bcInfoJoint (InformationTheory/Shannon/BroadcastChannel/Achievability/ErrorAnalysis.lean) である．値は同じでも，宣言としては別の式である．14.6 節命題 14.6.5 に紐付けた宣言も，この三つで書かれている．

劣化した通信路の逆定理

逆向き，すなわち達成できるレート対が上の二つの情報量で抑えられることを見る．抑えに現れる補助変数は，符号の側から作る．時刻 $𝑖$ ごとに，受け手 $2$ のメッセージと，受け手 $2$ が時刻 $𝑖$ までに見た出力とを束ねたものを $𝑈 𝑖$ とおく．これが上で借りた雲の役を果たす．

以下ではメッセージの対が一様分布に従うとして議論する．補題 14.5.7 と定理 14.5.8 はこれを主張の仮定として書いている．証明が一様性を実際に使うので落とせる条件ではないが，符号の側に課すものではない．定義 14.5.2 の平均誤り確率はメッセージの対ごとの誤り確率を一様な重み $1 / (𝑀 1 𝑀 2)$ で平均した量なので，対に一様分布を与えると，受け手 $𝑗$ の誤り確率 $P r [𝑑 𝑗 (𝑌 𝑛 𝑗) \neq M s g 𝑗]$ がちょうど $¯ 𝑃 𝑒, 𝑗$ になる．それを合わせるためにこちらが選ぶ分布である．

このあとの証明は，同じ計算を繰り返し使う． $𝐵$ で条件付けた $𝐴$ の分布が $𝐵$ の値の一部 $𝑔 (𝐵)$ だけで決まっているなら，条件を $𝑔 (𝐵)$ まで粗くしても同じ分布のままである，という計算である．先に切り出して名前を付けておく．

補題 14.5.6（条件を粗くする）. $𝐴$ と $𝐵$ を有限集合に値をとる確率変数とする（どちらも確率変数の組を一つにまとめたものでよい）． $𝑔$ を $𝐵$ の値の集合から有限集合への写像とし， $𝐴$ の値と $𝑔$ の値の対に実数を対応させる写像 $𝑓$ をとる． $P r [𝐵 = 𝑏] > 0$ を満たすどの $𝑏$ と， $𝐴$ のどの値 $𝑎$ についても

P r [𝐴 = 𝑎 ∣ 𝐵 = 𝑏] = 𝑓 (𝑎, 𝑔 (𝑏))

が成り立つとする．このとき， $P r [𝑔 (𝐵) = 𝑐] > 0$ を満たすどの $𝑐$ と， $𝐴$ のどの値 $𝑎$ についても $P r [𝐴 = 𝑎 ∣ 𝑔 (𝐵) = 𝑐] = 𝑓 (𝑎, 𝑐)$ である．

証明. $P r [𝑔 (𝐵) = 𝑐] > 0$ を満たす $𝑐$ と， $𝐴$ の値 $𝑎$ を固定する．事象 ${𝑔 (𝐵) = 𝑐}$ は， $𝑔 (𝑏) = 𝑐$ を満たす $𝑏$ についての事象 ${𝐵 = 𝑏}$ の交わらない合併だから

P r [𝐴 = 𝑎, 𝑔 (𝐵) = 𝑐] = \sum 𝑏 : 𝑔 (𝑏) = 𝑐 P r [𝐴 = 𝑎, 𝐵 = 𝑏]

である．右辺で $P r [𝐵 = 𝑏] = 0$ の項は $0$ だから落としてよい．残る項は，条件付き確率の定め方と仮定から $P r [𝐵 = 𝑏] 𝑓 (𝑎, 𝑔 (𝑏)) = P r [𝐵 = 𝑏] 𝑓 (𝑎, 𝑐)$ に等しい． $𝑓 (𝑎, 𝑐)$ は $𝑏$ によらないので和の外に出せて，残る $\sum 𝑏 P r [𝐵 = 𝑏]$ は $P r [𝑔 (𝐵) = 𝑐]$ である．よって $P r [𝐴 = 𝑎, 𝑔 (𝐵) = 𝑐] = 𝑓 (𝑎, 𝑐) P r [𝑔 (𝐵) = 𝑐]$ であり，両辺を $P r [𝑔 (𝐵) = 𝑐]$ で割れば主張を得る． $◻$

そのうえで，逆定理の証明に要る三つの評価を切り出しておく．

補題 14.5.7. $𝑊$ をブロードキャスト通信路（定義 14.5.1）， $𝑛 \geq 1$ とし， $(𝑀 1, 𝑀 2, 𝑐, 𝑑 1, 𝑑 2)$ を長さ $𝑛$ のブロードキャスト符号（定義 14.5.2）とする． $(M s g 1, M s g 2)$ を ${1, \dots, 𝑀 1} \times {1, \dots, 𝑀 2}$ 上の一様分布に従う対とし， $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1) : = 𝑐 (M s g 1, M s g 2)$ とおく． $(𝑌 𝑛 1, 𝑌 𝑛 2)$ を， $(M s g 1, M s g 2)$ を与えたときの条件付き分布が $𝑊 𝑛 (\cdot, \cdot ∣ 𝑋 𝑛)$ （定義 14.5.1）である確率変数の組とする． $𝑌 < 𝑖 1 : = (𝑌 1, 0, \dots, 𝑌 1, 𝑖 - 1)$ ， $𝑌 < 𝑖 2 : = (𝑌 2, 0, \dots, 𝑌 2, 𝑖 - 1)$ と書く．このとき次の三つが成り立つ．

$𝐻 (𝑌 𝑛 1 ∣ M s g 1, M s g 2) = \sum 𝑛 - 1 𝑖 = 0 𝐻 (𝑌 1, 𝑖 ∣ 𝑋 𝑖)$ である．
$0 \leq 𝑖 < 𝑛$ を満たす各 $𝑖$ について $𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 2, 𝑋 𝑖) = 𝐻 (𝑌 1, 𝑖 ∣ 𝑋 𝑖)$ である．
$𝑊$ が定義 14.5.4 の意味で物理的に劣化しているなら， $0 \leq 𝑖 < 𝑛$ を満たす各 $𝑖$ について $𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 1) \leq 𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 2)$ である．

証明. 以下，条件付き確率を $P r [\cdot ∣ \cdot]$ と書き，条件の側が正の確率をもつ点で考える．

まず，時刻 $𝑖$ の第 $1$ 出力の条件付き分布が同じ時刻の入力だけで決まることを見る．メッセージの対 $(𝑚 1, 𝑚 2)$ を固定すると符号語 $𝑥 𝑛 = 𝑐 (𝑚 1, 𝑚 2)$ が定まり，仮定より $𝑌 𝑛$ の条件付き分布は $\prod 𝑗 𝑊 (\cdot, \cdot ∣ 𝑥 𝑗)$ である．右辺は時刻ごとの因子の積だから， $(M s g 1, M s g 2)$ を与えたとき対 $(𝑌 1, 𝑗, 𝑌 2, 𝑗)$ たちは条件付き独立で，時刻 $𝑗$ の対の条件付き分布は $𝑊 (\cdot, \cdot ∣ 𝑥 𝑗)$ である．その第 $1$ 成分についての周辺は定義 14.5.1 より $𝑊 1 (\cdot ∣ 𝑥 𝑗)$ だから

P r [𝑌 1, 𝑖 = 𝑦 ∣ M s g 1 = 𝑚 1, M s g 2 = 𝑚 2, 𝑌 \neq 𝑖 1 = \cdot, 𝑌 \neq 𝑖 2 = \cdot] = 𝑊 1 (𝑦 ∣ 𝑥 𝑖)

がどの値の組についても成り立つ（ $𝑌 \neq 𝑖 1$ ， $𝑌 \neq 𝑖 2$ は時刻 $𝑖$ 以外の出力をすべて並べた組である）．右辺は $𝑥 𝑖$ ，すなわち $𝑋 𝑖$ の値だけの関数である．そこで補題 14.5.6 を， $𝐴$ に $𝑌 1, 𝑖$ ， $𝐵$ にこの四つ組と読み替えて当てる．得られるのは「条件を四つ組から粗くしても，残した条件から $𝑋 𝑖$ の値が読めるかぎり， $𝑌 1, 𝑖$ の条件付き分布は $𝑊 1 (\cdot ∣ 𝑋 𝑖)$ のままである」ということである．第 $1$ と第 $2$ の主張では，条件に残す組を変えてこれを使う．第 $3$ の主張では，同じ補題 14.5.6 を別の読み替えで当てる．

$(M s g 1, M s g 2) = (𝑚 1, 𝑚 2)$ を与えたとき， $𝑌 1, 0, \dots, 𝑌 1, 𝑛 - 1$ は条件付き独立で，第 $𝑗$ 成分の条件付き分布は $𝑊 1 (\cdot ∣ 𝑥 𝑗)$ である．独立な成分の組のエントロピーは成分のエントロピーの和である（定理 1.2.3 のチェイン則と，独立なら条件付きエントロピーが周辺のエントロピーに一致すること（定理 1.3.4 と命題 1.3.2 の等号条件）を $𝑛$ 回繰り返せばよい）．よってこの条件のもとでの $𝑌 𝑛 1$ のエントロピーは $\sum 𝑗 𝐻 (𝑊 1 (\cdot ∣ 𝑥 𝑗))$ である．定義 1.2.2 によりこれを $(𝑚 1, 𝑚 2)$ について平均すると
$𝐻 (𝑌 𝑛 1 ∣ M s g 1, M s g 2) = 𝑛 - 1 \sum 𝑗 = 0 𝔼 [𝐻 (𝑊 1 (\cdot ∣ 𝑋 𝑗))]$
である．いっぽう時刻 $𝑗$ について条件に $𝑋 𝑗$ だけを残すと， $𝑋 𝑗 = 𝑥$ を与えたときの $𝑌 1, 𝑗$ の条件付き分布は $𝑊 1 (\cdot ∣ 𝑥)$ だから，定義 1.2.2 より $𝐻 (𝑌 1, 𝑗 ∣ 𝑋 𝑗) = 𝔼 [𝐻 (𝑊 1 (\cdot ∣ 𝑋 𝑗))]$ である．二つを合わせて第 $1$ の主張を得る．
条件に $(M s g 2, 𝑌 < 𝑖 2, 𝑋 𝑖)$ を残す． $M s g 2$ はそのもの， $𝑌 < 𝑖 2$ は $𝑌 \neq 𝑖 2$ の一部， $𝑋 𝑖$ は $(M s g 1, M s g 2)$ の関数だから，これは四つ組から読める組であり， $𝑋 𝑖$ の値もそこから読める．この条件のもとで $𝑋 𝑖 = 𝑥$ である点での $𝑌 1, 𝑖$ の条件付き分布は $𝑊 1 (\cdot ∣ 𝑥)$ であり，そのエントロピーは $𝐻 (𝑊 1 (\cdot ∣ 𝑥))$ である．定義 1.2.2 により平均すると $𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 2, 𝑋 𝑖) = 𝔼 [𝐻 (𝑊 1 (\cdot ∣ 𝑋 𝑖))]$ であり，第 $1$ の主張の後半で見たとおりこれは $𝐻 (𝑌 1, 𝑖 ∣ 𝑋 𝑖)$ に等しい．
劣化の因子 $𝑊 2 ∣ 1$ をとる．メッセージの対を固定したときの $𝑌 𝑛$ の条件付き分布は $\prod 𝑗 𝑊 (\cdot, \cdot ∣ 𝑥 𝑗) = \prod 𝑗 𝑊 1 (\cdot ∣ 𝑥 𝑗) 𝑊 2 ∣ 1 (\cdot ∣ \cdot)$ だから， $(M s g 1, M s g 2)$ と $𝑌 𝑛 1 = 𝑦 𝑛 1$ を与えたときの $𝑌 𝑛 2$ の条件付き分布は $\prod 𝑗 𝑊 2 ∣ 1 (\cdot ∣ 𝑦 1, 𝑗)$ である．時刻 $𝑖$ より前だけを取り出すと
$P r [𝑌 < 𝑖 2 = 𝑦 < 𝑖 2 ∣ M s g 1, M s g 2, 𝑌 𝑛 1 = 𝑦 𝑛 1] = \prod 𝑗 < 𝑖 𝑊 2 ∣ 1 (𝑦 2, 𝑗 ∣ 𝑦 1, 𝑗)$
であり，右辺は $𝑦 < 𝑖 1$ だけの関数である．そこで補題 14.5.6 を， $𝐴$ に $𝑌 < 𝑖 2$ ， $𝐵$ に $(M s g 1, M s g 2, 𝑌 𝑛 1)$ と読み替えて二度当てる． $𝑔$ の行き先を $(M s g 2, 𝑌 < 𝑖 1, 𝑌 1, 𝑖)$ にとった場合と $(M s g 2, 𝑌 < 𝑖 1)$ にとった場合とで，どちらも $𝑦 < 𝑖 1$ が値から読めるので $𝑓$ は同じ写像でよい．よって
$P r [𝑌 < 𝑖 2 = 𝑦 < 𝑖 2 ∣ M s g 2, 𝑌 < 𝑖 1, 𝑌 1, 𝑖] = P r [𝑌 < 𝑖 2 = 𝑦 < 𝑖 2 ∣ M s g 2, 𝑌 < 𝑖 1]$
が成り立つ．これは $(M s g 2, 𝑌 < 𝑖 1)$ を与えたとき $𝑌 1, 𝑖$ と $𝑌 < 𝑖 2$ が条件付き独立だということだから，命題 1.4.2 の等号条件より $𝐼 (𝑌 1, 𝑖; 𝑌 < 𝑖 2 ∣ M s g 2, 𝑌 < 𝑖 1) = 0$ である．定理 1.4.3 をこの相互情報量に当てると
$𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 1) = 𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 1, 𝑌 < 𝑖 2)$
であり，定理 1.2.4 より右辺は $𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 2)$ 以下である．

$◻$

形式化上の注記. 補題 14.5.7 に対応する単独の宣言はない．形式化の側では，第 $1$ と第 $2$ の主張にあたる条件付き独立を束ねた述語と，第 $3$ の主張にあたる述語とが，次の定理 14.5.8 に紐付けた宣言の内側で符号から組み立てられている．補題 14.5.7 に付した証明が，この主張の保証のすべてである．

定理 14.5.8（劣化したブロードキャスト通信路の逆定理）. $𝑊$ をブロードキャスト通信路（定義 14.5.1）で定義 14.5.4 の意味で物理的に劣化しているものとし， $𝑛 \geq 1$ とする． $(𝑀 1, 𝑀 2, 𝑐, 𝑑 1, 𝑑 2)$ を長さ $𝑛$ のブロードキャスト符号（定義 14.5.2）で $𝑀 1 \geq 2$ かつ $𝑀 2 \geq 2$ を満たすものとし， $(M s g 1, M s g 2)$ ， $𝑋 𝑛$ ， $(𝑌 𝑛 1, 𝑌 𝑛 2)$ を補題 14.5.7 のとおりとする． $𝑃 𝑒, 1 : = P r [𝑑 1 (𝑌 𝑛 1) \neq M s g 1]$ ， $𝑃 𝑒, 2 : = P r [𝑑 2 (𝑌 𝑛 2) \neq M s g 2]$ とおき，各 $𝑖$ について $𝑈 𝑖 : = (M s g 2, 𝑌 < 𝑖 2)$ とおく．このとき

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

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

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

証明. 受け手 $2$ の側の評価は，ファノの不等式を出力列のチェイン則でほどけば出る. 定理 6.4.1 を，対象に $M s g 2$ ，観測に $𝑌 𝑛 2$ ，復号器に $𝑑 2$ を置いて当てると

l o g 𝑀 2 \leq 𝐼 (M s g 2; 𝑌 𝑛 2) + 𝐻 𝑏 (𝑃 𝑒, 2) + 𝑃 𝑒, 2 l o g (𝑀 2 - 1)

である（ $M s g 2$ は一様分布に従う．対 $(M s g 1, M s g 2)$ が一様なら成分も一様だからである）．第 $1$ 項を分解する．受け手 $2$ の出力列に $𝑛$ 変数チェイン則（定理 1.5.2）を当て，命題 1.3.3 と命題 1.4.2 の対称性で向きをそろえると

𝐼 (M s g 2; 𝑌 𝑛 2) = 𝑛 - 1 \sum 𝑖 = 0 𝐼 (M s g 2; 𝑌 2, 𝑖 ∣ 𝑌 < 𝑖 2)

である．各項に， $𝑈 𝑖$ から過去の出力 $𝑌 < 𝑖 2$ を先に取り出すチェイン則（定理 1.5.1）を当てると

𝐼 (𝑈 𝑖; 𝑌 2, 𝑖) = 𝐼 (𝑌 < 𝑖 2; 𝑌 2, 𝑖) + 𝐼 (M s g 2; 𝑌 2, 𝑖 ∣ 𝑌 < 𝑖 2)

であり，命題 1.3.2 より第 $1$ 項は非負だから $𝐼 (M s g 2; 𝑌 2, 𝑖 ∣ 𝑌 < 𝑖 2) \leq 𝐼 (𝑈 𝑖; 𝑌 2, 𝑖)$ である．和をとって第 $2$ の主張を得る．

受け手 $1$ には，相手のメッセージをただで渡してよい. 渡したうえでの評価もそのまま $l o g 𝑀 1$ の上界になるので，そこから始める．定理 6.4.1 を，対象に $M s g 1$ ，観測に対 $(M s g 2, 𝑌 𝑛 1)$ ，復号器に「第 $2$ 成分だけを見て $𝑑 1$ を当てる写像」を置いて当てる．その復号器の誤り確率は $P r [𝑑 1 (𝑌 𝑛 1) \neq M s g 1] = 𝑃 𝑒, 1$ だから

l o g 𝑀 1 \leq 𝐼 (M s g 1; (M s g 2, 𝑌 𝑛 1)) + 𝐻 𝑏 (𝑃 𝑒, 1) + 𝑃 𝑒, 1 l o g (𝑀 1 - 1)

である．第 $1$ 項を書き換える．対 $(M s g 2, 𝑌 𝑛 1)$ から $M s g 2$ を先に取り出すチェイン則（定理 1.5.1）を当て，命題 1.3.3 と命題 1.4.2 の対称性で向きをそろえると

𝐼 (M s g 1; (M s g 2, 𝑌 𝑛 1)) = 𝐼 (M s g 1; M s g 2) + 𝐼 (M s g 1; 𝑌 𝑛 1 ∣ M s g 2)

である．対 $(M s g 1, M s g 2)$ が一様分布に従うので二つの成分は独立であり，命題 1.3.2 の等号条件より第 $1$ 項は $0$ である．

残りをエントロピーの差に直す．出力列の側をエントロピーの差に開く形（定理 1.4.3）を当て，命題 1.4.2 の対称性で向きをそろえると

𝐼 (M s g 1; 𝑌 𝑛 1 ∣ M s g 2) = 𝐻 (𝑌 𝑛 1 ∣ M s g 2) - 𝐻 (𝑌 𝑛 1 ∣ M s g 1, M s g 2)

である．第 $1$ 項に定理 1.2.3 のチェイン則を $𝑛$ 回繰り返して

𝐻 (𝑌 𝑛 1 ∣ M s g 2) = 𝑛 - 1 \sum 𝑖 = 0 𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 1)

を得る（条件に $M s g 2$ を置いたままチェイン則を当てている）．第 $2$ 項には補題 14.5.7 の第 $1$ の主張を当てる．よって

𝐼 (M s g 1; 𝑌 𝑛 1 ∣ M s g 2) = 𝑛 - 1 \sum 𝑖 = 0 (𝐻 (𝑌 1, 𝑖 ∣ M s g 2, 𝑌 < 𝑖 1) - 𝐻 (𝑌 1, 𝑖 ∣ 𝑋 𝑖))

である．

劣化が効くのはここ一箇所で，条件を受け手 $1$ の過去の出力から受け手 $2$ の過去の出力に置き換えるところである. 各項の第 $1$ 成分に補題 14.5.7 の第 $3$ の主張を当てると，右辺は

𝑛 - 1 \sum 𝑖 = 0 (𝐻 (𝑌 1, 𝑖 ∣ 𝑈 𝑖) - 𝐻 (𝑌 1, 𝑖 ∣ 𝑋 𝑖))

以下である．補題 14.5.7 の第 $2$ の主張より $𝐻 (𝑌 1, 𝑖 ∣ 𝑋 𝑖) = 𝐻 (𝑌 1, 𝑖 ∣ 𝑈 𝑖, 𝑋 𝑖)$ だから，各項は $𝐻 (𝑌 1, 𝑖 ∣ 𝑈 𝑖) - 𝐻 (𝑌 1, 𝑖 ∣ 𝑈 𝑖, 𝑋 𝑖)$ の形をしており，出力の側をエントロピーの差に開く形（定理 1.4.3）と命題 1.4.2 の対称性より $𝐼 (𝑋 𝑖; 𝑌 1, 𝑖 ∣ 𝑈 𝑖)$ に等しい．合わせて第 $1$ の主張を得る． $◼$

形式化: bc_degraded_converse_from_code (ソース)

補助変数の作り方が，この証明のすべてである．受け手 $2$ の側は，出力列に定理 1.5.2 のチェイン則を当てて過去の出力を条件に置き，その条件をそのまま $𝑈 𝑖$ の一部に取り込んだだけである．第6章定理 6.4.3 は同じチェイン則を入力列のほうに当てて過去の入力を条件に置いており，割る対象が違う．受け手 $1$ の側では逆に， $𝑈 𝑖$ が条件として引く形で現れる．同じ $𝑈 𝑖$ が，片方の受け手にとっては運べる量そのもの，もう片方にとっては「すでに知っているぶん」になっている．二段の符号帳で雲と衛星を分けたのと，読み方が同じである．劣化を使った一箇所では，受け手 $2$ の過去の出力を条件に置いたほうが受け手 $1$ の過去の出力を置くより不確かさが残ること，つまり受け手 $2$ の観測のほうが粗いことが効いている．

借りた 重ね合わせ符号化の達成可能性 の劣化を仮定した形と定理 14.5.8 は，同じ二つの量 $𝐼 (𝑋; 𝑌 1 ∣ 𝑈)$ と $𝐼 (𝑈; 𝑌 2)$ を両側から挟んでいる．ただし挟み方はそろっていない．借用の側は補助変数の分布と入力への通信路を一組固定した形だが，定理 14.5.8 に現れる $𝑈 𝑖$ は符号から作られたもので，時刻ごとに違う分布をもつ．二つを同じ土俵に載せるには，時刻を一様に選ぶ変数をもう一段の補助変数として束ね，補助変数のとりうる値の個数を抑える段が要る．本書はその段を扱わない．

その段まで進めたときに何が言えるかが，本節の到達点である．道具をもう一つ借りる．劣化した通信路の容量領域，すなわち「劣化した通信路では，いまの二つの量が切る長方形を合わせた集合がちょうど容量領域である」という主張である．使う形を書いておく．

$𝑊$ をブロードキャスト通信路（定義 14.5.1）で定義 14.5.4 の意味で物理的に劣化しているものとし， $𝑊 (𝑦 1, 𝑦 2 ∣ 𝑥) > 0$ がすべての $𝑥 \in X$ ， $𝑦 1 \in Y 1$ ， $𝑦 2 \in Y 2$ で成り立つとする． $U$ ， $𝑝 𝑈$ ， $𝐾$ と四つ組 $(𝑈, 𝑋, 𝑌 1, 𝑌 2)$ は，上で借りた 重ね合わせ符号化の達成可能性 と同じ形にとる． $𝑝 𝑈$ と $𝐾$ がどちらも全点で正である組をすべて動かし，そのつど二つの量が切る長方形

{(𝑅 1, 𝑅 2) \in ℝ 2 : 𝑅 1 \leq 𝐼 (𝑋; 𝑌 1 ∣ 𝑈), 𝑅 2 \leq 𝐼 (𝑈; 𝑌 2)}

を合わせて閉包をとると，その集合は定義 14.5.3 の容量領域 $C (𝑊)$ に等しい．長方形と呼ぶが，定義 14.5.3 と同じくレートの非負性を課していないので左下には限りがない．呼び名は第一象限で見える形から来ている．

当てる対象は定義 14.5.3 の容量領域と上の長方形の合併だけで，本書のあとの主張がこれを引くことはない．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．内側は借りた 重ね合わせ符号化の達成可能性 の劣化を仮定した形が，外側は定理 14.5.8 が与える．二つのあいだを埋めるのが，いま述べた二つの段，すなわち時刻を一様に選ぶ変数で束ねる段と，補助変数のとりうる値の個数を抑える段である．

本書はこの主張を証明しない．その二つの段をどちらも扱わないからである．本書が自分で保証するのは，借用の与える内側と定理 14.5.8 の与える外側の二つまでである．

形式化: bc_lessNoisy_superposition_eq_capacity (ソース)

形式化上の注記. 宣言が仮定に置いているのは劣化ではなく，14.6 節定義 14.6.1 の意味で受け手 $1$ の側の雑音がより少ないことである．劣化していればこれが満たされる（14.6 節定理 14.6.3）ので，宣言は借りた形より広い場合を覆っている．仮定をさらに 14.6 節定義 14.6.2 の能力がより高い場合まで緩めた宣言 bc_moreCapable_superposition_eq_capacity (InformationTheory/Shannon/BroadcastChannel/Superposition/MoreCapable.lean) もあるが，そちらが容量領域に等しいと述べているのは，三本目の枠 $m a x (𝑅 1, 0) + 𝑅 2 \leq 𝐼 ((𝑈, 𝑋); 𝑌 1)$ まで課した集合であって，上の長方形の合併ではない．クラスを広げると集合のほうも変わるので，二つは別の主張である．合併がわたる範囲も，どちらの宣言でも補助アルファベットを ${1, \dots, 𝑘 + 1}$ の形のものに固定して $𝑘$ を動かす形になっている．

いま借りた 劣化した通信路の容量領域 と同じ集合が，次の 14.6 節でもう一度，別の表し方で現れる（系 14.6.7）．そちらは本節の二つの量ではなく，受け手ごとに補助変数を一つずつ置いた形で書かれる．

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