6.1 通信路と通信路容量

第2章と第3章は，情報源のもつ冗長さを取り除く話だった．同じ内容をより短く書けるのはどこまでか．その限界がエントロピーだった．本章で扱うのは逆向きの操作である．通信路は送った記号を確率的に取り違えるので，受け取った側が誤りを直せるように，送る側があらかじめ冗長さを足す．足しすぎれば運べる情報が減り，足りなければ誤りが残る．この綱引きの決着がどこにつくかが本章の主題である．

素朴に考えると，雑音のある通信路では誤り確率を 0 に近づけようとするたびに伝送速度が0 に落ちそうに思える．同じ記号を何度も繰り返して多数決をとれば誤りは減らせるが，繰り返した回数だけ速度は落ちる．Shannon の発見は，そうはならないということである．通信路ごとにある数 $𝐶$ が定まっていて， $𝐶$ より小さい速度である限り，誤り確率はいくらでも 0 に近づけられる．本節ではその $𝐶$ （通信路容量）を定義し，それが上限ではなく最大値として達成されることを示し，二つの通信路で値を計算する．

本章では $l o g$ の底を 2 にとる．第2章・第3章と同じく $2 𝑛 𝑅$ の形の量を扱うので，指数と対数の底をそろえておくと式が読みやすい．

形式化上の注記（本章共通）

単位は本文と形式化で違う．形式化は $l o g$ を自然対数にとるので，相互情報量も容量もナットが単位であり，本文が $2 𝑛 𝑅$ と書く量はあちらでは $e x p (𝑛 𝑅)$ にあたる．底をそろえれば同じ主張である．

形式化の Channel は条件付き分布の族そのもの（各入力に対して出力の分布を返す核）であって，各入力についての総和が 1 という条件は含まない．その条件は，Channel を使う主張の側に別の前提として付いている．

通信路と，その相互情報量

定義 6.1.1（離散無記憶通信路）. 入力アルファベット $X$ と出力アルファベット $Y$ はどちらも有限とし， $X$ は空でないとする．通信路 とは，各 $𝑥 \in X$ に対して $Y$ 上の分布 $𝑊 (\cdot ∣ 𝑥)$ を与える対応である．すなわち $𝑊 (𝑦 ∣ 𝑥) \geq 0$ であって，各 $𝑥$ について $\sum 𝑦 \in Y 𝑊 (𝑦 ∣ 𝑥) = 1$ を満たす．長さ $𝑛$ の入力 $𝑥 𝑛 = (𝑥 0, \dots, 𝑥 𝑛 - 1)$ に対する出力の分布が

𝑊 𝑛 (𝑦 𝑛 ∣ 𝑥 𝑛) = 𝑛 - 1 \prod 𝑖 = 0 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖)

で与えられるとき，この通信路を 記憶のない（memoryless）通信路 という．アルファベットが有限なので，これを 離散無記憶通信路 とも呼ぶ． $X$ 上の分布 $𝑝$ を入力に与えたときの入力と出力の 結合分布 を $𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ ，その第 2 成分の周辺分布 $𝑞 (𝑦) : = \sum 𝑥 𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ を出力分布 と呼ぶ．

$𝑊 (𝑦 ∣ 𝑥)$ は「 $𝑥$ を送ったときに $𝑦$ が受け取られる確率」である．通信路が定めるのはこの条件付き分布だけで，何を送るかは通信路の側では決まっていない．入力分布 $𝑝$ を与えてはじめて入力と出力が対になり，結合分布と出力分布が定まる．積の形の条件が言っているのは，各時刻の雑音がそれ以前の入出力に一切依存しない，ということである．これが「記憶のない」の内容で，第3章の記憶のある情報源とちょうど逆向きの仮定になっている．あちらは情報源に記憶があってよかったが，こちらは通信路に記憶がない．

形式化: Channel，結合分布 jointDistribution，出力分布 outputDistribution (ソース)

いちばん小さい通信路で確かめる. $X = Y = {0, 1}$ とし，送ったビットが確率 $0.1$ で反転する通信路を考える．遷移確率は

𝑊 (0 ∣ 0) = 𝑊 (1 ∣ 1) = 0.9, 𝑊 (1 ∣ 0) = 𝑊 (0 ∣ 1) = 0.1

である．同じ入力に対する二つの値の和が 1 になっていることが定義 6.1.1 の条件で，同じ出力に対する和には何の条件もない．通信路が定めるのは入力ごとの分布だからである．ここに入力分布 $𝑝 (0) = 𝑝 (1) = 1 / 2$ を与えると，結合分布は $(0, 0)$ と $(1, 1)$ に $0.45$ ， $(0, 1)$ と $(1, 0)$ に $0.05$ を置き，出力分布は $𝑞 (0) = 𝑞 (1) = 1 / 2$ になる．この通信路は，反転する確率を一般の値にした形で例 6.1.8 にふたたび現れる．

定義 6.1.2（通信路の相互情報量）. $X$ 上の分布 $𝑝$ と通信路 $𝑊$ に対し，出力分布を $𝑞 (𝑦) : = \sum 𝑥 𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ とおく．入力分布 $𝑝$ のもとでの $𝑊$ の相互情報量 を

𝐼 (𝑝; 𝑊) : = \sum 𝑥, 𝑦 𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥) l o g 𝑊 (𝑦 ∣ 𝑥) 𝑞 (𝑦)

で定める．和は $𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥) > 0$ の項についてとる．

対数の中身 $𝑊 (𝑦 ∣ 𝑥) / 𝑞 (𝑦)$ は，「 $𝑥$ が送られたと知ることで， $𝑦$ が受け取られるという見込みが何倍になったか」である．何を送っても出力の分布が変わらない通信路（雑音が入力を完全に潰してしまう通信路）では，この比が全点で 1 になって $𝐼 (𝑝; 𝑊) = 0$ になる．逆に $𝑥$ ごとに出力の分布がはっきり違えば比は 1 から離れ， $𝐼 (𝑝; 𝑊)$ は大きくなる．1.3 節の言葉でいえば， $𝐼 (𝑝; 𝑊)$ は入力と出力が独立からどれだけ隔たっているかを一つの数にまとめた量である．

形式化: mutualInfoOfChannel (ソース)

定義 6.1.2 は通信路の側から書いた式で，第1章の相互情報量とは見た目が違う．両者が同じものであることを先に確かめておく．

命題 6.1.3. $X$ 上の分布 $𝑝$ と通信路 $𝑊$ をとり， $(𝑋, 𝑌)$ を結合分布 $𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ に従う対とする．このとき

𝐼 (𝑝; 𝑊) = 𝐼 (𝑋; 𝑌) = 𝐻 (𝑋) + 𝐻 (𝑌) - 𝐻 (𝑋, 𝑌) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋) = 𝐻 (𝑋) - 𝐻 (𝑋 ∣ 𝑌) .

証明. $(𝑋, 𝑌)$ の同時分布は $𝑝 (𝑥, 𝑦) = 𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ であり，その周辺分布は $\sum 𝑦 𝑝 (𝑥, 𝑦) = 𝑝 (𝑥)$ と $\sum 𝑥 𝑝 (𝑥, 𝑦) = 𝑞 (𝑦)$ である．和をとる範囲 $𝑝 (𝑥, 𝑦) > 0$ では $𝑝 (𝑥) > 0$ なので約分してよく，定義 1.3.1 の対数の中身は

𝑝 (𝑥, 𝑦) 𝑝 (𝑥) 𝑞 (𝑦) = 𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥) 𝑝 (𝑥) 𝑞 (𝑦) = 𝑊 (𝑦 ∣ 𝑥) 𝑞 (𝑦)

になる．したがって定義 6.1.2 の右辺は定義 1.3.1 の右辺そのもので， $𝐼 (𝑝; 𝑊) = 𝐼 (𝑋; 𝑌)$ である．残る三つの等式は，この対 $(𝑋, 𝑌)$ に定理 1.3.4 を当てたものである． $◼$

形式化: 結合分布の相互情報量との一致 mutualInfoOfChannel_eq_mutualInfo_prod，三つのエントロピーの差の形 mutualInfoOfChannel_eq_HX_add_HY_sub_HZ (ソース)，出力の不確かさから雑音の分を引いた形 mutualInfoOfChannel_toReal_eq_outputEntropy_sub (ソース)

注記

最後の等式 $𝐻 (𝑋) - 𝐻 (𝑋 ∣ 𝑌)$ に対応する単独の宣言はない．定理 1.3.4 の形式化との合成で得られる．

雑音の分だけ減る，と読む. 以下でいちばん使うのは $𝐼 (𝑝; 𝑊) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋)$ の形である． $𝐻 (𝑌)$ は受け取った側から見た出力の不確かさ， $𝐻 (𝑌 ∣ 𝑋)$ は何を送ったかを知ってもなお残る不確かさ，すなわち雑音そのものの不確かさである．運べた情報とは，出力の不確かさから雑音の分を差し引いた残りだ，と読める．送る側に選べるのは $𝑝$ だけで， $𝑝$ を動かせば $𝐻 (𝑌)$ も $𝐻 (𝑌 ∣ 𝑋)$ も動く．その中で差を最大にする $𝑝$ を探す，というのが次の定義である．

通信路容量

定義 6.1.4（通信路容量）. 通信路 $𝑊$ の 通信路容量 を，入力分布全体にわたる上限

𝐶 (𝑊) : = s u p 𝑝 𝐼 (𝑝; 𝑊)

で定める． $𝑝$ は $X$ 上の分布全体，すなわち $𝑝 (𝑥) \geq 0$ かつ $\sum 𝑥 𝑝 (𝑥) = 1$ を満たす関数の全体を動く．

形式化: capacity (ソース)

$𝐶 (𝑊)$ は通信路だけで決まる数で，入力分布にも符号にも依存しない．定義の時点では「1 回の使用あたりどれだけ運べるか」という操作的な意味はまだ持っておらず，単に相互情報量の最大化問題の値でしかない．それが誤りなく送れるレートの限界と一致する，というのが 6.3 節以降の内容である．

上限と書いたが，実際には最大値である．それを示すには， $𝐼 (\cdot; 𝑊)$ が入力分布のつくる集合の上で連続であることと，その集合が有界閉集合であることの二つが要る．前者は，一次結合・合成・有限和が連続性を保つという微積分の計算規則と，補題 1.1.8 が示した $𝜑 (𝑡) = - 𝑡 l o g 𝑡$ の $[0, \infty)$ 上の連続性から下で組み立てる（計算規則のほうは既知とする）．後者から最大値の存在を引き出すために，次の一つを証明せずに借りる．

Weierstrass の最大値定理を借りる. 借りるのは「有限次元の実ベクトル空間の空でない有界閉集合の上の実数値連続関数は最大値をとる」という形である．当てる相手は，実ベクトル空間 $ℝ X$ の部分集合である確率単体

Δ : = {𝑝 : X \to ℝ ∣ 𝑝 (𝑥) \geq 0 (\forall 𝑥 \in X), \sum 𝑥 𝑝 (𝑥) = 1}

の上の実数値関数である．この借用に依存するのは定理 6.1.5 と，同じ最大値定理を 9.1 節で借り直している第9章命題 9.1.8，11.5 節で借り直している第11章命題 11.5.7・定理 11.6.2，および 15.2 節で借り直している第15章命題 15.2.2・命題 15.8.5 である．本章の以降の節と，第12章定理 12.3.4 が事前分布について最大値をとるところは，定理 6.1.5 の結論だけを使う．借り直した先が当てる相手は，確率単体 $Δ$ そのものではない．第9章は実ベクトル空間 $ℝ X \times ˆ X$ の部分集合である制約集合に，第11章は $ℝ$ の閉区間 $[0, 1]$ と，確率単体の閉部分集合とに，第15章は銘柄の番号の上の確率単体，すなわち $ℝ 𝑚$ の部分集合であるポートフォリオ全体に当てる．本書はこの最大値定理を証明しないが，形式化されていないわけではない．定理 6.1.5 の形式化は，Mathlib にある無条件の機械検証済みのこの定理をそのまま呼び出しているからである．「本書で証明しない」ことと「形式化されていない」ことは別である．

定理 6.1.5. $𝑊$ を通信路（定義 6.1.1）とし， $X$ 上の分布全体のなす集合を $Δ$ と書く．このとき $𝑝 \mapsto 𝐼 (𝑝; 𝑊)$ は $Δ$ の上で連続であり， $𝐼 (\cdot; 𝑊)$ を最大にする入力分布 $𝑝 * \in Δ$ が存在して $𝐶 (𝑊) = 𝐼 (𝑝 *; 𝑊)$ である．

証明. 連続性から示す． $(𝑋, 𝑌)$ を結合分布 $𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ に従う対とすると，命題 6.1.3 より $𝐼 (𝑝; 𝑊) = 𝐻 (𝑋) + 𝐻 (𝑌) - 𝐻 (𝑋, 𝑌)$ である．三つの項を $𝑝$ の関数として書き下すと

𝐻 (𝑋) = \sum 𝑥 𝜑 (𝑝 (𝑥)), 𝐻 (𝑌) = \sum 𝑦 𝜑 (\sum 𝑥 𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)), 𝐻 (𝑋, 𝑌) = \sum 𝑥, 𝑦 𝜑 (𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥))

となる．どの項も， $𝑝$ の成分の一次結合に $𝜑$ を合成したものの有限和である．一次結合は連続で， $𝜑$ は $[0, \infty)$ 上で連続だから， $𝑝 \mapsto 𝐼 (𝑝; 𝑊)$ は $Δ$ の上で連続である．

最大値の存在に移る． $Δ$ は $ℝ X$ の有界閉集合である（有界性は $0 \leq 𝑝 (𝑥) \leq 1$ から，閉であることは定義が等式と不等式で書けていることから従う）．よって借用した Weierstrass の最大値定理により， $𝐼 (\cdot; 𝑊)$ は $Δ$ の上で最大値をとる．それを与える点を $𝑝 *$ とする．

最後に $𝐶 (𝑊) = 𝐼 (𝑝 *; 𝑊)$ を見る． $𝐼 (𝑝 *; 𝑊)$ は値の集合 ${𝐼 (𝑝; 𝑊) : 𝑝 \in Δ}$ の上界であり，かつその集合の元でもある．上限は上界のうち最小のものだから，この二つから $𝐶 (𝑊) = 𝐼 (𝑝 *; 𝑊)$ である． $◼$

形式化: 連続性 continuous_mutualInfoOfChannel_left，最大化する入力分布の存在exists_capacity_achiever (ソース)

注記

等号 $𝐶 (𝑊) = 𝐼 (𝑝 *; 𝑊)$ に対応する単独の宣言はない．容量が上限として定義されていることcapacity と，その値の集合が上に有界であること capacity_bddAbove (InformationTheory/Shannon/ChannelCoding/ShannonTheorem.lean) との合成で得られる．

命題 6.1.6. 任意の通信路 $𝑊$ に対し $𝐶 (𝑊) \geq 0$ ．

証明. 定理 6.1.5 の $𝑝 *$ をとると $𝐶 (𝑊) = 𝐼 (𝑝 *; 𝑊)$ であり，命題 6.1.3 よりこれは対 $(𝑋, 𝑌)$ の相互情報量 $𝐼 (𝑋; 𝑌)$ に等しい．命題 1.3.2 よりそれは非負である． $◼$

形式化: capacity_nonneg (ソース)

命題 6.1.7. 任意の通信路 $𝑊$ に対し $𝐶 (𝑊) \leq l o g m i n (| X |, | Y |)$ ．

証明. 任意の入力分布 $𝑝$ をとり， $(𝑋, 𝑌)$ を結合分布に従う対とする．命題 6.1.3 より $𝐼 (𝑝; 𝑊) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋)$ であり，条件付きエントロピーは非負量の平均なので非負（定義 1.2.2 と命題 1.1.4）．よって $𝐼 (𝑝; 𝑊) \leq 𝐻 (𝑌)$ で，定理 1.1.5 より $𝐻 (𝑌) \leq l o g | Y |$ である．同じことを命題 6.1.3 のもう一つの形 $𝐼 (𝑝; 𝑊) = 𝐻 (𝑋) - 𝐻 (𝑋 ∣ 𝑌)$ で行えば $𝐼 (𝑝; 𝑊) \leq l o g | X |$ を得る． $𝑝$ は任意だったので， $l o g m i n (| X |, | Y |)$ は値の集合の上界であり，上限はそれ以下である． $◼$

読み方は素直である．1 回の使用で運べる情報は，入れ物の大きさを超えられない．送れる記号が $| X |$ 通りしかなければ，雑音がまったくなくても 1 回あたり $l o g | X |$ より多くは運べないし，受け取る側の区別が $| Y |$ 通りしかないなら同じことが出口の側で起きる．命題 6.1.7 は，容量が雑音の少なさだけでなく，入口と出口の狭いほうにも押さえられていることを言っている．

形式化上の注記

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

二つの通信路で計算する

例 6.1.8（二元対称通信路）. $𝜌 \in [0, 1]$ を固定する． $X = Y = {0, 1}$ とし，

𝑊 (1 ∣ 0) = 𝑊 (0 ∣ 1) = 𝜌, 𝑊 (0 ∣ 0) = 𝑊 (1 ∣ 1) = 1 - 𝜌

で定まる通信路を，反転確率 $𝜌$ の 二元対称通信路 という．送ったビットが確率 $𝜌$ で反転し，確率 $1 - 𝜌$ でそのまま届く通信路である（図 6.1.1）．その容量は

𝐶 (𝑊) = 1 - 𝐻 𝑏 (𝜌)

であり，一様入力 $𝑝 (0) = 𝑝 (1) = 1 / 2$ で達成される（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．さらに，どの入力分布 $𝑝$ についても， $𝜋 : = 𝑝 (1)$ とおくと

𝐼 (𝑝; 𝑊) = 𝐻 𝑏 ((1 - 𝜌) 𝜋 + 𝜌 (1 - 𝜋)) - 𝐻 𝑏 (𝜌)

である．

図 6.1.1. 反転確率 $𝜌$ の二元対称通信路．左が入力 $𝑋$ ，右が出力 $𝑌$ で，矢印に添えた数がその遷移の確率である．

証明. まず $𝐻 (𝑌 ∣ 𝑋)$ が入力分布によらないことを見る． $𝑋 = 𝑥$ を固定すると， $𝑌$ は確率 $1 - 𝜌$ で $𝑥$ ，確率 $𝜌$ で $𝑥$ の反対をとるので，その分布のエントロピーは $𝑥$ によらず $𝐻 𝑏 (𝜌)$ である．定義 1.2.2 はこれを $𝑝 (𝑥)$ で平均したものだから，どんな入力分布 $𝑝$ に対しても $𝐻 (𝑌 ∣ 𝑋) = 𝐻 𝑏 (𝜌)$ である．

次に $𝐼 (𝑝; 𝑊)$ を入力分布の式で書く． $𝜋 : = 𝑝 (1)$ とおくと

𝑞 (1) = 𝑝 (0) 𝑊 (1 ∣ 0) + 𝑝 (1) 𝑊 (1 ∣ 1) = (1 - 𝜋) 𝜌 + 𝜋 (1 - 𝜌)

であり， $𝑞 (0) = 1 - 𝑞 (1)$ である． $𝑌$ は二つの値しかとらないから例 1.1.2 より $𝐻 (𝑌) = 𝐻 𝑏 (𝑞 (1))$ であり，命題 6.1.3 より $𝐼 (𝑝; 𝑊) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋) = 𝐻 𝑏 (𝑞 (1)) - 𝐻 𝑏 (𝜌)$ となって，主張の一般の式を得る．

上界はここから出る． $| Y | = 2$ に定理 1.1.5 を当てると $𝐻 (𝑌) \leq l o g 2 = 1$ だから $𝐼 (𝑝; 𝑊) \leq 1 - 𝐻 𝑏 (𝜌)$ である．最後にこれが達成されることを見る． $𝑝 (0) = 𝑝 (1) = 1 / 2$ とすると $𝜋 = 1 / 2$ で $𝑞 (1) = 12 𝜌 + 12 (1 - 𝜌) = 12$ であり，出力は一様だから例 1.1.2 より $𝐻 (𝑌) = 𝐻 𝑏 (1 / 2) = l o g 2 = 1$ で， $𝐼 (𝑝; 𝑊) = 1 - 𝐻 𝑏 (𝜌)$ に等しい．上界が達成されたので，定義 6.1.4 の上限はこの値である． $◼$

形式化上の注記

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

例 6.1.9（二元消失通信路）. $𝜂 \in [0, 1]$ を固定する． $X = {0, 1}$ ， $Y = {0, 1, *}$ とし，

𝑊 (𝑥 ∣ 𝑥) = 1 - 𝜂, 𝑊 (* ∣ 𝑥) = 𝜂, 𝑊 (1 - 𝑥 ∣ 𝑥) = 0 (𝑥 \in {0, 1})

で定まる通信路を，消失確率 $𝜂$ の 二元消失通信路 という．送ったビットは確率 $1 - 𝜂$ でそのまま届き，確率 $𝜂$ で「読めなかった」ことを示す記号 $*$ に化ける．反転して届くことはない（図 6.1.2）．その容量は

𝐶 (𝑊) = 1 - 𝜂

であり（二元対称通信路の容量との比較は図 6.1.3），一様入力 $𝑝 (0) = 𝑝 (1) = 1 / 2$ で達成される．さらに，どの入力分布 $𝑝$ についても， $𝜋 : = 𝑝 (1)$ とおくと $𝐼 (𝑝; 𝑊) = (1 - 𝜂) 𝐻 𝑏 (𝜋)$ である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー）．

図 6.1.2. 消失確率 $𝜂$ の二元消失通信路．出力の $*$ は読めなかったことを示す記号で， $0$ と $1$ が入れ替わる遷移はない．

証明. 入力分布 $𝑝$ を任意にとり， $𝜋 : = 𝑝 (1)$ とおく．二元対称通信路のときと同じく， $𝑋 = 𝑥$ を固定したときの $𝑌$ の分布は「確率 $1 - 𝜂$ で $𝑥$ ，確率 $𝜂$ で $*$ 」で，そのエントロピーは $𝑥$ によらず $𝐻 𝑏 (𝜂)$ である．よって $𝐻 (𝑌 ∣ 𝑋) = 𝐻 𝑏 (𝜂)$ ．

出力分布は $𝑞 (0) = (1 - 𝜋) (1 - 𝜂)$ ， $𝑞 (1) = 𝜋 (1 - 𝜂)$ ， $𝑞 (*) = 𝜂$ である．定義 1.1.1 に代入し， $l o g$ の積を和に分けると

𝐻 (𝑌) = - (1 - 𝜂) (𝜋 l o g 𝜋 + (1 - 𝜋) l o g (1 - 𝜋)) - (1 - 𝜂) l o g (1 - 𝜂) - 𝜂 l o g 𝜂 = (1 - 𝜂) 𝐻 𝑏 (𝜋) + 𝐻 𝑏 (𝜂)

となる（確率 0 の項は $0 l o g 0 = 0$ の約束により両辺で消えるので，分け方に注意は要らない）．命題 6.1.3 より

𝐼 (𝑝; 𝑊) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋) = (1 - 𝜂) 𝐻 𝑏 (𝜋)

である．例 1.1.2 より $𝐻 𝑏 (𝜋) \leq l o g 2 = 1$ だから $𝐼 (𝑝; 𝑊) \leq 1 - 𝜂$ であり，一様入力 $𝜋 = 1 / 2$ ではこの値が達成される．上界が達成されたので，定義 6.1.4 の上限はこの値である． $◼$

図 6.1.3. 二元対称通信路の容量 $1 - 𝐻 𝑏 (𝜌)$ と，二元消失通信路の容量 $1 - 𝜂$ ．横軸は反転確率 $𝜌$ または消失確率 $𝜂$ である．

形式化上の注記

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

二つを数で比べる. 反転確率 $𝜌 = 0.1$ の二元対称通信路の容量は $1 - 𝐻 𝑏 (0.1) \approx 0.531$ ビットである．いっぽう消失確率 $𝜂 = 0.1$ の二元消失通信路は $1 - 0.1 = 0.9$ ビットで，こちらのほうがずっと大きい．どちらも10 回に 1 回は届いた記号が信用できないのに，差がこれだけ開くのは，どこが壊れたかを受け取る側が知っているかどうかの違いによる．消失通信路では壊れた位置が $*$ として見えるので，残りの $9$ 割はそのまま信用してよい．対称通信路では壊れた位置が見えないので，届いたビットのどれもが疑わしくなる．反転確率を $0.11$ まで上げると容量は約 $0.500$ ビットになり，雑音がないときの 1 ビットのちょうど半分に落ちる．

両端で確かめる. 二元対称通信路で $𝜌 = 0$ なら $𝐻 𝑏 (0) = 0$ で容量は 1 ビットである．雑音がないので 1 回に 1 ビット運べる． $𝜌 = 1$ でも $𝐻 𝑏 (1) = 0$ なので容量はやはり 1 ビットで，これは「必ず反転する」通信路が受け取る側で読み替えれば無雑音と同じだからである．いちばん悪いのは $𝜌 = 1 / 2$ で， $𝐻 𝑏 (1 / 2) = 1$ より容量は 0 になる．このとき出力は入力に依らず一様で，何も運べない．二元消失通信路のほうは $𝜂 = 0$ で1 ビット， $𝜂 = 1$ で 0 ビットと，消失確率にそのまま比例して減る．

容量を達成する入力分布 $𝑝 *$ は定理 6.1.5 で存在だけが分かっている．それが満たさなければならない条件は 6.6 節で与える（逆向き，つまりその条件を満たせば最大化子であるという主張は扱わない）．二つの例で一様入力が最大化したのは通信路の対称性のおかげで，一般にはそうならない．

情報理論入門（Lean による形式証明つき）・GitHub