信息论——Fano不等式

Posted on Edited on In

从XX到YY到X̂\hat{X}，其中X̂\hat {X}是对原有的XX的估计,而Y可以看作是一个中间过程，可以想象类似于编码解码的过程。这之间有什么联系？

Fano不等式如下： $$ P_e = Pr(X \ne \hat{X})\\ H(P_e) + P_e log|X| \geq H(X|\hat{X}) \geq H(X|Y) $$

证明如下： E={0,X=X̂1,X≠X̂ E = \left \{ \begin{array}{c} 0,X = \hat{X}\\ 1,X \ne \hat{X} \end{array} \right. 则：H(E)=H(Pe)H(E) = H(P_e).注意：当不等的时候为11,这个E可以看为错误。

现在考虑H(E,X|X̂)H(E,X|\hat{X}).由之前的条件熵可以知道： H(E,X|X̂)=H(X|X̂)+H(E|X,X̂)−−−−−(1)=H(E|X̂)+H(X|E,X̂)−−−−−(2) \begin{align} H(E,X|\hat {X}) &= H(X|\hat{X}) + H(E|X,\hat{X}) &-----(1)\\ &=H(E|\hat{X})+H(X|E,\hat{X}) &-----(2) \end{align}

很容易知道(1)中，H(E|X,X̂)=0H(E|X,\hat{X}) = 0,因为E的值就是由X,X̂X,\hat{X}确定的。

(2)中，H(E|X̂)≤H(Pe)H(E|\hat{X}) \leq H(P_e).而第二项H(X|E,X̂)H(X|E,\hat{X})满足： H(X|E,X̂)=PeH(X|X≠X̂,X̂)+(1−Pe)H(X|X=X̂,x̂). H(X|E,\hat{X}) = P_e H(X|X \ne \hat{X},\hat{X}) + (1-P_e) H(X|X = \hat{X},\hat{x}). 这步还是比较难懂的。

上式中，$P_e H(X|X ,) P_e |X|,H(X|X = ,) = 0 $.

因此组合起来： H(X|X̂)≤H(Pe)+log⁡|X|H(X|\hat{X}) \leq H(P_e) + \log |X|. 这就得到了Fano不等式的第一个不等号。

接下来证明I(X;Y)≥I(X;X̂)I(X;Y)\geq I(X;\hat{X}). I(X;Y,X̂)=I(X;Y)+I(X;X̂|Y)=I(X;X̂)+I(X;Y|X̂) \begin{align} I(X;Y,\hat{X}) &= I(X;Y) + I(X;\hat{X}|Y)\\ &= I(X;\hat{X}) + I(X; Y|\hat{X}) \end{align}

上式中， I(X;X̂|Y)=0I(X;\hat{X}|Y) = 0.除去Y的信息，X,X̂X,\hat{X}是统计独立的,而两个系统的互信息是大于等于0的。所以可以得到： I(X,Y)≥I(X;X̂). I(X,Y) \geq I(X;\hat{X}).

这告诉我们编码过程中，原有信息只会衰减，而不可能增大。

得到上式后，第二个不等式很快就可以得出： $$ H(X) - H(X|Y) \geq H(X) - H(X|\hat {X})\\ H(X|\hat{X})\geq H(X|Y) $$

所以整个不等式就得到了：

H(Pe)+Pelog⁡|X|≥H(X|X̂)≥H(X|Y)H(P_e) + P_e \log|X| \geq \ H(X|\hat {X}) \geq H(X|Y).