• 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!


Scribe-Note (Jan16)

Page history last edited by sidjaggi 14 years, 8 months ago

Entropy Definitions (Scribe: FONG Silas)


Key concepts from past lectures:


Let Formula be i.i.d. binary random variables with Pr{ X = 1 } = p. Let T(k) be the type class containing sequences with k 1's, where k=1, 2, ..., n.


Then, the largest type class, i.e., the type class having the largest number of elements, is T(n/2) and |T(n/2)| = Formula.

The type class whose individual sequences are the likeliest, is either T(0) or T(n) (with probability Formula or Formula each).

The likeliest type class. i.e., the type class with the highest probability, is T(np) and |T(np)| = Formula.


Formula where Formula denotes the number of 1's in Formula .


Problem set 2 question 1: 


Let (X,Y) = {0,1}x{0,1} be a pair of random variables such that Formula is denoted by p(i,j), for (i,j) in {0,1}x{0,1}.


Let Formula be n i.i.d. random variables where each has the distribution P={p(i,j)}.


Define the jointly strong typical set  Formula where Formula denotes Formula.


Claim 1: If  Formula , Formula may not be inside Formula.


Counter example: Suppose n=4, and  Formula. Let Formula = 1111 and Formula = 1100. It can be easily checked that Formula. However, Formula is not inside Formula because Formula.


Claim 2: If  Formula , Formula


Proof: Note that X is a binomial random variable with Formula.


If Formula ,   Formula and Formula.







Therefore,  Formula.


Claim 3: For any c>0, n and sufficiently small Formula>0, given Formula, if Formula and Formula, there exist Formula that are not inside Formula.



Suppose  Formula. Let Formula  and Formula be such that the first half of each string is all 1s, and the second half of each string is all 0s. 


Note that for any n, FormulaFormula and Formula. However, Formula is not in Formula because Formula.



 Formula where Formula

The proof is similar to the computation of the size of the typical set of a single variable.


 FACT 2:


Given any Formula , define Formula. Then, Formula where Formula.


Proof of FACT 2:


For each Formula, there are approximately nPr{Y=1}=n(p(0,1)+p(1,1)) 1's and nPr{Y=0}=n(p(0,0)+p(1,0)) 0's.


There are about Formula Formula such that  Formula. Using Stirling's approximation gives us the desired result.



Formula  where Formula.




The probability of observing a sequence Formula with type p(.) rather than the true type q(.) Formula where Formula (as observed in a previous class)


Comments (1)

sidjaggi said

at 4:55 pm on Mar 17, 2009

I'm done editing -- any comments from anyone else?

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