EE6340: Information Theory
Problem Set 3
1. The AEP and source coding. A discrete memoryless source emits a sequence of statistically
independent binary digits with probabilities p(1) = 0.005 and p(0) = 0.995. The digits are
taken 100 at a time and a binary codeword is provided for every sequences of 100 digits
containing three or fewer ones.
(a) Assuming that all codewords are the same length, find the minimum length required
to provide codewords for all sequence with three or fewer ones.
(b) Calculate the probability of observing a source sequence for which no codeword has
been assigned.
2. X1 , X2 , · · · , X8 are i.i.d. binary random variables (i.e. X = {0, 1}) with P r[X1 = 1] =
7/8.
(8)
(a) For what values of ǫ does the typical set Aǫ of sequences (x1 , x2 , · · · , x8 ) ∈ X 8 have
exactly 8 elements.
(b) List the elements in the resulting typical set. What is the probability of this typical
set?
(c) Find the number of elements in the typical set as a function of ǫ.
P
3. AEP. Let Xi be iid ∼ p(x), x ∈ {1, 2, ...., m}. Let µ = E[X] and H = P − p(x)log p(x).
Let An = {xn ∈ χn : | − n1 log p(xn ) − H| ≤ ǫ}. Let B n = {xn ∈ χn : | n1 ni=1 xi − µ| ≤ ǫ}.
(a) Does Pr{X n ∈ An } → 1?
(b) Does Pr{X n ∈ An ∩ B n } → 1?
(c) Show that |An ∩ B n | ≤ 2n(H+ǫ) for all n.
(d) Show that |An ∩ B n | ≥ 12 2n(H−ǫ) for n sufficiently large.
4. AEP-like limit. Let X1 , X2 , ..... be i.i.d. drawn according to probability mass function
p(x). Find
1
lim (p(X1 , X2 , .....Xn )) n .
n→∞
5. AEP. Let X1 , X2 , .... be independent, identically distributed random variables drawn ac-
cording
Qn to the probability mass function p(x), x ∈ {1, 2, ...., m}. Thus, p(x1 , x2 , ......xn ) =
1
Qni=1 p(xi ). We know that − n log p(X1 , X2 , .....Xn ) → H(X) in probability. Let q(x1 , x2 , ......xn ) =
i=1 q(xi ), where q is another probability mass function on {1, 2, 3.....m}.
(a) Evaluate lim − n1 log q(X1 , X2 , .....Xn ), where X1 , X2 , ..... are i.i.d. ∼ p(x).
q(X1 ,X2 ,.....Xn )
(b) Now evaluate the limit of the log likelihood ratio n1 log p(X1 ,X2 ,.....Xn )
when X1 , X2 , .....
are i.i.d.∼ p(x). Thus, the odds favoring q are exponentially small when p is true.