Extra Problems for Chapter 4

T.M. Cover and J.A. Thomas

  1. The past has little to say about the future. For a stationary stochastic process tex2html_wrap_inline490 , show that

    equation459

    Thus the dependence between adjacent n-blocks of a stationary process does not grow linearly with n.

  2. Functions of a stochastic process.
    1. Consider a stationary stochastic process tex2html_wrap_inline496 , and let tex2html_wrap_inline498 be defined by

      equation464

      for some function tex2html_wrap_inline500 . Prove that

      equation466

    2. What is the relationship between the entropy rates tex2html_wrap_inline502 and tex2html_wrap_inline504 if

      equation472

      for some function tex2html_wrap_inline506 .

  3. Stationary but not ergodic process. A bin has two biased coins, one with probability of heads p and the other with probability of heads 1-p. One of these coins is chosen at random (i.e., with probability 1/2), and is then tossed n times. Let X denote the identity of the coin that is picked, and let tex2html_wrap_inline516 and tex2html_wrap_inline518 denote the results of the first two tosses.
    1. Calculate tex2html_wrap_inline520 .
    2. Calculate tex2html_wrap_inline522 .
    3. Let tex2html_wrap_inline524 be the entropy rate of the Y process (the sequence of coin tosses). Calculate tex2html_wrap_inline524 . (Hint: Relate this to tex2html_wrap_inline530 ).

    You can check the answer by seeing the behavior as tex2html_wrap_inline532 .

  4. Random walk on graph. Consider a random walk on the graph
    1. Calculate the stationary distribution.
    2. What is the entropy rate?
    3. Find the mutual information tex2html_wrap_inline534 assuming the process is stationary.
  5. Entropy rate
    Let tex2html_wrap_inline536 be a stationary stochastic process with entropy rate tex2html_wrap_inline538 .
    1. Argue that tex2html_wrap_inline540 .
    2. What are the conditions for equality?
  6. Entropy rates

    Let tex2html_wrap_inline536 be a stationary process. Let tex2html_wrap_inline544 . Let tex2html_wrap_inline546 . Let tex2html_wrap_inline548 . Consider the entropy rates tex2html_wrap_inline538 , tex2html_wrap_inline552 , tex2html_wrap_inline554 , and tex2html_wrap_inline556 of the processes tex2html_wrap_inline536 , tex2html_wrap_inline560 , tex2html_wrap_inline562 , and tex2html_wrap_inline564 . What is the inequality relationship tex2html_wrap_inline566 , =, or tex2html_wrap_inline568 between each of the pairs listed below:

    1. tex2html_wrap_inline570 .
    2. tex2html_wrap_inline572 .
    3. tex2html_wrap_inline574 .
    4. tex2html_wrap_inline576 .
  7. Monotonicity.
    1. Show that tex2html_wrap_inline578 is non-decreasing in n.
    2. Under what conditions is the mutual information constant for all n?
  8. Transitions in Markov chains. Suppose tex2html_wrap_inline536 forms an irreducible Markov chain with transition matrix P and stationary distribution tex2html_wrap_inline588 . Form the associated ``edge-process'' tex2html_wrap_inline560 by keeping track only of the transitions. Thus the new process tex2html_wrap_inline560 takes values in tex2html_wrap_inline594 , and tex2html_wrap_inline596 .

    For example

    displaymath282

    becomes

    displaymath284

    Find the entropy rate of the edge process tex2html_wrap_inline560 .

  9. Maximal entropy graphs. Consider a random walk on a connected graph with 4 edges.
    1. Which graph has the highest entropy rate?
    2. Which graph has the lowest?
  10. Entropy rate

    Let tex2html_wrap_inline536 be a stationary tex2html_wrap_inline602 valued stochastic process obeying

    displaymath482

    where tex2html_wrap_inline562 is Bernoulli(p) and tex2html_wrap_inline608 denotes mod 2 addition. What is the entropy rate tex2html_wrap_inline538 ?

  11. Mixture of processes

    Suppose we observe one of two stochastic processes but don't know which. What is the entropy rate? Specifically, let tex2html_wrap_inline612 be a Bernoulli process with parameter tex2html_wrap_inline614 and let tex2html_wrap_inline616 be Bernoulli tex2html_wrap_inline618 . Let

    displaymath483

    and let tex2html_wrap_inline620 . be the observed stochastic process. Thus Y observes the process tex2html_wrap_inline624 or tex2html_wrap_inline626 .

    1. Is tex2html_wrap_inline560 stationary?
    2. Is tex2html_wrap_inline560 an i.i.d. process?
    3. What is the entropy rate H of tex2html_wrap_inline560 ?
    4. Does

      displaymath484

    5. Is there a code that achieves an expected per-symbol description length tex2html_wrap_inline636 ?

    Now let tex2html_wrap_inline638 be Bern( tex2html_wrap_inline640 ). Observe

    displaymath485

    Thus tex2html_wrap_inline642 is not fixed for all time, as it was in the first part, but is chosen i.i.d. each time. Answer (a), (b), (c), (d), (e) for the process tex2html_wrap_inline562 , labeling the answers (a tex2html_wrap_inline646 ), (b tex2html_wrap_inline646 ), (c tex2html_wrap_inline646 ), (d tex2html_wrap_inline646 ), (e tex2html_wrap_inline646 ).

  12. Graphs.
    Consider a random walk on a (connected) graph with 3 edges.
    1. Which graph has the lowest entropy rate?
    2. And what is the rate?


Latex file

Postscript file

 

Joy Thomas
Sat Aug 15 06:51:56 EDT 1998