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
2. Converse for source coding theorem.
---->,------> form a markov chain.
(i.i.d)
( H(x) = H(x|y) + I(x;y) )
(data processing inequality in the above Markov chain)
( I(x;y)<= H(y))
( H(x)<= log|X| )
(Fano's inequality)
,which means
Comments (8)
Mak said
at 8:12 pm on Feb 9, 2009
Is this note finished?
It is written in Scribe Notes 2 Feb that, "Last time, we proved the converse of the source coding theorem by ingenious use of several information-theoretic inequalities." But I can't seem to find the related info here?
Cho Yiu Ng said
at 8:19 pm on Feb 10, 2009
As I recall, there were certain discussions about this. So, Cheng Fan, would you mind writing down what we have discussed?
Harry said
at 10:28 pm on Feb 14, 2009
sorry,professor in class indeed discussed something about the converse of the source coding theorem. I will update it .
Cho Yiu Ng said
at 8:26 pm on Feb 22, 2009
Thanks Cheng Fan! Are there any comments?
Cho Yiu Ng said
at 11:32 am on Feb 24, 2009
As a number of you made a mistake in the problem set 3, I ask a question here (which was raised by Yuchen in the lecture as well). Is it correct to apply Fano's Inequality in the converse of Source Coding Theorem above? Please compare it carefully with the Fano's Inequality. On the other hand, if such application is incorrect, can we change the proof a little bit so that we can apply the Fano's Inequality?
Silas said
at 4:39 pm on Feb 24, 2009
I recall that we can follow the steps of the proof in the Fano's inequality to obtain the last inequality. The Fano's inequality utilizes the last inequality mentioned in the scribe note.
Silas said
at 4:41 pm on Feb 24, 2009
I see. We can make g(X) = X and apply the Fano's inequality.
Cho Yiu Ng said
at 4:20 pm on Feb 25, 2009
What is g(X)?
You don't have permission to comment on this page.