Description
(1) Answer the following questions.
(a) Provide an example where divergence violates the triangular inequality.
(b) Show that divergence is non-negative using Jensen’s inequality.
(2) The parallelogram identity for vectors x, y and z in R
n
states that
kx − zk
2 + ky − zk
2 = kx − (x + y)/2k
2 + ky − (x + y)/2k
2 + 2k(x + y)/2 − zk
2
where k · k denotes the euclidean (or L2) norm.
Show that an analogous identity holds for the divergence. Specifically, show that for any
three distributions P, Q and R defined on a common finite alphabet (i.e., support) X ,
we have
D(PkR) + D(QkR) = D
P
P + Q
2
+ D
Q
P + Q
2
+ 2D
P + Q
2
R
.
(3) Consider the binary finite-memory Polya contagion process {Zn} with memory order
M = 1 and parameters 0 < ρ := R/T < 1 and δ := ∆/T > 0 described in Example 3.17
in the textbook.
(a) Determine the transition matrix of the Markov source {Zi} and its stationary distribution in terms of the parameters ρ and δ. Is the Markov source a stationary
process?
(b) Determine I(Z2;Z3) and I(Z2;Z3|Z1).
(c) Show that I(Z2;Z3) > I(Z2;Z3|Z1).
(4) Let X → Y → (Z, W) form a Markov chain; i.e., for all (x, y, z, w) ∈ X × Y × Z × W,
PX,Y,Z,W (x, y, z, w) = PX(x)PY |X(y|x)PZ,W|Y (z, w|y).
Assuming that PX,Y,Z,W (x, y, z, w) > 0 for all (x, y, z, w), show that
I(X;Z) + I(X; W) ≤ I(X; Y ) + I(Z; W).
(5) Let {(Xi
, Yi)}
∞
i=1 be a two-dimensional discrete memoryless source with alphabet X × Y
and common distribution PX,Y .
(a) Find the limit as n → ∞ of the random variable
1
n
log2
[PXnY n (Xn
, Y n
)]1−α
[PXn (Xn)]1−α[PY n (Y
n)]α
for a fixed parameter 0 < α < 1.
(b) Evaluate (in terms of ) the limit of part (a) for α = 1/2 and the case of X = {0, 1}
and Y = {0, 1, 2} with PX,Y given by PX,Y (0, 0) = PX,Y (1, 1) = 1−
2
and PX,Y (0, 2) =
PX,Y (1, 2) =
2 where 0 < < 1/2 is fixed.
(6) Answer the following problems.
(i) Problem 3.19, Parts (a) and (b).
(ii) [MATH 874 only] Problem 3.19, Parts (c) and (d).
(7) Answer the following problems.
(i) Ternary Markov Source: To model the evolution of an epidemic through a population, the following three-state stationary Markov source {Xn}
∞
n=1 with alphabet
X = {0, 1, 2} is proposed. Here the state values 0, 1 and 2 represent an individual
being in a susceptible state, an infected state and a recovered state, respectively. The
Markov source’s transition probability is given by:
PXn+1|Xn
(j|i) := Pr(Xn+1 = j|Xn = i) =
1 − γ if i = 0 and j = 0
γ if i = 0 and j = 1
1 − β if i = 1 and j = 1
β if i = 1 and j = 2
α if i = 2 and j = 0
1 − α if i = 2 and j = 2
0 otherwise
where n ≥ 1, 0 ≤ α ≤ 1 and 0 < β, γ < 1.
(a) Determine the entropy rate of {Xn} in terms of α, β and γ.
(b) Suppose that α = 1. Is the Markov source {Xn} irreducible? What is the value
of the entropy rate in this case ?
(c) If α = 1 and β = γ = 1/3, compute the source redundancies ρD, ρM and ρT .
(d) If α = 1 and β = γ = 1/3, determine the average state value, 1
n
Pn
i=1 Xi
, as
n → ∞.
(ii) [MATH 874 only] Problem 3.20.
