ELEMENTS OF INFORMATION THEORY
CONTENTS 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 SUF?CIENT 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 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 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 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 CHANNEL CAPACITY EXAMPLES OF CHANNEL CAPACITY NOISELESS BINARY CHANNEL NOISY CHANNEL WITH NONOVERLAPPING OUTPUTS NOISY TYPEWRITER BINARY SYMMETRIC CHANNEL BINARY ERASURE CHANNEL SYMMETRIC CHANNELS PROPERTIES OF CHANNEL CAPACITY PREVIEW OF THE CHANNEL CODING THEOREM DE?NITIONS 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 DIFFERENTIAL ENTROPY AEP FOR CONTINUOUS RANDOM VARIABLES RELATION OF DIFFERENTIAL ENTROPY TO DISCRETE ENTROPY JOINT AND CONDITIONAL DIFFERENTIAL ENTROPY PROPERTIES OF DIFFERENTIAL ENTROPY, RELATIVE ENTROPY, AND MUTUAL INFORMATION GAUSSIAN CHANNEL GAUSSIAN CHANNEL: DE?NITIONS CONVERSE TO THE CODING THEOREM FOR GAUSSIAN CHANNELS BANDLIMITED CHANNELS PARALLEL GAUSSIAN CHANNELS CHANNELS WITH COLORED GAUSSIAN NOISE GAUSSIAN CHANNELS WITH FEEDBACK RATE DISTORTION THEORY QUANTIZATION CALCULATION OF THE RATE DISTORTION FUNCTION BINARY SOURCE GAUSSIAN SOURCE SIMULTANEOUS DESCRIPTION OF INDEPENDENT GAUSSIAN RANDOM VARIABLES 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 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 MAXIMUM ENTROPY MAXIMUM ENTROPY DISTRIBUTIONS EXAMPLES ANOMALOUS MAXIMUM ENTROPY PROBLEM SPECTRUM ESTIMATION ENTROPY RATES OF A GAUSSIAN PROCESS BURG’S MAXIMUM ENTROPY THEOREM UNIVERSAL CODES AND CHANNEL CAPACITY UNIVERSAL CODING FOR BINARY SEQUENCES ARITHMETIC CODING LEMPEL–ZIV CODING SLIDING WINDOW LEMPEL–ZIV ALGORITHM TREE-STRUCTURED LEMPEL–ZIV ALGORITHMS OPTIMALITY OF LEMPEL–ZIV ALGORITHMS SLIDING WINDOW LEMPEL–ZIV ALGORITHMS OPTIMALITY OF TREE-STRUCTURED LEMPEL–ZIV COMPRESSION KOLMOGOROV COMPLEXITY MODELS OF COMPUTATION KOLMOGOROV COMPLEXITY: DE?NITIONS 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 SUF?CIENT STATISTIC MINIMUM DESCRIPTION LENGTH PRINCIPLE NETWORK INFORMATION THEORY GAUSSIAN MULTIPLE-USER CHANNELS SINGLE-USER GAUSSIAN CHANNEL GAUSSIAN MULTIPLE-ACCESS CHANNEL WITH M USERS GAUSSIAN BROADCAST CHANNEL GAUSSIAN RELAY CHANNEL GAUSSIAN INTERFERENCE CHANNEL GAUSSIAN TWO-WAY CHANNEL MULTIPLE-ACCESS CHANNEL ACHIEVABILITY OF THE CAPACITY REGION FOR THE MULTIPLE-ACCESS CHANNEL COMMENTS ON THE CAPACITY REGION FOR THE MULTIPLE-ACCESS CHANNEL CONVEXITY OF THE CAPACITY REGION OF THE MULTIPLE-ACCESS CHANNEL CONVERSE FOR THE MULTIPLE-ACCESS CHANNEL M-USER MULTIPLE-ACCESS CHANNELS GAUSSIAN MULTIPLE-ACCESS CHANNELS ENCODING OF CORRELATED SOURCES ACHIEVABILITY OF THE SLEPIAN–WOLF THEOREM CONVERSE FOR THE SLEPIAN–WOLF THEOREM SLEPIAN–WOLF THEOREM FOR MANY SOURCES INTERPRETATION OF SLEPIAN–WOLF CODING DUALITY BETWEEN SLEPIAN–WOLF ENCODING AND MULTIPLE-ACCESS CHANNELS BROADCAST CHANNEL DE?NITIONS FOR A BROADCAST CHANNEL DEGRADED BROADCAST CHANNELS CAPACITY REGION FOR THE DEGRADED BROADCAST CHANNEL RELAY CHANNEL SOURCE CODING WITH SIDE INFORMATION RATE DISTORTION WITH SIDE INFORMATION GENERAL MULTITERMINAL NETWORKS INFORMATION THEORY AND PORTFOLIO THEORY THE STOCK MARKET: SOME DE?NITIONS 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 FINITE-HORIZON UNIVERSAL PORTFOLIOS HORIZON-FREE UNIVERSAL PORTFOLIOS SHANNON–MCMILLAN–BREIMAN THEOREM (GENERAL AEP) INEQUALITIES IN INFORMATION THEORY BASIC INEQUALITIES OF INFORMATION THEORY 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