Source Coding Theorem (Achievability) (Scribe: LIANG Tong)

We now derive and use properties of the to obtain a source code.

`As shown in the previous class/notes, 

                             (1)

For a "reasonable" source code we would expect that be very small, or in fact asymptotically negligible in n. This is possible if we let be a function of n, and set . In all that follows, we condition on the assumption that is indeed typical, and that

                                                                                      (2)

We remind ourselves that the relative entropy between two probability mass functions p(x) and q(x) is defined as

(also called the Kullback-Leibler divergence), where the  denotes the sample space of the random variable X.

As asked to prove in PS2, if   we have  

EDITING IN PROGRESS (Sid)

The number of  typical  

Question :                

               to prove  

by l'Hôpital's rule, we have   

the number of the typical type-class  and the number of the typical element

the size of largest set class   

Expected # bits  (the typical part + the atypical part)

the typical set decrease, as the epsilon decrease.

p <1/2 and n =10 in the following figures

Fig1: the relation between #of heads and probability,

Fig2: between # of heads and size of T(k,n)

the largest value of T(k,n) = T(n/2, n)   when k =n/2

Most likely of T(k,n) = T(np, n), when k=np

BSCT

(a) ,code with expected rate

(b)  code with and expected rate <

For General case(i  try my best to recall, but... Sorry here i just show a ref about source coding theorem)