5.4 Fano不等式

Fano不等式

基本形式与定义

Fano不等式是信息论中最重要的不等式之一，它建立了条件熵与错误概率之间的定量关系。考虑随机变量 $X$，其取值于字母表 $\mathcal{X}$，我们希望通过观测另一个随机变量 $Y$ 来估计 $X$ 的值。设 $\hat{X}=g(Y)$ 为根据 $Y$ 对 $X$ 的估计量，定义错误概率 $P_e=P(\hat{X}\ne X)$。Fano不等式给出了如下下界关系：

$$H(X|Y)\le H(P_e)+P_e\log (|\mathcal{X}|-1)$$

其中 $H(P_e)=-P_e\log P_e-(1-P_e)\log (1-P_e)$ 是二元熵函数，$|\mathcal{X}|$ 表示字母表的大小。该不等式也可以等价地写为：

$$P_e\ge \frac{H(X|Y)-1}{\log |\mathcal{X}|}$$

这是一个更简单但稍弱的下界形式，它直接给出了错误概率的下界与条件熵的关系。

证明思路与推导

Fano不等式的证明基于对条件熵的巧妙分解。引入指示变量 $E=I_{\{\hat{X}\ne X\}}$，利用熵的链式法则有：

$$H(E,X|Y)=H(X|Y)+H(E|X,Y)=H(X|Y)$$

另一方面，将 $H(E,X|Y)$ 按另一种方式展开：

$$H(E,X|Y)=H(E|Y)+H(X|E,Y)\le H(P_e)+P_e\log (|\mathcal{X}|-1)$$

其中 $H(E|Y)\le H(E)=H(P_e)$，且 $H(X|E,Y)=(1-P_e)\cdot 0+P_e\cdot H(X|E=1,Y)\le P_e\log (|\mathcal{X}|-1)$。将两部分结合即得到Fano不等式。

在信道编码中的应用

Fano不等式在信道编码定理的逆定理（converse）证明中扮演着核心角色。考虑一个信道，其输入为 $X^n$，输出为 $Y^n$，译码结果为 ${\hat{X}}^n$。利用Fano不等式，可以推导出当传输速率 $R$ 超过信道容量 $C$ 时，错误概率必然趋于1。具体而言，对于 $(2^{nR},n)$ 信道编码，有：

$$nR=H(X^n)=H(X^n|Y^n)+I(X^n;Y^n)\le 1+P_e^{(n)}nR+nC$$

整理得到 $P_e^{(n)}\ge 1-\frac{C}{R}-\frac{1}{nR}$，当 $R>C$ 且 $n\to \infty$ 时，$P_e^{(n)}\to 1$。这正是信道编码逆定理的核心结论。

推广形式

Fano不等式还可以推广到多种更一般的形式。例如，当估计量不唯一或估计空间为可数无限集时，不等式形式需做相应调整。在多类假设检验问题中，Fano不等式也被用于给出错误概率的下界，是信息论与统计学习理论之间的重要联系纽带。在机器学习中，Fano不等式被用于推导泛化误差的下界，为理解学习算法的基本局限性提供了信息论视角。

Fano不等式的深刻意义在于：它揭示了信息与不确定性之间的根本关系——当给定 $Y$ 条件下 $X$ 的条件熵很大时，任何基于 $Y$ 对 $X$ 的估计都必然具有较大的错误概率；只有当 $H(X|Y)=0$ 时，才有可能实现 $P_e=0$ 的无错估计。这一结论对整个信息科学领域具有基础性的指导意义。

链接到

• 上一个知识点：5.3 充分统计量
• 下一个知识点：无（本章最后一个知识点）