法诺不等式

假设我们知道随机变量Y，并且希望猜测一个相关随机变量X的值。法诺不等式将猜测随机变量 X 的误差概率与其条件熵 H(X|Y) 联系起来。这对于证明第7章中香农信道容量定理的逆定理至关重要。从问题 2.5 我们知道，给定一个随机变量 Y，随机变量 X 的条件熵为零，当且仅当 X 是 Y 的函数。因此，当且仅当 H(X|Y) = 0，我们才可以根据 Y 估计 X，且误差概率为零。

扩展此论点，仅当条件熵 H(X|Y ) 很小时，我们才期望能够以较低的误差概率估计 X。法诺不等式量化了这个想法。假设我们希望估计一个服从分布 p(x) 的随机变量 X。我们观察到一个随机变量 Y，它与 X 的关系服从条件分布 p(y|x)。从 Y ，我们计算出一个函数 \(g(Y) = \hat{X}\) ，其中 \(\hat{X}\) 是 X 的估计值，取 \(\hat{\mathcal{X}}\) 中的值。我们不会限制字母表 \(\hat{\mathcal{X}}\)等于 \(\mathcal{X}\)，并且我们还允许函数 g(Y ) 是随机的。我们希望界定\(\hat{X}\ne X\) 的概率。我们观察到\(X \rightarrow Y \rightarrow \hat{X}\) 形成一个马尔可夫链。定义误差概率

\[P_e = PR\{\hat{X} \ne X\}.\tag{2.129}\]

定理 2.10.1 （法诺不等式） 对于任意估计器\(\hat{X}\)，使得\(X \rightarrow Y \rightarrow \hat{X}\)，其中\(P_e = PR\{\hat{X} \ne X\}\)，得到

\[H(P_e) + P_e\ \text{log}\ |\mathcal{X}| \ge H(X|\hat{X})\ge H(X|Y).\tag{2.130}\]

该不等式可以弱化为

\[1 + P_e\ \text{log}|\mathcal{X}| \ge H(X|Y)\tag{2.131}\]

或

\[P_e \ge \frac{H(X|Y) - 1}{\text{log}\ |\mathcal{X}|}.\tag{2.132}\]

注（2.13 0）中的\(P_e=0\)意味着\(H（X|Y）=0\)，正如直觉所暗示的那样。

证明：我们首先忽视Y的作用，并证明（2.130）中的第一个不等式。然后，使用数据处理不等式来证明法诺不等式更传统的形式，由（2.130）中的第二个不等式给出。定义误差随机变量，

\[ E = \begin{cases} &1\quad \text{if}\hat{X}\ne X,\\ &0\quad \text{if}\hat{X} = X. \end{cases}\tag{2.133} \]

然后，对熵使用链式法则以两种不同方式展开\(H(E,X|\hat{X})\)，得到

\begin{align} H(E,X|\hat{X}) &= H(X|\hat{X}) + \overbrace{H(E|X, \hat{X})}^{=0}\tag{2.134}\\ &= \overbrace{H(E|\hat{X})}^{\le H(P_e)} + \overbrace{H(X|E,\hat{X})}^{\le P_e\ \text{log}|\mathcal{X}|}.\tag{2.135} \end{align}

由于条件作用减少熵，\(H(E|\hat{X}) \le H(E) = H(P_e)\)。现在，由于E是X和\(\hat{X}\)的函数，条件熵\(H(E|X,\hat{X})\)等于0。而且，由于E是二值随机变量，\(H(E) = H(P_e)\)。余下的项，\(H(X|E, \hat{X})\)可以界定如下：

\begin{align} H(X|E, \hat{X}) &= Pr(E = 0)H(X|\hat{X}, E = 0) + Pr(E = 1)H(X|\hat{X}, E=1)\\ &\le (1- P_e)0 + P_e\ \text{log}|\mathcal{X}|,\tag{2.136} \end{align}

由于给定 \(E = 0, X=\hat{X}\)，以及 \(E= 1\)，我们可以通过可能结果数量的对数来确定条件熵的上限。结合这些结果，我们得到

\[H(P_e) + P_e\ \text{log}|\mathcal{X}| \ge H(X|\hat{X}).\tag{2.137}\]

通过数据处理不等式，有\(I(X;\hat{X}) \le I(X;Y)\)，因为\(X\rightarrow Y\rightarrow \hat{X}\)是马尔科夫链，因此\(H(X|\hat{X}) \ge H(X|Y)\)。因此，得到

\[H(P_e) + P_e\ \text{log}|\mathcal{X}| \ge H(X|\hat{X})\ge H(X|Y).\tag{2.1398}\]

引理 对于任意两个随机变量X和Y，设\(p = Pr(X\ne Y)\)。 \[H(p) + p\ \text{log}|\mathcal{X}| \ge H(X|Y).\tag{2.139}\]

证明： 在法诺不等式中，设\(\hat{X} = Y\)。

对于任意两个随机变量X和Y，若估计器\(g(Y)\)取集合\(\mathcal{X}\)中的值，我们可以通过替换\(\text{log}|\mathcal{X}|\)为\(\text{log}(|\mathcal{X}|-1)\)来强化不等式。

引理 设\(P_e = Pr(X\ne \hat{X})\)，且\(\hat{X}: \mathcal{Y}\rightarrow \mathcal{X}\)；那么

\[H(P_e) + P_e\ \text{log}(|\mathcal{X}| -1) \ge H(X|Y).\tag{2.140}\]

证明：定理的证明没有改变，除了

\begin{align} H(X|E,\hat{X}) &= Pr(E=0)H(X|\hat{X},E=0) + Pr(E=1)H(X|\hat{X}, E=1)\tag{2.141}\\ &\le (1- P_e)0 + P_e\ \text{log}(|\mathcal{X}|-1),\tag{2.142} \end{align}

给定 E = 0，\(X=\hat{X}\)，且给定 E = 1，X 的可能结果范围为 \(|\mathcal{X}|-1\)，我们可以通过 \(\text{log}(|\mathcal{X}|-1)\)（可能结果数量的对数）来确定条件熵的上限。代入该公式，我们得到了更强的不等式。

注 假设Y没有知识。从而，X必须无信息猜测。设\(X\in \{1,2,\dots,m\})和 \(p_1\ge p_2\ge \dots \ge p_m\)。那么X最好的猜测是\(\hat{X}=1\)，以及结果误差概率是\(P_e = 1 - p_1\)。法诺不等式变为

\[H(P_e) + P_e\ \text{log}(m-1) \ge H(X).\text{2.143}\]

概率质量函数

\[(p_1,p_2,\dots,p_m) = (1- P_e, \frac{P_e}{m-1}, \dots,\frac{P_e}{m-1})\tag{2.144}\]

用等式达到了这个界限。因此，法诺不等式是尖锐的。

顺便引入一个新的不等式，将误差概率与熵联系起来。设 X 和 X′ 为两个独立同分布的随机变量，熵为 H(X)。X = X′ 处的概率为

\[Pr(X=X’) = \sum_x p^2(x).\tag{2.145}\]

我们有以下不等式：

引理 2.10。1 若X和X’独立同分布（iid），熵为H(X)， \[Pr(X= X’) \ge 2^{-H(X)},\tag{2.146}\]

当且仅当X具有均匀分布时，等式成立。

证明：假设\(X \sim p(x)\)。通过Jensen不等式，有

\[2^{E\ \text{log}\ p(X)}\le E\ 2^{\text{log}\ p(X)},\tag{2.147}\]

意味着

\[2^{-H(X)} = 2^{\sum p(x)\text{log}\ p(x)}\le \sum p(x)2^{\text{log}\ p(x)} = sum p^2(x). \tag{2.148}\]

推论 设 X, X’独立，\(X\sim p(x)\)，\(X’\sim r(x)\)， \(x,x’ \in \mathcal{X}\)。那么

\[Pr(X = X’) \ge 2^{-H(p) - D(p||r)}, \tag{2.149}\]

\[Pr(X = X’) \ge 2^{-H(r) - D(r||p)}, \tag{2.150}\]

证明： 我们有

\begin{align} 2^{-H(p) - D(p||r)} &= 2^{\sum p(x)\ \text{log}\ p(x) + \sum p(x)\ \text{log}\frac{r(x)}{p(x)}}\tag{2.151}\\ &= 2^{\sum p(x)\ \text{log}\ r(x)} \tag{2.152}\\ &\le \sum p(x)2^{\text{log}\ r(x)}\tag{2.153}\\ &= \sum p(x)r(x)\tag{2.154}\\ &= Pr(X = X’), \tag{2.155} \end{align}

其中不等式来自Jensen不等式，和函数\(f(y)=2^y\)的凸性。