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

View

# Scribe-Note (Jan16)

last edited by 14 years, 8 months ago

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) 