1.10 ファノの不等式

$𝑌$ を観測して $𝑋$ を推定（復号）したい． $𝑌$ から $𝑋$ を当てる復号器 $ˆ 𝑋 = 𝑔 (𝑌)$ の誤り確率を $𝑃 𝑒 = P r [ˆ 𝑋 \neq 𝑋]$ とする．直感的に， $𝑋$ に残る不確かさ $𝐻 (𝑋 ∣ 𝑌)$ が大きければ，どんな復号器でも誤りはそう小さくできないはずだ．ファノの不等式はこの直感を定量化する．

ここまでの節との関係でいうと，本章はずっと情報量の不等式を積み上げてきた．しかし最終的に知りたいのは「実際に何回間違えるか」という確率である．ファノの不等式は，その二つを結ぶ唯一の橋である．「 $𝐻 (𝑋 ∣ 𝑌)$ が大きい」という情報量の言明から「 $𝑃 𝑒$ が小さくできない」という確率の言明へ渡れるようになって初めて，通信路符号化の逆定理（容量を超えるレートでは誤りが消えない）が証明できる．橋の向きが片方向であることにも注意したい：不等式は $𝐻 (𝑋 ∣ 𝑌)$ を $𝑃 𝑒$ で上から抑える形をしており，これを裏返して $𝑃 𝑒$ の下界として使うのが実際の用途である．

主張と証明

定理 1.10.1（ファノの不等式）. $| X | \geq 2$ とし， $𝑔 : Y \to X$ を任意の復号器， $ˆ 𝑋 = 𝑔 (𝑌)$ ， $𝑃 𝑒 = P r [ˆ 𝑋 \neq 𝑋]$ とする．このとき

𝐻 (𝑋 ∣ 𝑌) \leq 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (| X | - 1),

ここで $𝐻 𝑏$ は二値エントロピー関数（例 1.1.2）．

右辺を読み解くと， $𝑋$ に残る不確かさは「誤ったか否か」の 1 ビット $𝐻 𝑏 (𝑃 𝑒)$ と，「誤ったとき，残り $| X | - 1$ 個のどれか」の不確かさ $𝑃 𝑒 l o g (| X | - 1)$ で説明しきれる，という上限になっている．裏返せば， $𝐻 (𝑋 ∣ 𝑌)$ が大きいのに $𝑃 𝑒$ を小さく保つことはできない． $𝐻 (𝑋 ∣ 𝑌) \to$ 大なら $𝑃 𝑒$ も下から押し上げられる．

証明. 誤り指示変数 $𝐸 : = 𝟏 [ˆ 𝑋 \neq 𝑋]$ （ $ˆ 𝑋 = 𝑔 (𝑌)$ ）を導入する．これは $P r [𝐸 = 1] = 𝑃 𝑒$ の二値確率変数である．結合量 $𝐻 (𝐸, 𝑋 ∣ 𝑌)$ を， $𝑌$ で条件付けたチェイン則（定理 1.2.3 を $𝑌$ のもとで適用）で二通りに展開する：

𝐻 (𝐸, 𝑋 ∣ 𝑌) = 𝐻 (𝑋 ∣ 𝑌) + 𝐻 (𝐸 ∣ 𝑋, 𝑌) = 𝐻 (𝐸 ∣ 𝑌) + 𝐻 (𝑋 ∣ 𝐸, 𝑌) .

左の展開から見る． $ˆ 𝑋 = 𝑔 (𝑌)$ は $𝑌$ の関数なので， $𝐸 = 𝟏 [𝑔 (𝑌) \neq 𝑋]$ は対 $(𝑋, 𝑌)$ から一意に決まる．決定的な量のエントロピーは 0 だから $𝐻 (𝐸 ∣ 𝑋, 𝑌) = 0$ ，ゆえに $𝐻 (𝐸, 𝑋 ∣ 𝑌) = 𝐻 (𝑋 ∣ 𝑌)$ ．

右の展開は，二項を個別に上から抑える．

$𝐻 (𝐸 ∣ 𝑌) \leq 𝐻 (𝐸)$ ：条件付けは平均エントロピーを増やさない（定理 1.2.4 の基本形）． $𝐸$ は $P r [𝐸 = 1] = 𝑃 𝑒$ の二値なので $𝐻 (𝐸) = 𝐻 𝑏 (𝑃 𝑒)$ ．よって $𝐻 (𝐸 ∣ 𝑌) \leq 𝐻 𝑏 (𝑃 𝑒)$ ．
$𝐻 (𝑋 ∣ 𝐸, 𝑌)$ を $𝐸$ の二値で分ける：
$𝐻 (𝑋 ∣ 𝐸, 𝑌) = (1 - 𝑃 𝑒) 𝐻 (𝑋 ∣ 𝑌, 𝐸 = 0) + 𝑃 𝑒 𝐻 (𝑋 ∣ 𝑌, 𝐸 = 1) .$
ここで $𝐻 (𝑋 ∣ 𝑌, 𝐸 = 𝑒)$ は 1.2 節で断った混合記法，すなわち $𝐸 = 𝑒$ に固定した世界での $𝐻 (𝑋 ∣ 𝑌)$ である（ $𝑦$ についての平均は条件付き分布 $𝑝 (𝑦 ∣ 𝐸 = 𝑒)$ でとる）． $𝐸 = 0$ のときは $𝑋 = ˆ 𝑋 = 𝑔 (𝑌)$ が $𝑌$ で決まるので $𝐻 (𝑋 ∣ 𝑌, 𝐸 = 0) = 0$ ． $𝐸 = 1$ のときは $𝑋$ が $𝑔 (𝑌)$ 以外，すなわち高々 $| X | - 1$ 個の値しかとらないので，最大エントロピー上界（定理 1.1.5）より $𝐻 (𝑋 ∣ 𝑌, 𝐸 = 1) \leq l o g (| X | - 1)$ ．したがって $𝐻 (𝑋 ∣ 𝐸, 𝑌) \leq 𝑃 𝑒 l o g (| X | - 1)$ ．

左の展開の等式と右の二つの上界を合わせて

𝐻 (𝑋 ∣ 𝑌) = 𝐻 (𝐸 ∣ 𝑌) + 𝐻 (𝑋 ∣ 𝐸, 𝑌) \leq 𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (| X | - 1) .

$◼$

形式化上の注記（実現が二つある）. 本ライブラリはこの不等式を，有限結合 pmf に対する形と，測度空間上の確率変数に対する形の二通りで実現している．前者は推定値そのもので条件付けた核（fano_core / fano_inequality）で，復号器を経る形はそこからデータ処理不等式で復元する（fano_inequality_decode）．後者は本文の定理 1.10.1 と同じく復号器 $𝑔$ を引数にとる．数学的内容はどれも同じである．

形式化: 測度論版 fano_inequality_measure_theoretic (ソース)，pmf 形の核 fano_core / fano_inequality (ソース)，復号器を明示した pmf 形 fano_inequality_decode (ソース)

裏返して使う

ファノの不等式を裏返すと， $𝐻 (𝑋 ∣ 𝑌)$ が大きいときに $𝑃 𝑒$ が下から評価される．これが逆定理で実際に使う向きである．

系 1.10.2（誤り確率の下界）. 定理 1.10.1 と同じ設定で， $𝑎$ を $0 \leq 𝑎 \leq 1 - 1 / | X |$ を満たす実数， $𝑃 𝑒$ も同じ範囲にあるとする．このとき

𝐻 𝑏 (𝑎) + 𝑎 l o g (| X | - 1) < 𝐻 (𝑋 ∣ 𝑌) ⟹ 𝑎 < 𝑃 𝑒 .

証明. 対偶をとる． $𝑃 𝑒 \leq 𝑎$ とすると，右辺 $𝐻 𝑏 (𝑡) + 𝑡 l o g (| X | - 1)$ は $𝑡$ について区間 $[0, 1 - 1 / | X |]$ 上で増加なので（この区間が「 $𝑃 𝑒$ が小さい範囲」の正確な意味である）， $𝐻 𝑏 (𝑃 𝑒) + 𝑃 𝑒 l o g (| X | - 1) \leq 𝐻 𝑏 (𝑎) + 𝑎 l o g (| X | - 1)$ ．定理 1.10.1 と合わせると $𝐻 (𝑋 ∣ 𝑌) \leq 𝐻 𝑏 (𝑎) + 𝑎 l o g (| X | - 1)$ となり，仮定の狭義不等式に反する． $◼$

右辺が増加する範囲に留まっているかぎり， $𝐻 (𝑋 ∣ 𝑌)$ の下界を持っていれば $𝑃 𝑒$ の下界が出る．第6章では，レートが容量を超えるという仮定から $𝐻 (𝑋 ∣ 𝑌)$ が大きいことを導き，ここを通して「誤り確率は 0 に収束しない」を結論する．効いているのは復号器 $𝑔$ を任意にとれることである．定理 1.10.1 が $𝑔$ について何も仮定していないので，系 1.10.2 もどんな復号器に対しても成り立つ．これが「どんな復号器を設計しても」という逆定理の普遍性の出どころである． $𝑃 𝑒$ 自身に置いた $𝑃 𝑒 \leq 1 - 1 / | X |$ という制約は，右辺の増加域に留まるための条件で，逆定理が扱う「誤り確率が小さい」領域では自動的に満たされる．

形式化: 復号器を明示した形 error_lower_bound_decode (ソース)，その核 error_lower_bound (ソース)

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