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

• Whenever you search in PBworks, Dokkio Sidebar (from the makers of PBworks) will run the same search in your Drive, Dropbox, OneDrive, Gmail, and Slack. Now you can find what you're looking for wherever it lives. Try Dokkio Sidebar for free.

View

# Scribe-Note (Jan16)

last edited by 13 years, 10 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) 