Information Theory — The Mathematics of Communication
Information theory answers two fundamental questions: what is information, and how much can we communicate reliably? Claude Shannon, in his 1948 paper "A Mathematical Theory of Communication," invented the entire field — defining entropy, channel capacity, and the limits of data compression and error correction. His work made the digital age possible: every time you zip a file, stream a video, or send a text, Shannon's mathematics is at work.
📊 Entropy — Measuring Uncertainty
Properties of Entropy
Entropy is always non-negative, maximized by the uniform distribution, and additive for independent events. For a distribution over n outcomes with probabilities p₁, p₂, ..., pₙ: H ≤ log₂(n), with equality iff all pᵢ = 1/n. Joint entropy H(X,Y) extends the definition to pairs. Conditional entropy H(Y|X) = H(X,Y) − H(X) measures the remaining uncertainty about Y after knowing X.
• p = 0.5: H = 1 bit (maximum uncertainty)
• p = 0.9: H ≈ 0.47 bits
• p = 0.99: H ≈ 0.08 bits
• p = 0 or 1: H = 0 bits (no uncertainty)
This function is called the binary entropy function H₂(p). It's symmetric around p=0.5 and concave — it peaks at maximum uncertainty and drops to zero at certainty.
🗜️ Data Compression — The Source Coding Theorem
Prefix Codes and Kraft's Inequality
A prefix code (or instantaneous code) is a code where no codeword is a prefix of another. This lets you decode without lookahead. Kraft's inequality gives a necessary and sufficient condition for the existence of a prefix code with codeword lengths ℓ₁, ..., ℓₙ: Σ 2^{−ℓᵢ} ≤ 1 (for binary codes). Huffman's algorithm constructs the optimal prefix code for a given distribution — it repeatedly merges the two least probable symbols and assigns them the longest codewords. The average codeword length L satisfies H ≤ L < H + 1.
📡 Channel Capacity and Reliable Communication
Mutual Information
The mutual information I(X; Y) = H(X) − H(X|Y) = H(Y) − H(Y|X) measures how much knowing one variable reduces uncertainty about another. It's symmetric, non-negative, and equals 0 iff X and Y are independent. Channel capacity is defined as the maximum mutual information over all input distributions: C = max_{p(x)} I(X; Y). This is the fundamental limit — the tightest upper bound on how fast we can send data through a noisy channel.
• p = 0: C = 1 bit (perfect channel — send raw bits)
• p = 0.5: C = 0 bits (channel is useless — output is independent of input)
• p = 0.1: C = 1 − (−0.1·log₂(0.1) − 0.9·log₂(0.9)) ≈ 1 − 0.47 = 0.53 bits
With a (7,4) Hamming code (which corrects 1 error per 7 bits), we can send 4 bits of information per 7 channel uses = 0.57 bits/use — below capacity at p=0.1. At p=0.01, capacity ≈ 0.92 bits/use, and the Hamming code still only gives 0.57 — we need more efficient codes like turbo or LDPC to approach the limit.
Error-Correcting Codes
Hamming codes (1950) were the first practical error-correcting codes. A (7,4) Hamming code encodes 4 data bits into 7 bits, correcting any single-bit error. Reed-Solomon codes correct burst errors and are used in CDs, QR codes, and space probes. Turbo codes (1993) and LPDC codes (rediscovered in the 1990s) approach the Shannon limit within fractions of a decibel — they're used in 4G/5G, satellite communication, and deep space networks. The search for capacity-approaching codes drove half a century of coding theory, and the field continues to evolve with polar codes (Arikan, 2009), the first provably capacity-achieving codes with low complexity.
🌌 Beyond Shannon — Entropy in Physics, ML, and Quantum Information
KL Divergence and the Information Bottleneck
The Kullback-Leibler divergence (or relative entropy) is the foundation of information geometry. It's not a metric (it's asymmetric), but it satisfies D_KL ≥ 0 with equality iff P = Q. The information bottleneck method finds a compressed representation Z of X that preserves information about Y — it maximizes I(Z; Y) − β·I(Z; X). This has become a framework for understanding deep learning: neural networks naturally learn to compress inputs while preserving task-relevant information.
Rate-Distortion Theory — Lossy Compression
Not all compression needs to be lossless. Rate-distortion theory answers: given a distortion measure (like mean squared error), what's the minimum bitrate needed to reconstruct a source within a given distortion D? The rate-distortion function R(D) characterizes this trade-off. For a Gaussian source with variance σ² and MSE distortion, R(D) = ½·log₂(σ²/D) for D ≤ σ². This is the theory behind JPEG, MP3, and video compression — you trade bits for perceptual quality, and Shannon tells you the optimal trade-off.
Naive reasoning: the other envelope has $50 or $200 with equal probability, expected value = $125, so switch! But this reasoning would apply regardless of what you found, so you'd switch even before opening — a contradiction.
The resolution: you need a prior distribution over the amounts. If all amounts are equally likely, the expected value is infinite (improper prior), and the calculation breaks down. Information theory tells us that without a proper prior, you can't assign meaningful probabilities — the "equally likely" assumption smuggles in an infinite expected value.
This shows how careful we must be with probabilistic reasoning — a key lesson for both information theory and decision theory.
🎯 Practice — Check Your Information Theory Intuition
These puzzles build information theory intuition — no heavy math needed.
Finite Blocklength Bounds and the Channel Dispersion
The classical channel coding theorem states that for any rate below capacity there exists a sequence of codes with blocklength n whose error probability tends to zero as n → ∞. In practice, however, blocklengths are finite and the asymptotic statement does not quantify the speed of convergence. The finite‑blocklength framework, developed by Polyanskiy, Poor, and Verdú (2010), provides a non‑asymptotic approximation: the maximal achievable rate R*(n, ε) for blocklength n and error probability ε satisfies
R*(n, ε) = C − √(V/n) · Q⁻¹(ε) + O(log n / n)
where C is the Shannon capacity, V is the channel dispersion, and Q⁻¹ is the inverse Gaussian Q‑function. The dispersion V captures the variance of the information density and determines how quickly the rate approaches capacity. For a binary symmetric channel with crossover probability p, V = p(1−p) [log₂((1−p)/p)]². For an additive white Gaussian noise channel with signal‑to‑noise ratio SNR, V = (SNR/(2(1+SNR))) log₂² e. These expressions allow engineers to predict the required blocklength for a target rate and reliability, which is essential for low‑latency communications such as URLLC in 5G.
The normal approximation is tight for many memoryless channels, but refinements exist. The third‑order term involves the skewness of the information density, and saddlepoint approximations give even sharper bounds. Moreover, the meta‑converse and dependence‑testing bounds provide computable upper and lower bounds that hold for any n. These tools have been extended to channels with memory, fading channels with channel state information at the receiver, and multi‑terminal settings. Understanding dispersion is also crucial for the design of short‑packet codes such as polar codes with CRC‑aided list decoding, which empirically approach the finite‑blocklength limits.
Network Information Theory — Multiple Access and Broadcast Channels
When several transmitters or receivers share a medium, the single‑user capacity formula no longer applies. The multiple‑access channel (MAC) models K senders transmitting to a common receiver. Its capacity region is the set of rate tuples (R₁,…,R_K) satisfying Σi∈S R_i ≤ I(X_S; Y | XS^c) for all subsets S ⊆ {1,…,K}, where the mutual information is evaluated under a product input distribution. The region is a polymatroid, and its corner points are achieved by successive decoding: the receiver decodes a subset of users while treating the rest as noise, subtracts their contribution, and proceeds iteratively. Time‑sharing between corner points yields the entire region.
The broadcast channel (BC) models one sender transmitting to K receivers. For the degraded BC, where the outputs form a Markov chain X → Y₁ → Y₂ → … → Y_K, the capacity region is known and given by Marton’s inner bound, which coincides with the outer bound. For general BCs, the capacity region remains open; the best known inner bound is due to Marton (1979) with a common message, and the best outer bound is the Nair–El Gamal bound. Superposition coding and indirect decoding are the key techniques: the transmitter encodes a cloud center for the weaker user and a satellite codeword for the stronger user, allowing the stronger user to decode both layers.
Interference channels, relay channels, and networks with feedback introduce further complexity. The Han–Kobayashi scheme for the two‑user interference channel achieves the best known rates by splitting each message into common and private parts. For the relay channel, the compress‑and‑forward and decode‑and‑forward strategies give achievable rates, while the cut‑set bound provides a universal outer bound. Network coding, introduced by Ahlswede, Cai, Li, and Yeung (2000), shows that in multicast networks the max‑flow min‑cut theorem extends to coding across edges, achieving the cut‑set bound. These results form the theoretical backbone of modern wireless systems such as NOMA, CoMP, and device‑to‑device communication.
Information‑Theoretic Security and the Wiretap Channel
Shannon’s 1949 paper on communication theory of secrecy systems laid the groundwork for physical‑layer security. Wyner (1975) introduced the wiretap channel: a sender transmits to a legitimate receiver while an eavesdropper observes a degraded version of the same signal. The secrecy capacity is the maximum rate at which reliable communication to the legitimate receiver is possible while the eavesdropper’s mutual information about the message vanishes. For the degraded wiretap channel, the secrecy capacity equals C_s = maxp(x) [I(X;Y) − I(X;Z)], where Y is the legitimate output and Z the eavesdropper’s output. The optimal input distribution is often Gaussian for additive white Gaussian noise wiretap channels, yielding C_s = ½ log₂(1+SNR_main) − ½ log₂(1+SNR_eve) when SNR_main > SNR_eve, and zero otherwise.
Csiszár and Körner (1978) generalized the result to broadcast channels with confidential messages, showing that the same difference of mutual informations characterizes the secrecy capacity region when the eavesdropper’s channel is less capable. The key coding technique is stochastic encoding: the transmitter uses a random binning (or coset coding) scheme where each message corresponds to a bin of codewords; the legitimate receiver decodes the exact codeword, while the eavesdropper sees only the bin index, which carries negligible information. This idea underpins modern wiretap codes based on polar codes and LDPC codes, which achieve the secrecy capacity with low complexity.
Extensions include the Gaussian MIMO wiretap channel, where the secrecy capacity involves an optimization over input covariance matrices: C_s = maxK⪰0, Tr(K)≤P [log det(I + H_main K H_mainᵀ) − log det(I + H_eve K H_eveᵀ)]. The optimal K often aligns with the generalized eigenvectors of the channel matrices, directing power into directions where the legitimate channel is strong and the eavesdropper’s channel is weak. Cooperative jamming, artificial noise, and secret‑key agreement from correlated sources are practical techniques that exploit the same information‑theoretic principles. These results are directly relevant to physical‑layer security in 5G/6G, satellite links, and IoT networks where computational cryptography may be infeasible.
Quantum Channel Capacity and Entanglement Assistance
Quantum information theory extends Shannon’s framework to channels that transmit quantum states. The classical capacity of a quantum channel 𝒩 is given by the Holevo‑Schumacher‑Westmoreland (HSW) theorem: C(𝒩) = max_{ {p_x, ρ_x} } χ( {p_x, 𝒩(ρ_x)} ), where χ = S( Σ p_x 𝒩(ρ_x) ) − Σ p_x S(𝒩(ρ_x)) is the Holevo information and S(ρ) = −Tr(ρ log ρ) is the von Neumann entropy. This formula is additive for many channels (e.g., entanglement‑breaking channels) but not in general; the regularized capacity requires an infinite‑blocklength limit of χ(𝒩⊗n)/n.
The quantum capacity Q(𝒩), which measures the ability to transmit quantum states faithfully, is given by the Lloyd‑Shor‑Devetak formula: Q(𝒩) = max_ρ I_c(ρ, 𝒩), where the coherent information I_c = S(𝒩(ρ)) − S((𝒩^c)(ρ)) and 𝒩^c is the complementary channel. Unlike classical capacity, quantum capacity can be super‑additive: there exist channels with zero single‑letter quantum capacity but positive capacity when used jointly (the “superactivation” effect discovered by Smith and Yard, 2008). This phenomenon has no classical analogue and highlights the role of entanglement between channel uses.
Entanglement‑assisted classical capacity C_E(𝒩) admits a single‑letter formula: C_E(𝒩) = max_ρ I(ρ, 𝒩), where I(ρ, 𝒩) = S(ρ) + S(𝒩(ρ)) − S((id ⊗ 𝒩)(Φ_ρ)) is the quantum mutual information of the channel with a maximally entangled input Φ_ρ. This capacity is additive and equals the quantum analogue of the Shannon capacity with unlimited shared entanglement. The trade‑off between classical communication, quantum communication, and entanglement consumption is captured by the capacity region of a quantum channel, known as the “quantum dynamic capacity theorem”. These results underpin quantum key distribution (QKD) protocols such as BB84 and device‑independent QKD, where the security proof reduces to bounding the eavesdropper’s information via the Holevo bound.
Algorithmic Information Theory — Kolmogorov Complexity and Universal Coding
Algorithmic information theory, founded by Solomonoff, Kolmogorov, and Chaitin in the 1960s, defines the information content of an individual object (a finite binary string) as the length of the shortest program that outputs it on a universal Turing machine. This quantity, the Kolmogorov complexity K(x), is invariant up to an additive constant independent of x. Unlike Shannon entropy, which applies to ensembles, K(x) measures the randomness of a single sequence. A sequence is algorithmically random (Martin‑Löf random) iff K(x) ≥ |x| − c for some constant c.
The connection to compression is immediate: any computable compressor yields an upper bound on K(x), and the optimal compressor achieves lengths close to K(x) + O(log K(x)). The celebrated “universal coding” result states that the two‑part code based on the universal prior (Solomonoff’s mixture) achieves expected code length within an additive constant of the Kolmogorov complexity for any computable distribution. This provides a theoretical justification for the Minimum Description Length (MDL) principle in statistical model selection.
Kolmogorov complexity is uncomputable (no algorithm can compute K(x) for all x), but its properties are powerful. The symmetry of information theorem states K(x,y) = K(x) + K(y|x*) + O(log K(x,y)), where x* is a shortest program for x. This mirrors the chain rule for Shannon entropy. The coding theorem of Levin and Gács links K(x) to the universal a priori probability m(x) = Σp:U(p)=x 2−|p|: −log m(x) = K(x) + O(1). These results have applications in anomaly detection (strings with low K are structured), in the analysis of learning algorithms (Occam’s razor formalized), and in the foundations of probability (algorithmic randomness as a definition of typicality). While not directly used in engineering codes due to uncomputability, the theory guides the design of practical universal compressors such as Lempel‑Ziv, which asymptotically achieve the entropy rate for stationary ergodic sources.
- Confusing channel dispersion with capacity — dispersion governs the √n penalty, not the asymptotic limit.
- Assuming the MAC capacity region is a rectangle — it is a polymatroid bounded by subset sum constraints.
- Neglecting the degradedness condition when applying the Wyner wiretap formula — the difference of mutual informations holds only for degraded or less‑capable eavesdroppers.
- Treating quantum capacity as additive — superactivation shows joint use can unlock capacity that single uses cannot.
- Equating Kolmogorov complexity with Shannon entropy for a single string — entropy is an ensemble average, complexity is an individual measure.
- Believing universal compressors achieve Kolmogorov complexity exactly — they achieve it only up to an additive logarithmic term and only for computable distributions.
- Overlooking that the finite‑blocklength normal approximation requires the channel to be memoryless and the information density to have finite variance.