• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!


lecture notes 3

This version was saved 15 years, 5 months ago View current version     Page history
Saved by Tong
on January 18, 2009 at 9:34:52 pm

lecture note 3


`      Formula

Since Formula is very small, from the right-hand side of the inequality we have Formula 



Definition(From the textbook): the relative entropy between two probability mass functions p(x) and q(x) is defined as




if ||p-q||  Formula we have Formula 


the number of  typical Formula 



Question :                Formula

               to prove   Formula


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



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

the size of largest set class Formula  

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



(a) Formula,Formulacode with expected rate Formula

(b) Formula code with Formulaand expected rate < Formula


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

Comments (0)

You don't have permission to comment on this page.