Extra Problems for Chapter 2

T.M. Cover and J.A. Thomas

 

  1. Relative entropy is not symmetric: Let the random variable X have three possible outcomes tex2html_wrap_inline434 . Consider two distributions on this random variable

    tabular217

    Calculate H(p), H(q), D(p||q) and D(q||p). Verify that in this case tex2html_wrap_inline448 .

  2. Symmetric relative entropy: Though, as the previous example shows, tex2html_wrap_inline448 in general, there could be distributions for which equality holds. Give an example of two distributions p and q on a binary alphabet such that D(p||q) = D(q||p) (other than the trivial case when p = q).
  3. Relative entropy is cost of miscoding: Let the random variable X have five possible outcomes tex2html_wrap_inline462 . Consider two distributions on this random variable

    tabular222

    1. Calculate H(p), H(q), D(p||q) and D(q||p).
    2. The last two columns above represent codes for the random variable. Verify that the average length of tex2html_wrap_inline480 under p is equal to the entropy H(p). Thus tex2html_wrap_inline480 is optimal for p. Verify that tex2html_wrap_inline490 is optimal for q.
    3. Now assume that we use code tex2html_wrap_inline490 when the distribution is p. What is the average length of the codewords. By how much does it exceed the entropy p?
    4. What is the loss if we use code tex2html_wrap_inline480 when the distribution is q?
  4. Another proof of non-negativity of relative entropy. In view of the fundamental nature of the result tex2html_wrap_inline504 , we will give another proof.
    1. Show that tex2html_wrap_inline506 for tex2html_wrap_inline508 .
    2. Justify the following steps:

      eqnarray414

    3. What are the conditions for equality?
  5. Grouping rule for entropy: Let tex2html_wrap_inline510 be a probability distribution on m elements, i.e, tex2html_wrap_inline514 , and tex2html_wrap_inline516 . Define a new distribution tex2html_wrap_inline518 on m-1 elements as tex2html_wrap_inline522 , tex2html_wrap_inline524 ,..., tex2html_wrap_inline526 , and tex2html_wrap_inline528 , i.e., the distribution tex2html_wrap_inline518 is the same as tex2html_wrap_inline532 on tex2html_wrap_inline534 , and the probability of the last element in tex2html_wrap_inline518 is the sum of the last two probabilities of tex2html_wrap_inline532 . Show that

    equation422

    where tex2html_wrap_inline540 .

  6. Relative Entropy: Let X,Y,Z be three random variables with a joint probability mass function p(x,y,z). The relative entropy between the joint distribution and the product of the marginals is

    equation426

    Expand this in terms of entropies. When is this quantity zero?

  7. The value of a question Let tex2html_wrap_inline546 , tex2html_wrap_inline548 . We are given a set tex2html_wrap_inline550 . We ask whether tex2html_wrap_inline552 and receive the answer

    displaymath430

    Suppose tex2html_wrap_inline554 . Find the decrease in uncertainty H(X)-H(X|Y).

    Apparently any set S with a given tex2html_wrap_inline560 is as good as any other.

  8. Entropy and pairwise independence.
    Let X,Y,Z be three binary Bernoulli tex2html_wrap_inline564 random variables that are pairwise independent, that is, I(X;Y)=I(X;Z)=I(Y;Z)=0.
    1. Under this constraint, what is the minimum value for H(X,Y,Z)?
    2. Give an example achieving this minimum.
  9. Discrete entropies

    Let X and Y be two independent integer-valued random variables. Let X be uniformly distributed over tex2html_wrap_inline576 , and let tex2html_wrap_inline578 , tex2html_wrap_inline580

    1. Find H(X)
    2. Find H(Y)
    3. Find H(X+Y, X-Y).
  10. Random questions

    One wishes to identify a random object tex2html_wrap_inline546 . A question tex2html_wrap_inline590 is asked at random according to r(q). This results in a deterministic answer tex2html_wrap_inline594 . Suppose X and Q are independent. Then I(X;Q,A) is the uncertainty in X removed by the question-answer (Q,A).

    1. Show I(X;Q,A)=H(A|Q). Interpret.
    2. Now suppose that two i.i.d. questions tex2html_wrap_inline608 are asked, eliciting answers tex2html_wrap_inline610 and tex2html_wrap_inline612 . Show that two questions are less valuable than twice a single question in the sense that tex2html_wrap_inline614 .
  11. Inequalities. Which of the following inequalities are generally tex2html_wrap_inline616 ? Label each with tex2html_wrap_inline618 or tex2html_wrap_inline620 .
    1. H(5X) vs. H(X)
    2. I(g(X);Y) vs. I(X;Y)
    3. tex2html_wrap_inline630 vs. tex2html_wrap_inline632
    4. tex2html_wrap_inline634 vs. tex2html_wrap_inline636 , where tex2html_wrap_inline638 is the Huffman codeword assigned to tex2html_wrap_inline640 .
    5. H(X,Y)/(H(X)+H(Y)) vs. 1
  12. Mutual information of heads and tails.
    1. Consider a fair coin flip. What is the mutual information between the top side and the bottom side of the coin?
    2. A 6-sided fair die is rolled. What is the mutual information between the top side and the front face (the side most facing you)?
  13. Conditional probability and relative entropy: Let tex2html_wrap_inline366 be the conditional probability of X given that X is in the set B. Show that

    equation360

  14. Pure randomness

    We wish to use a 3-sided coin to generate a fair coin toss. Let the coin X have probability mass function

    displaymath364

    where tex2html_wrap_inline376 are unknown.

    1. How would you use 2 independent flips tex2html_wrap_inline378 to generate (if possible) a Bernoulli( tex2html_wrap_inline380 ) random variable Z?
    2. What is the resulting maximum expected number of fair bits generated?
  15. Finite entropy. Show that for a discrete random variable tex2html_wrap_inline384 , if tex2html_wrap_inline386 , then tex2html_wrap_inline388 .
  16. The entropy of a missorted file.
    A deck of n cards in order tex2html_wrap_inline392 is provided. One card is removed at random then replaced at random. What is the entropy of the resulting deck?


Latex file

Postscript file

Joy Thomas
Sat Aug 15 20:29:04 EDT 1998