Information Theory¶
Job: quantify information, compression limits, and channel capacity; connect entropy and divergences to coding theorems, statistics, and security.
Core¶
Information theory treats random variables as sources of uncertainty and channels as conditional laws. The central scalars — entropy, mutual information, KL — have operational meaning via asymptotic coding rates, not only axiomatic characterizations.
| Layer | Content |
|---|---|
| Entropy / MI | \(H\), \(H(\cdot\mid\cdot)\), \(I(X;Y)\); chain rules |
| Divergences | \(D_{\mathrm{KL}}\), total variation, Pinsker; \(f\)-divergences |
| Source coding | AEP, typical sets, lossless rate \(H(X)\) |
| Channel coding | capacity \(C=\max I(X;Y)\); random coding |
| Continuous | differential entropy (caution); Gaussian channels |
| Interfaces | stats (large deviations), crypto (secrecy), ML (cross-entropy) |
Reading map¶
| Page | Focus |
|---|---|
| Foundations | entropy through Shannon theorems; Fano; BSC; continuous caveats |
| Network Information | MAC, broadcast, relay, interference, network coding |
| Rate-Distortion & Lossy | \(R(D)\), Shannon lower bound, Gaussian, reverse water-filling |
| Finite-Blocklength & Dispersion | PPV normal approximation, channel dispersion, HT converse |
| Quantum & Large Deviations | von Neumann, Holevo, quantum capacity, Sanov, Cramér |
Dependency order¶
- Discrete probability — probability foundations, finite alphabets first
- Foundations — \(H\), \(I\), \(D_{\mathrm{KL}}\), source & channel theorems
- Statistics asymptotics — Sanov, hypothesis testing (Chernoff–Stein)
- Crypto secrecy / ML training objectives as applied layers
Where it appears¶
- Probability: laws, independence, conditional entropy as residual uncertainty
- Statistics: likelihood ratios \(\leftrightarrow\) KL; AIC/BIC heuristics
- Cryptography: perfect secrecy \(I(M;C)=0\); computational analogues
- Optimization: variational representations of divergences; rate–distortion as opt
Signature results¶
| Theorem | Statement (schematic) |
|---|---|
| Source coding | \(R>H(X)\) achievable lossless asymp.; \(R<H\) not |
| Channel coding | \(R<C\) vanishing error; \(R>C\) error bounded away from 0 |
| Fano | $H(X\mid\hat X)\lesssim h_2(P_e)+P_e\log |
| Data processing | \(X\to Y\to Z\) Markov \(\Rightarrow I(X;Z)\le I(X;Y)\) |
See it¶
Random coding for the BSC. Generate \(2^{nR}\) codewords i.i.d. Bern\((1/2)\); decode by joint typicality (or nearest Hamming neighbor). For \(R<1-h_2(p)\), average error \(\to0\). The same template — random code + typicality — is the skeleton of most classical achievability proofs.
Check¶
Why is capacity a max over input laws, not a property of \(W\) alone as a metric?
\(I(X;Y)\) depends on \(p_X\) through the joint \(p_X W\). Different inputs explore different output marginals; \(C=\max_{p_X}I(X;Y)\) is the best asymptotic rate over choices of input distribution (and, operationally, over codes inducing empirical inputs).
State data processing and give a one-line consequence for estimation.
Markov \(X\to Y\to\hat X\) \(\Rightarrow I(X;\hat X)\le I(X;Y)\). Processing observations cannot increase information about \(X\); post-processing cannot beat the raw observation in mutual information.
Pitfalls¶
- Bits vs nats: \(\log_2\) vs \(\ln\); mixing units silently breaks capacity formulas.
- Differential entropy \(h(X)\) can be negative and is not a pure “bits of information”; prefer \(I\) for continuous settings.
- Empirical MI in high dimension is badly biased; plug-in estimators need regularization or variational bounds.
- Finite blocklength: asymptotic \(C\) is not a guarantee at small \(n\) (Polyanskiy–Poor–Verdú).
Refs¶
Cover–Thomas, Elements of Information Theory; Csiszár–Körner; Shannon 1948; Polyanskiy–Wu notes (modern finite-blocklength).
Next¶
Foundations · Probability · Cryptography · Statistics · Optimization · Network Information · Rate-Distortion & Lossy · Finite-Blocklength & Dispersion · Quantum & Large Deviations