ファノの不等式
情報理論において、ファノの不等式（ファノのふとうしき、）は、雑音の多い通信路で失われた情報の平均を分類誤りの確率と関連付ける不等式である。1950年代初めにロベルト・ファノによってMITでの情報理論のPh.Dセミナーで導かれ、その後の彼の1961年の教科書にも記載されている。ファノの逆定理(Fano converse)またはファノの補題(Fano lemma)とも呼ばれる。
これは、任意の復号器の誤り確率の下限と、におけるミニマックスリスクの下限を見つけるために使用される。
確率変数 "X" と "Y" を、同時分布 formula_1 による入力・出力メッセージとする。"e" を誤りの発生、すなわち、formula_2 を出力メッセージ "Y" から推定した入力メッセージ "X" としたとき、 formula_3 となることであるとする。すると、ファノの不等式は以下のように表される。
ここで、formula_5 は "X" のsupportを表し、
は通信誤りの確率、
対応する二値エントロピーである。
"X" を、 formula_9 個の確率密度 formula_10 の内の1つに等しい確率密度を持つ確率変数とする。さらに、密度の任意の対のカルバック・ライブラー情報量は大きすぎることはできない。
formula_13 をインデックスの推定とする。すると、ファノの不等式は以下のように表される。
ここで、formula_15 は formula_16 によって誘導される確率である。
以下の一般化は、Ibragimov and Khasminskii(1979)、Assouad and Birge(1983)によるものである。
F を、任意の "θ" ≠ "θ"′ に対して、 "r" + 1 個の密度 "ƒ" のサブクラスを有する密度のクラスとする。
最悪の場合、推定誤りの期待値は下から拘束され、
となる。ここで、"ƒ" は、サイズ "n" の標本に基づく任意のである。