Scribe Note 2( 22-Jan )

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