EE6340: Information Theory
Problem Set 4
1. Shuffles increase entropy. Argue that for any distribution on shuffles T and any distribu-
tion on card positions X that
H(T X) ≥ H(T X|T ) (1)
−1
= H(T T X|T ) (2)
= H(X|T ) (3)
= H(X), (4)
if X and T are independent.
2. Monotonic convergence of the empirical distribution. Let p̂n denote the empirical proba-
bility mass function corresponding to X1 , X2 , ....Xn i.i.d. ∼ p(x), x ∈ X . Specifically,
n
1X
p̂n (x) = I(Xi = x) (5)
n
i=1
is the proportion of times that Xi = x in the first n samples, where I is an indicator
function
(a) Show for X binary that
ED(p̂2n ||p) ≤ ED(p̂n ||p). (6)
Thus the expected relative entropy “distance” from the empirical distribution to the
0
true distribution decreases with sample size. Hint: Write p̂2n = 12 p̂n + 21 p̂n and use
the convexity of D.
(b) Show for an arbitrary discrete X that
ED(p̂n ||p) ≤ ED(p̂n−1 ||p). (7)
Hint: Write p̂n as the average of n empirical mass functions with each of the n
samples deleted in turn.
3. Random box size. An n-dimensional
Qn rectangular box with sides X1 , X2 , ...., Xn is to be
constructed. The volume is Vn = i=1 Xi . The edge length l of a n-cube with the same
1/n
volume as the random box is l = Vn . Let X1 , X2 , ...., Xn be i.i.d. uniform random
1
variables over the unit interval [0,1]. Find limn→∞ Vnn , and compare to (EVn )1/n . Clearly
the expected edge length does not capture the idea of the volume of the box.
4. Monotonicity of entropy per element. For a stationary stochastic process X1 , X2 , ...., Xn ,
show that,
(a)
H(X1 , X2 , ...., Xn ) H(X1 , X2 , ...., Xn−1 )
≤ . (8)
n n−1
(b)
H(X1 , X2 , ...., Xn )
≥ H(Xn |Xn−1 , .....X1 ) (9)
n
5. Doubly stochastic
P matrices. An n × P n matrix P = [Pij ] is said to be doubly stochastic if
Pij ≥ 0 and j Pij = 1 for all i and i Pij = 1 for all j. An n × n matrix P is said to be
a permutation matrix if it is doubly stochastic and there is precisely one Pij = 1 in each
row and each column.
It can be shown that every doubly stochastic matrix can be written as the convex combi-
nation of permutation matrices.
(a) Let at =(a1 , a2 ....an ), ai ≥ 0, ai = 1, be a probability vector. Let b = a P , where P
P
is doubly stochastic. Show that b is a probability vector and that H(b1 , b2 , ....bn ) ≥
H(a1 , a2 , ....an ). Thus stochastic mixing increases entropy.
(b) Show that a stationary distribution µ for a doubly stochastic matrix P is the uniform
distribution.
(c) Conversely, prove that if the uniform distribution is a stationary distribution for a
Markov transition matrix P , then P is doubly stochastic.
6. The entropy rate of a dog looking for a bone. A dog walks on the integers, possibly
reversing direction at each step with probability p = 0.1. Let X0 = 0. The first step is
equally likely to be positive or negative. A typical walk might look like this:
(X0 , X1 , ....) = (0, −1, −2, −3, −4, −3, −2, −1, 0, 1, ...)
(a) Find H(X0 , X1 , X2 , ..., Xn ).
(b) Find the entropy rate of this browsing dog.
(c) What is the expected number of steps the dog takes before reversing direction?