__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 *n*Pr{*Y*=1}=*n*(*p*(0,1)+*p*(1,1)) 1's and *n*Pr{*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)

## 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.