Extra Problems for Chapter 12

T.M. Cover and J.A. Thomas

1. Stirling's approximation: Derive a weak form of Stirling's approximation for factorials, i.e., show that

   

   using the approximation of integrals by sums. Justify the following steps:

   

   and

   

2. Asymptotic value of . Use the simple approximation of the previous problem to show that, if , and , i.e., k is the largest integer less than or equal to np, then

   

   Now let , be a probability distribution on m symbols, i.e., , and . What is the limiting value of

   

3. Sanov's theorem: Prove the simple version of Sanov's theorem for the binary random variables, i.e., let be a sequence of binary random variables, drawn i.i.d. according to the following distribution:

   

   Let the proportion of 1's in the sequence be , i.e.,

   

   By the laws of large numbers, we would expect to be close to q for large n. Sanov's theorem deals with the probability that is far away from q. In particular, for concreteness, if we take , Sanov's theorem states that

   

   Justify the following steps:

   • 
   • Argue that the term corresponding to is the largest term in the sum on the right hand side of the last equation.
   • Show that this term is approximately .
   • Prove an upper bound on the probability in Sanov's theorem using the above steps. Use similar arguments to prove a lower bound and complete the proof of Sanov's theorem.
4. Sanov. Let be i.i.d.
   1. Find the exponent in the behavior of This can be done from first principles (since the normal distribution is nice) or by using Sanov's theorem.
   2. What does the data look like if ? That is, what is the that minimizes ?
5. Counting states.
   Suppose an atom is equally likely to be in each of 6 states, . One observes n atoms independently drawn according to this uniform distribution. It is observed that the frequency of occurrence of state is twice the frequency of occurrence of state .
   1. To first order in the exponent, what is the probability of observing this event?
   2. Assuming n large, find the conditional distribution of the state of the first atom , given this observation.
6. Hypothesis testing

   Let be i.i.d. , . Consider two hypotheses vs. , where , and ,

   1. Find .
   2. Let . Find the minimal probability of error test for vs. given data .
7. Maximum likelihood estimation. Let denote a parametric family of densities with parameter . Let be i.i.d. . The function

   

   is known as the log likelihood function. Let denote the true parameter value.

   1. Let the expected log likelihood be

      

      and show that

      

   2. Show that the maximum over of the expected log likelihood is achieved by .
8. Large deviations. Let be i.i.d. random variables drawn according to the geometric distribution

   

   Find good estimates (to first order in the exponent) of

   1. 
   2. 
   3. Evaluate a) and b) for .
9. Another expression for Fisher information. Use integration by parts to show that

   

10. The running problem.. Let be i.i.d. , and be i.i.d. . Let and be independent. Find an expression for , good to first order in the exponent. Again, this answer can be left in parametric form.
11. Large likelihoods. Let be i.i.d. , . Let P(x) be some other probability mass function. We form the log likelihood ratio

    

    of the sequence and ask for the probability that it exceeds a certain threshold. Specifically, find (to first order in the exponent)

    

    There may be an undetermined parameter in the answer.

12. Fisher information for mixtures. Let and be two given probability densities. Let Z be Bernoulli( ), where is unknown. Let , if Z=1 and , if Z=0.
    1. Find the density of the observed X.
    2. Find the Fisher information .
    3. What is the Cramér-Rao lower bound on the mean squared error of an unbiased estimate of ?
    4. Can you exhibit an unbiased estimator of ?
13. Bent coins. Let be iid where

    

    Thus, the 's are iid Binomial (m,q).

    Show that, as ,

    

    where is Binomial (i.e. for some .

    Find .

14. Conditional limiting distribution.
    1. Find the exact value of

       

       if are Bernoulli( ) and n is a multiple of 4.

    2. Now let and let be i.i.d. uniform over Find the limit of

       

       for .

15. Hypothesis testing. Let be i.i.d. . Consider the hypothesis test versus . Let

    

    and

    

    1. Find the error exponent for Pr{ Decide true } in the best hypothesis test of vs. subject to Pr{ Decide true } .
16. Two envelope problem: One envelope contains b dollars, the other 2b dollars. The amount b is unknown. An envelope is selected at random. Let X be the amount observed in this envelope, and let Y be the amount in the other envelope.

    Adopt the strategy of switching to the other envelope with probability p(x), where . Let Z be the amount that the player receives. Thus

    

    

    1. Show that .
    2. Show that E(Y/X) = 5/4. (This is the origin of the switching paradox.) Observe that .
    3. Let J be the index of the envelope containing the maximum amount of money, and let J' be the index of the envelope chosen by the algorithm. Show that for any b, I(J; J') > 0. Thus the amount in the first envelope always contains some information about which envelope to choose.
    4. Show that E(Z) > E(X).
17. Variational inequality: Verify, for positive random variables X, that

    

    where and , and the supremum is over all , . It is enough to extremize .

Latex file

Postscript file