Extra Problems for Chapter 3

T.M. Cover and J.A. Thomas

1.   Calculation of typical set To clarify the notion of a typical set and the smallest set of high probability , we will calculate the set for a simple example. Consider a sequence of i.i.d. binary random variables, , where the probability that is 0.6 (and therefore the probability that is 0.4).
   1. Calculate H(X).
   2. With n=25 and , which sequences fall in the typical set ? What is the probability of the typical set? How many elements are there in the typical set? (This involves computation of a table of probabilities for sequences with k 1's, , and finding those sequences that are in the typical set.)

      

   3. How many elements are there in the smallest set that has probability 0.9?
   4. How many elements are there in the intersection of the sets in part (b) and (c)? What is the probability of this intersection?
2. Monotonic convergence of the empirical distribution. Let denote the empirical probability mass function corresponding to i.i.d. . Specifically,

   

   is the proportion of times that in the first n samples, where I is an indicator function.

   1. Show for binary that

      

      Thus the expected relative entropy ``distance'' from the empirical distribution to the true distribution decreases with sample size.
      Hint: Write and use the convexity of D.

   2. Show for an arbitrary discrete that

      

      Hint: Write as the average of n empirical mass functions with each of the n samples deleted in turn.

3. AEP. Let be i.i.d. . We form the log likelihood ratio of the hypothesis that X and Y are independent vs. the hypothesis that X and Y are dependent. What is the limit of

   

   
   

Latex file
Postscript file