Information Theory: Shannon Entropy to Channel Capacity

1. Shannon Entropy

Shannon entropy quantifies the average unpredictability of a random variable. It answers the question: how many binary questions must we ask on average to identify the outcome of an experiment? Shannon showed in 1948 that entropy is the unique measure satisfying four natural axioms — continuity, maximality for uniform distributions, symmetry, and a grouping rule — up to a positive multiplicative constant.

Definition and Units

For a discrete random variable X taking values in a finite alphabet with probability mass function p(x), the Shannon entropy is:

Self-Information

The self-information (surprisal) of a single event x with probability p(x) is I(x) = -log_2 p(x) bits. Rare events carry high information; a certain event carries zero information. Shannon entropy is the expected value of self-information: H(X) = E[I(X)].

Examples: Coin Flip and Dice

Properties of Entropy

• →Non-negativity: H(X) is greater than or equal to 0 for all distributions
• →Maximum: H(X) is maximized by the uniform distribution, giving H = log_2 n for n outcomes
• →Minimum: H(X) = 0 if and only if one outcome has probability 1 (no uncertainty)
• →Concavity: H is a concave function of the probability vector
• →Symmetry: H is invariant under permutation of the alphabet

Binary Entropy Function

For a Bernoulli random variable with P(X=1) = p, the binary entropy function is:

Nats vs. Bits

The choice of logarithm base is a matter of convention. Using natural logs gives entropy in nats, natural for theoretical work and connections to thermodynamics. Using log base 2 gives bits, natural for data compression and communication theory. The conversion is: 1 nat = 1/ln(2) approx 1.4427 bits. Shannon himself used bits in most applied work.

2. Joint and Conditional Entropy

When multiple random variables are involved, joint and conditional entropy describe how uncertainty is distributed across them. The chain rule for entropy is the fundamental decomposition theorem that relates these quantities.

Joint Entropy

For a pair (X, Y) with joint distribution p(x, y), the joint entropy measures total uncertainty in the pair:

Conditional Entropy

The conditional entropy H(Y|X) measures the expected remaining uncertainty in Y after observing X:

Chain Rule for Entropy

The chain rule decomposes joint entropy into a sum of conditional entropies. For two variables:

The general chain rule for n random variables:

Entropy Diagram (Venn-Diagram View)

3. Mutual Information

Mutual information is the central quantity in information theory. It measures how much one random variable tells us about another, appearing in channel capacity, feature selection, and the information bottleneck principle for deep learning.

Definition

Properties

• →Non-negativity: I(X;Y) is greater than or equal to 0
• →Equality with zero iff X and Y are independent
• →Symmetry: I(X;Y) = I(Y;X)
• →Self-information: I(X;X) = H(X)
• →Bound: I(X;Y) is less than or equal to min(H(X), H(Y))

Data Processing Inequality

If X, Y, Z form a Markov chain (Z depends on Y only through X), written X to Y to Z, then:

Processing data can only destroy information, never create it. This is the information-theoretic justification for why feature engineering and data augmentation must be done carefully: any deterministic processing Z = f(Y) satisfies I(X;Z) is less than or equal to I(X;Y). Equality holds when f is invertible.

Fano's Inequality

Fano's inequality lower-bounds the error probability when estimating X from Y. Let X-hat be any estimate of X based on Y, with error probability P_e = P(X-hat is not equal to X):

4. Kullback-Leibler Divergence

The Kullback-Leibler divergence (relative entropy) is a fundamental measure of how one probability distribution differs from another. It appears throughout machine learning, Bayesian inference, variational methods, and the theory of hypothesis testing.

Definition and Properties

Asymmetry and Its Consequences

KL divergence is not symmetric: D_KL(P||Q) measures expected log-likelihood ratio under P, while D_KL(Q||P) measures it under Q. When used in machine learning, the choice matters significantly:

Cross-Entropy

The cross-entropy H(P, Q) between distributions P and Q is:

In classification tasks, minimizing the cross-entropy loss H(P, Q) where P is the true label distribution and Q is the model's predicted distribution is equivalent to minimizing D_KL(P||Q), since H(P) is fixed with respect to the model parameters.

Jensen-Shannon Divergence

The Jensen-Shannon divergence is a symmetrized, smoothed version of KL divergence that is always finite and bounded:

5. Source Coding: Compression Theory

Source coding theory establishes the fundamental limits of lossless data compression. Shannon's source coding theorem shows that entropy is both a lower bound on compression and an achievable rate.

Shannon's Source Coding Theorem

The proof relies on the asymptotic equipartition property (AEP): for large n, nearly all probability is concentrated on approximately 2^(n*H(X)) typical sequences, each with probability approximately 2^(-n*H(X)). Assigning equal-length codes to the typical set suffices for near-optimal compression.

Asymptotic Equipartition Property

The AEP is the information-theoretic law of large numbers. For i.i.d. samples X_1, ..., X_n from distribution p:

Huffman Coding

Huffman coding constructs the optimal prefix-free code for a known symbol distribution. Algorithm:

1. 1.Create a leaf node for each symbol weighted by its probability
2. 2.Merge the two nodes with lowest probability into a new internal node with probability equal to their sum
3. 3.Repeat until one node remains; assign 0/1 to left/right branches

Huffman codes satisfy H(X) is less than or equal to L is less than H(X) + 1 bit per symbol. Codes on blocks of k symbols achieve H(X) is less than or equal to L/k is less than H(X) + 1/k, approaching entropy as k grows.

Arithmetic Coding

Arithmetic coding encodes an entire message as a single fractional number in [0, 1), partitioning the interval proportionally to symbol probabilities. It achieves expected length between H(X) and H(X) + 2/n bits for n symbols, far better than Huffman for small alphabets or highly skewed distributions. Arithmetic coding is the basis for modern compressors including LZMA, PAQ, and parts of JPEG 2000.

Lempel-Ziv Algorithms

The Lempel-Ziv family (LZ77, LZ78, LZW) achieves universal lossless compression without knowing the source distribution. LZ77 (basis of DEFLATE, used in gzip and PNG) replaces repeated substrings with back-references (distance, length) pairs. LZ78 and LZW build an explicit dictionary of encountered phrases.

6. Channel Capacity

Channel capacity is the maximum rate at which information can be transmitted reliably over a noisy communication channel. Shannon's noisy channel coding theorem establishes capacity as both an upper bound and an achievable rate.

Discrete Memoryless Channels

A discrete memoryless channel (DMC) is defined by input alphabet X, output alphabet Y, and transition probabilities p(y|x). Each channel use is independent. The capacity is:

Binary Symmetric Channel

The binary symmetric channel (BSC) with crossover probability p flips each transmitted bit independently with probability p. The uniform input distribution achieves capacity:

Binary Erasure Channel

The binary erasure channel (BEC) with erasure probability alpha delivers each bit correctly with probability 1 - alpha or erases it (outputs ?) with probability alpha. The capacity is:

AWGN Channel and the Shannon-Hartley Theorem

The additive white Gaussian noise (AWGN) channel model is Y = X + Z where Z is Gaussian with mean 0 and variance N, and input X satisfies power constraint E[X^2] is less than or equal to P. The Gaussian input distribution is capacity-achieving:

The Shannon-Hartley theorem explains modern wireless design: doubling bandwidth doubles capacity, while doubling SNR adds only about 1 bit per channel use. OFDM divides bandwidth into subchannels; MIMO adds spatial dimensions. Both increase effective bandwidth rather than relying solely on power.

7. Channel Coding and Error-Correcting Codes

Shannon's channel coding theorem guarantees that reliable communication is possible at any rate below capacity, but the proof is existential — it shows good codes exist without constructing them. Practical error-correcting codes achieve rates close to capacity with efficient encoding and decoding.

Shannon's Noisy Channel Coding Theorem

The achievability proof uses random coding: generate M = 2^(nR) codewords i.i.d. from the capacity-achieving input distribution. Joint typicality decoding declares the transmitted codeword to be the unique codeword jointly typical with the received sequence. The converse uses Fano's inequality to show that high reliability forces R to be less than or equal to C.

Hamming Codes

Hamming codes are perfect linear codes with parameters (2^r - 1, 2^r - 1 - r, 3) for any integer r is greater than or equal to 2. The (7, 4, 3) Hamming code encodes 4 data bits into 7 bits by appending 3 parity-check bits. The parity-check matrix H has columns equal to all nonzero 3-bit binary vectors.

Turbo Codes

Turbo codes, invented by Berrou, Glavieux, and Thitimajshima in 1993, combine two recursive systematic convolutional codes with an interleaver. They approach Shannon capacity within about 0.5 dB at practical block lengths through iterative belief-propagation decoding. Turbo codes are used in 3G/4G cellular standards (UMTS, LTE).

LDPC Codes

Low-density parity-check (LDPC) codes, invented by Gallager in 1962 and rediscovered in the 1990s, use sparse parity-check matrices and message-passing decoding on a bipartite Tanner graph. They provably achieve capacity on the binary erasure channel and perform within 0.01 dB of capacity in practice. LDPC codes are used in 5G NR, DVB-S2 (satellite TV), and Wi-Fi (802.11n/ac/ax).

Linear Codes and Key Parameters

8. Differential Entropy for Continuous Distributions

Differential entropy extends the entropy concept to continuous random variables. It behaves differently from discrete entropy in several important ways: it can be negative, is not invariant under reparameterization, and lacks direct interpretation as a bit count.

Definition

Differential Entropy of Common Distributions

Gaussian Maximizes Differential Entropy

Properties of Differential Entropy

• →Translation invariance: h(X + c) = h(X) for any constant c
• →Scaling: h(aX) = h(X) + log|a| for any nonzero constant a
• →Chain rule: h(X, Y) = h(X) + h(Y|X)
• →Conditioning reduces entropy: h(Y|X) is less than or equal to h(Y)
• →Not invariant under reparameterization (unlike discrete entropy)

Relative Entropy for Continuous Distributions

The KL divergence for continuous distributions replaces the sum with an integral:

9. Rate-Distortion Theory

Rate-distortion theory addresses lossy compression: what is the minimum bit rate needed to represent a source within a given distortion level? Shannon's rate-distortion theorem characterizes the optimal tradeoff between compression rate and reconstruction quality.

Distortion Measures

A distortion measure d(x, x-hat) quantifies the cost of representing source symbol x by reconstruction symbol x-hat. Common distortion measures include:

The Rate-Distortion Function

Rate-Distortion for Gaussian Sources

For a Gaussian source X with variance sigma^2 under squared error distortion, the rate-distortion function has the elegant closed form:

Shannon's Rate-Distortion Theorem

Blahut-Arimoto Algorithm

The Blahut-Arimoto algorithm computes R(D) numerically for discrete sources using an alternating optimization procedure. Starting from an initial test channel p(x-hat|x), it alternates between:

1. 1.Update the output distribution q(x-hat) = sum_x p(x) p(x-hat|x)
2. 2.Update the test channel using the Lagrangian condition with parameter lambda controlling the rate-distortion tradeoff

The algorithm converges geometrically and computes the entire rate-distortion curve by varying lambda from 0 to infinity. The same algorithm (with source and channel roles swapped) computes channel capacity, making it a unified computational tool for information-theoretic optimization.

10. Fisher Information and Statistical Estimation

Fisher information connects information theory to classical statistics. It measures how much information an observation carries about an unknown parameter, establishing fundamental limits on estimation accuracy through the Cramer-Rao bound.

Definition of Fisher Information

The Cramer-Rao Bound

The maximum likelihood estimator (MLE) achieves the Cramer-Rao bound asymptotically as n grows — it is asymptotically efficient. For the Gaussian model X is distributed as N(mu, sigma^2) with known sigma^2, I(mu) = 1/sigma^2 and the MLE mu-hat = sample mean achieves variance sigma^2/n, exactly matching the bound.

Sufficient Statistics

A statistic T(X) is sufficient for parameter theta if the conditional distribution of X given T(X) does not depend on theta. Sufficiency means T captures all the information about theta contained in the data.

Fisher Information and KL Divergence

Fisher information is the second-order local approximation of KL divergence. For nearby distributions parametrized by theta and theta + d_theta:

11. Applications Across Science and Engineering

Information theory provides foundational tools across data compression, communications, machine learning, and biology. Its concepts quantify uncertainty, channel efficiency, and learning capacity in a unified mathematical language.

Data Compression

Machine Learning and Neural Networks

Information theory is central to modern deep learning:

• →Cross-entropy loss: the standard classification loss H(P, Q) = -sum_y P(y) log Q(y) equals H(P) + D_KL(P||Q), so training minimizes KL divergence from predictions to labels
• →Decision trees (ID3, C4.5): split on the feature with maximum information gain = I(feature; label), a conditional mutual information criterion
• →Variational autoencoders (VAEs): maximize the evidence lower bound (ELBO) = E[log p(x|z)] - D_KL(q(z|x) || p(z)), trading reconstruction quality against posterior-prior divergence
• →Information bottleneck: deep learning can be interpreted as compressing X into a representation Z that maximizes I(Z; Y) while minimizing I(Z; X), a rate-distortion tradeoff in representation space
• →Natural gradient descent: replaces Euclidean gradient with Fisher-information-weighted gradient, performing optimization on the manifold of distributions rather than flat parameter space

Communications Engineering

Shannon's theorems set the engineering targets for telecommunications. The Shannon-Hartley theorem guides spectrum allocation and power budget design. Modern systems approach capacity limits:

• →5G NR uses LDPC codes for data and polar codes for control, both approaching AWGN capacity within 0.1 dB
• →OFDM divides the channel into parallel narrowband subchannels, each modeled as a flat AWGN channel for simpler capacity analysis
• →MIMO with m transmit and n receive antennas can achieve capacity up to min(m, n) times the single-antenna AWGN capacity

Biology and DNA Information

DNA stores genetic information using a 4-letter alphabet (A, C, G, T). Each base position carries log2(4) = 2 bits of information in the maximum entropy case. The human genome contains approximately 3 * 10^9 base pairs, storing about 750 MB of information at maximum entropy (though actual information content is lower due to repetition and regulatory structure).

Cryptography

Shannon's 1949 paper "Communication Theory of Secrecy Systems" founded information-theoretic cryptography. A cipher with key K encrypts plaintext M to ciphertext C. Shannon defined:

• →Perfect secrecy: I(M; C) = 0, meaning the ciphertext reveals no information about the plaintext. The one-time pad achieves perfect secrecy.
• →Unicity distance: the minimum ciphertext length at which the key becomes uniquely determinable, approximately H(K) / D, where D is the redundancy per symbol of the plaintext language. English has D approximately 3.5 bits/letter.

12. Practice Problems with Solutions

Work through these problems to solidify your understanding of information theory. Click each problem to reveal the solution.

Quick Reference: Key Formulas

Frequently Asked Questions