ALL CHAPTERS COVERED
,Contents
1 Introduction 7
2 Entropy, Relative Entropy and Mutual Information 9
3 The Asymptotic Equipartition Property 49
4 Entropy Rates of a Stochastic Process 61
5 Data Compression 97
6 Gambling and Data Compression 139
7 Channel Capacity 163
8 Differential Entropy 203
9 Gaussian channel 217
10 Rate Distortion Theory 241
11 Information Theory and Statistics 273
12 Maximum Entropy 301
13 Universal Source Coding 309
14 Kolmogorov Complexity 321
15 Network Information Theory 331
16 Information Theory and Portfolio Theory 377
17 Inequalities in Information Theory 391
3
,Preface
Here we have the solutions to all the problems in the second edition of Elements of Information
Theory. 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 the
homework problems and exam problems were generated each week. After a few years of
this double duty, the homework problems were rolled forward from previous years and only
the exam problems were fresh. So each year, the midterm and final exam problems became
candidates for addition to the body of homework problems that you see in the text. The
exam problems are necessarily brief, with a point, and reasonable free from time consuming
calculation, 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 for
the weekly homework assignments and handed back with the graded homeworks in the class
immediately following the date the assignment was due. Homeworks were optional and did
not enter into the course grade. Nonetheless most students did the homework. A list of the
many students who contributed to the solutions is given in the book acknowledgment. In
particular, 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 Mor-
rell, 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 Or-
dentlich, Sandeep Pombra, Arak Sutivong, Josh Sweetkind-Singer and Assaf Zeevi. We would
like to thank Prof. John Gill and Prof. Abbas El Gamal for many interesting problems and
solutions.
The solutions therefore show a wide range of personalities and styles, although some of
them have been smoothed out over the years by the authors. The best way to look at the
solutions is that they offer more than you need to solve the problems. And the solutions in
some cases may be awkward or inefficient. We view that as a plus. An instructor can see the
extent 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 available
to course instructors in PDF. We hope that all the solutions are not put up on an insecure
website—it will not be useful to use the problems in the book for homeworks and exams if the
solutions can be obtained immediately with a quick Google search. Instead, we will put up a
small selected subset of problem solutions on our website, http://www.elementsofinformationtheory.com,
available to all. These will be problems that have particularly elegant or long solutions that
would not be suitable homework or exam problems.
5
, 6 CONTENTS
We 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 copyrighted
and 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 Cover Joy Thomas
Durand 121, Information Systems Lab Stratify
Stanford University 701 N Shoreline Avenue
Stanford, CA 94305. Mountain View, CA 94043.
Ph. 650-723-4505 Ph. 650-210-2722
FAX: 650-723-8473 FAX: 650-988-2159
Email: Email:
,Contents
1 Introduction 7
2 Entropy, Relative Entropy and Mutual Information 9
3 The Asymptotic Equipartition Property 49
4 Entropy Rates of a Stochastic Process 61
5 Data Compression 97
6 Gambling and Data Compression 139
7 Channel Capacity 163
8 Differential Entropy 203
9 Gaussian channel 217
10 Rate Distortion Theory 241
11 Information Theory and Statistics 273
12 Maximum Entropy 301
13 Universal Source Coding 309
14 Kolmogorov Complexity 321
15 Network Information Theory 331
16 Information Theory and Portfolio Theory 377
17 Inequalities in Information Theory 391
3
,Preface
Here we have the solutions to all the problems in the second edition of Elements of Information
Theory. 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 the
homework problems and exam problems were generated each week. After a few years of
this double duty, the homework problems were rolled forward from previous years and only
the exam problems were fresh. So each year, the midterm and final exam problems became
candidates for addition to the body of homework problems that you see in the text. The
exam problems are necessarily brief, with a point, and reasonable free from time consuming
calculation, 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 for
the weekly homework assignments and handed back with the graded homeworks in the class
immediately following the date the assignment was due. Homeworks were optional and did
not enter into the course grade. Nonetheless most students did the homework. A list of the
many students who contributed to the solutions is given in the book acknowledgment. In
particular, 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 Mor-
rell, 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 Or-
dentlich, Sandeep Pombra, Arak Sutivong, Josh Sweetkind-Singer and Assaf Zeevi. We would
like to thank Prof. John Gill and Prof. Abbas El Gamal for many interesting problems and
solutions.
The solutions therefore show a wide range of personalities and styles, although some of
them have been smoothed out over the years by the authors. The best way to look at the
solutions is that they offer more than you need to solve the problems. And the solutions in
some cases may be awkward or inefficient. We view that as a plus. An instructor can see the
extent 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 available
to course instructors in PDF. We hope that all the solutions are not put up on an insecure
website—it will not be useful to use the problems in the book for homeworks and exams if the
solutions can be obtained immediately with a quick Google search. Instead, we will put up a
small selected subset of problem solutions on our website, http://www.elementsofinformationtheory.com,
available to all. These will be problems that have particularly elegant or long solutions that
would not be suitable homework or exam problems.
5
, 6 CONTENTS
We 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 copyrighted
and 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 Cover Joy Thomas
Durand 121, Information Systems Lab Stratify
Stanford University 701 N Shoreline Avenue
Stanford, CA 94305. Mountain View, CA 94043.
Ph. 650-723-4505 Ph. 650-210-2722
FAX: 650-723-8473 FAX: 650-988-2159
Email: Email:
