1. Fano's inequality
Intuition: If Y is a function of X, Y = g(X), then H(Y|X) =0 . If we can only estimate X from Y with some probability of error P(e), we can image that H(X|Y) will be small if P(e) is small ,and H(X|Y)->0 , as P(e) -> 0.
Proof: we model the process as a Markov Chain
X------> Y-------->
we define E as follows:
E = 1, if
= 0, if
We expand in two ways,
for the second equation,
(1)
,which means
for the first equation, since E is a function of X and , then
now, (2)
From (1),(2), we obtain
(3)
Next , we will prove
From data-processing inequality, we have
since
,we obtain
(4)
From (3),(4)
viz
Comments (0)
You don't have permission to comment on this page.