EE6340: Information Theory
Problem Set 2
1. Entropy of a sum. Let X and Y be random variables that take on values x1 , x2 , ...., xr
and y1 , y2 , ...., ys ,respectively. Let Z = X + Y .
(a) Show that H(Z|X) = H(Y |X). Argue that if X, Y are independent,then H(Y ) ≤
H(Z) and H(X) ≤ H(Z). Thus the addition of independent random variables adds
uncertainty.
(b) Give an example (of necessarily dependent random variables) in which H(X) > H(Z)
and H(Y ) > H(Z).
(c) Under what conditions does H(Z) = H(X) + H(Y )?
2. Entropy of a disjoint mixture. Let X1 and X2 be discrete random variables drawn
according to probability mass functions p1 (.) and p2 (.) over the respective alphabets
χ1 = {1, 2, ..., m} and χ2 = {m + 1, 2, ..., n}.Let
X1 , with probability α,
X=
X2 , with probability 1 − α
(a) Find H(X) in terms of H(X1 ) and H(X2 ) and α.
(b) Maximize over α to show that 2H(X) ≤ 2H(X1 ) +2H(X2 ) and interpret using the notion
that 2H(X) is the effective alphabet size.
(c) Let X1 and X2 be uniformly distributed over their [Link] is the maximizing
α and the associated H(X)?
3. Mixing increases entropy. Show that the entropy of a probability distribution,
p +p p +p
(p1 , ....pi , ...pj , ...pm ), is less than the entropy of the distribution p1 , ..., i 2 j , .., i 2 j , .., pm .
In general any transfer of probablity that makes the distribution more uniform increases
the entropy.
4. Run length coding. Let X1 , X2 , ....Xn be (possibly dependent) binary random variables.
Suppose one calculates the run lengths R=(R1 , R2 , ...) of this sequence (in order as they
occur). For example,the sequence X = 0001100100 yields run lengths R=(3, 2, 2, 1, 2).
Compare H(X1 , X2 , ..., Xn ), H(R) and H(Xn , R). Show all equations and inequalities,
and bound all the differences.
5. Conditional mutual information vs. unconditional mutual information. Give examples of
joint random variables X, Y and Z such that
(a) I(X; Y |Z) < I(X; Y ),
(b) I(X; Y |Z) > I(X; Y ).
6. Data processing. Let X1 Õ X2 Õ X3 Õ ....Õ Xn form a Markov chain in this order; i.e.,
let
p (x1 , x2 , ..., xn ) = p (x1 ) p (x2 |x1 ) ...p (xn |xn−1 ) .
Reduce I(X1 ; X2 , ..., Xn ) to its simplest form.