Skip to content
Information TheoryEntropySource CodingChannel CapacityBeyond ShannondefinesboundslimitsextendsShannon 1948: H(X) = -Σ p log pChannel Capacity C = max I(X;Y)vlymbooq
Information Theory Causal Chain From Entropy To Quantum — Shows how Shannon's entropy underpins source coding, channel capacity, and modern extensions. · Open the full diagram →
🔬 Scientist Pure mathematics — no exam syllabus

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.

"Information is the resolution of uncertainty."
— Claude Shannon

📊 Entropy — Measuring Uncertainty

Shannon's Great Question: What Is Information?
Before Shannon, nobody knew how to measure information. Shannon realized that information isn't about meaning — it's about uncertainty. A message you can predict (like "the sun will rise tomorrow") carries little information. A message that surprises you (like "it's snowing in the Sahara") carries lots. The self-information of an event with probability p is h(p) = −log₂(p) bits. A fair coin flip (p=1/2) gives 1 bit. A sure thing (p=1) gives 0 bits. The entropy H(X) of a random variable is the average self-information: H(X) = −Σ p(x) log₂ p(x). For a fair coin, H = 1 bit. For a biased coin (p=0.9), H = −0.9·log₂(0.9) − 0.1·log₂(0.1) ≈ 0.47 bits — less uncertainty, less information. Entropy is the fundamental limit on lossless compression: you cannot compress data to fewer bits than its entropy.
Information is not about meaning — it's about surprise. The more unpredictable something is, the more information it carries.

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.

Entropy
H(X) = −Σ p(x) log₂ p(x)
Joint Entropy
H(X,Y) = −ΣΣ p(x,y) log₂ p(x,y)
Conditional Entropy
H(Y|X) = H(X,Y) − H(X)
Chain Rule
H(X,Y) = H(X) + H(Y|X)
✨
Entropy of a Biased Coin ▶
A coin comes up Heads with probability p. The entropy is H = −p·log₂(p) − (1-p)·log₂(1-p).

• 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

Shannon's Source Coding Theorem — You Can't Beat Entropy
Shannon's source coding theorem (or noiseless coding theorem) establishes the fundamental limit of lossless data compression. For a source emitting symbols with entropy H, the average number of bits needed per symbol is at least H. Conversely, there exists a code that gets arbitrarily close to H. This means entropy is the ultimate compression ratio — no algorithm, no matter how clever, can compress data to fewer bits than its entropy without losing information. Huffman coding achieves entropy-optimal compression for known probability distributions (it assigns shorter codes to more frequent symbols). Lempel-Ziv (used in zip, gzip, PNG) achieves it for unknown distributions by building the dictionary adaptively. Every time you zip a file, you're getting closer to Shannon's limit — but you can never beat it.
Entropy is the hard limit of compression. You can't beat Shannon — but you can get arbitrarily close.

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.

Shannon's Source Coding Theorem
The minimum possible average codeword length for lossless compression is H(X)
You can approach H arbitrarily closely by coding blocks of symbols together (the "per-symbol" entropy).
Huffman Code for a 4-Symbol Source
Symbols A, B, C, D with probabilities 0.5, 0.25, 0.125, 0.125. Huffman assigns: A=0, B=10, C=110, D=111. Average length = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 bits. Entropy H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bits — optimal!

📡 Channel Capacity and Reliable Communication

Shannon's Second Theorem — How Much Can We Send Through a Noisy Channel?
Real communication channels are noisy — bits get flipped, signals fade, interference creeps in. The obvious solution is to add redundancy (error-correcting codes), but that reduces the effective data rate. Shannon's noisy channel coding theorem proves that for any channel with noise, there's a channel capacity C — the maximum rate at which information can be transmitted with arbitrarily low error probability. Below C, you can achieve near-perfect communication with the right code. Above C, reliable communication is impossible. The capacity of the additive white Gaussian noise channel is C = ½·log₂(1 + S/N) bits per channel use — the Shannon-Hartley theorem. This formula governs everything from WiFi to 5G to deep space communication. Modern turbo codes and LDPC codes get within a fraction of a dB of the Shannon limit.
Noise is inevitable, but Shannon tells us exactly how much we can communicate through it. The Shannon limit is the boundary between possible and impossible.

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.

Mutual Information
I(X;Y) = H(X) − H(X|Y)
Channel Capacity
C = max I(X;Y)
AWGN Capacity
C = ½·log₂(1 + S/N)
Binary Symmetric
C = 1 − H₂(p)
✨
Binary Symmetric Channel ▶
The simplest noisy channel: input bits are flipped with probability p (crossover probability). The channel capacity is C = 1 − H₂(p) bits per channel use.

• 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

From Thermodynamics to Machine Learning — The Universal Language of Uncertainty
Shannon's entropy is mathematically identical to Boltzmann's entropy in thermodynamics: S = k_B · ln(W) where W is the number of microstates. Shannon's H is just Boltzmann's S but with base-2 logs and a different constant. This is no coincidence — both measure the same thing: the number of possible states of a system, and thus our uncertainty about which one it's in. In machine learning, cross-entropy is the most common loss function for classification — it measures the difference between the predicted and actual probability distributions. KL divergence D_KL(P||Q) = Σ p(x) log(p(x)/q(x)) measures how much information is lost when using Q to approximate P. It's the foundation of variational inference, Bayesian deep learning, and generative models (VAEs use KL divergence to regularize latent spaces). In quantum information theory, the von Neumann entropy S(ρ) = −Tr(ρ log ρ) generalizes Shannon entropy to quantum states, and the Holevo bound limits how much classical information can be extracted from a quantum system.
Entropy is the bridge between physics, information, and learning — a single idea that connects the second law of thermodynamics to the training of neural networks.

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.

Data Processing Inequality
I(X; Y) ≥ I(X; f(Y)) for any function f
Processing can only destroy or preserve information — it can never create it. This simple inequality is the foundation of all data analysis.

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.

KL Divergence
D_KL(P‖Q) = Σ p·log(p/q)
Cross-Entropy
H(P,Q) = H(P) + D_KL(P‖Q)
Rate-Distortion
R(D) = min I(X;X̂)
Von Neumann Entropy
S(ρ) = −Tr(ρ log ρ)
✨
The Two Envelopes Paradox — An Information Puzzle ▶
Two envelopes contain money, one twice as much as the other. You pick one, open it, and find $100. Should you switch?

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.
"The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point. Frequently the messages have meaning; that is, they refer to or are correlated according to some system with certain physical or conceptual entities. These semantic aspects of communication are irrelevant to the engineering problem."
— Claude Shannon, 1948 — the opening of the paper that created information theory

🎯 Practice — Check Your Information Theory Intuition

These puzzles build information theory intuition — no heavy math needed.

← Back to Math Map

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.

Worked Example: MAC Sum‑Rate Bound
Consider a two‑user Gaussian MAC with received signal Y = X₁ + X₂ + Z, where Z ∼ N(0,1). Each transmitter has power constraint P. Compute the maximum sum‑rate R₁ + R₂.
For a Gaussian MAC the sum‑rate capacity is I(X₁,X₂; Y) = ½ log₂(1 + 2P). This follows because the joint input (X₁,X₂) has total power 2P and the channel is equivalent to a single‑user AWGN channel with SNR = 2P. The individual rates can be any pair satisfying R₁ ≤ ½ log₂(1+P), R₂ ≤ ½ log₂(1+P), and R₁+R₂ ≤ ½ log₂(1+2P). The corner points are achieved by successive decoding: decode user 1 treating user 2 as noise (rate ½ log₂(1+P/(1+P))) then subtract and decode user 2 at ½ log₂(1+P). The sum‑rate bound is therefore ½ log₂(1+2P).
Exam‑Day Strategy
When a question asks for the capacity region of a MAC or BC, first identify whether the channel is degraded or Gaussian. Write down the single‑letter mutual‑information expressions for all subsets (MAC) or the superposition‑coding rate region (degraded BC). For Gaussian channels, replace mutual informations with the corresponding log‑formulas using power constraints. Remember that time‑sharing convexifies the region; if the region is already convex (as for the Gaussian MAC), no time‑sharing is needed. Sketch the region quickly to verify corner points.

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.