6.4 逆定理

6.3 節は，レートが $𝐶 (𝑊)$ を下回ってさえいれば誤り確率をいくらでも小さくできることを示した．残るのは逆向きの問いである． $𝐶 (𝑊)$ を超えるレートではどうなるのか．言い換えれば，信頼できる通信ができるためにレートが満たさなければならない条件は何か．本節が示すのは $𝑅 \leq 𝐶 (𝑊)$ が必要だ，ということである．第2章が達成可能性（定理 2.3.2）と弱逆定理（定理 2.3.4）を対にして情報源符号化定理に至ったのと，同じ形の対をここで作る．

達成可能性の証明は符号を一つ作れば済んだが，逆定理はどんな符号を設計してもという全称の主張なので，構成では歯が立たない．使う道具は第2章の逆定理と同じ，ファノの不等式（定理 1.10.1）である．ただし今度は情報源のエントロピーではなく，メッセージの個数 $l o g 𝑀$ を左辺に置く．

論証は 4 歩でできている．(i) 一様なメッセージのもつ情報量 $l o g 𝑀$ を，ファノの不等式で「通信路が運んだぶん」と「誤りで説明されるぶん」に分ける（定理 6.4.1）．(ii) データ処理不等式で，復号器の手前にある通信路の入口と出口の相互情報量に移す（系 6.4.2）．ここまでは通信路に何の仮定も要らない．そこから先は二つの行き先がある．(iii) チェイン則で時刻ごとに分解する（定理 6.4.3）．記憶のなさを仮定しないので，記憶のある通信路にもそのまま当たる．ただしこれは本節の弱逆定理には使わない寄り道で，次の (iv) は (iii) を経由せず (ii) から直接出る．(iv) 記憶のなさを入れて，各時刻の相互情報量の和という扱いやすい形に落とす（定理 6.4.5）．最後にこれを容量で抑えて弱逆定理を得（系 6.4.8），6.3 節の達成可能性（系 6.3.8）と突き合わせて通信路符号化定理（定理 6.4.9）に至る．

以下， $𝑊$ を 6.1 節の通信路とし，長さ $𝑛$ のブロック通信路符号（定義 6.2.1）を扱う．メッセージを表す確率変数を $M s g$ ，その符号語を $𝑋 𝑛 = 𝑐 (M s g)$ ，通信路を通した出力を $𝑌 𝑛$ ，復号結果を $𝑑 (𝑌 𝑛)$ と書く． $𝑋 𝑖$ ， $𝑌 𝑖$ は第 $𝑖$ 成分， $𝑋 < 𝑖 : = (𝑋 0, \dots, 𝑋 𝑖 - 1)$ は先頭 $𝑖$ 文字である．メッセージが一様分布に従うとき， $P r [𝑑 (𝑌 𝑛) \neq M s g]$ は定義 6.2.1 の平均誤り確率 $¯ 𝑃 𝑒$ に一致する．メッセージごとの誤り確率を一様な重み $1 / 𝑀$ で平均したものだからである．

一様なメッセージを分ける

定理 6.4.1（単発逆定理）. $𝑀 \geq 2$ とし， $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数とする． $𝑌$ を有限集合に値をとる確率変数， $𝑔$ を $𝑌$ の値から ${1, \dots, 𝑀}$ への写像とし， $𝑃 𝑒 : = P r [𝑔 (𝑌) \neq M s g]$ とおく．このとき

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

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

証明. 一様分布のエントロピーは定義 1.1.1 から

𝐻 (M s g) = - 𝑀 \sum 𝑚 = 1 1 𝑀 l o g 1 𝑀 = l o g 𝑀

である．定理 1.3.4 のエントロピー表現を対 $(M s g, 𝑌)$ に当てると

𝐻 (M s g) = 𝐼 (M s g; 𝑌) + 𝐻 (M s g ∣ 𝑌)

となる．右辺の第 2 項に，対象を $M s g$ ，観測を $𝑌$ ，復号器を $𝑔$ としてファノの不等式（定理 1.10.1）を当てると $𝐻 (M s g ∣ 𝑌) \leq 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1)$ である．二つを合わせて主張を得る． $◼$

形式化: shannon_converse_single_shot (ソース)

左辺が誰のものかを見る. 第2章定理 2.3.4 では，左辺のブロックのエントロピー $𝑛 𝐻 (𝑋)$ が情報源だけで決まって動かせない量だった．こちらの左辺 $l o g 𝑀$ は逆に，符号を設計する側が決める量である．だから不等式の読み方も裏返る．あちらは「情報源が要求する量を符号語数が支えなければならない」だったが，こちらは「設計者が $𝑀$ を大きくとりたければ，それを支えるだけの相互情報量が要る」になる．右辺の後ろ 2 項は誤りで説明がつく分で，誤り確率を 0 に近づけるとどちらも消える．すると $l o g 𝑀$ をすべて $𝐼 (M s g; 𝑌)$ が支えなければならない．

形式化上の注記. 形式化のルートは本文と一段ずれる．本文はファノの不等式が復号器を引数にとる形（定理 1.10.1）をそのまま使ったが，形式化はまず復号結果で条件付けた形にファノの不等式を当て，そのあとデータ処理不等式（定理 1.8.2）で観測を $𝑌$ に戻す．到達する不等式は同じである．

形式化は出力の空間を有限とは仮定しないので，相互情報量が有限であるという前提が付く．本章は有限アルファベットだけを扱うので，これは自動的に満たされる．

復号器の手前へ移す

系 6.4.2. $𝑀 \geq 2$ とし， $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数とする． $X$ を有限集合， $𝑐 : {1, \dots, 𝑀} \to X$ を写像とし， $𝑋 : = 𝑐 (M s g)$ とおく． $𝑌$ を有限集合に値をとる確率変数， $𝑔$ を $𝑌$ の値から ${1, \dots, 𝑀}$ への写像とし， $𝑃 𝑒 : = P r [𝑔 (𝑌) \neq M s g]$ とおく． $M s g \to 𝑋 \to 𝑌$ がマルコフ連鎖（定義 1.8.3）をなすなら

l o g 𝑀 \leq 𝐼 (𝑋; 𝑌) + 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1) .

証明. 定理 1.8.4 を連鎖 $M s g \to 𝑋 \to 𝑌$ に当てると $𝐼 (M s g; 𝑌) \leq 𝐼 (𝑋; 𝑌)$ である．定理 6.4.1 の右辺の第 1 項をこれで置き換えればよい． $◼$

形式化: shannon_converse_single_shot_markov_encoder (ソース)

マルコフ連鎖の仮定がどこから来るのかを確かめておく．符号語 $𝑋 = 𝑐 (M s g)$ はメッセージの関数だから， $M s g$ を知れば $𝑋$ も決まる．しかし系 6.4.2 が要求しているのはその向きではなく， $𝑋$ を知ってしまえば出力 $𝑌$ が $M s g$ には直接よらないという向きである．通信路は符号語しか見ない，というのがその内容で，定義 6.1.1 の通信路を符号語に当てるかぎり自動的に満たされる．裏返せば，符号語を通さずにメッセージが出力へ漏れる経路があれば，この評価は使えない．

時刻ごとに分解する

定理 6.4.3. $𝑀 \geq 2$ ， $𝑛 \geq 1$ とし， $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数とする． $X$ を有限集合， $𝑐 : {1, \dots, 𝑀} \to X 𝑛$ を写像とし， $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1) : = 𝑐 (M s g)$ とおく． $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ を有限集合に値をとる確率変数の組， $𝑑$ を $𝑌 𝑛$ の値から ${1, \dots, 𝑀}$ への写像とし， $𝑃 𝑒 : = P r [𝑑 (𝑌 𝑛) \neq M s g]$ とおく． $M s g \to 𝑋 𝑛 \to 𝑌 𝑛$ がマルコフ連鎖（定義 1.8.3）をなすなら

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

ここで $𝑋 < 𝑖 : = (𝑋 0, \dots, 𝑋 𝑖 - 1)$ である．

証明. 定理 1.5.2 を，変数列 $𝑋 0, \dots, 𝑋 𝑛 - 1$ と，相手側の変数を $𝑌 𝑛$ として当てると

𝐼 (𝑋 𝑛; 𝑌 𝑛) = 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; 𝑌 𝑛 ∣ 𝑋 < 𝑖)

である．系 6.4.2 を $𝑋 \leftarrow 𝑋 𝑛$ ， $𝑌 \leftarrow 𝑌 𝑛$ ， $𝑔 \leftarrow 𝑑$ として使い，その右辺の第 1 項をこの和で置き換えればよい． $◼$

形式化: channel_coding_converse_general_chainRule (ソース)

定理 6.4.3 は通信路の記憶について何も仮定していない．積の形（定義 6.1.1）を満たさない通信路，つまり時刻をまたいで雑音が相関する通信路にもそのまま当たる．そのぶん右辺の項は扱いにくい． $𝐼 (𝑋 𝑖; 𝑌 𝑛 ∣ 𝑋 < 𝑖)$ は「それ以前の入力を知ったうえで，時刻 $𝑖$ の入力が出力ブロック全体について与える情報」であって，1 時刻分の量ではない．これを 1 時刻分に落とすところで，記憶のなさが初めて要る．

記憶のなさを入れる

定義 6.4.4（各時刻で記憶がない）. 確率変数の組 $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ が各時刻で記憶がない とは，すべての $𝑖$ について

(𝑋 \neq 𝑖, 𝑌 \neq 𝑖) \to 𝑋 𝑖 \to 𝑌 𝑖

がマルコフ連鎖（定義 1.8.3）をなすことをいう．ここで $𝑋 \neq 𝑖$ は $𝑋 𝑖$ 以外の入力をすべて並べた組， $𝑌 \neq 𝑖$ は $𝑌 𝑖$ 以外の出力をすべて並べた組である．

形式化: IsMemorylessChannel (ソース)

定義 6.1.1 は記憶のなさを，出力ブロックの条件付き分布が積に分かれるという通信路自身の性質として書いた．定義 6.4.4 が書いているのは，そこから出る別の顔である．すなわち，時刻 $𝑖$ の入力を知ってしまえば，時刻 $𝑖$ の出力は他の時刻の入出力について何も教えないということである．逆定理で要るのはこちらの形で，積の形のままでは相互情報量の評価に持ち込めない．積の形から定義 6.4.4が従うことは補題 6.4.6 で確かめる．

定理 6.4.5（記憶のない通信路の逆定理）. $𝑀 \geq 2$ ， $𝑛 \geq 1$ とし， $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数とする． $X$ を有限集合， $𝑐 : {1, \dots, 𝑀} \to X 𝑛$ を写像とし， $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1) : = 𝑐 (M s g)$ とおく． $𝑌 𝑛 = (𝑌 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) .

証明. 系 6.4.2 を $𝑋 \leftarrow 𝑋 𝑛$ ， $𝑌 \leftarrow 𝑌 𝑛$ ， $𝑔 \leftarrow 𝑑$ として使うと $l o g 𝑀 \leq 𝐼 (𝑋 𝑛; 𝑌 𝑛) + 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1)$ である．あとは第 1 項を $\sum 𝑖 𝐼 (𝑋 𝑖; 𝑌 𝑖)$ で抑えればよい．

そのために定理 1.8.5 を使う．あの定理が「記憶がない」として要求していたのは二つの条件だった． $𝑋 𝑛$ を与えたとき出力 $𝑌 0, \dots, 𝑌 𝑛 - 1$ が条件付き独立であること，および各 $𝑌 𝑖$ の条件付き分布が同じ時刻の入力 $𝑋 𝑖$ だけで決まることである．定義 6.4.4 からこの二つが出ることを見る．以下，条件付き確率を $P r [\cdot ∣ \cdot]$ と書き， $P r [𝑦 𝑖 ∣ 𝑥 𝑛]$ のように事象 ${𝑌 𝑖 = 𝑦 𝑖}$ ・ ${𝑋 𝑛 = 𝑥 𝑛}$ を値だけで表す（条件の側が正の確率をもつ点で考える）．定義 6.4.4 は， $𝑋 𝑖$ を与えたとき $𝑌 𝑖$ が $(𝑋 \neq 𝑖, 𝑌 \neq 𝑖)$ と条件付き独立であること，すなわち $P r [𝑦 𝑖 ∣ 𝑥 𝑛, 𝑦 \neq 𝑖] = P r [𝑦 𝑖 ∣ 𝑥 𝑖]$ を言っている．細かい条件での等式が全点で成り立つので，落とした変数について平均をとれば粗い条件での等式が従う．よって

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

がどちらも成り立つ．前者が第 2 の条件そのものである．後者を条件付き確率のチェイン則 $P r [𝑦 𝑛 ∣ 𝑥 𝑛] = \prod 𝑖 P r [𝑦 𝑖 ∣ 𝑥 𝑛, 𝑦 < 𝑖]$ に代入すると

P r [𝑦 𝑛 ∣ 𝑥 𝑛] = 𝑛 - 1 \prod 𝑖 = 0 P r [𝑦 𝑖 ∣ 𝑥 𝑖] = 𝑛 - 1 \prod 𝑖 = 0 P r [𝑦 𝑖 ∣ 𝑥 𝑛]

となり，これが第 1 の条件（ $𝑋 𝑛$ のもとでの出力の条件付き独立）である．

よって定理 1.8.5 より $𝐼 (𝑋 𝑛; 𝑌 𝑛) \leq \sum 𝑖 𝐼 (𝑋 𝑖; 𝑌 𝑖)$ であり，主張を得る． $◼$

形式化: channel_coding_converse_general_memoryless_pure (ソース)

形式化上の注記. 形式化も本文と同じく，系 6.4.2 から定理 1.8.5 へ渡る．定理 6.4.3 のチェイン則形から出発して各項を $𝐼 (𝑋 𝑖; 𝑌 𝑛 ∣ 𝑋 < 𝑖) \leq 𝐼 (𝑋 𝑖; 𝑌 𝑖)$ と時刻ごとに抑える道は，符号化写像を一般にとると途中で要る条件付き独立が成り立たないため通れない．同じ入力記号を二つの時刻に並べる符号化写像がその反例になる．

定理 6.4.5 が仮定に置いた定義 6.4.4 が，実際に通信路を使う場面では満たされていることを確かめておく．ここが積の形（定義 6.1.1）から記憶のなさの条件付き独立形へ渡る唯一の箇所であり，6.7 節も同じ橋をこの補題を通して渡る．

補題 6.4.6（積の形から各時刻の記憶のなさへ）. $𝑊$ を通信路（定義 6.1.1）， $𝑛 \geq 1$ とする． $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ を $X 𝑛$ に値をとる確率変数の組とし， $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ を， $𝑋 𝑛 = 𝑥 𝑛$ を与えたときの条件付き分布が $𝑊 𝑛 (\cdot ∣ 𝑥 𝑛) = \prod 𝑖 𝑊 (\cdot ∣ 𝑥 𝑖)$ である $Y 𝑛$ に値をとる確率変数の組とする．このとき， $𝑋 𝑛$ を与えたとき $𝑌 0, \dots, 𝑌 𝑛 - 1$ は条件付き独立であって各 $𝑌 𝑖$ の条件付き分布は $𝑊 (\cdot ∣ 𝑋 𝑖)$ であり， $𝑋 𝑛$ と $𝑌 𝑛$ は各時刻で記憶がなく（定義 6.4.4），さらに各 $𝑖$ について $𝑋 𝑖$ の分布を $𝑝 𝑖$ と書けば対 $(𝑋 𝑖, 𝑌 𝑖)$ の同時分布は $𝑝 𝑖 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ である．

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

条件付き独立と各時刻の条件付き分布. 仮定は $P r [𝑦 𝑛 ∣ 𝑥 𝑛] = \prod 𝑖 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖)$ そのものである．右辺は $𝑦 0, \dots, 𝑦 𝑛 - 1$ それぞれだけに依る因子の積だから， $𝑋 𝑛$ を与えたときの $𝑌 𝑛$ の条件付き分布は積に分かれており，これが条件付き独立である．第 $𝑖$ 成分の条件付き周辺分布は， $𝑗 \neq 𝑖$ の $𝑦 𝑗$ について和をとれば各因子の総和が 1 になるので， $𝑊 (\cdot ∣ 𝑥 𝑖)$ である．

各時刻で記憶がない. 積に分かれることから $P r [𝑦 𝑖 ∣ 𝑥 𝑛, 𝑦 \neq 𝑖] = 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖)$ である．右辺は $𝑥 𝑖$ だけの関数だから， $𝑥 𝑖$ を固定して $𝑥 \neq 𝑖$ について平均をとると $P r [𝑦 𝑖 ∣ 𝑥 𝑖] = 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖)$ を得る．二つを合わせて $P r [𝑦 𝑖 ∣ 𝑥 𝑛, 𝑦 \neq 𝑖] = P r [𝑦 𝑖 ∣ 𝑥 𝑖]$ であり，これは $𝑋 𝑖$ を与えたとき $𝑌 𝑖$ が $(𝑋 \neq 𝑖, 𝑌 \neq 𝑖)$ と条件付き独立だということ，すなわち定義 6.4.4 である．

対の同時分布は積の形になる. 条件付き周辺分布が $𝑊 (\cdot ∣ 𝑥 𝑖)$ であることから

P r [𝑋 𝑖 = 𝑥, 𝑌 𝑖 = 𝑦] = \sum 𝑥 𝑛 : 𝑥 𝑖 = 𝑥 P r [𝑋 𝑛 = 𝑥 𝑛] 𝑊 (𝑦 ∣ 𝑥) = 𝑝 𝑖 (𝑥) 𝑊 (𝑦 ∣ 𝑥)

である． $◻$

形式化上の注記. 補題 6.4.6 に対応する宣言は形式化されていない．補題 6.4.6 に付した証明が，この主張の保証のすべてである．形式化の側では，定理 6.4.5 に紐付けた宣言が定義 6.4.4 にあたる述語を仮定として受け取る形になっている．

弱逆定理

弱逆定理の証明には，ファノの不等式が残す二つの項が消えるという評価が要る．それだけを先に切り出しておく．

補題 6.4.7（補正項は消える）. $(𝑃 𝑛) 𝑛 \geq 1$ を $[0, 1]$ に値をとる実数列， $(𝑅 𝑛) 𝑛 \geq 1$ を上に有界な非負実数列とする． $𝑃 𝑛 \to 0$ ならば

𝐻 𝑏 (𝑃 𝑛) 𝑛 + 𝑃 𝑛 𝑅 𝑛 ⟶ 0 (𝑛 \to \infty)

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

証明. 第 1 項について．命題 1.1.4 より $𝐻 𝑏 (𝑃 𝑛) \geq 0$ であり，例 1.1.2 より $𝐻 𝑏 (𝑃 𝑛) \leq l o g 2 = 1$ である． $𝑛$ で割れば $0 \leq 𝐻 𝑏 (𝑃 𝑛) / 𝑛 \leq 1 / 𝑛$ であり，これは0 に収束する．

第 2 項について． $𝑅 𝑛 \leq 𝐵$ を満たす実数 $𝐵$ をとる． $𝑅 𝑛 \geq 0$ と $𝑃 𝑛 \geq 0$ から $0 \leq 𝑃 𝑛 𝑅 𝑛 \leq 𝑃 𝑛 𝐵$ であり， $𝑃 𝑛 \to 0$ よりこれも 0 に収束する．二つを足して主張を得る． $◻$

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

系 6.4.8（弱逆定理）. $𝑊$ を通信路（定義 6.1.1）とする．ブロック通信路符号の族 $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛) 𝑛 \geq 1$ が定義 6.2.2 の意味で達成可能なら，その達成レートは $𝐶 (𝑊)$ 以下である．すなわち $R (𝑊)$ のどの元も $𝐶 (𝑊)$ を超えない．

証明. 族を一つとり， $𝑅 𝑛 : = 1 𝑛 l o g 𝑀 𝑛$ とおく．定義 6.2.2 より $𝑃 (𝑛) 𝑒, m a x \to 0$ であり，レートの列は上に有界である． $𝑀 𝑛 \geq 1$ より $𝑅 𝑛 \geq 0$ でもある．

メッセージに一様分布を入れる. 定義 6.2.2 の達成可能性は最大誤り確率で書かれているので，メッセージにどんな分布を与えても平均誤り確率は $𝑃 (𝑛) 𝑒, m a x$ 以下である．そこで各 $𝑛$ について， $M s g$ が ${1, \dots, 𝑀 𝑛}$ 上の一様分布に従うとして議論する．これは符号に置く追加の仮定ではなく，評価のためにこちらが選ぶ分布である．このとき $𝑃 (𝑛) 𝑒 : = P r [𝑑 𝑛 (𝑌 𝑛) \neq M s g]$ は平均誤り確率に等しく， $𝑃 (𝑛) 𝑒 \leq 𝑃 (𝑛) 𝑒, m a x \to 0$ である．

$𝛿 𝑛 : = 𝐻 𝑏 (𝑃 (𝑛) 𝑒) / 𝑛 + 𝑃 (𝑛) 𝑒 𝑅 𝑛$ とおく．これは非負であり， $𝑃 (𝑛) 𝑒 \to 0$ と $(𝑅 𝑛)$ の有界性から，補題 6.4.7 より $𝛿 𝑛 \to 0$ である．以下，どの $𝑛$ でも $𝑅 𝑛 \leq 𝐶 (𝑊) + 𝛿 𝑛$ であることを示せばよい．

$𝑀 𝑛 = 1$ の項を片付ける. そのような $𝑛$ では $𝑅 𝑛 = 0$ であり，命題 6.1.6 より $0 \leq 𝐶 (𝑊)$ だから $𝑅 𝑛 \leq 𝐶 (𝑊) \leq 𝐶 (𝑊) + 𝛿 𝑛$ が成り立つ．残る $𝑛$ では $𝑀 𝑛 \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 𝐶 (𝑊)$ だから，和は $𝑛 𝐶 (𝑊)$ 以下である． $𝑀 𝑛 \geq 2$ より $l o g (𝑀 𝑛 - 1) \leq l o g 𝑀 𝑛 = 𝑛 𝑅 𝑛$ でもある． $𝑛$ で割ると

𝑅 𝑛 \leq 𝐶 (𝑊) + 𝐻 𝑏 (𝑃 (𝑛) 𝑒) 𝑛 + 𝑃 (𝑛) 𝑒 𝑅 𝑛 = 𝐶 (𝑊) + 𝛿 𝑛

を得る．

どの $𝑛$ でも $𝑅 𝑛 \leq 𝐶 (𝑊) + 𝛿 𝑛$ であり $𝛿 𝑛 \to 0$ だから，両辺で下極限をとって $l i m i n f 𝑛 𝑅 𝑛 \leq 𝐶 (𝑊)$ を得る． $◼$

形式化上の注記. 系 6.4.8 に対応する単独の宣言はない．定理 6.4.5 に紐付けた宣言と，和の各項を容量で抑える段の合成で得られる．後者にあたるのは mutualInfoOfChannel_toReal_le_capacity (InformationTheory/Shannon/BlockwiseChannel/MemorylessCapacity.lean) で，ファイルの中に閉じた補題である．

二つの補正項を見分ける. $𝐻 𝑏 (𝑃 (𝑛) 𝑒) / 𝑛$ のほうは「誤ったかどうか」の 1 ビット以下しかなく， $𝑛$ で割れば無条件に消える． $𝑃 (𝑛) 𝑒 l o g (𝑀 𝑛 - 1) / 𝑛$ のほうはそうではない． $l o g (𝑀 𝑛 - 1)$ は $𝑛$ とともに増える量（ほぼ $𝑛 𝑅 𝑛$ ）なので， $𝑛$ で割っても $𝑅 𝑛$ 程度にしか小さくならない．これが消えるのは $𝑃 (𝑛) 𝑒$ が 0 に向かうからであり，しかもそのためにはレートが上に有界であることが要る．補題 6.4.7 が有界性を仮定に置き，定義 6.2.2 がレートの列に上界を課していたのは，ここで効かせるためである．第2章定理 2.3.4 では同じ項が $l o g (| X | 𝑛 - 1) \leq 𝑛 l o g | X |$ とアルファベットの大きさで抑えられたので，この心配は要らなかった．符号のメッセージ数は設計者が決める量なので，上から抑える手が別に要る．

通信路符号化定理

達成可能性（系 6.3.8）と弱逆定理（系 6.4.8）がそろったので，本章の題目そのものを述べる．第2章が達成可能性と弱逆定理を情報源符号化定理（定理 2.3.6）にまとめたのと，同じ形の合わせ方である．

定理 6.4.9（通信路符号化定理）. $𝑊$ を通信路（定義 6.1.1）とする．このとき定義 6.2.2 の達成レートの集合 $R (𝑊)$ は空でなく，

s u p R (𝑊) = 𝐶 (𝑊)

である．

証明. $R (𝑊)$ は空でない. 各 $𝑛$ でメッセージ数 1 の符号をとる．符号語は 1 本で，復号器はつねに $1$ を返す．誤りの事象は空だから最大誤り確率は 0 であり，レートの列は $𝑅 𝑛 = 0$ で上に有界である．よってこの族は定義 6.2.2 の意味で達成可能で，その達成レートは $l i m i n f 𝑛 𝑅 𝑛 = 0$ である．すなわち $0 \in R (𝑊)$ である．

$s u p R (𝑊) \leq 𝐶 (𝑊)$ . 系 6.4.8 より $R (𝑊)$ のどの元も $𝐶 (𝑊)$ 以下だから， $𝐶 (𝑊)$ は $R (𝑊)$ の上界である．上限は上界のうち最小のものだから $s u p R (𝑊) \leq 𝐶 (𝑊)$ である．

$𝐶 (𝑊) \leq s u p R (𝑊)$ . 命題 6.1.6 より $𝐶 (𝑊) \geq 0$ なので， $𝐶 (𝑊) = 0$ か $𝐶 (𝑊) > 0$ かで場合は尽きている． $𝐶 (𝑊) = 0$ なら $0 \in R (𝑊)$ から $s u p R (𝑊) \geq 0 = 𝐶 (𝑊)$ である． $𝐶 (𝑊) > 0$ なら， $0 < 𝑅 < 𝐶 (𝑊)$ を満たす実数 $𝑅$ を任意にとると，系 6.3.8 より $𝑅 \in R (𝑊)$ であり $s u p R (𝑊) \geq 𝑅$ である． $𝑅$ は $𝐶 (𝑊)$ 未満の任意の正数だったから $s u p R (𝑊) \geq 𝐶 (𝑊)$ である．

二つを合わせて等号を得る． $◼$

形式化上の注記. 定理 6.4.9 に対応する単独の宣言はない．達成レートの集合そのものに対応する宣言が通信路の側には用意されていないので，両側を突き合わせるこの主張も形式化の外にある．片側ずつの機械検証は，達成可能性が定理 6.3.7 に，逆定理が定理 6.4.5 に紐付けた宣言まで及んでいる．

定理 6.4.9 は上限が達成されるかどうかを言っていない． $𝑅 = 𝐶 (𝑊)$ ちょうどのレートで最大誤り確率が 0 に収束する符号族があるかは，ここでは問わない．第2章定理 2.3.6 が下限の達成を問わなかったのと同じである．

二つの向きが $𝐶 (𝑊)$ を挟む. 定理 6.3.7 は $𝐶 (𝑊)$ 未満のどのレートでも符号が作れることを，系 6.4.8 は達成レートが $𝐶 (𝑊)$ を超えないことを言っている．前者は符号を一つ構成する存在の主張，後者はあらゆる符号にわたる全称の主張で，道具も証明の形も違う．この二つが $𝐶 (𝑊)$ を両側から挟むことで，6.1 節で最大化問題の値として定義したにすぎない $𝐶 (𝑊)$ が，通信路を 1 回使うあたりに運べる情報量という操作的な意味をもつ．

系 6.4.8 が $𝑃 (𝑛) 𝑒, m a x \to 0$ を仮定していることに注意しておきたい．言えているのは「レートが $𝐶 (𝑊)$ を超えるなら誤り確率は 0 に向かわない」までで，誤り確率がどこまで大きくなるかは何も言っていない．この仮定を置かず，誤り確率がむしろ 1 に向かうことを言う形は6.6 節で扱う．

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