1st Semester 2010/11

Solutions to Homework Set #1

Sanov’s Theorem, Rate distortion

1. Sanov’s theorem:
Prove the simple version of Sanov’s theorem for the binary random vari-
ables, i.e., let X1 , X2 , . . . , Xn be a sequence of binary random variables,
drawn i.i.d. according to the distribution:

Pr(X = 1) = q, Pr(X = 0) = 1 − q. (1)

Let the proportion of 1’s in the sequence X1 , X2 , . . . , Xn be pX , i.e.,

n
1X
pX n = Xi . (2)
n i=1

By the law of large numbers, we would expect pX to be close to q for

large n. Sanov’s theorem deals with the probability that pX n is far
away from q. In particular, for concreteness, if we take p > q > 12 ,
Sanov’s theorem states that
1 p 1−p
− log Pr {(X1 , X2 , . . . , Xn ) : pX n ≥ p} → p log +(1−p) log = D((p, 1−p)||(q, 1−q)
n q 1−q
(3)
Justify the following steps:
•
n  
X n i
Pr {(X1 , X2 , . . . , Xn ) : pX ≥ p} ≤ q (1 − q)n−i (4)
i
i=⌊np⌋

• Argue that the term corresponding to i = ⌊np⌋ is the largest term

in the sum on the right hand side of the last equation.
• Show that this term is approximately 2−nD .
• Prove an upper bound on the probability in Sanov’s theorem using
the above steps. Use similar arguments to prove a lower bound
and complete the proof of Sanov’s theorem.

1
Solution
Sanov’s theorem

• Since nX n has a binomial distribution, we have

 
n i
Pr(nX n = i) = q (1 − q)n−i (5)
i
and therefore
n  
X n i
Pr {(X1 , X2 , . . . , Xn ) : pX ≥ p} ≤ q (1 − q)n−i (6)
i
i=⌊np⌋

•
n


Pr(nX n = i + 1) i+1
q i+1 (1 − q)n−i−1 n−i q
= n i

= (7)
Pr(nX n = i) i
q (1 − q)n−i i+11−q

This ratio is less than 1 if n−i

i+1
< 1−q
q
,i.e., if i > nq − (1 − q). Thus
the maximum of the terms occurs when i = ⌊np⌋.
• From Example 11.1.3,
 
n .
= 2nH(p) (8)
⌊np⌋
and hence the largest term in the sum is
 
n
q ⌊np⌋ (1−q)n−⌊np⌋ = 2n(−p log p−(1−p) log(1−p))+np log q+n(1−p) log(1−q) = 2−nD(p||q)
⌊np⌋
(9)
• From the above results, it follows that
n  
X n i
Pr {(X1 , X2 , . . . , Xn ) : pX ≥ p} ≤ q (1 − q)n−i (10)
i
i=⌊np⌋
 
n
≤ (n − ⌊np⌋) q i (1 − q)(11)
n−i
⌊np⌋
≤ (n(1 − p) + 1)2−nD(p||q) (12)

where the second inequality follows from the fact that the sum is
less than the largest term times the number of terms. Taking the

2
 logarithm and dividing by n and taking the limit as n → ∞, we
obtain
1
lim log Pr {(X1 , X2 , . . . , Xn ) : pX ≥ p} ≤ −D(p||q) (13)
n→∞ n

Similarly, using the fact the sum of the terms is larger than the
largest term, we obtain
n  
X n i
Pr {(X1 , X2 , . . . , Xn ) : pX ≥ p} ≥ q (1 − q)n−i(14)
i
i=⌈np⌉
 
n
≥ q i (1 − q)n−i (15)
⌈np⌉
≥ 2−nD(p||q) (16)

and
1
lim log Pr {(X1 , X2 , . . . , Xn ) : pX ≥ p} ≥ −D(p||q) (17)
n→∞ n

Combining these two results, we obtain the special case of Sanov’s

theorem
1
lim log Pr {(X1 , X2 , . . . , Xn ) : pX ≥ p} = −D(p||q) (18)
n→∞ n

2. Strong Typicality
Let X n be drawn i.i.d.∼ P (x). Prove that for each xn ∈ Tδ (X),
′ ′
2−n(H(X)+δ ) ≤ P n (xn ) ≤ 2−n(H(X)−δ )

for some δ ′ = δ ′ (δ) that vanishes as δ → 0.

Solution: Strong Typicality
From our familiar trick, we have
P
P n (xn ) = 2 ( )
1
−n a∈X Pxn (a) log P (a)

δ
But, since xn ∈ Tδ (X), we have |Pxn (a) − P (a)| < |X |
for all a. There-
fore,
δ X 1 X 1 δ X 1
H(X)− log < Pxn (a) log < H(X)+ log
|X | a P (a) a∈X P (a) |X | a P (a)

3
 Hence,
′ ′
2−n(H(X)+δ ) ≤ P n (xn ) ≤ 2−n(H(X)−δ )
′ 1
where δ = |Xδ | a log P (a)
P

3. Weak Typicality vs. Strong Typicality

In this problem, we compare the weakly typical set Aǫ (P ) and the
strongly typical set Tδ (P ). To recall, the definition of two sets are
following.
   
n  1
n
 n n

Aǫ (P ) = x ∈ X : − log P (x ) − H(P ) ≤ ǫ 
n
 
n n δ
Tδ (P ) = x ∈ X : kPxn − P k∞ ≤
|X |

(a) Suppose P is such that P (a) > 0 for all a ∈ X . Then, there
is an inclusion relationship between the weakly typical set Aǫ (P )
and the strongly typical set Tδ (P ) for an appropriate choice of
ǫ. Which of the statement is true: Aǫ (P ) ⊆ Tδ (P ) or Aǫ (P ) ⊇
Tδ (P )? What is the appropriate relation between δ and ǫ?
(b) Give a description of the sequences that belongs to Aǫ (P ), vs. the
sequences that belongs to Tδ (P ), when the source is uniformly
distributed, i.e. P (a) = |X1 | , ∀a ∈ X . (Assume |X | < ∞.)
(c) Can you explain why Tδ (P ) is called strongly typical set and
Aǫ (P ) is called weakly typical set?

Solution: Weak Typicality vs. Strong Typicality

(a) From Problem 2, we can see that if xn ∈ Tδ (P ), then

 
 1
− log P n (xn ) − H(P ) ≤ δ ′ = δ 1
 X
 n log
 |X | a P (a)

1
Therefore, we can see that if ǫ > |Xδ | a log P (a)
P
, then Aǫ (P ) ⊇
Tδ (P ). To show that the other way does not hold, see the next
part.

4
 (b) When P is a uniform distribution, we can see that Aǫ (P ) includes
every possible sequences xn . To see this, we can easily see that
P n (xn ) = ( |X1 | )n , and thus, −1/n log P n (xn ) = log |X | = H(P ).
Thus, xn ∈ Aǫ (P ) for all xn , for all ǫ > 0. However, obviously,
among those sequences in Aǫ (P ), only those who have the type
1 δ 1 δ
− ≤ Pxn (a) ≤ +
|X | |X | |X | |X |
for each letter a ∈ X , are in Tδ (P ). Therefore, for sufficiently
small value of δ, there always exist some sequences that are in
Aǫ (P ), but not in Tδ (P ).
(c) From above questions, we can see that the strongly typical set is
contained in the weakly typical set for appropriate choice of δ and
ǫ. Thus, we can see that the definition of strong typical set is
stronger than that of the weakly typical set.

4. Rate distortion for uniform source with Hamming distortion.

Consider a source X uniformly distributed on the set {1, 2, . . . , m}.
Find the rate distortion function for this source with Hamming distor-
tion, i.e., 
0 if x = x̂,
d(x, x̂) =
1 if x 6= x̂.

Solution: Rate distortion for uniform source with Hamming

distortion. X is uniformly distributed on the set {1, 2, . . . , m}. The
distortion measure is

0 if x = x̂
d(x, x̂) =
1 if x 6= x̂

Consider any joint distribution that satisfies the distortion constraint

D. Since D = Pr(X 6= X̂), we have by Fano’s inequality

H(X|X̂) ≤ H(D) + D log(m − 1), (19)

and hence

I(X; X̂) = H(X) − H(X|X̂) (20)

≥ log m − H(D) − D log(m − 1). (21)

5
 We can achieve this lower bound by choosing p(x̂) to be the uniform
distribution, and the conditional distribution of p(x|x̂) to be

= 1−D if x̂ = x
p(x̂|x) (22)
= D/(m − 1) if x̂ 6= x.

It is easy to verify that this gives the right distribution on X and

satisfies the bound with equality for D < 1 − m1 . Hence

= log m − H(D) − D log(m − 1) if 0 ≤ D ≤ 1 − m1


R(D) (23)
0 if D > 1 − m1 .

5. Erasure distortion
Consider X ∼ Bernoulli( 12 ), and let the distortion measure be given by
the matrix  
0 1 ∞
d(x, x̂) = . (24)
∞ 1 0
Calculate the rate distortion function for this source. Can you suggest
a simple scheme to achieve any value of the rate distortion function for
this source?

Solution: Erasure distortion

The infinite distortion constrains p(0, 1) = p(1, 0) = 0. Hence by sym-
metry the joint distribution of (X, X̂) is of the form shown in Figure 1.

1−a
0 Q - 0
Q
Q
Q
Q
Q
aQ
s
Q e
a 
3





1  - 1
1−a

Figure 1: Joint distribution for erasure rate distortion of a binary source.

6
 For this joint distribution, it is easy to calculate the distortion D = a
and that I(X; X̂) = H(X) − H(X|X̂) = 1 − a. Hence we have R(D) =
1 − D for 0 ≤ D ≤ 1. For D > 1, R(D) = 0.
It is very see how we could achieve this rate distortion function. If D
is rational, say k/n, then we send only the first n − k of any block of n
bits. We reproduce these bits exactly and reproduce the remaining bits
as erasures. Hence we can send information at rate 1 − D and achieve
a distortion D. If D is irrational, we can get arbitrarily close to D by
using longer and longer block lengths.

6. Rate distortion.
A memoryless source U is uniformly distributed on {0, . . . , r − 1}. The
following distortion function is given by

 0, u = v,
d(u, v) = 1, u = v ± 1 mod r,
∞, otherwise.


Show that the rate distortion function is

log r − D − h2 (D), D ≤ 32 ,
(
R(D) =
log r − log 3, D > 23 .

Solution: Rate distortion

From the symmetry of the problem, we can assume the conditional

distribution of p(v|u) as

 1 − p u = v,
p(v|u) = p/2 u = v ± 1 mod r,
0 otherwise


Then, E(d(U, V )) = p. Therefore, the rate distortion function is

R(D) = min I(U; V ).
p≤D

Now, we know that

I(U; V ) =H(V ) − H(V |U)
= log r − H(1 − p, p/2, p/2),

7
 since U is uniform, and due to symmetry, V is also uniform. We know
that H(1 − p, p, p) ≤ log 3, and this is achieved when p = 2/3. There-
fore,
R(D) = log r − log 3, if D > 2/3.
Now, let’s consider the case when D ≤ 2/3. Denote

f (p) = H(1 − p, p/2, p/2) = − (1 − p) log(1 − p) − p/2 log p/2 × 2

= − (1 − p) log(1 − p) − p log p + p,

We know that f (p) is a concave function. By differentiating with re-

spect to p,

df (p) 1−p
= log(1 − p) + 1 − log p − 1 + 1 = log +1
dp p

and setting f (p) = 0, f (p) becomes maximum when p = 2/3. There-

fore, if D ≤ 2/3, f (p) is an increasing function of p. Thus,

R(D) = log 3 − D − h2 (D), if D ≤ 2/3.

7. Adding a column to the distortion matrix. Let R(D) be the rate

distortion function for an i.i.d. process with probability mass function
p(x) and distortion function d(x, x̂), x ∈ X , x̂ ∈ X̂ . Now suppose that
we add a new reproduction symbol x̂0 to Xˆ with associated distortion
d(x, x̂0 ), x ∈ X . Can this increase R(D)? Explain.
Solution: Adding a column
Let the new rate distortion function be denoted as R̃(D), and note that
we can still achieve R(D) by restricting the support of p(x, x̂), i.e., by
simply ignoring the new symbol. Thus, R̃(D) ≤ R(D).
Finally note the duality to the problem in which we added a row to the
channel transition matrix to have no smaller capacity (Problem 7.22).

8. Simplification. Suppose X = {1, 2, 3, 4}, Xˆ = {1, 2, 3, 4}, p(i) = 14 ,

i = 1, 2, 3, 4, and X1 , X2 , . . . are i.i.d. ∼ p(x). The distortion matrix

8
 d(x, x̂) is given by
1 2 3 4
1 0 0 1 1
2 0 0 1 1
3 1 1 0 0
4 1 1 0 0

(a) Find R(0), the rate necessary to describe the process with zero
distortion.
(b) Find the rate distortion function R(D).
(Hint: The distortion measure allows to simplify the problem into
one you have already seen.)
(c) Suppose we have a nonuniform distribution p(i) = pi , i = 1, 2, 3, 4.
What is R(D)?

Solution: Simplification

(a) We can achieve 0 distortion if we output X̂ = 1 if X = 1 or 2,

and X̂ = 3 if X = 3 or 4. Thus if we set Y = 1 if X = 1 or 2, and
Y = 2 if X = 3 or 4, we can recover Y exactly if the rate is greater
than H(Y ) = 1 bit. It is also not hard to see that any 0 distortion
code would be able to recover Y exactly, and thus R(0) = 1.
(b) If we define Y as in the previous part, and Ŷ similarly from X̂,
we can see that the distortion between X and X̂ is equal to the
Hamming distortion between Y and Ŷ . Therefore if the rate is
greater than the Hamming rate distortion function R(D) for Y ,
we can recover X to distortion D. Thus R(D) = 1 − H(D).
(c) If the distribution of X is not uniform, the same arguments hold
and Y has a distribution (p1 + p2 , p3 + p4 ), and the rate distortion
function is R(D) = H(p1 + p2 ) − H(D),

9. Rate distortion for two independent sources. Can one simulta-

neously compress two independent sources better than compressing the
sources individually? The following problem addresses this question.
Let the pair {(Xi , Yi )} be iid ∼ p(x, y). The distortion measure for
X is d(x, x̂) and its rate distortion function is RX (D). Similarly, the

9
distortion measure for Y is d(y, ŷ) and its rate distortion function is
RY (D).
Suppose we now wish to describe the process {(Xi , Yi )} subject to dis-
tortion constraints limn→∞ Ed(X n , X̂ n ) ≤ D1 and limn→∞ Ed(Y n , Ŷ n ) ≤
D2 . Our rate distortion theorem can be shown to naturally extend to
this setting and imply that the minimum rate required to achieve these
distortion is given by

RX,Y (D1 , D2 ) = min I(X, Y ; X̂, Ŷ )

p(x̂,ŷ|x,y):Ed(X,X̂)≤D1 ,Ed(Y,Ŷ )≤D2

Now, suppose the {Xi } process and the {Yi } process are independent
of each other.
(a) Show
RX,Y (D1 , D2 ) ≥ RX (D1 ) + RY (D2 ).
(b) Does equality hold?
Now answer the question.
Solution: Rate distortion for two independent sources.
(a) Given that X and Y are independent, we have
p(x, y, x̂, ŷ) = p(x)p(y)p(x̂, ŷ|x, y) (25)
Then
I(X, Y ; X̂, Ŷ ) = H(X, Y ) − H(X, Y |X̂, Ŷ ) (26)
= H(X) + H(Y ) − H(X|X̂, Ŷ ) − H(Y |X, X̂,(27)
Ŷ )
≥ H(X) + H(Y ) − H(X|X̂) − H(Y |Ŷ ) (28)
= I(X; X̂) + I(Y ; Ŷ ) (29)
where the inequality follows from the fact that conditioning re-
duces entropy. Therefore
RX,Y (D1 , D2 ) = min I(X, Y ; X̂, Ŷ ) (30)
p(x̂,ŷ|x,y):Ed(X,X̂)≤D1 ,Ed(Y,Ŷ )≤D2
 
≥ min I(X; X̂) + I(Y ; Ŷ(31)
)
p(x̂,ŷ|x,y):Ed(X,X̂)≤D1 ,Ed(Y,Ŷ )≤D2

= min I(X; X̂) + min I(Y ; (32)

Ŷ )
p(x̂|x):Ed(X,X̂)≤D1 p(ŷ|y):Ed(Y,Ŷ )≤D2

= RX (D1 ) + RY (D2 ) (33)

10
 (b) If
p(x, y, x̂, ŷ) = p(x)p(y)p(x̂|x)p(ŷ|y), (34)
then

I(X, Y ; X̂, Ŷ ) = H(X, Y ) − H(X, Y |X̂, Ŷ ) (35)

= H(X) + H(Y ) − H(X|X̂, Ŷ ) − H(Y |X, X̂,(36)
Ŷ )
= H(X) + H(Y ) − H(X|X̂) − H(Y |Ŷ ) (37)
= I(X; X̂) + I(Y ; Ŷ ) (38)

Let p(x, x̂) be a distribution that achieves the rate distortion

RX (D1 ) at distortion D1 and let p(y, ŷ) be a distribution that
achieves the rate distortion RY (D2 ) at distortion D2 . Then for the
product distribution p(x, y, x̂, ŷ) = p(x, x̂)p(y, ŷ), where the com-
ponent distributions achieve rates (D1 , RX (D1 )) and (D2 , RX (D2 )),
the mutual information corresponding to the product distribution
is RX (D1 ) + RY (D2 ). Thus

RX,Y (D1 , D2 ) = min I(X, Y ; X̂, Ŷ ) = RX (D1 )+RY (D2 )

p(x̂,ŷ|x,y):Ed(X,X̂)≤D1 ,Ed(Y,Ŷ )≤D2
(39)
Thus by using the product distribution, we can achieve the sum
of the rates.
Therefore the total rate at which we encode two independent
sources together with distortions D1 and D2 is the same as if
we encoded each of them separately.

10. One bit quantization of a single Gaussian random variable.

Let X ∼ Norm(0, σ 2 ) and let the distortion measure be squared er-
ror. Here we do not allow block descriptions. Show
qthat the optimum
reproduction points for 1 bit quantization are ± π2 σ, and that the
π−2 2
expected distortion for 1 bit quantization is π
σ .
Compare this with the distortion rate bound D = σ 2 2−2R for R = 1.
Solution: One bit quantization of a single Gaussian random
variable
With one bit quantization, the obvious reconstruction regions are the
positive and negative real axes. The reconstruction point is the centroid

11
 of each region. For example, for the positive real line, the centroid a is
given as
Z ∞
2 x2
a = x√ e− 2σ2 dx
0 2πσ 2
Z ∞ r
2 −y
= σ e dy
0 π
r
2
= σ ,
π
using the substitution y = x2 /2σ 2 . The expected distortion for one bit
quantization is
Z 0 r !2
2 1 x2
D = x+σ √ e− 2σ2 dx
−∞ π 2πσ 2
Z ∞ r ! 2
2 1 x2
+ x−σ √ e− 2σ2 dx
0 π 2πσ 2
Z ∞ 
2 1 x2
= 2 x2 + σ 2 √ e− 2σ2 dx
−∞ π 2πσ 2
Z ∞ r !
2 1 x2
−2 −2xσ √ e− 2σ2 dx
0 π 2πσ 2
r
2 2 2 1 2 2
= σ + σ − 4√ σ
π 2π π
π−2
= σ2
π
≈ .3634 σ 2 ,

which is much larger than the distortion rate bound D(1) = σ 2 /4.

11. Side information.

A memoryless source generates i.i.d. pairs of random variables (Ui , Si ), i =
1, 2, . . . on finite alphabets, according to
n
Y
n n
p(u , s ) = p(ui , si ).
i=1

12
We are interested in describing U, when S, called side information, is
known both at the encoder and at the decoder. Prove that the rate
distortion function is given by

RU |S (D) = min I(U; V |S).

p(v|u,s):E[d(U,V )]≤D

Compare RU |S (D) with the ordinary rate distortion function RU (D)

without any side information. What can you say about the influence
of the correlation between U and S on RU |S (D)?
Solution: Side information

Since both encoder and decoder have the common side information
S, we can be helped from the correlation of our source U and the side
information S. The idea for the achievability is, we use the different rate
distortion code for the source symbols that have different corresponding
side information. Therefore, for the symbols that has side information
S = s will have the rate distortion code at rate

RU |S=s (D) = min I(U; V |S = s)

p(v|u,S=s):E(d(U,V ))≤D

and expected distortion ≤ D. Now, the total rate will be

|S|
X
R= PS n (s)RU |S=s (D),
s=1

where PS n (s) is the empirical distribution of S n . As n becomes large

enough, we know that PS n (s) will be very close to the true distribution
of S, p(s), or with high probability, S n will be in the strong typical set
TP (δ), where
 
n δ
TP (δ) = s : max |Psn (s) − p(s)| < .
s∈S |S|

Therefore, if n sufficiently large, and δ sufficiently small, we will achieve

the rate X
R= p(s)I(U; V |S = s) = I(U; V |S)
s∈S

13
It is clear that the overall rate distortion code has the expected distor-
tion ≤ D.
For the converse, we have

nR ≥H(V n |S n )
=I(U n ; V n |S n )
=H(U n |S n ) − H(U n |V n , S n )
n
X
H(Ui |Si ) − H(Ui |U i−1 , V n , S n )


=
i=1
n
X
≥ (H(Ui |Si ) − H(Ui |Vi ))
i=1
Xn
= I(Ui ; Vi |Si )
i=1
n
X
≥ RU |S (Ed(Ui , Vi ))
i=1
≥RU |S (Ed(U n , V n ))
≥RU |S (D)

where each step has the identical reason as the original converse. Now,
to compare RU |S (D) and RU (D), consider following:

RU |S (D) = min I(U; V |S)

p(v|u,s):E(d(U,V ))≤D

≤ min I(U; V |S) (40)

p(v|u):E(d(U,V ))≤D

≤ min I(U; V ) (41)

p(v|u):E(d(U,V ))≤D

=RU (D).

Here, the inequality in (40) is from the fact that the minimization is
held on the smaller set. The inequality in (41) is from the fact that
S → U → V forms a Markov chain with the joint distribution that we
get from the minimization in (40). Also, we have,

I(U, S; V ) =I(U; V ) + I(S; V |U)

=I(S; V ) + I(U; V |S).

14
Since I(S; V |U) = 0 and I(S; V ) ≥ 0, we have the inequality in (41).
Therefore, we can only gain from the the side information. Intuitively,
this also makes sense, because we can always just ignore the side in-
formation and get the original rate distortion code, but the rate may
be worse. The two rates will be equal if and only if U and S are
independent, which achieves the equality in both (40) and (41).

15