Description
Material: Markov property, data processing, AEP and information rates.
Readings: Sections 3.1 and 3.2 of the textbook.
The referred problems are from the textbook.
(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.
