Fano 不等式

Fano 不等式把“从观测 $Y$ 估计离散变量 $X$ 的错误率”与剩余条件熵联系起来。若估计几乎总正确，知道估计或观测后对真值就只剩少量不确定性；反过来，若 $H(X|Y)$ 很大、残余信息太多，任何估计器都必须有显著错误，不可能准确恢复。它常用于证明不可能性：先下界恢复所需信息，再由观测携带的信息上界推出错误不能太小。

若 $X$ 在 $M$ 个类别上，估计错误概率为 $P_e$，则常见形式为

当 $P_e=0$ 时右侧为零，条件熵也为零，符合 $X$ 可由 $Y$ 完全恢复；当类别很多时，即使不大的错误率也允许较多剩余熵。若 $X$ 在 $M$ 个消息上均匀而观测只含很少互信息，结合 $H(X\mid Y)=H(X)-I(X;Y)$ 可得译码错误下界。

Fano 给的是条件熵上界，或由其间接推出的错误率下界，通常不是紧等式。使用时常结合 $H(X|Y)=H(X)-I(X;Y)$ 反推出 $P_e$ 下界；连续参数估计不能直接把无限类别数代入，需先离散化、构造有限 packing 或多假设检验，或者使用其他信息论下界。

Fano 不等式以 条件熵公理库条件熵Conditional entropy已知一个随机变量后另一个随机变量剩余不确定性的平均值。 与 互信息公理库互信息Mutual information一个随机变量对另一个随机变量不确定性的平均减少量。为桥梁，用于信道编码逆定理、通信下界、多假设检验和密码恢复不可能性。学习与统计估计中的 packing 选择、样本信息上界和极小极大风险公理库极小极大风险Minimax risk在模型族最坏参数上评价算法风险，再在所有允许算法中寻找最优值。归约统一由 Packing–Fano 学习下界公理库Packing–Fano 学习下界Packing-Fano method · Fano method for minimax lower bounds将参数空间离散成大量两两分离却统计上难以区分的候选，再由 Fano 不等式导出维数敏感的极小极大下界。承担。完整构造先选两两分离的有限参数候选，再上界样本互信息，最后把索引解码错误还原成估计误差。本页只提供熵—错误率关系；数据处理不等式公理库数据处理不等式Data processing inequality对 Markov 链 X→Y→Z，有 I(X;Z)≤I(X;Y)。则负责限制后处理从观测中保留的信息。