14.8 中継通信路

ここまでの四つの設定は，どれも参加者が二人に分かれるものだった．多元接続では二人の送り手，ブロードキャストでは二人の受け手，相関情報源では二人の圧縮者がそれぞれ取り分を持つので，どこまで送れるかの答えはレートの対についてのものになり，前の二つではそれを領域として書いた．副情報つきレート歪みでは符号化する側と復号する側で見えるものが違ったが，取り分を問う相手は圧縮する側だけなので，答えは定義 14.4.3 の $𝑅 W Z (𝐷)$ という一つの数だった．

本節の設定はそのどれとも違う．送り手も受け手も一人で，そのあいだに 助け手 が一人いる．助け手は自分でメッセージを持たず，通信路から聞こえてくるものを聞いて，受け手に届きやすいように何かを送り直す．取り分を問う相手は送り手だけなので，答えは 14.4 節と同じく領域ではなく数である．レート領域は本節に現れない．それでも評価に使う道具は前の節までのもので，しかも二つの切り口がそのまま 14.1 節の多元接続と 14.5 節のブロードキャストになる．中継を扱うのに二人ぶんの設定が要るというのが，本節を本章に置く理由である．

記号を一つ断っておく．本節では助け手の送るものに $𝑋 1$ ，助け手の聞くものに $𝑌 1$ と，どちらも番号 $1$ を付け，送り手の送るものと受け手の聞くものには番号を付けずに $𝑋$ ， $𝑌$ と書く．番号は 14.1 節と同じく参加者のもので，ここでは助け手が番号 $1$ をもつ．時刻を書くときも 14.1 節の約束どおりで，番号のある記号は $𝑋 1, 𝑖$ ，ない記号は $𝑋 𝑖$ とする．この約束では $𝑋 1$ と $𝑌 1$ の字面がどちらも二通りに読める．番号として読めば助け手の送るものと聞くもの，時刻として読めば送り手が時刻 $1$ に送るものと受け手が時刻 $1$ に聞くものである．助け手の記号は時刻まで書くときつねに番号を先に置いて $𝑋 1, 𝑖$ ， $𝑌 1, 𝑖$ とし，長さ $𝑛$ の組は $𝑋 𝑛 1$ ， $𝑌 𝑛 1$ と書くので，時刻を並べた式の中に下付きが一つだけの $𝑋 1$ や $𝑌 1$ が現れたら，それは送り手または受け手の側である．小文字のほうは分かれず， $𝑥 1$ は定義 14.8.1 のとおりつねに助け手の入力を指す．14.5 節から 14.7 節までの $𝑌 1$ ， $𝑌 2$ は二人の受け手の出力だったが，本節に受け手は一人しかいない．

通信路と符号

定義 14.8.1（中継通信路）. $X$ ， $X 1$ ， $Y$ ， $Y 1$ をどれも空でない有限アルファベットとする．中継通信路（relay channel）とは，入力の対 $(𝑥, 𝑥 1) \in X \times X 1$ ごとに $Y \times Y 1$ 上の分布 $𝑊 (\cdot, \cdot ∣ 𝑥, 𝑥 1)$ を与える対応である．すなわち $𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1) \geq 0$ であって，各対について $\sum 𝑦, 𝑦 1 𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1) = 1$ を満たす． $𝑥$ は送り手の入力， $𝑥 1$ は中継の入力， $𝑦$ は受け手の見る出力， $𝑦 1$ は中継の見る出力である．

入力が対で出力が対なので，字面の上では 14.1 節の多元接続通信路とも 14.5 節のブロードキャスト通信路とも違う．中身は二つを重ねたものである．入力の側は二人が別々に選ぶので多元接続と同じ形をしており，出力の側は一本の入力から二人が別々に受け取るのでブロードキャストと同じ形をしている．違うのは，入力の一方と出力の一方が同じ人に属していることで，助け手は聞いたものに応じて送るものを変えられる．定義 14.1.1 と定義 14.5.1 が長さ $𝑛$ への積の延長 $𝑊 𝑛$ を定めていたのに対し，ここではそれを定めていない．理由は，次の定義 14.8.2 で中継写像が出てからでないと言えない．

形式化: RelayChannel (ソース)

定義 14.8.2（中継符号）. $𝑊$ を中継通信路（定義 14.8.1）とし， $𝑛 \geq 1$ とする．長さ $𝑛$ の 中継符号 とは，メッセージ数 $𝑀 \geq 1$ と，符号化写像 $𝑐 : {1, \dots, 𝑀} \to X 𝑛$ ，各時刻 $𝑖$ ごとの 中継写像 $𝑟 𝑖 : Y 𝑖 1 \to X 1$ （ $0 \leq 𝑖 < 𝑛$ ），および復号器 $𝑑 : Y 𝑛 \to {1, \dots, 𝑀}$ の組である．時刻 $𝑖$ の中継入力は $𝑋 1, 𝑖 : = 𝑟 𝑖 (𝑌 1, 0, \dots, 𝑌 1, 𝑖 - 1)$ で定める．

中継写像が時刻 $𝑖$ より前の観測しか引数にとらないところが，この定義の要である．助け手は時刻 $𝑖$ に送るものを決めるとき，その時刻に自分が何を聞くかをまだ知らない．この性質を 因果的 であるという．因果性を落として $𝑟 𝑖$ に $𝑌 1, 𝑖$ まで渡してしまうと，助け手は自分がまだ聞いていないものを使って送ることになる．定義 14.8.2 が引数を時刻 $𝑖$ より前に限っているのは，そういう符号を数に入れないためである．時刻 $0$ では引数が空なので， $𝑋 1, 0$ は定数である．

積の延長を定めない理由がここから出る．中継符号を $𝑊$ に通すというのは，時刻ごとに，そこまでに定まった入力の対 $(𝑥 𝑖, 𝑥 1, 𝑖)$ に対して $𝑊$ が返す対 $(𝑦 𝑖, 𝑦 1, 𝑖)$ を引く，ということである．メッセージ $𝑚$ を与えたときの出力の組の同時分布を書き下すと，これは $\prod 𝑖 𝑊 (𝑦 𝑖, 𝑦 1, 𝑖 ∣ 𝑐 (𝑚) 𝑖, 𝑟 𝑖 (𝑦 < 𝑖 1))$ になる（ $𝑦 < 𝑖 1 : = (𝑦 1, 0, \dots, 𝑦 1, 𝑖 - 1)$ と書いた）．時刻 $𝑖$ の因子の第 $2$ 入力が過去の出力から作られているので，これは固定した入力の対の列 $(𝑥 𝑛, 𝑥 𝑛 1)$ を引数にとる形ではない．送り手が符号語を一本選んでも，助け手の入力の列は出力を見ながら定まっていくからである．そのため定義 14.8.1 に $𝑊 𝑛$ にあたる延長を置いても中継符号には当てはまらず，以下の主張は，出力の組に置く条件を主張ごとに書き込む形になっている．

形式化: RelayCode (ソース)

二つのカット

三人の参加者を二組に分ける切り口をとる．送り手が一方の組に，受け手がもう一方の組に入るように切ると，メッセージはかならずその切り口を越えることになるので，切り口を越えて運べる量が送れる量の上界になる．そういう切り口は，助け手をどちらの組に入れるかで二通りある．どちらも上界を与えるから，小さいほうが残る．以下の二つの評価がその二通りに対応する．

一つめは，受け手の側で切る．受け手から見ると，送り手と助け手という二人の送り手が同じ通信路に入力を流し込んでいるように見える．これは 14.1 節の多元接続にほかならない．

定理 14.8.3（多元接続のカット）. $𝑀 \geq 2$ ， $𝑛 \geq 1$ とし， $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数とする． $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝑋 𝑛 1 = (𝑋 1, 0, \dots, 𝑋 1, 𝑛 - 1)$ ， $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ をそれぞれ有限集合に値をとる確率変数の組とし， $𝑍 𝑖 : = (𝑋 𝑖, 𝑋 1, 𝑖)$ ， $𝑍 𝑛 : = (𝑍 0, \dots, 𝑍 𝑛 - 1)$ とおく． $𝑑$ を $𝑌 𝑛$ の値から ${1, \dots, 𝑀}$ への写像とし， $𝑃 𝑒 : = P r [𝑑 (𝑌 𝑛) \neq M s g]$ とおく． $M s g \to 𝑍 𝑛 \to 𝑌 𝑛$ がマルコフ連鎖（定義 1.8.3）をなし，かつ $𝑍 𝑛$ と $𝑌 𝑛$ が各時刻で記憶がない（定義 6.4.4）なら

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

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

証明. 定理 6.4.1 を，対象に $M s g$ ，観測に $𝑌 𝑛$ ，復号器に $𝑑$ を置いて当てると $l o g 𝑀 \leq 𝐼 (M s g; 𝑌 𝑛) + 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1)$ である．定理 1.8.4 を連鎖 $M s g \to 𝑍 𝑛 \to 𝑌 𝑛$ に当てると $𝐼 (M s g; 𝑌 𝑛) \leq 𝐼 (𝑍 𝑛; 𝑌 𝑛)$ だから，あとは $𝐼 (𝑍 𝑛; 𝑌 𝑛) \leq \sum 𝑖 𝐼 (𝑍 𝑖; 𝑌 𝑖)$ を示せばよい．

定理 1.8.5 を入力の組 $𝑍 𝑛$ と出力の組 $𝑌 𝑛$ に当てる．あの定理が求めているのは二つで， $𝑍 𝑛$ を与えたとき $𝑌 0, \dots, 𝑌 𝑛 - 1$ が条件付き独立であることと，各 $𝑌 𝑖$ の条件付き分布が同じ時刻の入力 $𝑍 𝑖$ だけで決まることである．定義 6.4.4 からこの二つが出ることを見る．以下，条件付き確率を $P r [\cdot ∣ \cdot]$ と書き，事象を値だけで表す（条件の側が正の確率をもつ点で考える）．定義 6.4.4 は， $𝑍 𝑖$ を与えたとき $𝑌 𝑖$ が $(𝑍 \neq 𝑖, 𝑌 \neq 𝑖)$ と条件付き独立であること，すなわち $P r [𝑦 𝑖 ∣ 𝑧 𝑛, 𝑦 \neq 𝑖] = P r [𝑦 𝑖 ∣ 𝑧 𝑖]$ を言っている．右辺は $𝑧 𝑖$ だけの関数で， $𝑍 𝑛$ も $(𝑍 𝑛, 𝑌 < 𝑖)$ も $(𝑍 𝑛, 𝑌 \neq 𝑖)$ の関数として書けるから，補題 14.5.6 を， $𝐴$ に $𝑌 𝑖$ ， $𝐵$ に $(𝑍 𝑛, 𝑌 \neq 𝑖)$ と読み替え， $𝑔$ の行き先を二通りにとって当てると

P r [𝑦 𝑖 ∣ 𝑧 𝑛] = P r [𝑦 𝑖 ∣ 𝑧 𝑖], P r [𝑦 𝑖 ∣ 𝑧 𝑛, 𝑦 < 𝑖] = P r [𝑦 𝑖 ∣ 𝑧 𝑖]

がどちらも成り立つ．前者が第 $2$ の条件そのものである．後者を条件付き確率のチェイン則 $P r [𝑦 𝑛 ∣ 𝑧 𝑛] = \prod 𝑖 P r [𝑦 𝑖 ∣ 𝑧 𝑛, 𝑦 < 𝑖]$ に代入すると $P r [𝑦 𝑛 ∣ 𝑧 𝑛] = \prod 𝑖 P r [𝑦 𝑖 ∣ 𝑧 𝑛]$ となり，これが第 $1$ の条件である．よって定理 1.8.5 より $𝐼 (𝑍 𝑛; 𝑌 𝑛) \leq \sum 𝑖 𝐼 (𝑍 𝑖; 𝑌 𝑖)$ である． $◼$

形式化: relay_mac_cut_outer_bound (ソース)

定理 14.8.3 は中継符号を名指していない．入力の組が符号から作られていることも，中継写像が因果的であることも使っていないからである．第6章定理 6.4.5 が符号化写像を仮定に置いていたのに対し，こちらがそれを置かないのはそのためである．そのかわりに置いているのが，マルコフ連鎖と定義 6.4.4 の二つの条件である．後者は，中継符号から作った $𝑍 𝑛$ と $𝑌 𝑛$ が自動的に満たすものではない．破れる筋道は，中継入力が過去の観測の関数であるところにある．時刻 $𝑖$ より後の中継入力は時刻 $𝑖$ の助け手の観測を引数にとるので， $𝑗 > 𝑖$ の $𝑍 𝑗$ がその観測を含む．その観測が同じ時刻の受け手の出力と結びついているかどうかが分かれ目になる．満たされる場合と破れる場合を，次の命題 14.8.4 と例 14.8.5 で一つずつ見ておく．

命題 14.8.4. $𝑊$ を中継通信路（定義 14.8.1）とし，その二つの周辺通信路を

𝑊' (𝑦 ∣ 𝑥, 𝑥 1) : = \sum 𝑦 1 𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1), 𝑊' 1 (𝑦 1 ∣ 𝑥, 𝑥 1) : = \sum 𝑦 𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1)

で定める．すべての $(𝑥, 𝑥 1, 𝑦, 𝑦 1)$ について $𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1) = 𝑊' (𝑦 ∣ 𝑥, 𝑥 1) 𝑊' 1 (𝑦 1 ∣ 𝑥, 𝑥 1)$ が成り立つとする（入力の対を与えたとき，受け手の出力と助け手の観測が条件付き独立だということである）． $𝑛 \geq 1$ とし， $(𝑀, 𝑐, 𝑟, 𝑑)$ を長さ $𝑛$ の中継符号（定義 14.8.2）とする． $M s g$ を ${1, \dots, 𝑀}$ に値をとる確率変数とし， $𝑋 𝑖 : = 𝑐 (M s g) 𝑖$ とおく． $(𝑌 𝑛, 𝑌 𝑛 1)$ を， $M s g$ を与えたときの条件付き分布が $\prod 𝑖 𝑊 (𝑦 𝑖, 𝑦 1, 𝑖 ∣ 𝑋 𝑖, 𝑟 𝑖 (𝑦 < 𝑖 1))$ である確率変数の組とし， $𝑋 1, 𝑖 : = 𝑟 𝑖 (𝑌 < 𝑖 1)$ ， $𝑍 𝑖 : = (𝑋 𝑖, 𝑋 1, 𝑖)$ ， $𝑍 𝑛 : = (𝑍 0, \dots, 𝑍 𝑛 - 1)$ とおく．このとき $M s g \to 𝑍 𝑛 \to 𝑌 𝑛$ はマルコフ連鎖（定義 1.8.3）をなし， $𝑍 𝑛$ と $𝑌 𝑛$ は定義 6.4.4 の意味で各時刻で記憶がない．

証明. 以下，条件付き確率を $P r [\cdot ∣ \cdot]$ と書き，条件の側が正の確率をもつ点で考える． $𝑌 \neq 𝑖$ と書いたら，時刻 $𝑖$ 以外の受け手の出力をすべて並べた組である．

メッセージと助け手の観測をすべて与えると，受け手の出力の列の分布は入力の対の列だけで決まる. $M s g = 𝑚$ を与えると入力 $𝑥 𝑗 = 𝑐 (𝑚) 𝑗$ がすべての $𝑗$ で定まり， $𝑌 𝑛 1 = 𝑦 𝑛 1$ を与えると中継入力 $𝑟 𝑗 (𝑦 < 𝑗 1)$ もすべての $𝑗$ で定まる．そこで定まる $𝑍 𝑗$ の値を $𝑧 𝑗$ と書く．これは $𝑚$ と $𝑦 < 𝑗 1$ だけの関数で，受け手の出力にはよらない．仮定の積の形を入れると， $M s g = 𝑚$ を与えたときの $(𝑌 𝑛, 𝑌 𝑛 1) = (𝑦 𝑛, 𝑦 𝑛 1)$ の確率は $\prod 𝑗 𝑊' (𝑦 𝑗 ∣ 𝑧 𝑗) 𝑊' 1 (𝑦 1, 𝑗 ∣ 𝑧 𝑗)$ である． $𝑧 𝑗$ が $𝑦 𝑛$ によらないので， $𝑦 𝑛$ について和をとると第 $1$ の因子の和が時刻ごとに $1$ になり， $M s g = 𝑚$ を与えたときの $𝑌 𝑛 1 = 𝑦 𝑛 1$ の確率は $\prod 𝑗 𝑊' 1 (𝑦 1, 𝑗 ∣ 𝑧 𝑗)$ である．割ると

P r [𝑌 𝑛 = 𝑦 𝑛 ∣ M s g, 𝑌 𝑛 1] = \prod 𝑗 𝑊' (𝑦 𝑗 ∣ 𝑍 𝑗)

である．

マルコフ連鎖は，条件を $𝑍 𝑛$ まで粗くすれば出る. 右辺は $𝑍 𝑛$ の値だけの関数であり， $𝑍 𝑛$ も対 $(M s g, 𝑍 𝑛)$ も $(M s g, 𝑌 𝑛 1)$ の関数として書ける．そこで補題 14.5.6 を， $𝐴$ に $𝑌 𝑛$ ， $𝐵$ に対 $(M s g, 𝑌 𝑛 1)$ ， $𝑓$ に「 $𝑌 𝑛$ の値 $𝑦 𝑛$ と行き先の値の対から，そこに含まれる $𝑍 𝑛$ の値を読んで $\prod 𝑗 𝑊' (𝑦 𝑗 ∣ 𝑧 𝑗)$ を返す写像」と読み替え， $𝑔$ の行き先を $𝑍 𝑛$ にとった場合と $(M s g, 𝑍 𝑛)$ にとった場合とで二度当てると $P r [𝑌 𝑛 = 𝑦 𝑛 ∣ 𝑍 𝑛] = P r [𝑌 𝑛 = 𝑦 𝑛 ∣ M s g, 𝑍 𝑛]$ である．条件付き確率のチェイン則より $P r [M s g = 𝑚, 𝑌 𝑛 = 𝑦 𝑛 ∣ 𝑍 𝑛] = P r [M s g = 𝑚 ∣ 𝑍 𝑛] P r [𝑌 𝑛 = 𝑦 𝑛 ∣ M s g, 𝑍 𝑛]$ だから，右の因子をいまの等式で置き換えると $P r [M s g = 𝑚 ∣ 𝑍 𝑛] P r [𝑌 𝑛 = 𝑦 𝑛 ∣ 𝑍 𝑛]$ になる．これが定義 1.8.3 の条件である．

記憶のなさは，同じ等式を時刻 $𝑖$ 以外の出力まで条件に入れて読めば出る. 時刻 $𝑖$ を固定する．第一段の等式で $𝑦 \neq 𝑖$ を固定して $𝑦 𝑖$ を動かすと，変わる因子は $𝑊' (𝑦 𝑖 ∣ 𝑧 𝑖)$ だけであり， $𝑦 𝑖$ について和をとるとそれは $1$ になるから $P r [𝑌 𝑖 = 𝑦 ∣ M s g, 𝑌 𝑛 1, 𝑌 \neq 𝑖] = 𝑊' (𝑦 ∣ 𝑍 𝑖)$ である．右辺は $𝑍 𝑖$ の値だけの関数であり， $(𝑍 𝑛, 𝑌 \neq 𝑖)$ も $𝑍 𝑖$ も三つ組 $(M s g, 𝑌 𝑛 1, 𝑌 \neq 𝑖)$ の関数として書ける．そこで補題 14.5.6 を， $𝐴$ に $𝑌 𝑖$ ， $𝐵$ にこの三つ組と読み替え， $𝑔$ の行き先を二通りにとって当てると $P r [𝑌 𝑖 = 𝑦 ∣ 𝑍 𝑛, 𝑌 \neq 𝑖] = P r [𝑌 𝑖 = 𝑦 ∣ 𝑍 𝑖]$ である．これは $𝑍 𝑖$ を与えたとき $𝑌 𝑖$ が $(𝑍 \neq 𝑖, 𝑌 \neq 𝑖)$ と条件付き独立だということ，すなわち定義 6.4.4 である． $◼$

形式化上の注記. 命題 14.8.4 に対応する単独の宣言はない．命題 14.8.4 に付した証明が，この主張の保証のすべてである．形式化の側では，定理 14.8.3 に紐付けた宣言が定義 6.4.4 にあたる述語を仮定として受け取る形になっており，第6章補題 6.4.6 のときと同じである．

例 14.8.5（記憶のなさが破れる中継符号）. $X = X 1 = Y = Y 1 = {0, 1}$ とし， $𝑦 = 𝑦 1$ のとき $𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1) : = 1 / 2$ ， $𝑦 \neq 𝑦 1$ のとき $𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1) : = 0$ で定まる対応を $𝑊$ とする（入力によらず，同じ公平なコインの値が受け手と助け手の両方に届く）．長さ $2$ の中継符号（定義 14.8.2）で，中継写像が，値 $0$ をとる定数写像 $𝑟 0$ と，引数をそのまま返す $𝑟 1 (𝑦 1, 0) = 𝑦 1, 0$ であるものをとり， $(𝑀, 𝑐, 𝑟, 𝑑)$ と書く． $M s g$ を ${1, \dots, 𝑀}$ に値をとる確率変数とし， $𝑋 𝑖 : = 𝑐 (M s g) 𝑖$ とおく． $(𝑌 2, 𝑌 21)$ を， $M s g$ を与えたときの条件付き分布が $\prod 1 𝑖 = 0 𝑊 (𝑦 𝑖, 𝑦 1, 𝑖 ∣ 𝑋 𝑖, 𝑟 𝑖 (𝑦 < 𝑖 1))$ である確率変数の組とし， $𝑋 1, 𝑖 : = 𝑟 𝑖 (𝑌 < 𝑖 1)$ ， $𝑍 𝑖 : = (𝑋 𝑖, 𝑋 1, 𝑖)$ ， $𝑍 2 : = (𝑍 0, 𝑍 1)$ とおく（受け手の出力の組は $𝑌 2 = (𝑌 0, 𝑌 1)$ で，助け手の観測は二つの番号を付けて $𝑌 1, 0$ ， $𝑌 1, 1$ と書く）．このとき $𝑊$ は定義 14.8.1 の意味で中継通信路であり， $𝑍 2$ と $𝑌 2$ は定義 6.4.4 の意味で各時刻で記憶がない，という条件を満たさない．

証明. 中継通信路であることは，各入力の対について $\sum 𝑦, 𝑦 1 𝑊 (𝑦, 𝑦 1 ∣ 𝑥, 𝑥 1) = 1 / 2 + 1 / 2 = 1$ から出る．

出力の側を読む．条件付き分布の各因子は $𝑦 𝑖 = 𝑦 1, 𝑖$ のとき $1 / 2$ ，そうでないとき $0$ で，入力の値を含まない．したがって $(𝑌 2, 𝑌 21)$ の分布は $M s g$ の値によらず， $(𝑌 2, 𝑌 21)$ は $M s g$ と独立である．また確率 $1$ で各時刻の助け手の観測は同じ時刻の受け手の出力に等しく，二つの時刻の出力は互いに独立でどちらも ${0, 1}$ 上一様である．中継写像より $𝑋 1, 1 = 𝑟 1 (𝑌 1, 0) = 𝑌 0$ だから， $𝑍 1 = (𝑋 1, 𝑌 0)$ は $𝑌 0$ の値を第 $2$ 成分に含む．

時刻 $0$ で条件が破れることを見る．定義 6.4.4 が時刻 $0$ について求めているのは $(𝑍 \neq 0, 𝑌 \neq 0) \to 𝑍 0 \to 𝑌 0$ がマルコフ連鎖をなすこと，すなわち定義 1.8.3 により， $𝑍 0$ を与えたとき $𝑌 0$ と $(𝑍 \neq 0, 𝑌 \neq 0)$ が条件付き独立であることである． $𝑍 0 = (𝑐 (M s g) 0, 0)$ が正の確率をとる値を一つ選んで $𝑧 0$ とする．その条件のもとで $𝑋 1$ が正の確率をとる値を一つ選んで $𝑎$ とし，時刻 $1$ の受け手の出力の値を一つ選んで $𝑏$ とし， $𝑤 : = ((𝑎, 1), 𝑏)$ とおく．これは $(𝑍 \neq 0, 𝑌 \neq 0)$ のとりうる値で，しかも $𝑍 1$ の第 $2$ 成分を $1$ にとっている． $𝑍 1$ の第 $2$ 成分は $𝑌 0$ だから， $𝑌 0 = 0$ と $(𝑍 \neq 0, 𝑌 \neq 0) = 𝑤$ は同時には起こらず，二つの事象の条件付き確率は $0$ である．いっぽう $(𝑌 2, 𝑌 21)$ が $M s g$ と独立で二つの時刻の出力が独立な公平なコインであることから $P r [𝑌 0 = 0 ∣ 𝑍 0 = 𝑧 0] = 1 / 2$ であり， $P r [(𝑍 \neq 0, 𝑌 \neq 0) = 𝑤 ∣ 𝑍 0 = 𝑧 0] = P r [𝑋 1 = 𝑎 ∣ 𝑍 0 = 𝑧 0] / 4 > 0$ である．積が正で左辺が $0$ だから，定義 1.8.3 の積の形は成り立たない． $◼$

形式化上の注記. 例 14.8.5 に対応する宣言は形式化されていない．例 14.8.5 に付した証明が，この主張の保証のすべてである．

二つめは，送り手の側で切る．送り手から見ると，自分の入力から助け手と受け手という二人が別々に受け取っているように見える．これは 14.5 節のブロードキャストにほかならない．ただしこちらは本書が証明しない．

道具を一つ借りる．ブロードキャストのカット，すなわち「送り手の側で切ると，メッセージ数は，助け手の入力を条件に置いた時刻ごとの相互情報量の和で上から抑えられる」という主張である．使う形を書いておく．

$𝑀 \geq 2$ ， $𝑛 \geq 1$ とし， $𝑊$ を中継通信路（定義 14.8.1）， $(𝑀, 𝑐, 𝑟, 𝑑)$ を長さ $𝑛$ の中継符号（定義 14.8.2）とする． $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数とし， $𝑋 𝑖 : = 𝑐 (M s g) 𝑖$ ， $𝑋 1, 𝑖 : = 𝑟 𝑖 (𝑌 1, 0, \dots, 𝑌 1, 𝑖 - 1)$ とし， $(𝑌 𝑛, 𝑌 𝑛 1)$ を，各時刻の対 $(𝑌 𝑖, 𝑌 1, 𝑖)$ が入力の対 $(𝑋 𝑖, 𝑋 1, 𝑖)$ に対して $𝑊$ が返す出力であるような組とする． $𝑃 𝑒 : = P r [𝑑 (𝑌 𝑛) \neq M s g]$ とおく．各時刻 $𝑖$ について，対 $(𝑋 𝑖, 𝑋 1, 𝑖)$ を与えたとき対 $(𝑌 1, 𝑖, 𝑌 𝑖)$ が $(M s g, (𝑌 1, 𝑗, 𝑌 𝑗) 𝑗 < 𝑖)$ と条件付き独立である（定義 1.8.3）とする．このとき

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

である．

当てる対象は定義 14.8.1 の中継通信路と定義 14.8.2 の中継符号だけで，依存するのは系 14.8.6 の証明と，本節の終わりの地の文である．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．送り手の入力 $𝑋 𝑖$ から，助け手と受け手の対 $(𝑌 1, 𝑖, 𝑌 𝑖)$ へのブロードキャスト通信路とみなす．助け手の入力 $𝑋 1, 𝑖$ は送り手が選んだものではないので，条件に置いて動かさないことにする．それが条件付き相互情報量の条件の側に $𝑋 1, 𝑖$ が現れる理由である．

本書はこの主張を証明しない．時刻ごとにほどく段が，第6章定理 6.4.5 のように一度で済まないからである．中継入力が過去の観測の関数なので，時刻 $𝑖$ の項に時刻 $𝑖$ より前の量が入り込み，それを順に打ち消していく段（時刻をまたいで項がたたみ込まれるので，たたむ操作そのものを一本の補題にする必要がある）が要る．

形式化: relay_broadcast_cut_outer_bound (ソース)

形式化上の注記. 宣言は中継符号を引数にとるが，中継通信路は引数にとらない．出力の組 $(𝑌 𝑛, 𝑌 𝑛 1)$ は有限集合に値をとる任意の確率変数の組でよく，通信路との関わりは，借りた形が最後に置いた条件付き独立の仮定だけから来ている．借りた形が「各時刻の対 $(𝑌 𝑖, 𝑌 1, 𝑖)$ が入力の対に対して $𝑊$ が返す出力である」と書いたぶんは，宣言の側には現れない．そのぶん宣言は借りた形より広い場合を覆っている．

カットセット外界

系 14.8.6（カットセット外界）. $𝑀 \geq 2$ ， $𝑛 \geq 1$ とし， $𝑊$ を中継通信路（定義 14.8.1）， $(𝑀, 𝑐, 𝑟, 𝑑)$ を長さ $𝑛$ の中継符号（定義 14.8.2）とする． $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数とし， $𝑋 𝑖 : = 𝑐 (M s g) 𝑖$ ， $𝑋 1, 𝑖 : = 𝑟 𝑖 (𝑌 1, 0, \dots, 𝑌 1, 𝑖 - 1)$ とし， $(𝑌 𝑛, 𝑌 𝑛 1)$ を，各時刻の対 $(𝑌 𝑖, 𝑌 1, 𝑖)$ が入力の対 $(𝑋 𝑖, 𝑋 1, 𝑖)$ に対して $𝑊$ が返す出力であるような組とする． $𝑃 𝑒 : = P r [𝑑 (𝑌 𝑛) \neq M s g]$ ， $𝑍 𝑖 : = (𝑋 𝑖, 𝑋 1, 𝑖)$ ， $𝑍 𝑛 : = (𝑍 0, \dots, 𝑍 𝑛 - 1)$ とおく． $M s g \to 𝑍 𝑛 \to 𝑌 𝑛$ がマルコフ連鎖（定義 1.8.3）をなし， $𝑍 𝑛$ と $𝑌 𝑛$ が各時刻で記憶がなく（定義 6.4.4），かつ各時刻 $𝑖$ について対 $𝑍 𝑖$ を与えたとき対 $(𝑌 1, 𝑖, 𝑌 𝑖)$ が $(M s g, (𝑌 1, 𝑗, 𝑌 𝑗) 𝑗 < 𝑖)$ と条件付き独立であるとする． $𝐹 : = 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1)$ とおくと

l o g 𝑀 \leq m i n (𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; (𝑌 1, 𝑖, 𝑌 𝑖) ∣ 𝑋 1, 𝑖) + 𝐹, 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑍 𝑖; 𝑌 𝑖) + 𝐹)

である．

証明. 右の括弧の中の第 $2$ の量は定理 14.8.3 の右辺であり，仮定の前半二つがその定理の仮定そのものだから $l o g 𝑀$ はこれ以下である．第 $1$ の量は借りた ブロードキャストのカット の右辺であり，仮定の後半がその借用の仮定そのものだから $l o g 𝑀$ はこれ以下である． $l o g 𝑀$ が二つの量のどちらにも抑えられるので，小さいほうにも抑えられる． $◼$

形式化: relay_cutset_outer_bound (ソース)

系 14.8.6 が置いた三つの条件のうち，前の二つは命題 14.8.4 の仮定のもとで満たされる．いっぽう例 14.8.5 が示したとおり，中継符号であるというだけでは定義 6.4.4 のほうが満たされない．三つめは借りた ブロードキャストのカット が置いている条件で，これが中継符号についてどこまで成り立つかを本書は述べない．

だから系 14.8.6 は，命題 14.8.4 の条件を満たす通信路についての主張として読むのが安全である．そこでは前の二つが自動で片づくので，残るのは三つめだけになる．例 14.8.5 の通信路のようにその条件を満たさないものでは，系 14.8.6 の右辺をその通信路の上界として読むことはできない．条件を置かない一般の中継通信路について同じ形の上界が成り立つかどうかは，本書の範囲にない．

教科書でよく見るカットセット外界は，二つのカットの内側にある相互情報量を入力の同時分布について最大化した形で書かれる．ここでの二つのカットは時刻ごとの和のままである．入力分布についての最大化は，本書も形式化も行っていない．和を一文字あたりの量に直すには，時刻を一様に選ぶ変数をもう一段の補助変数として束ねる段が要り，そこまで進めて初めて「送り手と助け手の入力の同時分布を動かした最大値」という形になる．

二つのカットの読み方を確かめておく．多元接続のカットは，送り手と助け手が示し合わせて一人のように送ったとしても受け手が取り出せる量はこれだけだ，と言っている．助け手が実際には示し合わせられないことを無視しているので，抑えとしては甘い．ブロードキャストのカットは逆に，助け手の入力を教えてもらったうえで，送り手の出す情報が助け手と受け手の両方に届く量を測っている．助け手が受け取った情報をすべて無料で受け手に転送できるとしても，これだけしか出せない，という意味である．どちらのカットも，実際には成り立たない好条件を許してしまっているので，二つとも上界にしかならない．その小さいほうをとるのが系 14.8.6 である．

内側からの評価

本節は外側からの評価しか置いていない．内側からの評価，すなわち「このレートなら実際に送れる」という主張を本書は扱わない．中継の分野でよく使われる方式（助け手がメッセージを復号してから送り直すもの，復号せずに観測を圧縮して送るもの）はどれもランダム符号化の議論で，しかも助け手が送るものを時間的にずらして重ねる段を伴う．

本章がここまでに借りた情報理論の主張は，どれも本書が証明を載せないだけで形式化はされているものだった．中継の達成可能性はそうではなく，本書も扱わず，形式化もされていない．14.1 節で本章に一つだけあると断った例外がこれである．したがって本節の内容は，カットセット外界までである．

中継通信路の容量は一般には分かっていない．外界は系 14.8.6 が与えるが，それに一致する内界は，最大化まで進めた形であっても知られていない．分かっていないというのは，容量を与える式がまだ見つかっていないという意味であって，そういう式が存在しえないことが示されているわけではない．14.7 節が一般のブロードキャスト通信路について述べたのと同じ状況が，助け手が一人いるだけの，これ以上ないほど単純に見えるネットワークでも起きている．

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