Information Theory

Entropy, mutual information, KL divergence, and the limits of communication.

Shannon Entropy — H(X) = - _x p(x) p(x) — the average surprise per draw.
Conditional Entropy — H(X | Y) measures how many bits of uncertainty survive after you see Y.
Mutual Information — I(X; Y) = D_ KL(p_XY | p_X p_Y) — the information X and Y share.
Noisy Channels — Meet the BSC and BEC: the two toy channels that make entropy and decoding feel concrete.
MAP vs. ML Decoding — Likelihood explains the data; posterior probability picks the best overall guess.
KL Divergence — D_ KL(P | Q) ≥ 0 — Gibbs' inequality, the engine of information theory.
Log-Sum Inequality — ∑ a_i (a_i / b_i) ≥ (∑ a_i) ∑ a_i/∑ b_i — un-normalized KL.
Data Processing Inequality — For a Markov chain X → Y → Z, I(X; Z) ≤ I(X; Y) — processing can only destroy information.
Fano's Inequality — H(X | Y) ≤ H(P_e) + P_e (| X| - 1) — the universal lower bound on estimation error.

Further Topics

Asymptotic Equipartition Property — Typical sequences, entropy concentration, and the 2^nH count.
Typical Sets — The small set that holds almost all the probability.
Kraft Inequality & Prefix Codes — Which codeword lengths a prefix code can realize, and the entropy bound.
Source Coding Theorem — Entropy is the exact bits-per-symbol floor for lossless compression.
Channel Capacity Theorem — Capacity C = _p(x) I(X;Y) as the limit of reliable rate.
Differential Entropy — The continuous analog of entropy: h(X) = -∫ f f.
Gaussian Channel Capacity — The capacity C = 12 _2(1 + P/N) from a Gaussian input.
Maximum Entropy Distributions — Moment constraints pick the entropy-maximizing exponential family.
Method of Types & Sanov's Theorem — Type-counting turns large deviations into relative-entropy minimization.
Rate-Distortion Function — The least rate for a tolerated average distortion: R(D) = min I(X; X-hat).
Entropy Rate of a Markov Chain — Per-symbol entropy of a dependent source as a stationary-weighted average of row entropies.
Lempel-Ziv Universal Coding — Parse a sequence into phrases and compress to the entropy rate, no model needed.