~vaibhav

Elements of Information Theory

My annotations of the book "Elements of Information Theory" (Cover & Thomas).

· 1 min read · 22 words
Open document ↗

Annotated copy of Cover & Thomas, Elements of Information Theory — the source text behind the information theory notes that cite it.

Reading order

  1. 1Information, Entropy, Relative Entropy, and Mutual InformationFundamental definitions, Relationships between them, and Chain rules
  2. 2The Asymptotic Equipartition PropertyThe information-theoretic law of large numbers, the typical set, the source code it yields, and its optimality among high-probability sets
  3. 3Entropy Rates of a Stochastic ProcessStationarity, Markov chains, the entropy rate and its two definitions, random walks on graphs, the second law, and functions of Markov chains
  4. 4Data Compression and Source CodingCodes and their hierarchy (nonsingular, uniquely decodable, instantaneous); the Kraft and McMillan inequalities; the entropy lower bound L ≥ H and D-adic distributions; Shannon codes, block coding and the entropy rate; the wrong-code penalty D(p‖q); Huffman codes and their optimality; Shannon–Fano–Elias coding; competitive optimality of the Shannon code; and generating random variables from fair coin flips
  5. 5Gambling and Data CompressionThe horse race, wealth relatives and the doubling rate; Kelly (proportional) gambling is log-optimal; the conservation law W* + H = log m; fair, superfair and subfair odds; the financial value of side information equals mutual information; dependent races and the entropy rate; red-and-black; Markov approximations and the entropy of English; a gambler as a data compressor; and the Shannon guessing game and gambling estimates of English's entropy
  6. 6Channel CapacityThe information capacity of a discrete memoryless channel, worked examples, jointly typical sequences, Shannon's second theorem and its converse, Hamming codes, feedback, and source–channel separation
  7. 7Differential EntropyEntropy of continuous random variables, the continuous AEP and volume of the typical set, the quantization relation, the Gaussian as maximum-entropy distribution, and the estimation counterpart to Fano
  8. 8The Gaussian ChannelCapacity of the additive white Gaussian noise channel, sphere packing, bandlimited channels and the Shannon–Hartley formula, water-filling over parallel and colored channels, and how little feedback buys
  9. 9Rate Distortion TheoryLossy compression — quantization, the rate distortion function for binary and Gaussian sources, reverse water-filling, the converse and achievability proofs, and the Blahut–Arimoto algorithm
  10. 10Information Theory and StatisticsThe method of types, universal source coding, Sanov's theorem and large deviations, the conditional limit theorem, hypothesis testing, Chernoff–Stein and Chernoff information, and Fisher information
  11. 11Maximum EntropyThe maximum entropy distribution under moment constraints, worked examples, the anomalous ε-achievable case, spectrum estimation, and Burg's maximum entropy theorem
  12. 12Universal Source CodingCoding when the source distribution is unknown; redundancy as relative entropy; minimax redundancy equals the capacity of the channel from parameter to source (Gallager–Ryabko); universal codes for binary sequences via two-stage descriptions and Bayesian mixtures, the Laplace and Krichevsky–Trofimov estimators; arithmetic coding and the probability integral transform; the sliding-window (LZ77) and tree-structured (LZ78) Lempel–Ziv algorithms; Kac's recurrence lemma, an Elias-style integer code, and the optimality of LZ77; the distinct-parsing phrase bound, Ziv's inequality, and the optimality of LZ78
  13. 13Kolmogorov ComplexityAlgorithmic complexity as the length of the shortest program that prints a string; Turing machines, Church's thesis and prefix-free programs; invariance of complexity across universal computers; length-conditional complexity, self-delimiting integer codes and log*; the counting argument that most strings are incompressible; expected complexity equals entropy; complexity of integers; algorithmic randomness, incompressible sequences and their law of large numbers; universal probability, the halting problem, noncomputability and the Berry paradox; Chaitin's Omega; universal gambling; Occam's razor and Laplace's sunrise problem; the equivalence K(x) ≈ log 1/P_U(x); the Kolmogorov structure function and sufficient statistic; and the minimum description length principle
  14. 14Network Information TheoryMany senders and receivers; Gaussian multiple-access, broadcast, relay, interference and two-way channels; joint typicality for many variables; the multiple-access channel capacity region, its corner points, time-sharing, convexity, Carathéodory, the converse, m users, and CDMA versus FDMA/TDMA; Slepian–Wolf coding of correlated sources by random binning, its converse and graph-colouring interpretation; the duality between Slepian–Wolf coding and the multiple-access channel; broadcast channels, degradedness, superposition coding and the binary symmetric and Gaussian examples; the relay channel, cut-set bound and block-Markov coding; source coding with coded side information; Wyner–Ziv rate distortion with side information; the cut-set bound for general networks; and the failures of source–channel separation and of the no-feedback-gain theorem in networks
  15. 15Information Theory and Portfolio TheoryThe stock market as a generalized horse race; price relatives, portfolios and wealth relatives; why mean–variance theory is the wrong objective for reinvested wealth; growth rate and log-optimal portfolios; concavity, convexity and the Kuhn–Tucker characterization; one-day optimality E[S/S*] ≤ 1 and expected proportions that stay constant; asymptotic optimality against every causal strategy via Markov and Borel–Cantelli; the cost of a wrong distribution D(f‖g) and the value of side information ≤ I(X;Y); stationary markets, the chain rule for W*, the supermartingale S_n/S_n* and the AEP for the stock market; competitive optimality with fair randomization; finite-horizon minimax universal portfolios and the Shtarkov factor V_n ~ n^{-(m-1)/2}; horizon-free Dirichlet(1/2) universal portfolios; and the sandwich proof of the Shannon–McMillan–Breiman theorem
  16. 16Information Theory InequalitiesJensen's Inequality, Log Sum Inequality, Data Processing Inequality and Sufficient Statistics, and Fano's Inequality

← All notes