6.6 強逆定理

6.4 節の弱逆定理（系 6.4.8）が言えたのは，誤り確率を 0 に近づけられるレートは $𝐶 (𝑊)$ 以下だ，ということまでだった． $𝐶 (𝑊)$ を超えるレートで何が起きるかは，そこでは何も言っていない．誤り確率が 0 に向かわないことだけは分かるが， $0.01$ のあたりで止まるのか， $1 / 2$ に落ち着くのか，それとも 1 まで上がりきるのか．本節が示すのは最後の答えである．すなわち，レートが $𝐶 (𝑊)$ を超えれば，どんな符号を設計しても平均誤り確率は 1 に向かう．ほぼ必ず誤る，というところまで悪くなる． $𝐶 (𝑊)$ を境に事情が完全に切り替わり，中間の振る舞いが起きる余地はない．

道具立ては 6.4 節とまったく違う．先に地図を描いておく．

塊 1 は容量を達成する入力分布の見分け方である（補題 6.6.1〜例 6.6.5）．定理 6.1.5 は最大値が達成されることを示したが，どの分布が達成するのかは言っていなかった．そこを埋める．本節がこれを必要とするのは見かけよりも切実な理由による．塊 2 で導入する情報密度という量の平均を押さえたいのだが，その平均は符号語ごとに現れる．符号語は設計者が勝手に選ぶものだから， $𝑝 *$ から引いたものだとは仮定できない．どの入力記号を並べた符号語についても一様に効く上界が要る．塊 1 が与えるのはその一様な上界である．

塊 2 は情報密度という量と，それを使った単発の評価である（定義 6.6.6〜定理 6.6.9）．相互情報量は平均をとってしまった量だが，誤り確率を評価するには平均する前の量，つまり出力語 1 本ごとの量が要る．塊 2 は，ブロック長も誤り確率の極限も出てこない，1 つの符号に対する不等式だけでできている．

塊 3 で二つを合わせる（補題 6.6.10〜系 6.6.12）．塊 1 の一様な上界で情報密度の平均を $𝑛 𝐶 (𝑊)$ で抑え，レートが $𝐶 (𝑊)$ を超えていれば塊 2 のしきい値を平均から $𝑛$ に比例して離してとれる．離れた側の確率が 0 に向かうことを Chebyshev の不等式で言う．

以下， $𝑊$ は 6.1 節の通信路， $X$ と $Y$ は有限アルファベット， $𝜑 (𝑡) = - 𝑡 l o g 𝑡$ は 1.1 節の関数， $𝐷 (\cdot ‖ \cdot)$ は 1.6 節の相対エントロピーである．

容量を達成する入力分布

最大化する点を見分ける道具は微分である． $𝑝 *$ が最大化子なら，そこから他の点へ動かしても値は増えない．だから動かす向きに沿った微分は $0$ 以下でなければならない．これが唯一のアイデアで，あとは何を「動かす向き」にとるかである．ここで効くのは，入力分布の集合が確率単体という平らな集合だという事実である． $𝑝 *$ から入力記号 $𝑎$ の点質量へ向かってまっすぐ動けば，途中の点はすべて入力分布のままである．この線分に沿った右微分をとると，式が読みやすい形にほどける．

有限和の項別微分と片側微分を借りる. 借りるのは次の三つである．有限個の微分可能な関数の和は微分可能で，導関数は各項の導関数の和であること，微分可能な関数の合成もまた微分可能で，その導関数が内側と外側の導関数の積になること，そして区間の端点では片側の微分だけを問うてよいことである．当てる相手は， $𝑡 \in [0, 1]$ に対する $𝑡 \mapsto 𝜑 ((1 - 𝑡) 𝑞 (𝑦) + 𝑡 𝑊 (𝑦 ∣ 𝑎))$ の有限和と，その $𝑡 = 0$ における右微分である（ $𝑞 (𝑦) > 0$ でなければ $𝜑$ が $𝑡 = 0$ で微分可能にならないので，この点は仮定に書く）．この借用に依存するのは補題 6.6.1 と命題 6.6.4 の二つで，以降はその結論だけを使う．本書はこの三つを証明しないが，形式化されていないわけではない．どれも Mathlib にある無条件の機械検証済みの定理として形式化されている．

補題 6.6.1. $𝑊$ を通信路， $𝑝$ を $X$ 上の分布とし，その出力分布 $𝑞$ がすべての $𝑦 \in Y$ で $𝑞 (𝑦) > 0$ を満たすとする．入力記号 $𝑎 \in X$ を一つ固定し， $𝑎$ に全確率を置く分布を $𝟏 𝑎$ と書いて， $𝑡 \in [0, 1]$ に対し $𝑝 𝑡 : = (1 - 𝑡) 𝑝 + 𝑡 𝟏 𝑎$ とおく．このとき $𝑡 \mapsto 𝐼 (𝑝 𝑡; 𝑊)$ は $𝑡 = 0$ で右微分可能で，

l i m 𝑡 ↓ 0 𝐼 (𝑝 𝑡; 𝑊) - 𝐼 (𝑝; 𝑊) 𝑡 = 𝐷 (𝑊 (\cdot ∣ 𝑎) ∥ 𝑞) - 𝐼 (𝑝; 𝑊)

である．

証明. 各 $𝑡 \in [0, 1]$ で $𝑝 𝑡$ は非負であり $\sum 𝑥 𝑝 𝑡 (𝑥) = 1$ だから， $𝑝 𝑡$ は $X$ 上の分布である． $(𝑋 𝑡, 𝑌 𝑡)$ を結合分布 $𝑝 𝑡 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ に従う対とすると，命題 6.1.3 より $𝐼 (𝑝 𝑡; 𝑊) = 𝐻 (𝑌 𝑡) - 𝐻 (𝑌 𝑡 ∣ 𝑋 𝑡)$ である．二つの項を $𝑡$ の関数として別々に見る．

条件付きの項は $𝑡$ の 1 次式である. 各 $𝑥$ について $ℎ (𝑥) : = \sum 𝑦 𝜑 (𝑊 (𝑦 ∣ 𝑥))$ とおくと，定義 1.2.2 より $𝐻 (𝑌 𝑡 ∣ 𝑋 𝑡) = \sum 𝑥 𝑝 𝑡 (𝑥) ℎ (𝑥)$ である． $𝑝 𝑡$ は $𝑡$ の 1 次式だから，この項も $𝑡$ の 1 次式であり，その導関数は

ℎ (𝑎) - \sum 𝑥 𝑝 (𝑥) ℎ (𝑥) = ℎ (𝑎) - 𝐻 (𝑌 ∣ 𝑋)

である．ここで $(𝑋, 𝑌)$ は結合分布 $𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ に従う対とした．

出力の項に項別微分を当てる. 定義 6.1.1 より $𝑝 𝑡$ の出力分布は $𝑞 𝑡 (𝑦) = (1 - 𝑡) 𝑞 (𝑦) + 𝑡 𝑊 (𝑦 ∣ 𝑎)$ であり，定義 1.1.1 より $𝐻 (𝑌 𝑡) = \sum 𝑦 𝜑 (𝑞 𝑡 (𝑦))$ である． $𝑞 (𝑦) > 0$ だから $𝜑$ は $𝑞 (𝑦)$ の近傍で微分可能で， $𝜑' (𝑢) = - l o g 𝑢 - l o g 𝑒$ である．借用した項別微分・合成関数の微分・片側微分により， $𝑡 = 0$ での右微分は

\sum 𝑦 𝜑' (𝑞 (𝑦)) (𝑊 (𝑦 ∣ 𝑎) - 𝑞 (𝑦))

に等しい． $𝑊 (\cdot ∣ 𝑎)$ も $𝑞$ も分布だから $\sum 𝑦 (𝑊 (𝑦 ∣ 𝑎) - 𝑞 (𝑦)) = 0$ であり， $𝜑'$ のうち定数 $- l o g 𝑒$ の寄与は消える．残るのは

\sum 𝑦 (𝑊 (𝑦 ∣ 𝑎) - 𝑞 (𝑦)) (- l o g 𝑞 (𝑦)) = - \sum 𝑦 𝑊 (𝑦 ∣ 𝑎) l o g 𝑞 (𝑦) - 𝐻 (𝑌)

である．

二つの導関数の差が求める右微分だから，それは

(- \sum 𝑦 𝑊 (𝑦 ∣ 𝑎) l o g 𝑞 (𝑦) - 𝐻 (𝑌)) - (ℎ (𝑎) - 𝐻 (𝑌 ∣ 𝑋))

に等しい． $- ℎ (𝑎) = \sum 𝑦 𝑊 (𝑦 ∣ 𝑎) l o g 𝑊 (𝑦 ∣ 𝑎)$ だから， $𝑞$ を含む項と $- ℎ (𝑎)$ を合わせると

\sum 𝑦 𝑊 (𝑦 ∣ 𝑎) l o g 𝑊 (𝑦 ∣ 𝑎) 𝑞 (𝑦) = 𝐷 (𝑊 (\cdot ∣ 𝑎) ∥ 𝑞)

になる（ $𝑊 (𝑦 ∣ 𝑎) = 0$ の項は $𝜑 (0) = 0$ と 1.6 節の約束により，どちらの和にも寄与しない）．残る $- 𝐻 (𝑌) + 𝐻 (𝑌 ∣ 𝑋)$ は命題 6.1.3 より $- 𝐼 (𝑝; 𝑊)$ である． $◻$

形式化: mutualInfo_segment_hasDerivAt (ソース)

右辺の形が本節を動かす． $𝐷 (𝑊 (\cdot ∣ 𝑎) ‖ 𝑞)$ は「入力 $𝑎$ を知っている人の見込みと，入力を知らない人の見込みとの隔たり」である．それが現在の平均 $𝐼 (𝑝; 𝑊)$ より大きければ， $𝑎$ に重みを移すと $𝐼$ は増える．逆に小さければ減る．すなわちこの右微分は，入力記号 $𝑎$ が平均より得か損かを測っている．最大化子ではどの記号も得ではありえない，というのが次の命題である．

命題 6.6.2（容量達成条件）. $𝑊$ を通信路とし， $𝑝 *$ を $𝐼 (\cdot; 𝑊)$ を最大にする入力分布（定理 6.1.5）， $𝑞 *$ をその出力分布とする． $𝑞 *$ がすべての $𝑦 \in Y$ で $𝑞 * (𝑦) > 0$ を満たすなら，すべての $𝑎 \in X$ について

𝐷 (𝑊 (\cdot ∣ 𝑎) ∥ 𝑞 *) \leq 𝐶 (𝑊)

が成り立つ．

証明. $𝑎 \in X$ を固定し， $𝑡 \in [0, 1]$ に対し $𝑝 * 𝑡 : = (1 - 𝑡) 𝑝 * + 𝑡 𝟏 𝑎$ とおく．補題 6.6.1 の証明の最初に見たとおり $𝑝 * 𝑡$ は入力分布だから，定義 6.1.4 より $𝐼 (𝑝 * 𝑡; 𝑊) \leq 𝐶 (𝑊)$ である．いっぽう $𝑝 * 0 = 𝑝 *$ であり，定理 6.1.5 より $𝐼 (𝑝 *; 𝑊) = 𝐶 (𝑊)$ であるから， $𝑡 \in (0, 1]$ に対して

𝐼 (𝑝 * 𝑡; 𝑊) - 𝐼 (𝑝 *; 𝑊) 𝑡 \leq 0

が成り立つ． $𝑡 ↓ 0$ とすると，極限も $0$ 以下である．補題 6.6.1 よりこの極限は $𝐷 (𝑊 (\cdot ∣ 𝑎) ‖ 𝑞 *) - 𝐼 (𝑝 *; 𝑊)$ に等しく， $𝐼 (𝑝 *; 𝑊) = 𝐶 (𝑊)$ だから主張を得る． $◼$

形式化: klDiv_channel_le_capacity (ソース)

系 6.6.3. $𝑊$ を通信路とし， $𝑝 *$ を $𝐼 (\cdot; 𝑊)$ を最大にする入力分布（定理 6.1.5）， $𝑞 *$ をその出力分布とする． $𝑞 *$ がすべての $𝑦 \in Y$ で $𝑞 * (𝑦) > 0$ を満たすなら， $𝑝 * (𝑎) > 0$ を満たすすべての $𝑎 \in X$ について

𝐷 (𝑊 (\cdot ∣ 𝑎) ∥ 𝑞 *) = 𝐶 (𝑊)

が成り立つ．

証明. 定義 6.1.2 の二重和を $𝑥$ ごとにまとめると

𝐼 (𝑝 *; 𝑊) = \sum 𝑥 𝑝 * (𝑥) \sum 𝑦 𝑊 (𝑦 ∣ 𝑥) l o g 𝑊 (𝑦 ∣ 𝑥) 𝑞 * (𝑦) = \sum 𝑥 𝑝 * (𝑥) 𝐷 (𝑊 (\cdot ∣ 𝑥) ∥ 𝑞 *)

であり，内側の和が相対エントロピーそのものであることは 1.6 節の定義による．定理 6.1.5 より左辺は $𝐶 (𝑊)$ である．

いま $𝑝 * (𝑎 0) > 0$ を満たすある $𝑎 0$ で $𝐷 (𝑊 (\cdot ∣ 𝑎 0) ‖ 𝑞 *) < 𝐶 (𝑊)$ だとする．命題 6.6.2 より他のすべての $𝑥$ で $𝐷 (𝑊 (\cdot ∣ 𝑥) ‖ 𝑞 *) \leq 𝐶 (𝑊)$ だから， $𝑝 *$ が非負で総和 1 であることと合わせて

𝐶 (𝑊) = \sum 𝑥 𝑝 * (𝑥) 𝐷 (𝑊 (\cdot ∣ 𝑥) ∥ 𝑞 *) < \sum 𝑥 𝑝 * (𝑥) 𝐶 (𝑊) = 𝐶 (𝑊)

となって矛盾する．よってそのような $𝑎 0$ はない． $◼$

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

$𝑞 *$ からの隔たりで読む. 命題 6.6.2 と系 6.6.3 を合わせると，容量とは何かの別の読み方が出てくる． $𝑞 *$ から見ると，どの入力記号 $𝑎$ の出力分布 $𝑊 (\cdot ∣ 𝑎)$ も $𝑞 *$ から $𝐶 (𝑊)$ 以内の隔たりにあり，しかも実際に使われる記号（ $𝑝 *$ が正の重みを置く記号）はちょうど $𝐶 (𝑊)$ の隔たりにある．すなわち $𝑞 *$ は，実際に使う入力記号のどれからも等しい隔たりにあり，使わない記号もそれより遠くはない出力分布である．容量とは，そういう出力分布を許す隔たりの値だ，と読める．定義 6.1.4 が最大化問題の値としか言っていなかったものに，これで幾何的な姿がついた．

使い方を確かめておく．候補の入力分布 $𝑝$ を持ってきたら，その出力分布 $𝑞$ に対して $𝐷 (𝑊 (\cdot ∣ 𝑎) ‖ 𝑞)$ をすべての $𝑎$ について計算すればよい． $𝑝$ が最大化子なら，系 6.6.3 よりこれらは $𝑝 (𝑎) > 0$ となる $𝑎$ の上で共通の値をとり，命題 6.6.2 よりどの $𝑎$ もその値を超えない．二つのどちらかが破れれば， $𝑝$ は最大化子ではない．この二つが成り立てば $𝑝$ は最大化子であり，共通の値が $𝐶 (𝑊)$ である，という逆向きの主張も正しいが，本書では証明せず，形式化もされていない．以降のどの証明も逆向きは使わないので，認めないまま読み進めてよい．

$𝑞 *$ が全点で正だという仮定は，命題 6.6.2 と系 6.6.3 が置いたものであり，補題 6.6.10以降の主張にも付いて回る（塊 2 の主張は持たない．相手にするのが 1 つの符号だけだからである）． $𝜑$ は $0$ で微分可能でないから，これがないと補題 6.6.1 の右微分が意味をもたず，命題 6.6.2 の証明が通らない．どの入力からも正の確率で届かない出力記号は，最初から $Y$ に入れる理由がないので落としてよい．落としてもなお $𝑞 * (𝑦) = 0$ となる $𝑦$ が残るのではないか，という心配は要らない．最大化子については，この仮定は実質的に無条件だからである．

命題 6.6.4（最大化子の出力分布は全点で正）. $𝑊$ を通信路とし， $𝑝 *$ を $𝐼 (\cdot; 𝑊)$ を最大にする入力分布（定理 6.1.5）， $𝑞 *$ をその出力分布とする． $𝑞 * (𝑦 0) = 0$ を満たす $𝑦 0 \in Y$ があれば，すべての $𝑎 \in X$ について $𝑊 (𝑦 0 ∣ 𝑎) = 0$ である．

証明. 対偶を示す． $𝑦 0 \in Y$ と $𝑎 \in X$ が $𝑊 (𝑦 0 ∣ 𝑎) > 0$ を満たすとし， $𝑞 * (𝑦 0) > 0$ を導く．背理法で $𝑞 * (𝑦 0) = 0$ とする．定義 6.1.1 より $𝑞 * (𝑦 0) = \sum 𝑥 𝑝 * (𝑥) 𝑊 (𝑦 0 ∣ 𝑥)$ は非負項の和だから，各項が 0 である．とくに $𝑝 * (𝑎) 𝑊 (𝑦 0 ∣ 𝑎) = 0$ であり， $𝑊 (𝑦 0 ∣ 𝑎) > 0$ から $𝑝 * (𝑎) = 0$ を得る．

$𝑎$ へ向かって動かす. $𝑎$ に全確率を置く分布を $𝟏 𝑎$ と書き， $𝑡 \in [0, 1]$ に対し $𝑝 𝑡 : = (1 - 𝑡) 𝑝 * + 𝑡 𝟏 𝑎$ とおく． $𝑝 𝑡$ は非負で総和が 1 だから入力分布であり，定義 6.1.1 よりその出力分布は $𝑞 𝑡 (𝑦) = (1 - 𝑡) 𝑞 * (𝑦) + 𝑡 𝑊 (𝑦 ∣ 𝑎)$ である． $(𝑋 𝑡, 𝑌 𝑡)$ を結合分布 $𝑝 𝑡 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ に従う対とすると，命題 6.1.3 より $𝐼 (𝑝 𝑡; 𝑊) = 𝐻 (𝑌 𝑡) - 𝐻 (𝑌 𝑡 ∣ 𝑋 𝑡)$ である．

条件付きの項の変化は $𝑡$ に比例する. 各 $𝑥$ について $ℎ (𝑥) : = \sum 𝑦 𝜑 (𝑊 (𝑦 ∣ 𝑥))$ とおくと，定義 1.2.2 より $𝐻 (𝑌 𝑡 ∣ 𝑋 𝑡) = \sum 𝑥 𝑝 𝑡 (𝑥) ℎ (𝑥)$ である． $𝑝 𝑡$ は $𝑡$ の 1 次式だから

𝐻 (𝑌 𝑡 ∣ 𝑋 𝑡) - 𝐻 (𝑌 0 ∣ 𝑋 0) = 𝑡 (ℎ (𝑎) - \sum 𝑥 𝑝 * (𝑥) ℎ (𝑥))

であり，括弧の中は $𝑡$ によらない実数である．これを $𝐾$ と書く．

出力の項は $𝑡 l o g (1 / 𝑡)$ の速さで増える. 定義 1.1.1 より $𝐻 (𝑌 𝑡) = \sum 𝑦 𝜑 (𝑞 𝑡 (𝑦))$ である．和を $𝑞 * (𝑦) = 0$ の $𝑦$ と $𝑞 * (𝑦) > 0$ の $𝑦$ に分ける．

$𝑞 * (𝑦) = 0$ の $𝑦$ では $𝑞 𝑡 (𝑦) = 𝑡 𝑊 (𝑦 ∣ 𝑎)$ である． $0 \leq 𝑢 \leq 1$ なら $l o g 𝑢 \leq 0$ だから $𝜑 (𝑢) = - 𝑢 l o g 𝑢 \geq 0$ であり， $𝜑 (𝑞 * (𝑦)) = 𝜑 (0) = 0$ と合わせて，これらの $𝑦$ の寄与は非負である．とくに $𝑦 = 𝑦 0$ の寄与は

𝜑 (𝑡 𝑊 (𝑦 0 ∣ 𝑎)) = 𝑡 𝑊 (𝑦 0 ∣ 𝑎) l o g 1 𝑡 - 𝑡 𝑊 (𝑦 0 ∣ 𝑎) l o g 𝑊 (𝑦 0 ∣ 𝑎)

である． $𝑞 * (𝑦) > 0$ の $𝑦$ では $𝜑$ が $𝑞 * (𝑦)$ の近傍で微分可能だから，借用した合成関数の微分・片側微分により $(𝜑 (𝑞 𝑡 (𝑦)) - 𝜑 (𝑞 * (𝑦))) / 𝑡$ は $𝑡 ↓ 0$ で有限の値に収束する．収束する量はある $𝑡 1 > 0$ をとれば $0 < 𝑡 \leq 𝑡 1$ で有界だから，これらの $𝑦$ の寄与の総和は $- 𝐾' 𝑡$ 以上である（ $𝐾'$ は $𝑡$ によらない実数）．

$𝑡$ を小さくとる. 三つを合わせると， $0 < 𝑡 \leq 𝑡 1$ に対して

𝐼 (𝑝 𝑡; 𝑊) - 𝐼 (𝑝 *; 𝑊) \geq 𝑡 (𝑊 (𝑦 0 ∣ 𝑎) l o g 1 𝑡 - 𝐾 ″)

となる（ $𝐾 ″$ は $𝐾$ ， $𝐾'$ ， $𝑊 (𝑦 0 ∣ 𝑎) l o g 𝑊 (𝑦 0 ∣ 𝑎)$ から決まる， $𝑡$ によらない実数）． $𝑊 (𝑦 0 ∣ 𝑎) > 0$ であり $𝑡 ↓ 0$ で $l o g (1 / 𝑡) \to \infty$ だから， $𝑡$ を十分小さくとれば右辺は正になる．すると $𝐼 (𝑝 𝑡; 𝑊) > 𝐼 (𝑝 *; 𝑊) = 𝐶 (𝑊)$ となり， $𝑝 𝑡$ が入力分布であることと定義 6.1.4 に反する．よって $𝑞 * (𝑦 0) > 0$ である． $◼$

形式化上の注記. 命題 6.6.4 に対応する宣言は形式化されていない．命題 6.6.4 に付した証明が，この主張の保証のすべてである．形式化の側では，命題 6.6.2 に紐付けた宣言も補題 6.6.10 に紐付けた宣言も，出力分布が全点で正であることを仮定として受け取る形になっている．

命題 6.6.4 が言っているのは，最大化子は「どの入力からも届かない出力記号」以外には確率 0 を置かない，ということである．届かない記号を $Y$ から落としさえすれば，全点で正という仮定は自動的に満たされる．落とす前と後で通信路の振る舞いは変わらないので，これは仮定というより記法の整え方に近い．

塊 1 をいちばん小さい通信路で確かめておく．

例 6.6.5（二元対称通信路の最大化子）. $𝜌 \in [0, 1]$ とし， $𝑊$ を反転確率 $𝜌$ の二元対称通信路（例 6.1.8）， $𝑝 * (0) = 𝑝 * (1) = 1 / 2$ をその一様入力とする．例 6.1.8 より $𝑝 *$ は $𝐼 (\cdot; 𝑊)$ を最大にする入力分布である．このとき $𝑝 *$ の出力分布 $𝑞 *$ は一様で，とくにすべての $𝑦$ で $𝑞 * (𝑦) > 0$ である．さらに両方の入力記号 $𝑎 \in {0, 1}$ について

𝐷 (𝑊 (\cdot ∣ 𝑎) ∥ 𝑞 *) = 1 - 𝐻 𝑏 (𝜌) = 𝐶 (𝑊)

が成り立つ．

証明. 出力分布は

𝑞 * (1) = 12 𝑊 (1 ∣ 0) + 12 𝑊 (1 ∣ 1) = 12 𝜌 + 12 (1 - 𝜌) = 12

であり， $𝑞 * (0) = 1 / 2$ も同様である．よって $𝑞 *$ は一様で，全点で正である．

$𝑎 = 0$ のとき $𝑊 (\cdot ∣ 0)$ は $0$ に $1 - 𝜌$ ， $1$ に $𝜌$ を置く分布だから，1.6 節の定義より

𝐷 (𝑊 (\cdot ∣ 0) ∥ 𝑞 *) = (1 - 𝜌) l o g 1 - 𝜌 1 / 2 + 𝜌 l o g 𝜌 1 / 2 = l o g 2 + (1 - 𝜌) l o g (1 - 𝜌) + 𝜌 l o g 𝜌

である． $l o g$ の底は 2 なので $l o g 2 = 1$ であり，例 1.1.2 より $- (1 - 𝜌) l o g (1 - 𝜌) - 𝜌 l o g 𝜌 = 𝐻 𝑏 (𝜌)$ だから，右辺は $1 - 𝐻 𝑏 (𝜌)$ に等しい（ $𝜌 = 0$ と $𝜌 = 1$ では確率 0 の項が $0 l o g 0 = 0$ の約束で消える）． $𝑎 = 1$ のときは $𝑊 (\cdot ∣ 1)$ が $𝑊 (\cdot ∣ 0)$ の二つの値を入れ替えた分布であり， $𝑞 *$ が一様なので同じ値になる．例 6.1.8 より $𝐶 (𝑊) = 1 - 𝐻 𝑏 (𝜌)$ である． $◼$

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

例 6.6.5 では塊 1 の三つが同時に見えている． $𝑞 *$ が全点で正であること（命題 6.6.4 が一般に保証する），どの入力記号からの隔たりも $𝐶 (𝑊)$ を超えないこと（命題 6.6.2），そして $𝑝 *$ が正の重みを置く記号，ここでは両方の記号で，隔たりがちょうど $𝐶 (𝑊)$ であること（系 6.6.3）である．二つの入力記号が対称なので共通の値をとるのは当然だが， $𝜌$ を動かすと隔たりの値そのものが $1 - 𝐻 𝑏 (𝜌)$ として動くこと，すなわち容量が「 $𝑞 *$ からの共通の隔たり」として読めることは，ここで数値として確かめられる．

情報密度

塊 2 に移る．ここからしばらく極限は出てこない．相手にするのは 1 つの符号だけで，示すのはその符号の平均誤り確率についての不等式である．

出発点は，相互情報量が平均をとってしまった量だという反省である． $𝐼 (𝑝; 𝑊)$ は入力と出力がどれだけ結びついているかを 1 つの数にまとめているが，誤り確率を評価するには，受け取った出力語 1 本ごとに「これはこの符号語らしいか」を測る量が要る．平均する前の量に戻る，というのがここでの動きである．

定義 6.6.6（情報密度）. $𝑊$ を通信路， $𝑛 \geq 1$ をブロック長， $𝑄$ を $Y 𝑛$ 上の分布とする．入力語 $𝑥 𝑛 \in X 𝑛$ と出力語 $𝑦 𝑛 \in Y 𝑛$ に対し， $𝑄$ を 参照分布 とする情報密度 を

ℓ 𝑄 (𝑥 𝑛; 𝑦 𝑛) : = l o g 𝑊 𝑛 (𝑦 𝑛 ∣ 𝑥 𝑛) 𝑄 (𝑦 𝑛)

で定める． $𝑊 𝑛 (𝑦 𝑛 ∣ 𝑥 𝑛) = 0$ の対では $ℓ 𝑄 = - \infty$ ， $𝑊 𝑛 (𝑦 𝑛 ∣ 𝑥 𝑛) > 0$ かつ $𝑄 (𝑦 𝑛) = 0$ の対では $ℓ 𝑄 = + \infty$ と読む．

対数の中身は二人の見込みの比である．分母の $𝑄 (𝑦 𝑛)$ は，何が送られたか知らない人が出力語 $𝑦 𝑛$ に置く見込み．分子の $𝑊 𝑛 (𝑦 𝑛 ∣ 𝑥 𝑛)$ は， $𝑥 𝑛$ が送られたと知っている人が置く見込みである．比が大きければ，その出力語は $𝑥 𝑛$ を強く指し示している．比が 1 のあたりなら何も指し示していない．情報密度は，出力語 1 本が入力語 1 本についてもつ証拠の強さである．

6.1 節とのつながりは，平均をとると見える． $𝑛 = 1$ で参照分布を入力分布 $𝑝$ の出力分布 $𝑞$ にとると，定義 6.1.2 の右辺は

𝐼 (𝑝; 𝑊) = \sum 𝑥, 𝑦 𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥) ℓ 𝑞 (𝑥; 𝑦)

と書き直せる．相互情報量とは，情報密度を結合分布で平均したものにほかならない．逆に情報密度は，相互情報量を平均する前に戻した量である．

定義 6.6.7（高情報密度集合）. $𝑊$ を通信路， $𝑐$ を長さ $𝑛 \geq 1$ ・メッセージ数 $𝑀 \geq 1$ の符号帳（定義 6.3.1）， $𝑄$ を $Y 𝑛$ 上の分布， $𝜃$ を実数とする．メッセージ $𝑚 \in {1, \dots, 𝑀}$ の 高情報密度集合 を

Γ 𝑚 (𝜃) : = {𝑦 𝑛 \in Y 𝑛 : 𝑊 𝑛 (𝑦 𝑛 ∣ 𝑐 (𝑚)) > 2 𝜃 𝑄 (𝑦 𝑛)}

で定める．すなわち，符号語 $𝑐 (𝑚)$ に対する情報密度 $ℓ 𝑄 (𝑐 (𝑚); 𝑦 𝑛)$ がしきい値 $𝜃$ を超える出力語の集合である．

形式化: highLLRSet (ソース)

形式化上の注記. 情報密度（定義 6.6.6）に対応する単独の宣言はない．形式化は比を対数にとらず，定義 6.6.7 の不等式の形のまま扱うので，情報密度は高情報密度集合の定義の中に現れるだけである． $l o g 0$ を避けられるぶん，こちらのほうが扱いやすい．

また，形式化の側は高情報密度集合を符号帳ではなく符号（符号帳と復号器の組）で添字づけている．定義に使うのは符号語だけなので，復号器はどう選んでもこの集合は変わらない．同じことが補題 6.6.8 に紐付けた宣言にも当てはまる．

$Γ 𝑚 (𝜃)$ の外側では $𝑊 𝑛 (𝑦 𝑛 ∣ 𝑐 (𝑚)) \leq 2 𝜃 𝑄 (𝑦 𝑛)$ が成り立っている．この不等式は符号語ごとの出力の分布を，符号にまったく依存しない参照分布 $𝑄$ で置き換えてよい，と言っている．ただし $2 𝜃$ 倍の代償を払うことになり，しかも置き換えてよいのは $Γ 𝑚 (𝜃)$ の外側でだけである．次の補題はこれを 1 行で書き下したものである．

補題 6.6.8. $𝑊$ を通信路， $𝑐$ を長さ $𝑛 \geq 1$ ・メッセージ数 $𝑀 \geq 1$ の符号帳（定義 6.3.1）， $𝑄$ を $Y 𝑛$ 上の分布， $𝜃$ を実数， $𝑚 \in {1, \dots, 𝑀}$ をメッセージ， $𝑠 \subseteq Y 𝑛$ を部分集合とする．定義 6.6.7 の高情報密度集合を $Γ 𝑚 (𝜃)$ と書き， $𝑊 𝑛 (𝑠 ∣ 𝑥 𝑛) : = \sum 𝑦 𝑛 \in 𝑠 𝑊 𝑛 (𝑦 𝑛 ∣ 𝑥 𝑛)$ と書くと

𝑊 𝑛 (𝑠 ∣ 𝑐 (𝑚)) \leq 2 𝜃 𝑄 (𝑠) + 𝑊 𝑛 (Γ 𝑚 (𝜃) ∣ 𝑐 (𝑚))

が成り立つ．

証明. $𝑠$ を $Γ 𝑚 (𝜃)$ の外側と内側に分ける：

𝑊 𝑛 (𝑠 ∣ 𝑐 (𝑚)) = 𝑊 𝑛 (𝑠 ∖ Γ 𝑚 (𝜃) ∣ 𝑐 (𝑚)) + 𝑊 𝑛 (𝑠 \cap Γ 𝑚 (𝜃) ∣ 𝑐 (𝑚))

である．

第 1 項について． $𝑦 𝑛 \in 𝑠 ∖ Γ 𝑚 (𝜃)$ なら定義 6.6.7 の条件が破れているので $𝑊 𝑛 (𝑦 𝑛 ∣ 𝑐 (𝑚)) \leq 2 𝜃 𝑄 (𝑦 𝑛)$ である． $𝑦 𝑛$ について和をとると

𝑊 𝑛 (𝑠 ∖ Γ 𝑚 (𝜃) ∣ 𝑐 (𝑚)) \leq 2 𝜃 𝑄 (𝑠 ∖ Γ 𝑚 (𝜃)) \leq 2 𝜃 𝑄 (𝑠)

となる．最後は $𝑄$ が非負であることによる．第 2 項は $𝑠 \cap Γ 𝑚 (𝜃) \subseteq Γ 𝑚 (𝜃)$ から $𝑊 𝑛 (Γ 𝑚 (𝜃) ∣ 𝑐 (𝑚))$ 以下である．二つを足して主張を得る． $◻$

形式化: channelCoding_per_codeword_decomposition (ソース)

ここまで復号器は一度も現れていない．定義 6.6.7 も補題 6.6.8 も符号語の並びだけで決まる話だからである．復号器が効くのは次の定理で，その復号領域が $Y 𝑛$ の分割をなすところである．補題 6.6.8 をその分割に当てると，符号全体の評価になる．

定理 6.6.9. $𝑊$ を通信路， $(𝑐, 𝑑)$ を長さ $𝑛 \geq 1$ ・メッセージ数 $𝑀 \geq 1$ のブロック通信路符号（定義 6.2.1）， $𝑄$ を $Y 𝑛$ 上の分布， $𝜃$ を実数とする．符号帳 $𝑐$ に対する $Γ 𝑚 (𝜃)$ を定義 6.6.7 の高情報密度集合とすると，この符号の平均誤り確率 $¯ 𝑃 𝑒$ （定義 6.2.1）について

1 - ¯ 𝑃 𝑒 \leq 2 𝜃 𝑀 + 1 𝑀 𝑀 \sum 𝑚 = 1 𝑊 𝑛 (Γ 𝑚 (𝜃) ∣ 𝑐 (𝑚))

が成り立つ．

証明. メッセージ $𝑚$ の 復号領域 を $D 𝑚 : = {𝑦 𝑛 \in Y 𝑛 : 𝑑 (𝑦 𝑛) = 𝑚}$ とおく． $𝑑$ は写像だから $D 1, \dots, D 𝑀$ は互いに交わらず，合併は $Y 𝑛$ 全体である．定義 6.2.1 の誤り確率は $𝑃 𝑒 (𝑚) = 1 - 𝑊 𝑛 (D 𝑚 ∣ 𝑐 (𝑚))$ だから， $𝑚$ について平均して

1 - ¯ 𝑃 𝑒 = 1 𝑀 𝑀 \sum 𝑚 = 1 𝑊 𝑛 (D 𝑚 ∣ 𝑐 (𝑚))

である．

各項に，符号帳 $𝑐$ について補題 6.6.8 を $𝑠 \leftarrow D 𝑚$ として当てると

1 - ¯ 𝑃 𝑒 \leq 1 𝑀 𝑀 \sum 𝑚 = 1 2 𝜃 𝑄 (D 𝑚) + 1 𝑀 𝑀 \sum 𝑚 = 1 𝑊 𝑛 (Γ 𝑚 (𝜃) ∣ 𝑐 (𝑚))

を得る． $D 𝑚$ は $Y 𝑛$ の分割をなし $𝑄$ は分布だから $\sum 𝑚 𝑄 (D 𝑚) = 1$ であり，第 1 の和は $2 𝜃 / 𝑀$ に等しい． $◼$

形式化: channelCoding_average_success_le (ソース)

分割が代償を 1 回にまとめる. 補題 6.6.8 の代償 $2 𝜃 𝑄 (𝑠)$ はメッセージ 1 個あたりにかかっているのに，定理 6.6.9 ではそれが $2 𝜃 / 𝑀$ まで縮んでいる．効いているのは復号領域が $Y 𝑛$ の分割だという 1 点である． $𝑀$ 個の領域が参照分布を分け合うので， $𝑄 (D 𝑚)$ を全部足しても 1 にしかならない． $𝑀$ 個の代償の合計が $𝑀$ 倍ではなく $2 𝜃$ になり，平均をとる $1 / 𝑀$ でさらに割られる．

しきい値をどこに置くかがこれで見えてくる． $𝜃 = l o g 𝑀 + 𝛾$ と書けば第 1 項はちょうど $2 𝛾$ である． $𝛾$ を大きく負にとれば，すなわちしきい値を $l o g 𝑀$ より十分下に置けば，第 1 項は小さい．いっぽう第 2 項は，しきい値が低いほど大きくなる．情報密度がしきい値を超える確率だからである． $l o g 𝑀$ より十分低く，しかも情報密度がそこまで届かないほど高いしきい値がとれるかどうかが勝負になる．ここで効くのが命題 6.6.2 の一様な上界で，これを使うと情報密度の平均が符号によらず $𝑛 𝐶 (𝑊)$ 以下だと言える（補題 6.6.10）． $l o g 𝑀$ が $𝑛 𝐶 (𝑊)$ より $𝑛$ に比例して大きければ，その隙間にしきい値を置ける． $1 𝑛 l o g 𝑀 > 𝐶 (𝑊)$ という条件がここで初めて姿を見せる．

誤り確率が 1 に向かう

Chebyshev の不等式と分散の加法性を借りる. 借りるのは二つである．一つは Chebyshev の不等式で，形は「確率変数 $𝑍$ が平均 $𝜇$ ，分散 $𝜎 2$ をもつとき，任意の $𝜏 > 0$ に対し $P r [| 𝑍 - 𝜇 | \geq 𝜏] \leq 𝜎 2 / 𝜏 2$ 」．もう一つは分散の加法性で，形は「互いに独立な確率変数の有限和の分散は，各項の分散の和に等しい」．どちらも当てる相手は，有限アルファベット上の有界な独立確率変数の有限個の和である．この二つに依存するのは補題 6.6.10 だけで，以降は補題 6.6.10 の結論だけを使う．

補題 6.6.10. $𝑊$ を通信路， $𝑝 *$ を $𝐼 (\cdot; 𝑊)$ を最大にする入力分布（定理 6.1.5）， $𝑞 *$ をその出力分布とし， $𝑞 *$ はすべての $𝑦 \in Y$ で $𝑞 * (𝑦) > 0$ を満たすとする． $𝛿 > 0$ を固定する．各 $𝑛 \geq 1$ について長さ $𝑛$ ・メッセージ数 $𝑀 𝑛 \geq 1$ の符号帳 $𝑐 𝑛$ （定義 6.3.1）が与えられているとし，参照分布を $𝑄 𝑛 (𝑦 𝑛) : = \prod 𝑛 - 1 𝑖 = 0 𝑞 * (𝑦 𝑖)$ ，しきい値を $𝜃 𝑛 : = 𝑛 (𝐶 (𝑊) + 𝛿 / 2)$ として，定義 6.6.7 の高情報密度集合を $Γ (𝑛) 𝑚 (𝜃 𝑛)$ と書く．このとき

1 𝑀 𝑛 𝑀 𝑛 \sum 𝑚 = 1 𝑊 𝑛 (Γ (𝑛) 𝑚 (𝜃 𝑛) ∣ 𝑐 𝑛 (𝑚)) ⟶ 0 (𝑛 \to \infty)

である．

証明. $𝑛 \geq 1$ とメッセージ $𝑚$ を固定し， $𝑥 𝑛 : = 𝑐 𝑛 (𝑚)$ と書く． $𝑌 𝑛$ を $𝑊 𝑛 (\cdot ∣ 𝑥 𝑛)$ に従う出力語とする．

情報密度は独立な和である. 定義 6.1.1 より $𝑊 𝑛 (𝑦 𝑛 ∣ 𝑥 𝑛) = \prod 𝑖 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖)$ であり， $𝑄 𝑛$ も積の形だから，対数をとると

ℓ 𝑄 𝑛 (𝑥 𝑛; 𝑦 𝑛) = 𝑛 - 1 \sum 𝑖 = 0 l o g 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖) 𝑞 * (𝑦 𝑖)

である．そこで $𝑉 𝑖 : = l o g 𝑊 (𝑌 𝑖 ∣ 𝑥 𝑖) 𝑞 * (𝑌 𝑖)$ ， $𝑍 : = \sum 𝑖 𝑉 𝑖$ とおく．同じ積の形から $𝑌 0, \dots, 𝑌 𝑛 - 1$ は互いに独立で， $𝑌 𝑖$ は $𝑊 (\cdot ∣ 𝑥 𝑖)$ に従う． $𝑉 𝑖$ は $𝑌 𝑖$ だけの関数だから， $𝑉 0, \dots, 𝑉 𝑛 - 1$ も互いに独立である．

$𝑛$ によらない上界で押さえる. $𝑊 (𝑦 ∣ 𝑥 𝑖) = 0$ となる $𝑦$ は $𝑊 (\cdot ∣ 𝑥 𝑖)$ のもとで確率 0 でしか現れないので，

𝜅 : = m a x {∣ l o g 𝑊 (𝑦 ∣ 𝑥) 𝑞 * (𝑦) ∣ : 𝑥 \in X, 𝑦 \in Y, 𝑊 (𝑦 ∣ 𝑥) > 0}

とおけば，確率 1 で $| 𝑉 𝑖 | \leq 𝜅$ である． $𝑞 *$ が全点で正だから中身はどれも有限で，有限個の実数の最大値として $𝜅$ は有限である．しかも $𝜅$ は $𝑊$ と $𝑞 *$ だけで決まり， $𝑛$ にも符号にもメッセージにもよらない．

平均は $𝑛 𝐶 (𝑊)$ 以下である. 定義から

𝔼 [𝑉 𝑖] = \sum 𝑦 𝑊 (𝑦 ∣ 𝑥 𝑖) l o g 𝑊 (𝑦 ∣ 𝑥 𝑖) 𝑞 * (𝑦) = 𝐷 (𝑊 (\cdot ∣ 𝑥 𝑖) ∥ 𝑞 *)

であり，命題 6.6.2 よりこれは $𝐶 (𝑊)$ 以下である．期待値の線形性から $𝔼 [𝑍] \leq 𝑛 𝐶 (𝑊)$ を得る．ここで効いているのは，命題 6.6.2 が入力記号 $𝑥 𝑖$ について一様だということである． $𝑥 𝑛$ は符号の設計者が選んだ任意の語であって， $𝑝 *$ から引いたものではない．

分散は $𝑛 𝜅 2$ 以下である. $V a r (𝑉 𝑖) \leq 𝔼 [𝑉 2 𝑖] \leq 𝜅 2$ であり，借用した分散の加法性から $V a r (𝑍) = \sum 𝑖 V a r (𝑉 𝑖) \leq 𝑛 𝜅 2$ である．

Chebyshev の不等式を当てる. $𝑦 𝑛 \in Γ (𝑛) 𝑚 (𝜃 𝑛)$ は $ℓ 𝑄 𝑛 (𝑥 𝑛; 𝑦 𝑛) > 𝜃 𝑛$ ，すなわち $𝑍 > 𝑛 (𝐶 (𝑊) + 𝛿 / 2)$ を意味する． $𝔼 [𝑍] \leq 𝑛 𝐶 (𝑊)$ だからこれは $𝑍 - 𝔼 [𝑍] > 𝑛 𝛿 / 2$ を導き，とくに $| 𝑍 - 𝔼 [𝑍] | \geq 𝑛 𝛿 / 2$ である．借用した Chebyshev の不等式より

𝑊 𝑛 (Γ (𝑛) 𝑚 (𝜃 𝑛) ∣ 𝑥 𝑛) \leq 𝑛 𝜅 2 (𝑛 𝛿 / 2) 2 = 𝜅 2 (𝛿 / 2) 2 \cdot 1 𝑛

を得る．右辺は $𝑚$ にも符号にもよらないので， $𝑚$ について平均しても同じ上界で押さえられ， $𝑛 \to \infty$ で 0 に収束する． $◻$

形式化: channelCoding_highLLR_tendsto_zero (ソース)

形式化上の注記. 一様な上界のとり方が本文と形式化で違う．本文は正の確率をもつ対にわたる最大値 $𝜅$ をとったが，形式化は全対にわたる絶対値の総和 llrUnifBound (InformationTheory/Shannon/ChannelCoding/StrongConverseAsymptotic.lean) をとる．こちらのほうが粗いが， $l o g 0 = 0$ という規約のもとで確率 0 の対を除く手間なしに定義できる．どちらも $𝑛$ にも符号にもよらない定数で，証明の筋は変わらない．分散の評価にも差があり，形式化は有界な確率変数の分散が区間の半幅の 2 乗以下だという事実を使う．

$1 / 𝑛$ という速さは主張には要らない．要るのは 0 に収束することだけで，そのために効いたのは分散が $𝑛$ の 1 乗でしか増えないのに，しきい値までの距離が $𝑛$ に比例することである． $𝑛$ が大きくなるほど，情報密度は平均のまわりの $\sqrt 𝑛$ の幅に集中していくのに，しきい値は平均から $𝑛 𝛿 / 2$ だけ離れていく．距離のほうが速く伸びるので，超える確率は消える．第2章の典型集合が「実際に出る系列はほぼすべて典型」と言ったのと同じ形の集中が，ここでは情報密度について起きている．

同じ集中が 6.3 節とは逆向きに働いていることに注意しておきたい．達成可能性では，本物の入出力対の情報密度が $𝑛 𝐼 (𝑝; 𝑊)$ の近くまで届くことが味方だった．届くからこそ結合典型復号器が正しい符号語を選べた．ここではしきい値を平均よりさらに上に置くので，同じ集中が今度は「どの符号語も情報密度をそこまで持ち上げられない」という敵側の壁として働く．測っている量も集中の仕方も同じで，しきい値を平均のどちら側に置くかだけが違う．

定理 6.6.11（強逆定理）. $𝑊$ を通信路， $𝑝 *$ を $𝐼 (\cdot; 𝑊)$ を最大にする入力分布（定理 6.1.5）， $𝑞 *$ をその出力分布とし， $𝑞 *$ はすべての $𝑦 \in Y$ で $𝑞 * (𝑦) > 0$ を満たすとする． $𝛿 > 0$ とする．各 $𝑛 \geq 1$ について長さ $𝑛$ ・メッセージ数 $𝑀 𝑛 \geq 1$ のブロック通信路符号 $(𝑐 𝑛, 𝑑 𝑛)$ が与えられ，十分大きいすべての $𝑛$ で

1 𝑛 l o g 𝑀 𝑛 \geq 𝐶 (𝑊) + 𝛿

が成り立つとする．このときその平均誤り確率は $¯ 𝑃 (𝑛) 𝑒 \to 1$ を満たす．

証明. 参照分布を $𝑄 𝑛 (𝑦 𝑛) : = \prod 𝑖 𝑞 * (𝑦 𝑖)$ ，しきい値を $𝜃 𝑛 : = 𝑛 (𝐶 (𝑊) + 𝛿 / 2)$ にとる．定理 6.6.9 より，各 $𝑛$ について

1 - ¯ 𝑃 (𝑛) 𝑒 \leq 2 𝑛 (𝐶 (𝑊) + 𝛿 / 2) 𝑀 𝑛 + 1 𝑀 𝑛 𝑀 𝑛 \sum 𝑚 = 1 𝑊 𝑛 (Γ (𝑛) 𝑚 (𝜃 𝑛) ∣ 𝑐 𝑛 (𝑚))

である．右辺の二項がどちらも 0 に収束することを見ればよい．

第 1 項について．十分大きい $𝑛$ では仮定より $l o g 𝑀 𝑛 \geq 𝑛 (𝐶 (𝑊) + 𝛿)$ ，すなわち $𝑀 𝑛 \geq 2 𝑛 (𝐶 (𝑊) + 𝛿)$ である．よって

2 𝑛 (𝐶 (𝑊) + 𝛿 / 2) 𝑀 𝑛 \leq 2 𝑛 (𝐶 (𝑊) + 𝛿 / 2) - 𝑛 (𝐶 (𝑊) + 𝛿) = 2 - 𝑛 𝛿 / 2

であり， $𝛿 > 0$ だからこれは 0 に収束する．第 2 項は補題 6.6.10 そのもので，0 に収束する．

したがって $1 - ¯ 𝑃 (𝑛) 𝑒$ の上極限は 0 以下である．誤り確率は 1 以下だから $1 - ¯ 𝑃 (𝑛) 𝑒 \geq 0$ でもあり，はさみうちにより $1 - ¯ 𝑃 (𝑛) 𝑒 \to 0$ ，すなわち $¯ 𝑃 (𝑛) 𝑒 \to 1$ である． $◼$

形式化: channelCoding_strong_converse_asymptotic (ソース)

系 6.6.12. $𝑊$ を通信路， $𝑝 *$ を $𝐼 (\cdot; 𝑊)$ を最大にする入力分布（定理 6.1.5）， $𝑞 *$ をその出力分布とし， $𝑞 *$ はすべての $𝑦 \in Y$ で $𝑞 * (𝑦) > 0$ を満たすとする．実数 $𝑅$ が次の条件を満たすとする．どんな $𝜀 > 0$ に対しても，ある $𝑁$ があって， $𝑛 \geq 𝑁$ ならばメッセージ数 $𝑀 \geq 2 𝑛 𝑅$ の長さ $𝑛$ のブロック通信路符号で，平均誤り確率が $¯ 𝑃 𝑒 < 𝜀$ を満たすものが存在する，という条件である．このとき $𝑅 \leq 𝐶 (𝑊)$ である．

証明. $𝑅 > 𝐶 (𝑊)$ だとして矛盾を導く． $𝛿 : = 𝑅 - 𝐶 (𝑊) > 0$ とおく．仮定を $𝜀 : = 1 / 2$ に対して使うと，ある $𝑁$ があって， $𝑛 \geq 𝑁$ ならばメッセージ数 $𝑀 𝑛 \geq 2 𝑛 𝑅$ で平均誤り確率が $¯ 𝑃 (𝑛) 𝑒 < 1 / 2$ の長さ $𝑛$ の符号 $(𝑐 𝑛, 𝑑 𝑛)$ がとれる． $𝑛 < 𝑁$ については，メッセージ数 1 の符号（符号語も復号結果も 1 通り）を当てておく．

こうしてできた族に定理 6.6.11 を当てる． $𝑀 𝑛 \geq 2 𝑛 𝑅 > 0$ より $𝑀 𝑛 \geq 1$ であり， $𝑛 \geq 𝑁$ では

1 𝑛 l o g 𝑀 𝑛 \geq 𝑅 = 𝐶 (𝑊) + 𝛿

だから，十分大きいすべての $𝑛$ でレートの条件が満たされている．よって $¯ 𝑃 (𝑛) 𝑒 \to 1$ である．ところが $𝑛 \geq 𝑁$ ではつねに $¯ 𝑃 (𝑛) 𝑒 < 1 / 2$ なので，極限は $1 / 2$ 以下でなければならない．これは矛盾である． $◼$

形式化: channelCoding_operational_rate_le_capacity (ソース)

同じ結論を 2 度出す理由. 系 6.6.12 の結論（達成できるレートは $𝐶 (𝑊)$ 以下）は系 6.4.8 の結論と同じである．違うのは前提のほうで，二つは強弱で並ぶのではなく，要求の置き場所が違う．系 6.4.8 は符号の族に，最大誤り確率が 0 に向かうことと，レートの列が上に有界であることを求めていた．系 6.6.12 が符号に求めるのは平均誤り確率を $𝜀$ 未満にできることだけで，最大誤り確率にもレートの有界性にも触れない．そのかわり系 6.6.12 は通信路のほうに，最大化子の出力分布が全点で正だという条件を負っている．これは系 6.4.8 が負っていない条件である．符号への要求は緩く，通信路への要求は厳しい．

証明の使い方を見ると差はもっとはっきりする．系 6.6.12 の証明が前提を使ったのは $𝜀 = 1 / 2$ の 1 回だけだった．平均誤り確率が $1 / 2$ を下回る符号が大きいすべての $𝑛$ でとれれば，それだけで $𝑅 \leq 𝐶 (𝑊)$ が出る． $0$ に向かうことも， $1 / 2$ より小さくなることも要らない．要るのは $1$ に向かわないということだけである．定理 6.6.11 が「 $1$ に向かう」まで言い切っているからこうなる．

弱い逆定理と強い逆定理. 二つの逆定理が言っていることを並べると，強さの違いは境目の描き方に出る．弱逆定理（系 6.4.8）は「誤り確率を 0 にできるレートは $𝐶 (𝑊)$ 以下」と言う． $𝐶 (𝑊)$ を超えたところで誤り確率が 0 に落ちないことは分かるが，どこで止まるかは分からない．強逆定理（定理 6.6.11）は「 $𝐶 (𝑊)$ を超えたレートでは誤り確率は 1 に向かう」と言う．中間の振る舞い（誤り確率が $0$ と $1$ のあいだのどこかに落ち着くレート帯）が存在しないことを主張しているのが，強い側の内容である．

この違いは通信路を使う側にとって実際的な意味をもつ．弱逆定理しかなければ， $𝐶 (𝑊)$ を少し超えたレートで誤り確率 $10 - 3$ が達成できる可能性が残る．強逆定理はそれを閉じる． $𝐶 (𝑊)$ を超えたら， $𝑛$ を大きくとるほど事態は悪くなり，ほとんどすべてのメッセージが誤って復号される． $𝐶 (𝑊)$ は，そこを境に成功が失敗へ反転する敷居であって，性能がなだらかに劣化しはじめる点ではない．

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