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