ENEE 627: INFORMATION THEORY
Spring 2016
Problem Set 1
Narayan
Posted: February 5, 2016, Due: February 16, 2016
Problem 1 (Axiomatic derivation of entropy)
Cover-Thomas, problem 2.46.
Problem 2
Show that a rv with values in a countable set can have infinite entropy.
Problem 3
Let X be a rv taking values in the (finite) set {1, . . . , M } with pmf PX such that
PX (1) . . . PX (M ).
Show that
[3a]
H(X) log PX (M );
[3b]
H(X) PX (M ) log PX (M ) (1 PX (M )) log(1 PX (M )).
Problem 4
The interpretation of entropy as a measure of uncertainty of a rv suggests that more
uniform pmfs have larger entropy. For two pmfs P and Q on a finite set X = {1, . . . , r},
we say that P is more uniform than Q, denoted P > Q, if for the nonincreasing ordering
P
P
of probabilities p1 p2 . . . pr , q1 q2 . . . qr , it holds that ki=1 pi ki=1 qi
for every 1 k r. Show that P > Q implies H(P ) H(Q).
Problem 5
Let X be a rv with values in the set of positive integers {1, 2, . . .} and with pmf P
satisfying
EP [X] =
xP (x) = ,
1 < < .
x=1
Using Lagrange multipliers or otherwise, determine the pmf P which maximizes H(X)
subject to the constraint above, and show that the resulting maximum entropy is given
by
H(P ) = log ( 1) log( 1).
Problem 6 ((Exponential) Rate of smallest sets with positive probability)
[6a] Let {Xt }
t=1 be an i.i.d. process with pmf PX on X , where X is a finite set. For
(n)
(n)
=
> 0, let (n, ) be the minimum cardinality of sets B X n with PX B
P (X n Bn ) 1 > 0 for all n large. Show that
lim
n
1
log (n, ) = H(PX ),
n
for all 0 < < 1.
[6b] Is the qualifier minimum needed in [6a]? Justify your answer.
Problem 7
Let {Xt }
t=1 be a X -valued DMS, where X = {0, 1, . . . , q 1} for an integer q 2.
Let pi = Pr{X = i}, i X . Given > 0 and a positive integer n, consider the -typical
(n)
set A
X n.
(n)
[7a] Let X be distributed uniformly on X . Characterize explicitly the set A .
[7b] Suppose next that X has a nonuniform pmf PX = (p0 , p1 , . . . , pq1 ). Show that
q1
)
X n (xn )
i
xn X n :
pi log2 pi
n
i=0
(
A(n)
=
where ni (xn ) = number of occurrences of the symbol i in xn , i X , xn X n .
[7c] For the special case q = 2, show in [7b] that
A(n)
n
n1 (x )
n
n
.
= x X :
p1
n
1
log2 1p
p1
Problem 8
[8a] Let X and Y be finite sets, and let f be a map with domain X . Let X and Y be
rvs with values in X and Y, respectively. Verify that
H(X, f (X)) = H(X),
H(Y |X, f (X)) = H(Y |X),
I(X, f (X) Y ) = I(X Y ).
[8b] Using [8a] above, prove the following inequalities, and determine in each case the
condition for equality:
H(f (X)) H(X),
H(Y |f (X)) H(Y |X),
I(f (X) Y ) I(X Y ).
[8c] State the analogs of the inequalities above with a conditioning rv Z (which takes
values in a finite set Z) and a map f with domain X Z. (For instance, H(f (X, Z)|Z)
H(X|Z), etc.)
[4d] If H(Y |X) = 0, show that Y is a function of X, i.e., for all x X with PX (x) > 0,
there is only one possible y Y with PXY (x, y) > 0.
Problem 9
Let X and Y be rvs with values in the finite sets X and Y, respectively. Set Z , X+Y .
(For instance, take X , Y to be finite subsets of the set of real numbers.)
[9a] Show that H(Z|X) = H(Y |X). Argue that if X and Y are independent, then
H(Y ) H(Z) and H(X) H(Z). Thus, the addition of independent rvs increases
uncertainty.
[9b] Give an example (of necessarily dependent rvs) for which H(X) > H(Z) and H(Y ) >
H(Z).
[9c] Find conditions under which H(Z) = H(X) + H(Y ).
Problem 10
Give examples of rvs (X, Y, Z) such that
[10a]
I(X Y |Z) < I(X Y );
[10b]
I(X Y |Z) > I(X Y ).
Problem 11
Let X be a finite set.
[11a] Let P be a pmf on X . Let W = {W (x|x0 ) : x, x0 X } be a doubly-stochastic
matrix, i.e., W is a |X | |X |-matrix of nonnegative elements with row and column sums
equal to 1. Show that
H(P W ) H(P )
where P W is a pmf on X given by
(P W )(x) =
P (x0 )W (x|x0 ),
x X.
x0 X
[11b] Is the assertion of [11a] valid if W is not doubly-stochastic, but is just a stochastic
matrix with nonnegative elements whose rows sum to 1? If yes, provide a proof; if no,
give a counterexample.
Problem 12
Let X and Y be finite sets. Let X n , (X1 , . . . , Xn ) and Y n , (Y1 , . . . , Yn ) be
collections of X - and Y-valued rvs, respectively.
[12a] Assume X1 , . . . , Xn to be mutually independent. Show that
n
I(X Y )
n
X
I(Xt Yt )
t=1
and deduce the necessary and sufficient condition for equality.
[12b] Drop the assumption in [12a] of the mutual independence of X1 , . . . , Xn , and assume
instead that
PY n |X n (y n |xn ) = nt=1 PYt |Xt (yt |xt )
for all xn X n and y n Y n . Now, show that
I(X n Y n )
n
X
I(Xt Yt )
t=1
and deduce the necessary and sufficient condition for equality.
Problem 13
Let P and Q be pmfs on a finite set X . Consider the mapping f : X Y, where Y
is a finite set. The mapping f induces pmfs Pf and Qf on Y corresponding to P and Q,
respectively, where
Pf (y) ,
P (x),
xX : f (x)=y
Qf (y) ,
Q(x),
y Y.
xX : f (x)=y
[13a] Either prove or disprove that
D(Pf ||Qf ) D(P ||Q).
[13b] Determine a condition which is both necessary and sufficient for equality above.
Problem 14
Let {Xt }
t=1 be a sequence of {0, 1}-valued i.i.d. rvs with
P (X1 = 1) =
1
= 1 P (X1 = 0).
2
Let the sequence of rvs {Yt }
t=1 be defined according to
Yt = Xt + V t
mod 2,
t1
where {Vt }
t=1 be a sequence of {0, 1}-valued i.i.d. rvs with
P (V1 = 1) = p = 1 P (V1 = 0),
0<p<1
and with {Vt }
t=1 independent of {Xt }t=1 .
[14a] Compute H(X n |Y n ), n 1, in terms of n, p. You must justify each step and show
all your calculations in order to receive credit.
[14b] Show that
lim inf P(X n 6= Y n ) h(p)
n
where h(p) = p log2 p (1 p) log2 (1 p).
[14c] Consider the rvs Z1 , Z2 defined by
Zt = Xt + V
mod 2,
t = 1, 2
where V is a {0, 1}-valued rv with
P (V = 1) = p = 1 P (V = 0),
0<p<1
and with V independent of (X1 , X2 ). Compute H(X1 , X2 |Z1 , Z2 ) in terms of p.
Problem 15
Suppose that Ahmed and Praneeth observe, respectively, the finite-valued rvs X and
Y with joint pmf P . They engage in interactive communication, i.e., Ahmed sends to
Praneeth a rv F1 = f1 (X) and Praneeth responds with a rv F2 = f2 (Y, f1 (X)). Here, f1
and f2 are fixed mappings. Prove that
I(X Y |F1 , F2 ) I(X Y ).
Thus, conditioned on their interactive communication, Ahmed and Praneeth are no better mutually informed than without it!
Problem 16 (Shannons Cipher System, 1949)
Secret key
K
K
Message
M
K
E = e(M, K)
Sender
Receiver
In the cipher system above, a sender and a receiver share a secret key K. The
sender then transmits a message rv M in encrypted form as E = e(M, K) such that the
following two requirements are met:
(a) M is independent of E = e(M, K), i.e., an eavesdropper observing E on a public
channel cannot learn M ;
(b) M is a function of (E, K), i.e., the receiver can recover M from a knowledge of K
and E = e(M, K).
Here, e is a fixed mapping. The rvs M, K (and hence E) are finite-valued with joint pmf
P.
Prove that the requirements (a) and (b) imply that
H(K) H(M ).
Problem 17
Let P and Q be two pmfs on a finite set X , and assume that P (x) > 0, Q(x) > 0, x
(n)
X . For > 0, define the mismatched -typical set B
B(n)
X n by
n
o
1
n n
n
n
= x X : log Q (x ) H(P ) + D(P ||Q)
n
(n)
[17a] Prove that for every > 0, limn P n (B ) = 1.
[17b] Show that
h n
oi
(n)
B exp n H(P ) + D(P ||Q) + .
Remark: This problem shows that fixed-to-fixed length data compression of an i.i.d. source
with true pmf P , but using a mismatched typical set for a pmf Q, can be performed
at a penalized compression rate H(P ) + D(P ||Q).
Problem 18
Consider n distinct (and fixed) points ai = (xi , yi , zi ), i = 1, . . . , n, in R3 . Suppose
that these points have n1 , n2 , and n3 distinct projection on the xy, xz, and yzplanes,
respectively. (For instance, the projections of a1 = (x1 , y1 , z1 ) on the xyplane is the
point (x1 , y1 ).) Show that
n2 n1 n2 n3 .
Hint: Let the rv A = (X, Y, Z) be distributed uniformly on {a1 , . . . , an }. The projections of A on the three planes are Axy = (X, Y ), Axz = (X, Z), and Ayz = (Y, Z),
respectively. Show that
2H(A) H (Axy ) + H (Axz ) + H (Ayz ) .
