Entropy Definitions (Scribe: FONG Silas)

Key concepts from past lectures:

Let 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)| = .

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

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

 where  denotes the number of 1's in  .

Problem set 2 question 1: 

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

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

Define the jointly strong typical set   where  denotes .

Claim 1: If   ,  may not be inside .

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

Claim 2: If   ,

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

If  ,    and .

Now,

.

Therefore,  .

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

Proof:

Suppose  . Let   and  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, ,  and . However,  is not in  because .

FACT 1:

  where 

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

 FACT 2:

Given any  , define . Then,  where .

Proof of FACT 2:

For each , 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   such that  . Using Stirling's approximation gives us the desired result.

FACT 3:

  where .

FACT 4:

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