Elements of Information Theory
Second Edition
Solutions to Problems
Thomas M. Cover
Joy A. Thomas
September 22, 2006
1
COPYRIGHT 2006
Thomas Cover
Joy Thomas
All rights reserved
2
Contents
1 Introduction
2 Entropy, Relative Entropy and Mutual Information
3 The Asymptotic Equipartition Property
4 Entropy Rates of a Stochastic Process
5 Data Compression
6 Gambling and Data Compression
7
9
49
61
97
139
3
4
CONTENTS
Preface
The problems in the book, \Elements of Information Theory, Second Edition", were chosen
from the problems used during the course at Stanford. Most of the solutions here were
prepared by the graders and instructors of the course. We would particularly like to thank
Prof. John Gill, David Evans, Jim Roche, Laura Ekroot and Young Han Kim for their help
in preparing these solutions.
Most of the problems in the book are straightforward, and we have included hints in
the problem statement for the dicult problems. In some cases, the solutions include extra
material of interest (for example, the problem on coin weighing on Pg. 12).
We would appreciate any comments, suggestions and corrections to this Solutions Man-
ual.
Tom Cover
Durand 121, Information Systems Lab
Joy Thomas
Stratify
Stanford University
Stanford, CA 94305.
Ph. 415-723-4505
FAX: 415-723-8473
701 N Shoreline Avenue
Mountain View, CA 94043.
Ph. 650-210-2722
FAX: 650-988-2159
Email: cover@isl.stanford.edu
Email: jat@stratify.com
5
6
CONTENTS
Chapter 1
Introduction
7