| |

| |

Preface to the Second Edition | |

| |

| |

Preface to the First Edition | |

| |

| |

Acknowledgments for the Second Edition | |

| |

| |

Acknowledgments for the First Edition | |

| |

| |

| |

Introduction and Preview | |

| |

| |

| |

Preview of the Book | |

| |

| |

| |

Entropy, Relative Entropy, and Mutual Information | |

| |

| |

| |

Entropy | |

| |

| |

| |

Joint Entropy and Conditional Entropy | |

| |

| |

| |

Relative Entropy and Mutual Information | |

| |

| |

| |

Relationship Between Entropy and Mutual Information | |

| |

| |

| |

Chain Rules for Entropy, Relative Entropy, and Mutual Information | |

| |

| |

| |

Jensen's Inequality and Its Consequences | |

| |

| |

| |

Log Sum Inequality and Its Applications | |

| |

| |

| |

Data-Processing Inequality | |

| |

| |

| |

Sufficient Statistics | |

| |

| |

| |

Fano's Inequality | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Asymptotic Equipartition Property | |

| |

| |

| |

Asymptotic Equipartition Property Theorem | |

| |

| |

| |

Consequences of the AEP: Data Compression | |

| |

| |

| |

High-Probability Sets and the Typical Set | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Entropy Rates of a Stochastic Process | |

| |

| |

| |

Markov Chains | |

| |

| |

| |

Entropy Rate | |

| |

| |

| |

Example: Entropy Rate of a Random Walk on a Weighted Graph | |

| |

| |

| |

Second Law of Thermodynamics | |

| |

| |

| |

Functions of Markov Chains | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Data Compression | |

| |

| |

| |

Examples of Codes | |

| |

| |

| |

Kraft Inequality | |

| |

| |

| |

Optimal Codes | |

| |

| |

| |

Bounds on the Optimal Code Length | |

| |

| |

| |

Kraft Inequality for Uniquely Decodable Codes | |

| |

| |

| |

Huffman Codes | |

| |

| |

| |

Some Comments on Huffman Codes | |

| |

| |

| |

Optimality of Huffman Codes | |

| |

| |

| |

Shannon-Fano-Elias Coding | |

| |

| |

| |

Competitive Optimality of the Shannon Code | |

| |

| |

| |

Generation of Discrete Distributions from Fair Coins | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Gambling and Data Compression | |

| |

| |

| |

The Horse Race | |

| |

| |

| |

Gambling and Side Information | |

| |

| |

| |

Dependent Horse Races and Entropy Rate | |

| |

| |

| |

The Entropy of English | |

| |

| |

| |

Data Compression and Gambling | |

| |

| |

| |

Gambling Estimate of the Entropy of English | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Channel Capacity | |

| |

| |

| |

Examples of Channel Capacity | |

| |

| |

| |

Symmetric Channels | |

| |

| |

| |

Properties of Channel Capacity | |

| |

| |

| |

Preview of the Channel Coding Theorem | |

| |

| |

| |

Definitions | |

| |

| |

| |

Jointly Typical Sequences | |

| |

| |

| |

Channel Coding Theorem | |

| |

| |

| |

Zero-Error Codes | |

| |

| |

| |

Fano's Inequality and the Converse to the Coding Theorem | |

| |

| |

| |

Equality in the Converse to the Channel Coding Theorem | |

| |

| |

| |

Hamming Codes | |

| |

| |

| |

Feedback Capacity | |

| |

| |

| |

Source-Channel Separation Theorem | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Differential Entropy | |

| |

| |

| |

Definitions | |

| |

| |

| |

AEP for Continuous Random Variables | |

| |

| |

| |

Relation of Differential Entropy to Discrete Entropy | |

| |

| |

| |

Joint and Conditional Differential Entropy | |

| |

| |

| |

Relative Entropy and Mutual Information | |

| |

| |

| |

Properties of Differential Entropy, Relative Entropy, and Mutual Information | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Gaussian Channel | |

| |

| |

| |

Gaussian Channel: Definitions | |

| |

| |

| |

Converse to the Coding Theorem for Gaussian Channels | |

| |

| |

| |

Bandlimited Channels | |

| |

| |

| |

Parallel Gaussian Channels | |

| |

| |

| |

Channels with Colored Gaussian Noise | |

| |

| |

| |

Gaussian Channels with Feedback | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Rate Distortion Theory | |

| |

| |

| |

Quantization | |

| |

| |

| |

Definitions | |

| |

| |

| |

Calculation of the Rate Distortion Function | |

| |

| |

| |

Converse to the Rate Distortion Theorem | |

| |

| |

| |

Achievability of the Rate Distortion Function | |

| |

| |

| |

Strongly Typical Sequences and Rate Distortion | |

| |

| |

| |

Characterization of the Rate Distortion Function | |

| |

| |

| |

Computation of Channel Capacity and the Rate Distortion Function | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Information Theory and Statistics | |

| |

| |

| |

Method of Types | |

| |

| |

| |

Law of Large Numbers | |

| |

| |

| |

Universal Source Coding | |

| |

| |

| |

Large Deviation Theory | |

| |

| |

| |

Examples of Sanov's Theorem | |

| |

| |

| |

Conditional Limit Theorem | |

| |

| |

| |

Hypothesis Testing | |

| |

| |

| |

Chernoff-Stein Lemma | |

| |

| |

| |

Chernoff Information | |

| |

| |

| |

Fisher Information and the Cramï¿½er-Rao Inequality | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Maximum Entropy | |

| |

| |

| |

Maximum Entropy Distributions | |

| |

| |

| |

Examples | |

| |

| |

| |

Anomalous Maximum Entropy Problem | |

| |

| |

| |

Spectrum Estimation | |

| |

| |

| |

Entropy Rates of a Gaussian Process | |

| |

| |

| |

Burg's Maximum Entropy Theorem | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Universal Source Coding | |

| |

| |

| |

Universal Codes and Channel Capacity | |

| |

| |

| |

Universal Coding for Binary Sequences | |

| |

| |

| |

Arithmetic Coding | |

| |

| |

| |

Lempel-Ziv Coding | |

| |

| |

| |

Optimality of Lempel-Ziv Algorithms | |

| |

| |

Compression | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Kolmogorov Complexity | |

| |

| |

| |

Models of Computation | |

| |

| |

| |

Kolmogorov Complexity: Definitions and Examples | |

| |

| |

| |

Kolmogorov Complexity and Entropy | |

| |

| |

| |

Kolmogorov Complexity of Integers | |

| |

| |

| |

Algorithmically Random and Incompressible Sequences | |

| |

| |

| |

Universal Probability | |

| |

| |

| |

Kolmogorov complexity | |

| |

| |

| |

Universal Gambling | |

| |

| |

| |

Occam's Razor | |

| |

| |

| |

Kolmogorov Complexity and Universal Probability | |

| |

| |

| |

Kolmogorov Sufficient Statistic | |

| |

| |

| |

Minimum Description Length Principle | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Network Information Theory | |

| |

| |

| |

Gaussian Multiple-User Channels | |

| |

| |

| |

Jointly Typical Sequences | |

| |

| |

| |

Multiple-Access Channel | |

| |

| |

| |

Encoding of Correlated Sources | |

| |

| |

| |

Duality Between Slepian-Wolf Encoding and Multiple-Access Channels | |

| |

| |

| |

Broadcast Channel | |

| |

| |

| |

Relay Channel | |

| |

| |

| |

Source Coding with Side Information | |

| |

| |

| |

Rate Distortion with Side Information | |

| |

| |

| |

General Multiterminal Networks | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Information Theory and Portfolio Theory | |

| |

| |

| |

The Stock Market: Some Definitions | |

| |

| |

| |

Kuhn-Tucker Characterization of the Log-Optimal Portfolio | |

| |

| |

| |

Asymptotic Optimality of the Log-Optimal Portfolio | |

| |

| |

| |

Side Information and the Growth Rate | |

| |

| |

| |

Investment in Stationary Markets | |

| |

| |

| |

Competitive Optimality of the Log-Optimal Portfolio | |

| |

| |

| |

Universal Portfolios | |

| |

| |

| |

Shannon-McMillan-Breiman Theorem | |

| |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

| |

Inequalities in Information Theory | |

| |

| |

| |

Basic Inequalities of Information Theory | |

| |

| |

| |

Differential Entropy | |

| |

| |

| |

Bounds on Entropy and Relative Entropy | |

| |

| |

| |

Inequalities for Types | |

| |

| |

| |

Combinatorial Bounds on Entropy | |

| |

| |

| |

Entropy Rates of Subsets | |

| |

| |

| |

Entropy and Fisher Information | |

| |

| |

| |

Entropy Power Inequality and Brunn-Minkowski Inequality | |

| |

| |

| |

Inequalities for Determinants | |

| |

| |

| |

Inequalities for Ratios of Determinants | |

| |

| |

Summary | |

| |

| |

Problems | |

| |

| |

Historical Notes | |

| |

| |

Bibliography | |

| |

| |

List of Symbols | |

| |

| |

Index | |