1.10 ファノの不等式

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

本章のはじめに挙げた三つ目の問い，聞こえた単語 $𝑌$ から言った単語 $𝑋$ を推し量るとき聞き違える確率をどこまで小さくできるか，に答えるのが本節である．ここまでの節はずっと情報量の不等式を積み上げてきた．しかし聞き違いについて最終的に知りたいのは「実際にどれだけの確率で間違えるか」という確率である．ファノの不等式は，その二つを結ぶ橋である．「 $𝐻 (𝑋 ∣ 𝑌)$ が大きい」という情報量の言明から「 $𝑃 𝑒$ を小さくできない」という確率の言明へ渡れる．第6章では，電話を一般の通信路に置き換えて，容量を超える速さで送ろうとすると誤りの確率が $0$ に近づかないこと（通信路符号化の逆定理）を示すが，その証明の要がこの橋である．橋の向きにも注意したい．不等式は $𝐻 (𝑋 ∣ 𝑌)$ を $𝑃 𝑒$ で上から抑える形をしており，実際の用途では，その対偶をとって $𝑃 𝑒$ の下界として使う．

主張と証明

定理 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) .

$◼$

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

注記（実現が二つある）

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

誤り確率を下から抑える

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

図 1.10.1. $| X | = 4$ のときの，ファノの不等式の右辺 $𝐻 𝑏 (𝑡) + 𝑡 l o g (| X | - 1)$ ． $𝑡 \leq 1 - 1 / | X |$ で増加するので，曲線が $𝐻 (𝑋 ∣ 𝑌)$ の高さに届く点 $𝑎$ より左に $𝑃 𝑒$ は来られない．

系 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 (ソース)

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