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