Description
(1) Problem 2.9.
(2) A single unbiased die is tossed once. If the face of the die is 1, 2, 3 or 4, an unbiased coin
is tossed once. If the face of the die is 5 or 6, the coin is tossed twice. If we let X denote
the face of the die and Y denote the number of heads obtained, determine H(X, Y ) and
I(X; Y ) in bits.
(3) Problem 2.11.
(4) Answer the following questions.
(a) Let f(y) be an arbitrary function defined for y ≥ 1. Let X be a discrete random variable with alphabet X = {a1, a2, . . . , aN } and probability distribution {p1, p2, . . . , pN },
where pi = P r{X = ai}, i = 1, 2, . . . , N. Define the f-entropy of X by
Hf (X) = X
N
i=1
pi f
1
pi
.
If f(·) is concave, show that the following inequality is always satisfied:
Hf (X) ≤ f(N).
(b) Let p(y|x), x ∈ X , y ∈ Y, be a conditional distribution defined on the finite
alphabets X and Y. Let p1(·) and p2(·) be two distributions on X , and q1(·) and
q2(·) be two corresponding distributions on Y defined by
qi(y) = X
x∈X
p(y|x)pi(x),
∀y ∈ Y and i = 1, 2. Show that
D(p1||p2) ≥ D(q1||q2).
(5) Information theoretic metric. A real-valued function d(·, ·) defined on X × X is said to
be a metric if for all x, y ∈ X ,
• d(x, y) ≥ 0,
• d(x, y) = d(y, x),
• d(x, y) = 0 if and only if x = y,
• d(x, y) + d(y, z) ≥ d(x, z) for all z ∈ X .
(a) Define the information-theoretic function ∆(·, ·) of discrete random variables by
∆(X, Y ) := H(X|Y ) + H(Y |X).
Show that ∆(·, ·) satisfies all the properties required of a metric, except that X = Y
is not a necessary condition for ∆(X, Y ) = 0. What is the necessary and sufficient
condition for ∆(X, Y ) = 0 ?
(b) Show that
|H(X) − H(Y )| ≤ ∆(X, Y ),
and
|H(X1|X2) − H(Y1|Y2)| ≤ ∆(X1, Y1) + ∆(X2, Y2).
(6) Answer the following problems.
(i) For the sequence of (jointly distributed) random variables X1, X2, . . . , Xn, Y1, Y2, . . . , Yn,
show the following:
(a) If X1, X2, . . . , Xn are independent, then
I(X1, X2, . . . , Xn; Y1, Y2, . . . , Yn) ≥
Xn
i=1
I(Xi
; Yi).
(b) If given Xi
, the random variable Yi
is conditionally independent of the remaining
random variables, for i = 1, . . . , n, then
I(X1, X2, . . . , Xn; Y1, Y2, . . . , Yn) ≤
Xn
i=1
I(Xi
; Yi).
(ii) [MATH 874 only] Problem 2.28.
(7) Given a fixed positive integer n > 1, consider two probability distributions
p = (p1, p2, . . . , pn) and q = (q1, q2, . . . , qn)
with support X = {1, 2, . . . , n}; i.e. pi
, qi > 0 for i = 1, . . . , n and Pn
i=1 pi =
Pn
i=1 qi = 1.
Given α > 0 and α 6= 1, the R´enyi cross-entropy between p and q of order α is given by
Hα(p; q) := 1
1 − α
log2
Xn
i=1
piq
α−1
i
!
.
(a) Prove whether or not Hα(p; q) > 0.
(b) Prove whether or not Hα(p; q) is non-increasing in α.
(c) [MATH 874 only] Determine limα→1 Hα(p; q).
(d) [MATH 874 only] Compare limα→1 Hα(p; q) to both H(p) and D(pkq).
