6.3 ランダム符号化と達成可能性

前節までに，送るとはどういう操作かの定義（定義 6.2.1）と，辻褄の合う入出力の対を数える道具（定理 6.2.5〜定理 6.2.7）がそろった．残るのは符号を実際に作ることである． $𝑅 < 𝐶 (𝑊)$ のとき，誤り確率がいくらでも小さい符号がある．これを示すには，そういう符号を一つ見つければよい．

ところが，良い符号を名指しで書き下すのは今でも難しい．Shannon が使ったのは，その難しさを迂回する手である．符号語をでたらめに選び，そうして作った符号の全体について誤り確率を平均する．平均が小さければ，平均以下の符号が少なくとも一つはある．それがどれかは分からないが，あることは分かる．存在だけが要るので，それで足りる．本節はこの筋を，2 歩に分けてたどる．1 歩目で平均誤り確率の小さい符号を作り，2 歩目で誤りの大きいメッセージを捨てて最大誤り確率に直す．

本節も 6.2 節の設定と仮定を引き継ぐ．ただし補題 6.3.5 と定理 6.3.7 では入力分布 $𝑝$ を動かすので，そこでは仮定を主張の中に書き込む．

ランダム符号帳

定義 6.3.1（符号帳と結合典型復号器）. $𝑀 \geq 1$ ， $𝑛 \geq 1$ ， $𝜀 > 0$ とする．符号帳 とは，定義 6.2.1 の符号化写像 $𝑐 : {1, \dots, 𝑀} \to X 𝑛$ のことである（復号器を伴わない符号語の並び，という意味でこう呼ぶ）．符号帳 $𝑐$ に対する 結合典型復号器 を，受け取った $𝑦 𝑛$ に対し

𝑑 (𝑦 𝑛) : = {𝑚 (𝑐 (𝑚), 𝑦 𝑛) \in 𝐴 (𝑛) 𝜀 となる 𝑚 がただ一つのとき 1 それ以外のとき

で定める．符号帳とこの復号器を組にすれば，定義 6.2.1 のブロック通信路符号がひとつできる．

ランダム符号帳 とは， $𝑀 \times 𝑛$ 個の記号 $𝑐 (𝑚) 𝑖$ をすべて独立に入力分布 $𝑝$ から引いて作った符号帳のことをいう．すなわち符号帳 $𝑐$ が選ばれる確率は $\prod 𝑀 𝑚 = 1 \prod 𝑛 - 1 𝑖 = 0 𝑝 (𝑐 (𝑚) 𝑖)$ である．

復号規則は素朴である．受け取った $𝑦 𝑛$ と辻褄の合う符号語をひとつ探し，ちょうど一つならそれを答える．見つからないときも二つ以上あるときも，あきらめて $1$ を返す（何を返しても誤りには変わりないので，返す値に意味はない）．届いた出力にいちばん近い符号語を探すような，より賢い復号器も考えられるが，ここでは要らない．典型性という道具がすでに手元にあるので，それだけで足りる．

ランダム符号帳のほうが本節の要点である．符号語をでたらめに選ぶのは，良い符号の作り方としては乱暴に見える．しかし $𝑛$ が大きければ，独立に引いた $2 𝑛 𝑅$ 本の符号語は $X 𝑛$ の中でたがいに遠く散らばり，辻褄がぶつかることがめったにない．定理 6.2.7 が測っていたのは，まさにそのぶつかりの確率だった．

形式化: 符号帳 Codebook，結合典型復号器 jointTypicalDecoder，両者を符号に束ねるcodebookToCode (ソース)

1 歩目：平均誤り確率の小さい符号を作る

補題 6.3.2. $𝑀 \geq 1$ ， $𝑛 \geq 1$ ， $𝜀 > 0$ とし，符号帳 $𝑐$ と結合典型復号器（定義 6.3.1）からできるブロック通信路符号を考える．任意のメッセージ $𝑚 \in {1, \dots, 𝑀}$ について， $𝑚$ を送ったときの出力の分布を $P r 𝑚$ と書けば

𝑃 𝑒 (𝑚) \leq P r 𝑚 [(𝑐 (𝑚), 𝑌 𝑛) \notin 𝐴 (𝑛) 𝜀] + \sum 𝑚' \neq 𝑚 P r 𝑚 [(𝑐 (𝑚'), 𝑌 𝑛) \in 𝐴 (𝑛) 𝜀] .

証明. $𝑦 𝑛$ を受け取ったときに誤りが起きる，すなわち $𝑑 (𝑦 𝑛) \neq 𝑚$ だとする．もし $(𝑐 (𝑚), 𝑦 𝑛) \in 𝐴 (𝑛) 𝜀$ であって，かつ $𝑚' \neq 𝑚$ のどれについても $(𝑐 (𝑚'), 𝑦 𝑛) \notin 𝐴 (𝑛) 𝜀$ ならば，定義 6.3.1 の条件を満たす添字は $𝑚$ ただ一つなので $𝑑 (𝑦 𝑛) = 𝑚$ となり，誤りは起きない．したがって誤りが起きる $𝑦 𝑛$ は， $(𝑐 (𝑚), 𝑦 𝑛) \notin 𝐴 (𝑛) 𝜀$ であるか，または $(𝑐 (𝑚'), 𝑦 𝑛) \in 𝐴 (𝑛) 𝜀$ となる $𝑚' \neq 𝑚$ が存在するかのいずれかを満たす．前者の集合と，後者の $𝑚'$ ごとの集合との合併に誤りの事象が含まれるので，確率の劣加法性から主張の右辺で押さえられる． $◻$

形式化: errorProbAt_le_E1_plus_E2 (ソース)

不等式の二つの項は，それぞれ定理 6.2.6 と定理 6.2.7 が待ち構えている形をしている．第 1 項は「送ったものと受け取ったものの辻褄が合わない」確率，第 2 項は「無関係な符号語が偶然辻褄を合わせてしまう」確率である．符号帳を固定したままではどちらも評価できない． $𝑐 (𝑚)$ が具体的にどの系列かに依るからである．そこで符号帳について平均する．

以下，無作為なものは，符号帳をどう引くかと通信路の雑音の二つである． $𝔼 𝑐$ は符号帳についてだけとる平均， $P r 𝑚$ は符号帳を固定したもとで雑音についてとる確率であり，6.2 節から引き継いだ $(𝑋 𝑛, 𝑌 𝑛)$ についての $P r$ は，入力を $𝑝$ から引く段と雑音の段の両方を含む．

補題 6.3.3. $𝑀 \geq 1$ ， $𝑛 \geq 1$ ， $𝜀 > 0$ とする．ランダム符号帳について平均すると

𝔼 𝑐 [¯ 𝑃 𝑒 (𝑐)] \leq P r [(𝑋 𝑛, 𝑌 𝑛) \notin 𝐴 (𝑛) 𝜀] + (𝑀 - 1) 2 - 𝑛 (𝐼 (𝑝; 𝑊) - 3 𝜀) .

証明. 補題 6.3.2 を各 $𝑚$ について使い， $𝑚$ について平均し，さらに符号帳について平均する．和の順序を入れ替えれば，右辺の二種類の項をそれぞれ符号帳について平均したものの和になる．

第 1 項を見る．ランダム符号帳のもとで $𝑐 (𝑚)$ は入力分布 $𝑝$ から引いた i.i.d. 系列であり， $𝑌 𝑛$ はそれを通信路に通した出力である．つまり対 $(𝑐 (𝑚), 𝑌 𝑛)$ の分布は $(𝑋 𝑛, 𝑌 𝑛)$ の分布そのもので， $𝑚$ にも依らない．よってこの項の平均は $P r [(𝑋 𝑛, 𝑌 𝑛) \notin 𝐴 (𝑛) 𝜀]$ に等しい．

第 2 項に移る． $𝑚' \neq 𝑚$ とする．符号語は互いに独立に引かれているから， $𝑐 (𝑚')$ は $𝑐 (𝑚)$ とも，したがって $𝑌 𝑛$ とも独立である．しかも $𝑐 (𝑚')$ の分布は $𝑋 𝑛$ の分布に等しい．よって対 $(𝑐 (𝑚'), 𝑌 𝑛)$ は定理 6.2.7 の $(˜ 𝑋 𝑛, 𝑌 𝑛)$ そのものであり，この項の平均は $2 - 𝑛 (𝐼 (𝑝; 𝑊) - 3 𝜀)$ 以下である． $𝑚' \neq 𝑚$ の個数は $𝑀 - 1$ 個だから，和は $(𝑀 - 1) 2 - 𝑛 (𝐼 (𝑝; 𝑊) - 3 𝜀)$ 以下である． $◻$

形式化: random_codebook_average_le (ソース)

形式化上の注記. 「符号帳について平均する」一行は，形式化では符号帳の空間の上の積測度に対する和の入れ替えになる．本文が $𝑚$ と符号帳の二重の平均を一度に入れ替えているところが，あちらでは二つの補題に分かれている．

補題 6.3.4. $𝐵$ を実数とする．ランダム符号帳の平均が $𝔼 𝑐 [¯ 𝑃 𝑒 (𝑐)] \leq 𝐵$ を満たすなら， $¯ 𝑃 𝑒 (𝑐) \leq 𝐵$ を満たす符号帳 $𝑐$ が少なくとも一つ存在する．

証明. そのような符号帳がないとすると，すべての符号帳 $𝑐$ で $¯ 𝑃 𝑒 (𝑐) > 𝐵$ である．符号帳の選ばれる確率は非負で，全体にわたる総和は 1 だから，それを重みとする平均は

𝔼 𝑐 [¯ 𝑃 𝑒 (𝑐)] = \sum 𝑐 P r [𝑐] ¯ 𝑃 𝑒 (𝑐) > \sum 𝑐 P r [𝑐] \cdot 𝐵 = 𝐵

となって仮定に反する． $◻$

形式化: exists_codebook_le_avg (ソース)

補題 6.3.4 が確率的手法の全体である．平均を計算しただけで，名指しできない符号の存在が出てくる．実際に良い符号を手に入れたわけではない．というのも，どの符号帳が当たりかは，この議論からは何も分からないからである．

以下，レートは正とする． $𝑅 \leq 0$ は $⌈ 2 𝑛 𝑅 ⌉ = 1$ ，すなわちメッセージが1 通りしかない符号にあたり，運べる情報がないので考える意味がない．

補題 6.3.5. $X$ 上の分布 $𝑝$ が全点で正であり，通信路 $𝑊$ もすべての $(𝑥, 𝑦)$ で $𝑊 (𝑦 ∣ 𝑥) > 0$ を満たすとする． $0 < 𝑅 < 𝐼 (𝑝; 𝑊)$ と $𝜁 > 0$ に対し，ある $𝑁$ があって， $𝑛 \geq 𝑁$ ならばメッセージ数 $𝑀 \geq ⌈ 2 𝑛 𝑅 ⌉$ の長さ $𝑛$ のブロック通信路符号で，平均誤り確率が $¯ 𝑃 𝑒 < 𝜁$ を満たすものが存在する．

証明. $𝜀 : = (𝐼 (𝑝; 𝑊) - 𝑅) / 6 > 0$ とおき， $𝑀 : = ⌈ 2 𝑛 𝑅 ⌉$ としてランダム符号帳を考える．補題 6.3.3 と補題 6.3.4 より，

¯ 𝑃 𝑒 (𝑐) \leq P r [(𝑋 𝑛, 𝑌 𝑛) \notin 𝐴 (𝑛) 𝜀] + (𝑀 - 1) 2 - 𝑛 (𝐼 (𝑝; 𝑊) - 3 𝜀)

を満たす符号帳 $𝑐$ がとれる．右辺の二項がどちらも 0 に収束することを見ればよい．

第 1 項は定理 6.2.6 より 0 に収束する．第 2 項は，天井関数の定義から $𝑀 - 1 < 2 𝑛 𝑅$ なので

(𝑀 - 1) 2 - 𝑛 (𝐼 (𝑝; 𝑊) - 3 𝜀) < 2 - 𝑛 (𝐼 (𝑝; 𝑊) - 3 𝜀 - 𝑅)

であり， $𝜀$ の取り方から $𝐼 (𝑝; 𝑊) - 3 𝜀 - 𝑅 = (𝐼 (𝑝; 𝑊) - 𝑅) / 2 > 0$ だから，これも 0 に収束する．よって $𝑛$ を十分大きくとれば二項の和は $𝜁$ 未満にできる． $◻$

形式化: channel_coding_achievability (ソース)

2 歩目：平均から最大へ

補題 6.3.5 が与えるのは平均誤り確率の評価で，定義 6.2.2 が要求する最大誤り確率ではない．平均が小さくても，特定のメッセージだけがひどく誤っている可能性が残っている．これを直す手は乱暴だが確実である．誤りの大きいメッセージを，使うのをやめてしまうのである．

補題 6.3.6. 長さ $𝑛$ ，メッセージ数 $𝑀'$ のブロック通信路符号が $¯ 𝑃 𝑒 < 𝜁$ を満たすとする．このとき $𝑃 𝑒 (𝑚) \geq 2 𝜁$ となるメッセージは $𝑀' / 2$ 個未満である．とくに $𝑃 𝑒 (𝑚) < 2 𝜁$ となるメッセージを $⌈ 𝑀' / 2 ⌉$ 個選んで残せば，メッセージ数 $⌈ 𝑀' / 2 ⌉$ ，最大誤り確率 $2 𝜁$ 未満の符号が得られる．

証明. $𝑆 : = {𝑚 : 𝑃 𝑒 (𝑚) \geq 2 𝜁}$ とおく．誤り確率は非負だから

𝑀' ¯ 𝑃 𝑒 = 𝑀' \sum 𝑚 = 1 𝑃 𝑒 (𝑚) \geq \sum 𝑚 \in 𝑆 𝑃 𝑒 (𝑚) \geq | 𝑆 | \cdot 2 𝜁

であり， $¯ 𝑃 𝑒 < 𝜁$ と合わせて $| 𝑆 | < 𝑀' / 2$ を得る．よって補集合の要素数は $𝑀' / 2$ より大きく，整数だから $⌈ 𝑀' / 2 ⌉$ 以上である．

そこから $⌈ 𝑀' / 2 ⌉$ 個のメッセージを選び，その符号語だけを残して番号を $1, \dots, ⌈ 𝑀' / 2 ⌉$ に付け替える．復号器は元のものをそのまま使い，捨てたメッセージを指したときは $1$ を返すことにする．新しい番号 $𝑗$ （元の番号 $𝑚 𝑗$ ）に対する誤りの事象は， $𝑗 \neq 1$ なら元の誤りの事象と同じ集合であり， $𝑗 = 1$ ならその部分集合である．符号語も通信路も変えていないので出力の分布は元のままで，したがって新しい符号の誤り確率は元の $𝑃 𝑒 (𝑚 𝑗)$ 以下であり，選び方から $2 𝜁$ 未満である． $◻$

形式化: 捨てるメッセージの個数を数える段 errorProbAt_filter_card_bound，部分符号の構成Code.subcode と，その誤り確率が元を超えないこと Code.subcode_errorProbAt_le (ソース)

形式化上の注記. 補題 6.3.6 の全体に対応する単独の宣言はない．形式化はレートの帳尻合わせまで一緒にしたexists_subcode_maxError_lt_two_mul の形で持っていて，メッセージ数の下界と二つのレートの比較を仮定に置き，結論のメッセージ数も本文の $⌈ 𝑀' / 2 ⌉$ ではなく目標レートの側で書いている．本文の補題 6.3.6 は，errorProbAt_filter_card_bound とCode.subcode_errorProbAt_le の合成で得られる．

証明の要点は一つだけである．平均が小さいなら，平均の何倍もある項は少ない．これはMarkov の不等式そのもので，第3章 3.5 節でも同じ形が使われている．ここでは確率変数のかわりにメッセージごとの誤り確率を，確率のかわりに個数を数えているだけである．半分捨てるのでメッセージ数は半減するが， $l o g$ をとって $𝑛$ で割ればレートの目減りは $1 / 𝑛$ ビットにすぎず， $𝑛 \to \infty$ で消える．捨てる操作の代償がこれだけで済む，というのがこの 2 歩目の勘所である．

通信路符号化定理（達成可能性）

1 歩目と 2 歩目がそろったので，主定理を述べる．主張は通信路に何の仮定も置かないが，本文が証明を付けるのは $𝑊$ が全点で正の場合までである．仮定を外す段は証明の最後に道筋だけを示す．形式化のほうは仮定を置かない形に到達しているので，主張そのものは無条件の機械検証済みである．

定理 6.3.7（通信路符号化定理の達成可能性）. 通信路 $𝑊$ と $0 < 𝑅 < 𝐶 (𝑊)$ ， $𝜁 > 0$ をとる．このとき，ある $𝑁$ があって， $𝑛 \geq 𝑁$ ならばメッセージ数 $𝑀 \geq ⌈ 2 𝑛 𝑅 ⌉$ の長さ $𝑛$ のブロック通信路符号で，最大誤り確率が $𝑃 𝑒, m a x < 𝜁$ を満たすものが存在する．

証明. まず $𝑊$ がすべての $(𝑥, 𝑦)$ で $𝑊 (𝑦 ∣ 𝑥) > 0$ を満たす場合を示す．

入力分布を全点で正にとる. 定理 6.1.5 より $𝐼 (𝑝 *; 𝑊) = 𝐶 (𝑊)$ となる $𝑝 *$ がある． $X$ 上の一様分布を $𝑢$ とし， $𝛿 \in (0, 1)$ に対し $𝑝 𝛿 : = (1 - 𝛿) 𝑝 * + 𝛿 𝑢$ とおくと， $𝑝 𝛿$ は全点で正である．定理 6.1.5 より $𝐼 (\cdot; 𝑊)$ は入力分布について連続だから， $𝛿 \to 0$ のとき $𝑝 𝛿 \to 𝑝 *$ より $𝐼 (𝑝 𝛿; 𝑊) \to 𝐶 (𝑊) > 𝑅$ であり， $𝛿$ を十分小さくとれば $𝑅 < 𝐼 (𝑝 𝛿; 𝑊)$ にできる． $𝑊$ が全点で正なので，結合分布 $𝑝 𝛿 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ も全点で正である．

レートに余裕をとって 2 歩を踏む. $𝑅 < 𝑅' < 𝐼 (𝑝 𝛿; 𝑊)$ となる $𝑅'$ をとる．補題 6.3.5 を入力分布 $𝑝 𝛿$ ，レート $𝑅'$ ，目標 $𝜁 / 2$ に対して使うと，ある $𝑁 1$ があって， $𝑛 \geq 𝑁 1$ ならばメッセージ数 $𝑀' \geq ⌈ 2 𝑛 𝑅' ⌉$ で $¯ 𝑃 𝑒 < 𝜁 / 2$ を満たす符号がとれる．これに補題 6.3.6 を当てると，メッセージ数 $⌈ 𝑀' / 2 ⌉$ ，最大誤り確率 $𝜁$ 未満の符号が得られる．あとはメッセージ数が足りることを見ればよい． $𝑛 (𝑅' - 𝑅) \geq 1$ ならば

⌈ 𝑀' 2 ⌉ \geq 𝑀' 2 \geq 2 𝑛 𝑅' 2 = 2 𝑛 (𝑅' - 𝑅) - 1 \cdot 2 𝑛 𝑅 \geq 2 𝑛 𝑅

であり，左辺は整数だから $⌈ 2 𝑛 𝑅 ⌉$ 以上である．よって $𝑁$ としては， $𝑁 1$ と $⌈ 1 / (𝑅' - 𝑅) ⌉$ の大きいほうをとればよい．

「全点で正」の仮定を外す段は本書では証明しない. 一般の $𝑊$ に対しては， $𝜉 \in (0, 1)$ をとって通信路を $𝑊 𝜉 (𝑦 ∣ 𝑥) : = (1 - 𝜉) 𝑊 (𝑦 ∣ 𝑥) + 𝜉 / | Y |$ と摂動して全点で正にしてから上の議論を当て， $𝑊$ と $𝑊 𝜉$ の誤り確率の差を評価して戻す，という道筋をとる．差の評価は長さ $𝑛$ のブロックで $𝑛 𝜉$ の程度になるので， $𝜉$ を $𝑛$ とともに小さくしなければならず，そのためには補題 6.3.5 の $𝑁$ が $𝜉$ に依らずにとれることを確かめる必要がある．本節の評価を $𝜉$ について一様に取り直す作業になるので，本書ではここまでとする． $◼$

形式化: shannon_noisy_channel_coding_theorem_general (ソース)

形式化上の注記. 本文の証明と形式化の到達点は，最後の段だけ食い違う．形式化のshannon_noisy_channel_coding_theorem_general は通信路への仮定を持たない無条件の主張で，本文が証明を付けなかった摂動の段まで含んでいる．「全点で正」の仮定を残した中間段はshannon_noisy_channel_coding_theorem (InformationTheory/Shannon/ChannelCoding/ShannonTheorem.lean) にあり，本文の証明が到達したのはこちらである．

証明が使ったのは前節の三つだけである. 定理 6.2.6 が第 1 項を，定理 6.2.7 が第 2 項を消し，定理 6.2.5 は定理 6.2.7 の中で個数を数えていた．それ以外に効いたのは，平均から存在を取り出す補題 6.3.4 と，平均から最大へ渡す補題 6.3.6 という二つの初等的な議論だけである． $𝑅 < 𝐶 (𝑊)$ という条件が入ったのは 1 か所，補題 6.3.5 の第 2 項が 0 に収束するところで，そこでレートと相互情報量の差が指数の肩に現れた．

定理 6.3.7 が言っているのは，雑音のある通信路でも，レートを $𝐶 (𝑊)$ 未満に抑えるかぎり誤り確率はいくらでも小さくできる，ということである．誤りを減らそうとすればレートが 0 に落ちるという，6.1 節に書いた素朴な予想は外れている．繰り返しによる冗長さは1 記号ずつの多数決という形をとっていたが，ランダム符号化が入れる冗長さは長さ $𝑛$ のブロック全体に散らばっていて， $𝑛$ を大きくするほど効率がよくなる．

数で見る. 例 6.1.8 の二元対称通信路を反転確率 $0.1$ でとると，容量は約 $0.531$ ビットだった．ここで $𝑅 = 0.5$ ， $𝑛 = 100$ とすれば，符号語は $250$ 本（およそ $1.1 \times 1015$ 本）で，どれも長さ 100 ビットである．符号帳を表として書き下すと $250 \times 100$ ビット，すなわち約 14 ペタバイトになる．定理 6.3.7 が主張しているのはこの規模の表がひとつ存在するということであって，それを見つける手順ではない．補題 6.3.4 が「平均以下のものが少なくとも一つある」としか言っていないことが，そのまま効いている．

達成レートに言い換える

定理 6.3.7 は「どの目標値についても，十分長いところに目標を満たす符号がある」という形をしている．いっぽう定義 6.2.2 の達成レートは，1 本の符号族について述べられている．両者を突き合わせるには，定理 6.3.7 が長さごとに与える符号を 1 本の族に組み立て，そのレートの列をそろえておく必要がある．

系 6.3.8. $𝑊$ を通信路（定義 6.1.1）とし， $0 < 𝑅 < 𝐶 (𝑊)$ とする．このとき $𝑅$ は達成レートである．すなわち $𝑅 \in R (𝑊)$ ．

証明. 長さごとの符号を 1 本の族に貼り合わせる. 各 $𝑘 \geq 1$ について定理 6.3.7 を目標値 $1 / 𝑘$ に対して使い，得られる $𝑁$ を $𝑁 𝑘$ と書く． $𝑁' 𝑘 : = m a x (𝑁 1, \dots, 𝑁 𝑘, 𝑘)$ とおけば， $(𝑁' 𝑘)$ は広義単調増加で $𝑁' 𝑘 \geq 𝑘$ だから $𝑁' 𝑘 \to \infty$ である．よって $𝑛 \geq 𝑁' 1$ のとき ${𝑘 : 𝑁' 𝑘 \leq 𝑛}$ は空でない有限集合で，その最大値を $𝑘 (𝑛)$ と書ける． $𝑛 \geq 𝑁' 𝑘 (𝑛) \geq 𝑁 𝑘 (𝑛)$ だから，長さ $𝑛$ について定理 6.3.7 の符号がとれる．その符号はメッセージ数が $⌈ 2 𝑛 𝑅 ⌉$ 以上で，最大誤り確率が $1 / 𝑘 (𝑛)$ 未満である． $𝑛 < 𝑁' 1$ の有限個については，メッセージ数 1 の符号（復号器はつねに $1$ を返す）をとる．このとき誤りの事象は空なので，最大誤り確率は 0 である．

メッセージ数をちょうどに削る. $𝑛 \geq 𝑁' 1$ でとった符号のメッセージ数は $⌈ 2 𝑛 𝑅 ⌉$ 以上でしかないので，レートの列をそろえるために削る．メッセージを $⌈ 2 𝑛 𝑅 ⌉$ 個だけ選んで残し，番号を $1, \dots, ⌈ 2 𝑛 𝑅 ⌉$ に付け替える．符号語はそのまま，復号器は元のものを使い，捨てたメッセージを指したときは $1$ を返すことにする．新しい番号 $𝑗$ （元の番号 $𝑚 𝑗$ ）に対する誤りの事象は， $𝑗 \neq 1$ なら元の誤りの事象と同じ集合であり， $𝑗 = 1$ ならその部分集合である．符号語も通信路も変えていないので出力の分布は元のままで，したがって最大誤り確率は増えない．以下， $𝑀 𝑛 : = ⌈ 2 𝑛 𝑅 ⌉$ （ $𝑛 \geq 𝑁' 1$ ）， $𝑀 𝑛 : = 1$ （ $𝑛 < 𝑁' 1$ ）とする．

誤り確率とレートの極限をとる. 最大誤り確率を見る． $𝜁 > 0$ をとり， $1 / 𝑘 < 𝜁$ となる $𝑘$ を選ぶと， $𝑛 \geq 𝑁' 𝑘$ では $𝑘 (𝑛) \geq 𝑘$ だから最大誤り確率は $1 / 𝑘 (𝑛) \leq 1 / 𝑘$ 未満であり， $𝜁$ 未満である．よって $𝑃 (𝑛) 𝑒, m a x \to 0$ である．次にレートを見る． $𝑅 > 0$ と $𝑛 \geq 1$ より $2 𝑛 𝑅 \geq 1$ だから

2 𝑛 𝑅 \leq ⌈ 2 𝑛 𝑅 ⌉ < 2 𝑛 𝑅 + 1 \leq 2 \cdot 2 𝑛 𝑅

であり， $l o g$ をとって $𝑛$ で割ると $𝑛 \geq 𝑁' 1$ について $𝑅 \leq 𝑅 𝑛 < 𝑅 + 1 / 𝑛$ を得る．とくにレートの列は上に有界で， $𝑛 \to \infty$ で $𝑅$ に収束する．残りの $𝑛$ は有限個で $𝑅 𝑛 = 0$ だから，上に有界であることも下極限の値も変わらない．よってこの族は定義 6.2.2 の意味で達成可能で，その達成レートは $l i m i n f 𝑛 𝑅 𝑛 = 𝑅$ である． $◼$

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

逆向きの主張，つまり $𝐶 (𝑊)$ を超えるレートでは誤り確率を 0 にできないことについては，まだ何も言えていない．系 6.3.8 は $R (𝑊)$ が $𝐶 (𝑊)$ 未満の正のレートをすべて含むことを示しただけで， $R (𝑊)$ の上限がちょうど $𝐶 (𝑊)$ であるためには，どんな符号を設計しても $𝐶 (𝑊)$ を超えられないという全称の主張が要る．それは 6.4 節で与える．第2章で達成可能性と逆定理が別の道具を要したのと同じ構図で，その道具はふたたびファノの不等式（定理 1.10.1）である．

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