WIXLIB

Elements of Information TheorySecond EditionSolutions to ProblemsThomas M. CoverJoy A. ThomasAugust 23, 2007

1COPYRIGHT 2006Thomas CoverJoy ThomasAll rights reserved

2

Contents1 Introduction72 Entropy, Relative Entropy and Mutual Information93 The Asymptotic Equipartition Property494 Entropy Rates of a Stochastic Process615 Data Compression976 Gambling and Data Compression1397 Channel Capacity1638 Differential Entropy2039 Gaussian channel21710 Rate Distortion Theory24111 Information Theory and Statistics27312 Maximum Entropy30713 Universal Source Coding32314 Kolmogorov Complexity33715 Network Information Theory34716 Information Theory and Portfolio Theory39317 Inequalities in Information Theory4073

4CONTENTS

PrefaceHere we have the solutions to all the problems in the second edition of Elements of InformationTheory. First a word about how the problems and solutions were generated.The problems arose over the many years the authors taught this course. At first thehomework problems and exam problems were generated each week. After a few years ofthis double duty, the homework problems were rolled forward from previous years and onlythe exam problems were fresh. So each year, the midterm and final exam problems becamecandidates for addition to the body of homework problems that you see in the text. Theexam problems are necessarily brief, with a point, and reasonable free from time consumingcalculation, so the problems in the text for the most part share these properties.The solutions to the problems were generated by the teaching assistants and graders forthe weekly homework assignments and handed back with the graded homeworks in the classimmediately following the date the assignment was due. Homeworks were optional and didnot enter into the course grade. Nonetheless most students did the homework. A list of themany students who contributed to the solutions is given in the book acknowledgment. Inparticular, we would like to thank Laura Ekroot, Will Equitz, Don Kimber, Mitchell Trott,Andrew Nobel, Jim Roche, Vittorio Castelli, Mitchell Oslick, Chien-Wen Tseng, Michael Morrell, Marc Goldberg, George Gemelos, Navid Hassanpour, Young-Han Kim, Charles Mathis,Styrmir Sigurjonsson, Jon Yard, Michael Baer, Mung Chiang, Suhas Diggavi, Elza Erkip,Paul Fahn, Garud Iyengar, David Julian, Yiannis Kontoyiannis, Amos Lapidoth, Erik Ordentlich, Sandeep Pombra, Arak Sutivong, Josh Sweetkind-Singer and Assaf Zeevi. We wouldlike to thank Prof. John Gill and Prof. Abbas El Gamal for many interesting problems andsolutions.The solutions therefore show a wide range of personalities and styles, although some ofthem have been smoothed out over the years by the authors. The best way to look at thesolutions is that they offer more than you need to solve the problems. And the solutions insome cases may be awkward or inefficient. We view that as a plus. An instructor can see theextent of the problem by examining the solution but can still improve his or her own version.The solution manual comes to some 400 pages. We are making electronic copies availableto course instructors in PDF. We hope that all the solutions are not put up on an insecurewebsite—it will not be useful to use the problems in the book for homeworks and exams if thesolutions can be obtained immediately with a quick Google search. Instead, we will put up asmall selected subset of problem solutions on our website, le to all. These will be problems that have particularly elegant or long solutions thatwould not be suitable homework or exam problems.5

6CONTENTSWe have also seen some people trying to sell the solutions manual on Amazon or Ebay.Please note that the Solutions Manual for Elements of Information Theory is copyrightedand any sale or distribution without the permission of the authors is not permitted.We would appreciate any comments, suggestions and corrections to this solutions manual.Tom CoverDurand 121, Information Systems LabStanford UniversityStanford, CA 94305.Ph. 650-723-4505FAX: 650-723-8473Email: cover@stanford.eduJoy ThomasStratify701 N Shoreline AvenueMountain View, CA 94043.Ph. 650-210-2722FAX: 650-988-2159Email: joythomas@stanfordalumni.org

Chapter 1Introduction7

8Introduction

Chapter 2Entropy, Relative Entropy andMutual Information1. Coin flips. A fair coin is flipped until the first head occurs. Let X denote the numberof flips required.(a) Find the entropy H(X) in bits. The following expressions may be useful: ! !1r ,1 rn 0nnr n n 0r.(1 r)2(b) A random variable X is drawn according to this distribution. Find an “efficient”sequence of yes-no questions of the form, “Is X contained in the set S ?” CompareH(X) to the expected number of questions required to determine X .Solution:(a) The number X of tosses till the first head appears has the geometric distributionwith parameter p 1/2 , where P (X n) pq n 1 , n {1, 2, . . .} . Hence theentropy of X isH(X) !pq n 1 log(pq n 1 )n 1" !n 0pq log p nn 0 p log p pq log q 1 qp2 p log p q log q p H(p)/p bits. If p 1/2 , then H(X) 2 bits.9 !npq log qn#

10Entropy, Relative Entropy and Mutual Information(b) Intuitively, it seems clear that the best questions are those that have equally likelychances of receiving a yes or a no answer. Consequently, one possible guess isthat the most “efficient” series of questions is: Is X 1 ? If not, is X 2 ?If not, is X 3 ? . . . with a resulting expected number of questions equal to nn 1 n(1/2 ) 2. This should reinforce the intuition that H(X) is a measure of the uncertainty of X . Indeed in this case, the entropy is exactly thesame as the average number of questions needed to define X , and in generalE(# of questions) H(X) . This problem has an interpretation as a source coding problem. Let 0 no, 1 yes, X Source, and Y Encoded Source. Thenthe set of questions in the above procedure can be written as a collection of (X, Y )pairs: (1, 1) , (2, 01) , (3, 001) , etc. . In fact, this intuitively derived code is theoptimal (Huffman) code minimizing the expected number of questions.2. Entropy of functions. Let X be a random variable taking on a finite number ofvalues. What is the (general) inequality relationship of H(X) and H(Y ) if(a) Y 2X ?(b) Y cos X ?Solution: Let y g(x) . Then!p(y) p(x).x: y g(x)Consider any set of x ’s that map onto a single y . For this set!x: y g(x)p(x) log p(x) !p(x) log p(y) p(y) log p(y),x: y g(x) since log is a monotone increasing function and p(x) x: y g(x) p(x) p(y) . Extending this argument to the entire range of X (and Y ), we obtainH(X) !p(x) log p(x)x!!p(x) log p(x)y x: y g(x)!p(y) log p(y)y H(Y ),with equality iff g is one-to-one with probability one.(a) Y 2X is one-to-one and hence the entropy, which is just a function of theprobabilities (and not the values of a random variable) does not change, i.e.,H(X) H(Y ) .(b) Y cos(X) is not necessarily one-to-one. Hence all that we can say is thatH(X) H(Y ) , with equality if cosine is one-to-one on the range of X .

Entropy, Relative Entropy and Mutual Information113. Minimum entropy. What is the minimum value of H(p 1 , ., pn ) H(p) as p rangesover the set of n -dimensional probability vectors? Find all p ’s which achieve thisminimum.Solution: We wish to find all probability vectors p (p 1 , p2 , . . . , pn ) which minimizeH(p) !pi log pi .iNow pi log pi 0 , with equality iff pi 0 or 1 . Hence the only possible probabilityvectors which minimize H(p) are those with p i 1 for some i and pj 0, j % i .There are n such vectors, i.e., (1, 0, . . . , 0) , (0, 1, 0, . . . , 0) , . . . , (0, . . . , 0, 1) , and theminimum value of H(p) is 0.4. Entropy of functions of a random variable. Let X be a discrete random variable.Show that the entropy of a function of X is less than or equal to the entropy of X byjustifying the following steps:H(X, g(X))(a) (b) H(X, g(X))(c) (d) Thus H(g(X)) H(X).H(X) H(g(X) X)(2.1)H(X);(2.2)H(g(X)) H(X g(X))(2.3)H(g(X)).(2.4)Solution: Entropy of functions of a random variable.(a) H(X, g(X)) H(X) H(g(X) X) by the chain rule for entropies.(b) H(g(X) X) 0 since for any particular value of X, g(X) is fixed, and hence H(g(X) X) x p(x)H(g(X) X x) x 0 0 .(c) H(X, g(X)) H(g(X)) H(X g(X)) again by the chain rule.(d) H(X g(X)) 0 , with equality iff X is a function of g(X) , i.e., g(.) is one-to-one.Hence H(X, g(X)) H(g(X)) .Combining parts (b) and (d), we obtain H(X) H(g(X)) .5. Zero conditional entropy. Show that if H(Y X) 0 , then Y is a function of X ,i.e., for all x with p(x) 0 , there is only one possible value of y with p(x, y) 0 .Solution: Zero Conditional Entropy. Assume that there exists an x , say x 0 and twodifferent values of y , say y1 and y2 such that p(x0 , y1 ) 0 and p(x0 , y2 ) 0 . Thenp(x0 ) p(x0 , y1 ) p(x0 , y2 ) 0 , and p(y1 x0 ) and p(y2 x0 ) are not equal to 0 or 1.ThusH(Y X) !xp(x)!p(y x) log p(y x) p(x0 )( p(y1 x0 ) log p(y1 x0 ) p(y2 x0 ) log p(y2 x0 )) 0,(2.5)y(2.6)(2.7)

12Entropy, Relative Entropy and Mutual Informationsince t log t 0 for 0 t 1 , and is strictly positive for t not equal to 0 or 1.Therefore the conditional entropy H(Y X) is 0 if and only if Y is a function of X .6. Conditional mutual information vs. unconditional mutual information. Giveexamples 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 ) .Solution: Conditional mutual information vs. unconditional mutual information.(a) The last corollary to Theorem 2.8.1 in the text states that if X Y Z thatis, if p(x, y z) p(x z)p(y z) then, I(X; Y ) I(X; Y Z) . Equality holds ifand only if I(X; Z) 0 or X and Z are independent.A simple example of random variables satisfying the inequality conditions aboveis, X is a fair binary random variable and Y X and Z Y . In this case,I(X; Y ) H(X) H(X Y ) H(X) 1and,I(X; Y Z) H(X Z) H(X Y, Z) 0.So that I(X; Y ) I(X; Y Z) .(b) This example is also given in the text. Let X, Y be independent fair binaryrandom variables and let Z X Y . In this case we have that,I(X; Y ) 0and,I(X; Y Z) H(X Z) 1/2.So I(X; Y ) I(X; Y Z) . Note that in this case X, Y, Z are not markov.7. Coin weighing. Suppose one has n coins, among which there may or may not be onecounterfeit coin. If there is a counterfeit coin, it may be either heavier or lighter thanthe other coins. The coins are to be weighed by a balance.(a) Find an upper bound on the number of coins n so that k weighings will find thecounterfeit coin (if any) and correctly declare it to be heavier or lighter.(b) (Difficult) What is the coin weighing strategy for k 3 weighings and 12 coins?Solution: Coin weighing.(a) For n coins, there are 2n 1 possible situations or “states”. One of the n coins is heavier. One of the n coins is lighter. They are all of equal weight.