Fano 不等式

Fano 不等式把恢复真值的剩余工作分为两步：先告知估计是否正确，再在估计错误时指出正确类别。令 $E=\mathbf{1}\{X\ne \hat{X}\}$。因为 $E$ 由 $(X,\hat{X})$ 确定，条件熵的链式法则给出

第一项至多为 $H(E)=h_2(P_e)$。当 $E=0$ 时真值已经确定；当 $E=1$ 时，排除已猜的类别后只剩至多 $M-1$ 个选择，所以第二项至多为 $P_e{\log }_2(M-1)$。这也解释了为什么估计输出必须属于同一字母表。

因此，少量错误只容许少量残余信息。证明不可能性时反向使用：先证明观测留下的条件熵较大，便能排除错误率过低的估计器，而不是直接由熵构造一个好估计器。

从信息预算得到错误下界 ​

设 $X$ 均匀分布在 $M=16$ 个消息上，观测满足 $I(X;Y)\le 1$ bit。于是 $H(X\mid Y)\ge 4-1=3$ bit。利用 $h_2(P_e)\le 1$ 与 ${\log }_2(M-1)\le {\log }_{2}M$，任何基于 $Y$ 的估计都满足

这个便于使用的界放松了二元熵项，通常并不紧。若分子为负，只能得到平凡下界 $P_e\ge 0$，不能把负数解释为错误概率。

等号与条件缺失 ​

公平比特经过翻转率为 $p$ 的二元对称信道，取 $\hat{X}=Y$，则 $P_e=p$、$H(X\mid Y)=h_2(p)$；因为 $M-1=1$，Fano 恰取等号。$P_e=1$ 也可有零条件熵：始终猜相反比特虽总猜错，仍完整揭示真值。

相反，若 $Y$ 为常数而估计器偷看 $X$ 后输出 $\hat{X}=X$，则 $P_e=0$，但 $H(X\mid Y)=H(X)$。这没有违反估计版本，而是观测版本的 Markov 条件不成立。

连续参数估计不能把无限类别数直接代入；需先离散化、构造有限 packing 或多假设检验，再将类别判断错误转回参数误差。

信道逆界保留哪一项 ​

对 $M$ 条均匀消息、$n$ 次容量为 $C$ 的无记忆信道使用，信息预算为 $I(U;Y^n)\le nC$。因此精细有限块逆界是

先保留二元熵，再求右边函数的最小根，通常比直接用 $h_2(P_e)\le 1$ 更强。有噪信道编码定理理路有噪信道编码定理Noisy-channel coding theorem · Channel coding theorem低于离散无记忆信道容量的速率可实现任意小错误概率，而高于容量的速率不能可靠传输。给出 $nC$ 的熵分解，并在 BSC$(0.1)$、$n=100$、$M=2^{60}$ 下比较两个界。这里的 $P_e$ 是消息块平均错误；Fano 的这个论证排除高于容量时错误趋零，并未证明错误趋一。

Fano 不等式以 条件熵理路条件熵Conditional entropy已知一个随机变量后另一个随机变量剩余不确定性的平均值。 与 互信息理路互信息Mutual information用联合分布相对独立边缘乘积的 KL 散度量化统计依赖。为桥梁，用于信道编码逆定理、通信下界、多假设检验和密码恢复不可能性。学习与统计估计中的 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)。则负责限制后处理从观测中保留的信息。