Information Theory — Foundations

Job: Define entropy and mutual information; state Shannon's source and channel coding theorems with operational meaning; track divergences and continuous caveats.

Core

Entropy and chain rules

Discrete entropy (Shannon) for r.v. \(X\) on finite/countable alphabet: $$ H(X)=-\sum_x p(x)\log p(x)\quad(0\log0:=0),\qquad\text{bits if }\log_2. $$ \(0\le H(X)\le\log|\mathcal{X}|\), max at uniform. Joint / conditional: $$ H(X,Y)=H(X)+H(Y\mid X),\qquad H(Y\mid X)=\mathbb{E}_x[H(Y\mid X=x)]. $$ Chain rule: \(H(X_1,\ldots,X_n)=\sum_{i=1}^n H(X_i\mid X^{i-1})\). Conditioning reduces entropy: \(H(X\mid Y)\le H(X)\).

Mutual information and KL

Mutual information: $$ I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y), $$ and \(I(X;Y)=D_{\mathrm{KL}}(p_{XY}\|p_X p_Y)\ge0\), zero iff independence.

KL divergence: \(D_{\mathrm{KL}}(p\|q)=\sum p\log(p/q)\in[0,\infty]\); asymmetric, no triangle. Pinsker: \(\|p-q\|_{\mathrm{TV}}^2\le\frac12 D_{\mathrm{KL}}(p\|q)\). Data processing: \(X\to Y\to Z\) Markov \(\Rightarrow I(X;Z)\le I(X;Y)\) and \(D_{\mathrm{KL}}(p_Z\|q_Z)\le D_{\mathrm{KL}}(p_Y\|q_Y)\) under the same channel.

Variational formula (Donsker–Varadhan): \(D_{\mathrm{KL}}(p\|q)=\sup_f\bigl(\mathbb{E}_p f-\log\mathbb{E}_q e^f\bigr)\) — engine for PAC-Bayes and variational inference bounds.

Continuous / differential entropy

Differential entropy \(h(X)=-\int f\log f\) for densities — can be negative; not a pure “information content.” Chain rules for \(h\) hold under regularity; \(I(X;Y)\) remains nonnegative and operationally meaningful. Gaussian maximizes \(h\) under fixed variance: \(h(N(0,\sigma^2))=\frac12\log(2\pi e\sigma^2)\).

Typical sets and source coding

AEP: for i.i.d. \(X_i\sim p\), \(-\frac1n\log p(X^n)\to H(X)\) in probability. Typical set \(A_\varepsilon^{(n)}\) has \(\mathbb{P}(A_\varepsilon^{(n)})\to1\) and \(|A_\varepsilon^{(n)}|\approx 2^{nH}\).

Source coding theorem (lossless, i.i.d.). For any \(R>H(X)\) there exist codes of rate \(R\) with error \(\to0\); if \(R<H(X)\), error \(\not\to0\). Operational meaning of \(H\).

Rate–distortion (pointer): lossy compression minimizes \(I(X;\hat X)\) s.t. \(\mathbb{E}\,d(X,\hat X)\le D\); \(R(D)\) is the fundamental limit.

Channel coding

DMC \(W(y\mid x)\), capacity $$ C=\max_{p_X}I(X;Y). $$ For \(R<C\), exist codes with \(M=2^{nR}\) messages, max/avg error \(\to0\) as \(n\to\infty\); for \(R>C\), error bounded away from 0. Achievability: random coding + joint typicality (or information density / Feinstein). Converse: Fano + data processing / chain rules.

Fano's inequality: \(H(X\mid\hat X)\le h_2(P_e)+P_e\log(|\mathcal{X}|-1)\) — converse engine.

Channel Capacity (bits, schematic)
BSC(\(p\)) \(C=1-h_2(p)\)
BEC(\(\varepsilon\)) \(C=1-\varepsilon\)
AWGN power \(P\), noise \(N\) \(C=\frac12\log(1+P/N)\) (per real channel use)

Chernoff–Stein: best type-II error exponent for testing \(p\) vs \(q\) at fixed type-I level is \(D_{\mathrm{KL}}(p\|q)\). Sanov's theorem: large-deviation rate for empirical measures is KL — same geometry.

See it

BSC(\(p\)): \(Y=X+Z\bmod2\), \(Z\sim\mathrm{Bern}(p)\), capacity \(C=1-h_2(p)\), achieved at uniform \(X\). At \(p=1/2\), \(C=0\) (output independent of input). Random coding achieves rates below \(C\); Hamming / modern LDPC codes approach \(C\) with efficient decoding in practice.

One-time pad: \(C=M\oplus K\), \(K\) uniform independent of \(M\) \(\Rightarrow I(M;C)=0\) (perfect secrecy) — information-theoretic security needs key entropy \(\ge\) message entropy (Shannon).

Check

Prove \(I(X;Y)=0\Leftrightarrow X\perp Y\).

\(I=D_{\mathrm{KL}}(p_{XY}\|p_Xp_Y)=0\) iff \(p_{XY}=p_Xp_Y\) a.e. (strict convexity of \(t\log t\) / Gibbs inequality). Equivalently \(H(X\mid Y)=H(X)\).

Why can \(h(X)\) be negative while \(H\) cannot?

Differential entropy is not a limit of discrete entropies under naive quantization without bin-size corrections (\(\log\Delta\) divergence). \(I(X;Y)\) for continuous variables stays nonnegative and operationally meaningful.

Sketch the weak converse: \(R>C\Rightarrow\liminf P_e>0\).

Fano: \(H(W\mid\hat W)\le 1+P_e\log M\). Data processing + chain rule bound \(I(W;Y^n)\le nC\). Relate \(H(W)=nR\) (uniform messages) to residual entropy via \(P_e\) — if \(R>C\) then \(P_e\) cannot vanish.

Pitfalls

  • Units: nats (\(\ln\)) vs bits (\(\log_2\)); capacity formulas must match.
  • Mutual information estimates from samples are biased in high dimension (kNN, variational bounds).
  • Channel capacity is a supremum over input distributions — not a property of a single codebook metric alone.
  • Finite-blocklength: asymptotic \(C\) is not a guarantee at small \(n\) (channel dispersion).
  • “Entropy of a deterministic real” is not well-posed; discretize carefully.

Refs

Cover–Thomas, Elements of Information Theory; Csiszár–Körner; Shannon 1948; Polyanskiy–Wu (lecture notes, modern finite-blocklength); Csiszár–Shields (survey).

Next

Index · Probability foundations · Cryptography · Statistics · Optimization · ML mathematics — information-theoretic limits of learning; sample complexity · Network Information · Rate-Distortion & Lossy · Finite-Blocklength & Dispersion · Quantum & Large Deviations