Contents of Information Theory T M Cover and J A Thomas Wiley series in telecommunications NY 1991 1. Introduction and preview .................................. 1 2. Entropy, relative entropy and mutual information ........... 12 2.1 Entropy 2.2 Joint and conditional entrop 2.3 Relative entropy and mutual information 2.4 Relationship between entropy and mutual information 2.5 Chain rules 2.6 Jensen's inequality 2.7 The log sum inequality 2.8 Data processing 2.9 The second law of thermodynamics 2.10 Sufficient statistics 2.11 Fano's inequality 3. The asymptotic equirepartition property ................... 50 3.1 The AEP 3.2 Consequences of the AEP 3.3 High probability sets 4. Entropy rates of a stochastic process ..................... 60 4.1 Markov chains 4.2 Entropy rate 4.3 Example 4.4 Hidden Markov models 5. Data compression .......................................... 78 5.1 Examples of codes 5.2 Kraft inequality 5.3 Optimal codes 5.4 Bounds on optimal codelength 5.5 Kraft inequality 5.6 Hufmann codes 5.7 Comments on Hufmann codes 5.8 Optimality of Hufmann codes 5.9 Shannon-Fano-Elias coding 5.10 Arithmetic coding 5.11 Competitive optimality of Shannon code 5.12 Generation of discrete distributions from fair coins 6. Gambling and data compression ............................. 125 6.1 The horse race 6.2 Gambling 6.3 Dependent horse races 6.4 The entropy of English 6.5 Data compression and gambling 6.6 Gambling estimate of the entropy of English 7. Kolmogorov complexity ..................................... 144 7.1 Models of computation 7.2 Kolmogorov complexity: definitions and examples 7.3 Kolmogorov complexity and entropy 7.4 Kolmogorov complexity of integers 7.5 Algorithmically random incompressible sequences 7.6 Universal probability 7.7 Halting problem 7.8 $\Omega$ 7.9 Universal gambling 7.10 Occam's razor 7.11 Kolmogorov complexity and universal probability 7.12 The Kolmogorov sufficient statistic 8. Channel capacity .......................................... 183 8.1 Examples of channel capacity 8.2 Symmetric channels 8.3 Properties of channel capacity 8.4 Preview if channel coding theorem 8.5 Definitions 8.6 Jointly typical sequences 8.7 The channel coding theorem 8.8 Zero-error codes 8.9 Fano's inequality and the converse to the coding theorem 8.10 Equality in the converse to the channel coding 8.11 Hamming codes 8.12 Feedback capacity 8.13 The joint source channel coding 9. Differential entropy ..................................... 224 9.1 Definitions 9.2 The AEP for continuous variables 9.3 Relation of differential entropy 9.4 Joint and conditional differential entropy 9.5 Relative entropy and mutual information 9.6 Properties of differential entropy 9.7 Differential entropy bound on discrete entropy 10. The Gaussian channel ..................................... 239 10.1 Definitions 10.2 Converse to the coding theorem for Gaussian channels 10.3 Band-limited channels 10.4 Parallel Gaussian channels 10.5 Channels with coloured noise 10.6 Gaussian channels with feedback 11. Maximum entropy and spectral estimation .................. 266 11.1 Maximum entropy distributions 11.2 Examples 11.3 An anomalous maximum entropy problem 11.4 Spectrum estimation 11.5 Entropy rates 11.6 Burg's maximum entropy theorem 12. Information theory and statistics ........................ 279 12.1 The method of types 12.2 The law of large numbers 12.3 Universal source coding 12.4 Large deviation theory 12.5 Examples of Sanov's theorem 12.6 Conditional limit theorem 12.7 Hypothesis testing 12.8 Stein's lemma 12.9 Chernoff's bound 12.10 Lempel-Ziv coding 12.11 Fisher information 13. Rate distortion theory ................................... 336 13.1 Quantisation 13.2 Definitions 13.3 Calculation of rate distortion function 13.4 Converse to the rate distortion function 13.5 Achievability of the rate distortion function 13.6 Strongly typical sequences and rate distortion 13.7 Characterisation of the rate distortion function 13.8 Computation of channel capacity 14. Network information theory ............................... 374 14.1 Gaussian multiple user channels 14.2 Jointly typical sequences 14.3 Multiple access channel 14.4 Encoding correlated sources 14.5 Duality between Slepian-Wolf encoding and multiple access channels 14.6 Broadcast channel 14.7 Relay channel 14.8 Source coding with side information 14.9 Rate distortion with side information 14.10 General multiterminal networks 15. Information theory and the stock market .................. 459 15.1 Definitions 15.2 Kuhn-Tucker characterisation of log-optimal portofolio 15.3 Asymptotic optimality 15.4 Side-information 15.5 Investment in stationary markets 15.6 Competitive optimality 15.7 Shannon-McMillan-Breiman theorem 16. Inequalities in information theory ....................... 482 16.1 Basic inequalities 16.2 Differential entropy 16.3 Bounds on entropy 16.4 Inequalities for types 16.5 Entropy rates 16.6 Entropy and Fisher information 16.7 Brunn-Minkowski inequality 16.8 Inequalities for determinants 16.9 Inequalities for ratios of determinants Bibliography .................................................. 510 Symbols ....................................................... 526 Index ......................................................... 529