8.3 逆定理

8.2 節の $𝐶 (𝑃, 𝑁) = 12 l o g (1 + 𝑃 / 𝑁)$ は，相互情報量の最大化問題の値でしかない．第6章 6.1 節の $𝐶 (𝑊)$ と同じで，この段階では「 $1$ 回の使用あたり $𝐶 (𝑃, 𝑁)$ ビット運べる」と言う資格がない．本節はまず，ガウス通信路を使って送るとはどういう操作かを符号として定義し，そのうえで，どんな符号の族を設計しても達成レートが $𝐶 (𝑃, 𝑁)$ を超えられないことを示す． $1$ 本の符号については，誤り確率を大きく許せばレートはいくらでも上げられるので，超えられないのは誤り確率を $0$ に近づける族が残せるレートのほうである．

論証の形は第6章 6.4 節と同じである．一様なメッセージのもつ情報量 $l o g 𝑀$ を，ファノの不等式で「通信路が運んだぶん」と「誤りで説明されるぶん」に分ける．運んだぶんは，系 8.1.5 と同じ形で出力の微分エントロピー $ℎ (𝑌 𝑛)$ から雑音の分を引いたものになり， $ℎ (𝑌 𝑛)$ を電力制約で抑えれば $𝑛 2 l o g (1 + 𝑃 / 𝑁)$ が出る．抑えるのに使う道具は二つで，微分エントロピーの劣加法性（定理 7.4.3）と，分散を固定したときの最大エントロピー性（定理 7.2.4）である．道具の対応も見ておく．第6章では，記憶のなさが $l o g 𝑀$ の右辺を各時刻の相互情報量の和 $\sum 𝑖 𝐼 (𝑋 𝑖; 𝑌 𝑖)$ に落とした（定理 6.4.5）．本節でその役をするのは，出力の側を成分ごとにほどく劣加法性 $ℎ (𝑌 𝑛) \leq \sum 𝑖 ℎ (𝑌 𝑖)$ と，雑音の側の $𝑛$ 成分が独立なので $ℎ$ が和になること（系 7.4.4）の二つである．記憶のなさは，長さ $𝑛$ の出力の結合密度を積の形にとった定義 8.1.1 に，すでに書き込まれている．

条件付けについて，先に断っておくことがある．8.1 節が条件付き微分エントロピーの定義で手間をかけたのは，条件付ける相手が実数値の入力で， $𝑋 = 𝑥$ という確率 $0$ の事象で条件付けることになるからだった．本節が条件付ける相手はメッセージで，これは有限個の値を確率 $1 / 𝑀$ ずつでとるから，その困難には当たらない．避けたのは連続な側で条件付けることであって，離散な側で条件付けることではない．

そのうえで，一つだけ第6章と事情が違うところがある．符号語は有限個しかないので，入力 $𝑋 𝑛$ がとる値は $ℝ 𝑛$ の有限個の点である．したがって対 $(𝑋 𝑛, 𝑌 𝑛)$ は， $ℝ 2 𝑛$ の中で「第 $1$ 座標の組がその有限個の点のどれかに等しい」という集合の上に確率 $1$ を置く．この集合の $2 𝑛$ 次元の体積が $0$ であることを微積分の計算規則として既知とすると，7.1 節で借りた体積 $0$ の集合の確率により， $(𝑋 𝑛, 𝑌 𝑛)$ には定義 7.1.1 の意味の結合密度がない．したがって定義 8.1.2 の条件付き微分エントロピーは当てられず，ファノの不等式を通す段も第6章のままでは書けない．そこはひとまとめに借用する．

借りる道具

観測が実数値のときのファノの不等式を，単発逆定理（実数値の観測） という名前で証明せずに借りる．主張の形は次のとおりである． $𝑀 \geq 2$ と $𝑘 \geq 1$ をとり， $M s g$ を ${1, \dots, 𝑀}$ 上の一様分布に従う確率変数， $𝑉$ を $ℝ 𝑘$ に値をとる確率変数とする． $𝑞 1, \dots, 𝑞 𝑀$ を $ℝ 𝑘$ 上の密度で， $M s g = 𝑚$ を与えたときの $𝑉$ の条件付き分布が $𝑞 𝑚$ を密度にもつものとし， $𝑞 𝑚$ を密度にもつ確率変数の微分エントロピーを $ℎ 𝑚$ と書く． $𝑉$ が密度をもって $ℎ (𝑉)$ が定まり，各 $ℎ 𝑚$ も定まるとする． $ℝ 𝑘$ から ${1, \dots, 𝑀}$ への復号器 $𝑑$ が，どの $𝑚$ についても $𝑞 𝑚$ を集合 ${𝑦 \in ℝ 𝑘 : 𝑑 (𝑦) \neq 𝑚}$ の上で積分できるものであるならば， $𝑃 𝑒 : = P r [𝑑 (𝑉) \neq M s g]$ について

l o g 𝑀 \leq ℎ (𝑉) - 1 𝑀 𝑀 \sum 𝑚 = 1 ℎ 𝑚 + 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (𝑀 - 1)

が成り立つ（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．当てる対象は，定義 8.3.1 のブロック通信路符号をガウス通信路に通して得られる組 $(M s g, 𝑌 𝑛)$ だけであり，依存するのは定理 8.3.5 の証明だけである．

これは定理 6.4.1 の観測が実数値の場合にあたる．右辺の読み方を書いておく． $M s g = 𝑚$ を与えるごとに $𝑉$ の分布は $𝑞 𝑚$ に定まるから，その微分エントロピー $ℎ 𝑚$ を $1 / 𝑀$ で平均した第 $2$ 項は，メッセージを知ったあとに $𝑉$ に残る散らばりを測っている．したがって右辺の第 $1$ 項と第 $2$ 項の差 $ℎ (𝑉) - 1 𝑀 \sum 𝑚 ℎ 𝑚$ は，命題 8.1.3 の $ℎ (𝑌) - ℎ (𝑌 ∣ 𝑋)$ と同じ形をしている（メッセージは有限個の値をとるので対に結合密度はなく，定義 8.1.2 の意味の条件付き微分エントロピーそのものは書けない）．借りるのは，この差が定理 6.4.1 の $𝐼 (M s g; 𝑌)$ の役を果たすということである．

本書がこれを証明しないのは，観測が実数値のときに $𝐻 (M s g ∣ 𝑉)$ を定めるのに，第7章が避けた「確率 $0$ の事象で条件付けた分布」の道具が要るからである．形式化は測度論の言葉で相互情報量を直接扱えるので第6章と同じ道を通れるが，本書はその道具を用意していないので，ここでは結論の形だけを借りる．借りたからといって，そこから出る不等式が保証の外に出るわけではない．定理 8.3.5 の不等式そのものは無条件に機械検証されている．ただし形式化はこの一歩を通らず，別のルートで同じ不等式に達している．

電力制約つきブロック通信路符号

定義 8.3.1（電力制約つきブロック通信路符号）. $𝑁 > 0$ ， $𝑃 > 0$ ， $𝑀 \geq 1$ ， $𝑛 \geq 1$ とする．雑音の分散 $𝑁$ のガウス通信路（定義 8.1.1）に対する長さ $𝑛$ ，電力 $𝑃$ の 電力制約つきブロック通信路符号 とは，符号化写像 $𝑐 : {1, \dots, 𝑀} \to ℝ 𝑛$ と復号器 $𝑑 : ℝ 𝑛 \to {1, \dots, 𝑀}$ の組であって，各 $𝑚$ について 電力制約

𝑛 - 1 \sum 𝑖 = 0 (𝑐 (𝑚) 𝑖) 2 \leq 𝑛 𝑃

を満たし，どの $𝑚$ とどの $𝑚'$ についても，密度 $𝑦 𝑛 \mapsto \prod 𝑛 - 1 𝑖 = 0 𝑔 𝑐 (𝑚') 𝑖, 𝑁 (𝑦 𝑖)$ を集合 ${𝑦 𝑛 \in ℝ 𝑛 : 𝑑 (𝑦 𝑛) \neq 𝑚}$ の上で積分できるものをいう．その レート を $𝑅 : = 1 𝑛 l o g 𝑀$ で定める．メッセージ $𝑚$ を送ったときの 誤り確率，およびそれを $𝑚$ について最悪値と平均で束ねた 最大誤り確率・平均誤り確率 を

𝑃 𝑒 (𝑚) : = \int {𝑦 𝑛 : 𝑑 (𝑦 𝑛) \neq 𝑚} 𝑛 - 1 \prod 𝑖 = 0 𝑔 𝑐 (𝑚) 𝑖, 𝑁 (𝑦 𝑖) 𝑑 𝑦 𝑛, 𝑃 𝑒, m a x : = m a x 1 \leq 𝑚 \leq 𝑀 𝑃 𝑒 (𝑚), ¯ 𝑃 𝑒 : = 1 𝑀 𝑀 \sum 𝑚 = 1 𝑃 𝑒 (𝑚)

で定める．

第6章の定義 6.2.1 との違いは三つである．符号語が $X 𝑛$ ではなく $ℝ 𝑛$ に住むこと，電力制約が付いたこと，そして誤りの事象の上で密度を積分できることを求めていることである．三つめは，出力が実数値になったせいで誤り確率が和ではなく積分で定まることから来る条件で，第6章では誤りの事象が有限集合だったので要らなかった．7.1 節が積分の線形性や単調性を微積分の計算規則として既知としたのと同じ資格で，積分できる集合どうしの有限個の和と差もまた積分できる集合であることを，本章では既知とする（使うのは系 8.4.2 の証明だけである）．電力制約を $𝑛 𝑃$ で書いたのは， $1$ 回の使用あたりの電力を $𝑃$ までに抑える，という意味である．レートの読み方も第6章と同じで， $𝑀$ 通りのメッセージを区別するのに要る $l o g 𝑀$ ビットを $𝑛$ 回の使用で割った， $1$ 回あたりの取り分である．

形式化: AwgnCode (ソース)

形式化上の注記. 形式化の AwgnCode は符号化写像・復号器・電力制約を一つにまとめた構造で，定義 8.3.1 の「密度を積分できる」にあたる条件は，復号器が可測であることとして書かれている．誤り確率は errorProbAt を核 awgnChannel に当てたもので，本文の積分にあたる．最大誤り確率を束ねた宣言はなく，第6章 6.2 節と同じく「すべてのメッセージについて誤り確率が小さい」という形で書かれる．

定義 8.3.2（達成レート）. $𝑁 > 0$ ， $𝑃 > 0$ とする．長さ $𝑛$ ，電力 $𝑃$ のブロック通信路符号を第 $𝑛$ 項とする族 $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛) 𝑛 \geq 1$ が 達成可能 であるとは，最大誤り確率が $𝑃 (𝑛) 𝑒, m a x \to 0$ を満たし，かつレートの列 $𝑅 𝑛 = 1 𝑛 l o g 𝑀 𝑛$ が上に有界なことをいう．このとき $l i m i n f 𝑛 𝑅 𝑛$ をその族の 達成レート と呼び，達成レート全体の集合を $R (𝑃, 𝑁)$ と書く．

定義 6.2.2 をそのままガウス通信路に移した定義である．電力制約は符号の側に入っているので，達成レートの定義そのものは第6章と変わらない．

形式化上の注記. 達成レートに対応する宣言はガウス通信路の側にはない．第6章 6.2 節で触れたとおり，通信路の側に達成レートの集合そのものを表す宣言がまだ用意されていないためである．

出力の微分エントロピーを抑える

符号語を有限個並べて一様に選ぶと，出力の分布はガウス分布の混合になる．その微分エントロピーが定まることと，各成分の $2$ 乗の平均がどんな値になるかを，先に確かめておく．その値に電力制約を当てて上から抑えるのは，補題 8.3.4 のほうである．

補題 8.3.3（ガウス分布の混合）. $𝑁 > 0$ ， $𝑀 \geq 1$ ， $𝑘 \geq 1$ とし， $𝑎 1, \dots, 𝑎 𝑀 \in ℝ 𝑘$ とする．

¯ 𝑞 (𝑦) : = 1 𝑀 𝑀 \sum 𝑚 = 1 𝑘 - 1 \prod 𝑗 = 0 𝑔 𝑎 𝑚, 𝑗, 𝑁 (𝑦 𝑗) (𝑦 \in ℝ 𝑘)

は $ℝ 𝑘$ 上の密度である． $¯ 𝑞$ を密度にもつ $ℝ 𝑘$ 値の確率変数を $𝑉 = (𝑉 0, \dots, 𝑉 𝑘 - 1)$ とすると， $ℎ (𝑉)$ は定まり，各 $𝑗$ について $𝑉 𝑗$ は密度 $𝑡 \mapsto 1 𝑀 \sum 𝑚 𝑔 𝑎 𝑚, 𝑗, 𝑁 (𝑡)$ をもち， $ℎ (𝑉 𝑗)$ は定まって

𝔼 [𝑉 2 𝑗] = 𝑁 + 1 𝑀 𝑀 \sum 𝑚 = 1 𝑎 2 𝑚, 𝑗

である．

証明. この補題があとで使う内容は一つで，混合の $2$ 乗平均が，混ぜる前の各分布の $2$ 乗平均の平均になる，ということである．残りはすべて， $¯ 𝑞$ が密度であること，その周辺密度が何になるか，微分エントロピーが定まること，の確認にあたる．

$¯ 𝑞$ が密度であることを見る．非負であり，7.4 節で借りた独立と積の密度により各 $𝑦 \mapsto \prod 𝑗 𝑔 𝑎 𝑚, 𝑗, 𝑁 (𝑦 𝑗)$ は $ℝ 𝑘$ 上の密度だから，その平均である $¯ 𝑞$ の全積分も $1$ である．

周辺密度を求める．8.1 節で借りた累次積分により， $\prod 𝑗 𝑔 𝑎 𝑚, 𝑗, 𝑁 (𝑦 𝑗)$ を第 $𝑗$ 変数以外について積分すると，各因子の全積分が $1$ だから $𝑔 𝑎 𝑚, 𝑗, 𝑁 (𝑦 𝑗)$ が残る．よって定義 7.4.1 の第 $𝑗$ 周辺密度は $𝑡 \mapsto 1 𝑀 \sum 𝑚 𝑔 𝑎 𝑚, 𝑗, 𝑁 (𝑡)$ であり，7.4 節で借りた周辺密度の存在によりこれは $𝑉 𝑗$ の密度である．

$2$ 乗の平均を求める．定理 8.2.2 の証明と同じ計算で，7.2 節で借りたガウス分布の基本性質から $\int 𝑔 𝑎, 𝑁 (𝑡) 𝑡 2 𝑑 𝑡 = 𝑁 + 𝑎 2$ である．よって 7.1 節で借りた期待値の積分表示より

𝔼 [𝑉 2 𝑗] = \int ℝ 1 𝑀 𝑀 \sum 𝑚 = 1 𝑔 𝑎 𝑚, 𝑗, 𝑁 (𝑡) 𝑡 2 𝑑 𝑡 = 1 𝑀 𝑀 \sum 𝑚 = 1 (𝑁 + 𝑎 2 𝑚, 𝑗)

であり，これが主張の値である．同じ計算を $𝑡 2$ のかわりに $(𝑡 - 𝑎 1, 𝑗) 2$ について行うと， $𝔼 [(𝑉 𝑗 - 𝑎 1, 𝑗) 2] = 1 𝑀 \sum 𝑚 (𝑁 + (𝑎 𝑚, 𝑗 - 𝑎 1, 𝑗) 2)$ もやはり有限である．

$ℎ (𝑉)$ が定まることを見る． $¯ 𝑞$ は $ℝ 𝑘$ のすべての点で正である．上からは，各因子が $𝑔 𝑎, 𝑁 (𝑡) \leq (2 𝜋 𝑁) - 1 / 2$ を満たすから $¯ 𝑞 (𝑦) \leq (2 𝜋 𝑁) - 𝑘 / 2$ であり，したがって $l o g ¯ 𝑞 (𝑦) \leq - 𝑘 2 l o g (2 𝜋 𝑁)$ である．下からは，和の一項だけを残して $¯ 𝑞 (𝑦) \geq 1 𝑀 \prod 𝑗 𝑔 𝑎 1, 𝑗, 𝑁 (𝑦 𝑗)$ であり，定義 7.2.1 の密度の対数をとると

- l o g ¯ 𝑞 (𝑦) \leq l o g 𝑀 + 𝑘 2 l o g (2 𝜋 𝑁) + l o g 𝑒 2 𝑁 𝑘 - 1 \sum 𝑗 = 0 (𝑦 𝑗 - 𝑎 1, 𝑗) 2

である．二つを合わせると，右辺の第 $2$ 項を絶対値に替えた $𝑦$ の $2$ 次以下の多項式

l o g 𝑀 + 𝑘 2 ∣ l o g (2 𝜋 𝑁) ∣ + l o g 𝑒 2 𝑁 𝑘 - 1 \sum 𝑗 = 0 (𝑦 𝑗 - 𝑎 1, 𝑗) 2

が $| l o g ¯ 𝑞 (𝑦) |$ を上から抑える．いま見たとおり各 $𝔼 [(𝑉 𝑗 - 𝑎 1, 𝑗) 2]$ は有限だから，7.1 節で借りた期待値の積分表示より，これに $¯ 𝑞$ を掛けた積分は有限である．よって $\int ℝ 𝑘 | ¯ 𝑞 l o g ¯ 𝑞 |$ も有限で， $ℎ (𝑉)$ は定まる． $𝑘 = 1$ の場合を各 $𝑉 𝑗$ の密度に当てれば， $ℎ (𝑉 𝑗)$ が定まることも同じ議論から従う． $◻$

補題 8.3.4（出力の微分エントロピーの上界）. $𝑁 > 0$ ， $𝑃 > 0$ ， $𝑀 \geq 1$ ， $𝑛 \geq 1$ とし，長さ $𝑛$ ，電力 $𝑃$ のブロック通信路符号（定義 8.3.1）をとる． ${1, \dots, 𝑀}$ 上の一様分布に従うメッセージ $M s g$ の符号語をガウス通信路に通して得られる出力を $𝑌 𝑛$ とすると， $ℎ (𝑌 𝑛)$ は定まり

ℎ (𝑌 𝑛) \leq 𝑛 2 l o g (2 𝜋 𝑒 (𝑃 + 𝑁))

である．

証明. 出力の密度を求める． $M s g = 𝑚$ を与えたときの $𝑌 𝑛$ の分布は，定義 8.1.1 より密度 $\prod 𝑖 𝑔 𝑐 (𝑚) 𝑖, 𝑁 (𝑦 𝑖)$ をもつ． $M s g$ は $𝑀$ 個の値を等確率でとるから，どの直方体 $𝐽$ についても

P r [𝑌 𝑛 \in 𝐽] = 1 𝑀 𝑀 \sum 𝑚 = 1 \int 𝐽 𝑛 - 1 \prod 𝑖 = 0 𝑔 𝑐 (𝑚) 𝑖, 𝑁 (𝑦 𝑖) 𝑑 𝑦 𝑛

であり，右辺は補題 8.3.3 の $¯ 𝑞$ を $𝑎 𝑚 : = 𝑐 (𝑚)$ ， $𝑘 : = 𝑛$ ととったものの $𝐽$ の上での積分である．よって定義 7.1.1 の意味で $𝑌 𝑛$ の密度はこの $¯ 𝑞$ であり，補題 8.3.3 より $ℎ (𝑌 𝑛)$ と各 $ℎ (𝑌 𝑖)$ は定まって

𝔼 [𝑌 2 𝑖] = 𝑁 + 1 𝑀 𝑀 \sum 𝑚 = 1 (𝑐 (𝑚) 𝑖) 2

である．以下この値を $𝜎 2 𝑖$ と書く． $𝑁 > 0$ より $𝜎 2 𝑖 > 0$ である．

成分ごとに抑える．補題 8.3.3 より $𝑌 𝑖$ は密度をもち， $ℎ (𝑌 𝑖)$ は定まる． $𝔼 [𝑌 2 𝑖]$ が有限だから $| 𝑡 | \leq (1 + 𝑡 2) / 2$ より $𝑌 𝑖$ は平均をもち，その分散は $𝔼 [𝑌 2 𝑖] - 𝔼 [𝑌 𝑖] 2 \leq 𝜎 2 𝑖$ である．よって定理 7.2.4 より $ℎ (𝑌 𝑖) \leq 12 l o g (2 𝜋 𝑒 𝜎 2 𝑖)$ である．

和を抑える．定理 7.4.3 の劣加法性より $ℎ (𝑌 𝑛) \leq \sum 𝑖 ℎ (𝑌 𝑖) \leq \sum 𝑖 12 l o g (2 𝜋 𝑒 𝜎 2 𝑖)$ である．補題 1.1.9 を，凹関数 $l o g$ （補題 1.1.6 による），重み $𝑤 𝑖 = 1 / 𝑛$ ，点 $𝑡 𝑖 = 2 𝜋 𝑒 𝜎 2 𝑖 > 0$ ととって当てると

1 𝑛 𝑛 - 1 \sum 𝑖 = 0 l o g (2 𝜋 𝑒 𝜎 2 𝑖) \leq l o g (1 𝑛 𝑛 - 1 \sum 𝑖 = 0 2 𝜋 𝑒 𝜎 2 𝑖)

である．電力制約より

1 𝑛 𝑛 - 1 \sum 𝑖 = 0 𝜎 2 𝑖 = 𝑁 + 1 𝑛 𝑀 𝑀 \sum 𝑚 = 1 𝑛 - 1 \sum 𝑖 = 0 (𝑐 (𝑚) 𝑖) 2 \leq 𝑁 + 1 𝑛 𝑀 \cdot 𝑀 \cdot 𝑛 𝑃 = 𝑁 + 𝑃

である．補題 8.2.5 より $l o g$ は単調だから，上の二つを合わせて

ℎ (𝑌 𝑛) \leq 𝑛 2 \cdot 1 𝑛 𝑛 - 1 \sum 𝑖 = 0 l o g (2 𝜋 𝑒 𝜎 2 𝑖) \leq 𝑛 2 l o g (2 𝜋 𝑒 (𝑃 + 𝑁))

を得る． $◻$

補題 8.3.4 の二つの不等号は，別のことを言っている．劣加法性のほうは， $𝑛$ 回の使用をまとめて見たときの散らばりが， $1$ 回ずつ見たときの和を超えないことである．捨てているのは，出力の成分 $𝑌 0, \dots, 𝑌 𝑛 - 1$ のあいだの依存で，符号語が時刻をまたいで作る相関はそこに現れる．補題 1.1.9 のほうは，各時刻の分散を平均で置き換えて上から抑えている段で，成分ごとの偏りをここで捨てている．どちらも $\leq$ の向きが逆定理に必要な向きにそろっている． $l o g$ の凹性が上から抑える向きに効くのは，8.2 節の例 8.2.6 で「薄く広げるほうが $Φ$ を大きくする」ことを見たのと同じ形である．

逆定理

定理 8.3.5（ガウス通信路の逆定理）. $𝑁 > 0$ ， $𝑃 > 0$ ， $𝑀 \geq 2$ ， $𝑛 \geq 1$ とし，長さ $𝑛$ ，電力 $𝑃$ のブロック通信路符号（定義 8.3.1）をとる．メッセージが ${1, \dots, 𝑀}$ 上の一様分布に従うとしたときの平均誤り確率を $¯ 𝑃 𝑒$ とすると

l o g 𝑀 \leq 𝑛 2 l o g (1 + 𝑃 𝑁) + 𝐻 𝑏 (¯ 𝑃 𝑒) + ¯ 𝑃 𝑒 l o g (𝑀 - 1)

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

証明. 借りた単発逆定理を， $𝑘 : = 𝑛$ ， $𝑉 : = 𝑌 𝑛$ ， $𝑞 𝑚 (𝑦) : = \prod 𝑖 𝑔 𝑐 (𝑚) 𝑖, 𝑁 (𝑦 𝑖)$ ととって当てる．仮定を確かめる． $M s g = 𝑚$ を与えたときの $𝑌 𝑛$ の分布が $𝑞 𝑚$ を密度にもつことは定義 8.1.1 そのものであり， $𝑌 𝑛$ が密度をもって $ℎ (𝑌 𝑛)$ が定まることは補題 8.3.4 で見た．復号器 $𝑑$ が各 $𝑚$ について $𝑞 𝑚$ を集合 ${𝑦 𝑛 : 𝑑 (𝑦 𝑛) \neq 𝑚}$ の上で積分できることは，定義 8.3.1 が $𝑚' = 𝑚$ の場合として求めている条件である．

各 $ℎ 𝑚$ を求める．7.4 節で借りた独立と積の密度により， $𝑞 𝑚$ を密度にもつ確率変数の成分は独立で，第 $𝑖$ 成分は $𝑔 𝑐 (𝑚) 𝑖, 𝑁$ を密度にもつ．定理 7.2.2 より各成分の微分エントロピーは定まって $12 l o g (2 𝜋 𝑒 𝑁)$ だから，系 7.4.4 より

ℎ 𝑚 = 𝑛 - 1 \sum 𝑖 = 0 12 l o g (2 𝜋 𝑒 𝑁) = 𝑛 2 l o g (2 𝜋 𝑒 𝑁)

である．これは $𝑚$ によらないので， $1 𝑀 \sum 𝑚 ℎ 𝑚$ も同じ値である．

誤り確率を読み替える．メッセージが一様分布に従うとき $P r [𝑑 (𝑌 𝑛) \neq M s g]$ は，メッセージごとの誤り確率を一様な重み $1 / 𝑀$ で平均したものだから，定義 8.3.1 の平均誤り確率 $¯ 𝑃 𝑒$ に一致する．

以上を借りた単発逆定理に入れると

l o g 𝑀 \leq ℎ (𝑌 𝑛) - 𝑛 2 l o g (2 𝜋 𝑒 𝑁) + 𝐻 𝑏 (¯ 𝑃 𝑒) + ¯ 𝑃 𝑒 l o g (𝑀 - 1)

である．補題 8.3.4 より $ℎ (𝑌 𝑛) \leq 𝑛 2 l o g (2 𝜋 𝑒 (𝑃 + 𝑁))$ だから，第 $1$ 項と第 $2$ 項の差は

𝑛 2 l o g (2 𝜋 𝑒 (𝑃 + 𝑁)) - 𝑛 2 l o g (2 𝜋 𝑒 𝑁) = 𝑛 2 l o g 𝑃 + 𝑁 𝑁

以下であり，右辺は $𝑛 2 l o g (1 + 𝑃 / 𝑁)$ である． $◼$

形式化: awgn_converse (ソース)

形式化上の注記. 形式化の awgn_converse は，本文と同じ不等式を無条件に与える．仮定は本文と一つずつ対応していて，符号が AwgnCode であることが定義 8.3.1 の電力制約と可測性に，メッセージ数が $2$ 以上であることが本文の $𝑀 \geq 2$ に，長さが正であることが $𝑛 \geq 1$ に，雑音の分散が $0$ でないことが本文の $𝑁 > 0$ に，平均誤り確率の等式が本文の $¯ 𝑃 𝑒$ にあたる．本文に対して真に増えている条件は，核が可測であるという正則性のもの一つだけで，これは同じ名前空間の isAwgnChannelMeasurable (InformationTheory/Shannon/AWGN/ChannelMeasurability.lean) が与えるので，実際には条件になっていない．形式化は $l o g$ を自然対数にとるので単位はナットであり，本文が底を $2$ にとったのと単位の名前だけが違う．

証明のルートは本文と食い違う．本文は，実数値の観測についてのファノの不等式を単発逆定理としてまとめて借り，そこから出る $ℎ (𝑌 𝑛) - 1 𝑀 \sum 𝑚 ℎ 𝑚$ を微分エントロピーの劣加法性（定理 7.4.3）で成分ごとにほどいた．形式化は劣加法性をまったく通らない．離散のファノの不等式をメッセージと復号結果に当て，データ処理不等式でメッセージと出力の相互情報量に移し，相互情報量のチェイン則と記憶のなさで各時刻の相互情報量の和に落とし，各時刻の相互情報量を出力の微分エントロピーと雑音の微分エントロピーの差に書き換え（awgn_per_letter_mi_bridge_genuine (InformationTheory/Shannon/AWGN/Converse.lean)），最大エントロピー性と Jensen の不等式で抑える．保証されているのは定理 8.3.5 の不等式そのもので，そこに至る手順ではない．

左辺が誰のものかを見る. 第6章定理 6.4.1 のときと同じで，左辺の $l o g 𝑀$ は符号を設計する側が決める量である．右辺の第 $1$ 項が通信路と電力制約で決まる量，残る $2$ 項が誤りで説明のつく量である．両辺を $𝑛$ で割ってから誤り確率を $0$ に近づけると，レートが上に有界でありさえすれば後ろの $2$ 項は消える（そこは系 8.3.6 で確かめる）．すると $1 𝑛 l o g 𝑀$ をすべて $12 l o g (1 + 𝑃 / 𝑁)$ が支えなければならず，レートが $12 l o g (1 + 𝑃 / 𝑁)$ を超えられないという主張になる．

弱逆定理

系 8.3.6（弱逆定理）. $𝑁 > 0$ ， $𝑃 > 0$ とする．長さ $𝑛$ ，電力 $𝑃$ のブロック通信路符号を第 $𝑛$ 項とする族 $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛) 𝑛 \geq 1$ が定義 8.3.2 の意味で達成可能なら，その達成レートは $12 l o g (1 + 𝑃 / 𝑁)$ 以下である．すなわち $R (𝑃, 𝑁)$ のどの元も $12 l o g (1 + 𝑃 / 𝑁)$ を超えない．

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

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

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

$𝑀 𝑛 = 1$ の項を片付ける. そのような $𝑛$ では $𝑅 𝑛 = 0$ である． $𝑃 > 0$ と $𝑁 > 0$ より $1 + 𝑃 / 𝑁 > 1$ であり，補題 8.2.5 より $12 l o g (1 + 𝑃 / 𝑁) > 0$ である．よって $𝑅 𝑛 \leq 12 l o g (1 + 𝑃 / 𝑁) + 𝛿 𝑛$ が成り立つ．残る $𝑛$ では $𝑀 𝑛 \geq 2$ である．

定理 8.3.5 を当てる. $𝑀 𝑛 \geq 2$ の $𝑛$ について定理 8.3.5 より

l o g 𝑀 𝑛 \leq 𝑛 2 l o g (1 + 𝑃 𝑁) + 𝐻 𝑏 (¯ 𝑃 (𝑛) 𝑒) + ¯ 𝑃 (𝑛) 𝑒 l o g (𝑀 𝑛 - 1)

である． $𝑀 𝑛 \geq 2$ より $l o g (𝑀 𝑛 - 1) \leq l o g 𝑀 𝑛 = 𝑛 𝑅 𝑛$ だから， $𝑛$ で割って

𝑅 𝑛 \leq 12 l o g (1 + 𝑃 𝑁) + 𝐻 𝑏 (¯ 𝑃 (𝑛) 𝑒) 𝑛 + ¯ 𝑃 (𝑛) 𝑒 𝑅 𝑛 = 12 l o g (1 + 𝑃 𝑁) + 𝛿 𝑛

を得る．

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

形式化上の注記. 系 8.3.6 に対応する単独の宣言はない．達成レートの集合そのものに対応する宣言が通信路の側に用意されていないので，この主張は形式化の外にある．機械検証が及んでいるのは，各 $𝑛$ についての不等式である定理 8.3.5 に紐付けた宣言までで，補正項が消える段（第6章補題 6.4.7 にあたる部分）は形式化されていない．

系 8.3.6 が言えたので，あとは逆向き，すなわち $12 l o g (1 + 𝑃 / 𝑁)$ 未満のレートが実際に達成できることを示せば，8.2 節で最大化問題の値として定めた $𝐶 (𝑃, 𝑁)$ に操作的な意味が付く．それが 8.4 節の内容である．

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