Classical Information Theory

Shannon asked a question with a number for an answer: how many bits does it take to describe the output of a random source? The answer — entropy — and its relatives (mutual information, relative entropy) are the classical skeleton on which the quantum theory of von Neumann entropy and quantum mutual information is built.

Learning Objectives

By the end of this lesson you will be able to:

1. Define Shannon entropy $H(X)$, joint entropy $H(X,Y)$, and conditional entropy $H(Y\mid X)$, and state their units.
2. Define mutual information $I(X;Y)$ and relative entropy (KL divergence) $D(p\,\Vert\,q)$, and relate them.
3. Prove non-negativity of KL divergence via Gibbs' inequality, and derive $I(X;Y)\ge 0$ as a corollary.
4. Apply the chain rule for entropy and state the data-processing inequality.
5. Explain the source-coding theorem's operational meaning (entropy as the compression limit).
6. Compute entropy, mutual information, and KL divergence for sample distributions in NumPy.

Intuition

Information is surprise. An outcome you were sure of carries no information; a rare outcome carries a lot. Shannon's masterstroke was to insist the measure of surprise be additive for independent events — learning two independent facts should cost the sum of their individual costs. The only function (up to a constant fixing the unit) that turns multiplication of probabilities into addition is the logarithm, so the surprise of an outcome with probability $p$ is $-\log p$. Entropy is the average surprise of a source.

From this one idea everything follows:

• Entropy $H(X)$ — your average uncertainty about $X$ before seeing it; equivalently, the minimum bits/symbol to compress a stream of i.i.d. $X$'s.
• Conditional entropy $H(Y\mid X)$ — uncertainty about $Y$ that remains after you learn $X$.
• Mutual information $I(X;Y)$ — uncertainty about $Y$ that learning $X$ removes; the shared information between two variables.
• Relative entropy $D(p\,\Vert\,q)$ — the penalty (in extra bits) you pay for compressing data that's really distributed as $p$ using a code optimized for the wrong distribution $q$.

These are not just analogies; each has an operational coding theorem behind it. And each has a direct quantum descendant — the von Neumann entropy $S(\rho) = -\mathrm{Tr}(\rho\log\rho)$ replaces $H$, and quantum mutual information replaces $I$ — which we develop once density matrices arrive in Term 1.5.

Theory

Throughout, $\log = \log_2$ so information is measured in bits; using $\ln$ gives nats (natural units), differing only by the constant factor $\ln 2$. We adopt the standard convention $0\log 0 = 0$, justified by $\lim_{p\to0^+} p\log p = 0$.

Shannon entropy

For a discrete random variable $X$ with PMF $p(x) = \mathbb P(X=x)$ over alphabet $\mathcal X$, the Shannon entropy is the expected surprise:

Properties. $H(X) \ge 0$ (each term $-p\log p \ge 0$ on $[0,1]$), with $H(X) = 0$ iff $X$ is deterministic. And $H(X) \le \log|\mathcal X|$, with equality iff $X$ is uniform — we prove this below as a one-line corollary of Gibbs' inequality. For a binary variable with $\mathbb P(X=1)=p$, the binary entropy function is

peaking at $H_b(\tfrac12) = 1$ bit (a fair coin / equal superposition is maximally uncertain) and vanishing at $p\in\{0,1\}$.

Joint and conditional entropy

For a pair $(X,Y)$ with joint PMF $p(x,y)$, the joint entropy is

and the conditional entropy of $Y$ given $X$ is the expected entropy of $Y$ once $X$ is known:

Chain rule. Using $p(x,y) = p(x)p(y\mid x)$ and $\log p(x,y) = \log p(x) + \log p(y\mid x)$:

In words: the total uncertainty in $(X,Y)$ is the uncertainty in $X$ plus the leftover uncertainty in $Y$ once $X$ is known. By symmetry $H(X,Y) = H(Y) + H(X\mid Y)$ as well. The general chain rule iterates this:

Relative entropy (KL divergence) and Gibbs' inequality

The relative entropy (Kullback–Leibler divergence) from $p$ to $q$, two PMFs on the same alphabet, is

with the conventions $0\log\frac0q = 0$ and $p\log\frac{p}{0} = +\infty$ if $p(x)>0$ for some $x$ with $q(x)=0$. It is not a metric — it is asymmetric, $D(p\Vert q)\ne D(q\Vert p)$ in general, and violates the triangle inequality — but it is the right notion of "statistical distance" for coding and inference: it measures the inefficiency (extra bits per symbol) of assuming the distribution is $q$ when it is really $p$.

Theorem (Gibbs' inequality / non-negativity of KL). For any PMFs $p, q$,

Proof. Work in nats (multiply by $\log_2 e$ at the end; sign unaffected). Use the fundamental bound $\ln t \le t - 1$ for all $t>0$, with equality iff $t=1$ (the line $t-1$ is tangent to the concave $\ln$ at $t=1$). Then, restricting the sum to the support $S = \{x : p(x)>0\}$,

since $\sum_{x\in S} q(x) \le \sum_{\text{all }x} q(x) = 1$. Hence $D(p\,\Vert\,q) \ge 0$. Equality requires equality in $\ln t \le t-1$ at every $x\in S$, forcing $q(x)/p(x)=1$ there, and $\sum_{x\in S} q(x) = 1$ (no $q$-mass outside the support of $p$); together these give $p=q$. $\blacksquare$

Corollary (uniform maximizes entropy). Let $u(x) = 1/|\mathcal X|$ be uniform. Then

so $H(X) \le \log|\mathcal X|$, with equality iff $p = u$. Maximum uncertainty is the uniform distribution — exactly the equal-superposition state in the quantum case.

Mutual information

The mutual information between $X$ and $Y$ is the KL divergence between their joint distribution and the product of marginals:

It measures how far $(X,Y)$ is from being independent. Expanding the log gives the entropy identities, all equivalent definitions:

The first form is the headline: mutual information is the reduction in uncertainty about $X$ from learning $Y$. Because $I(X;Y)$ is a KL divergence, Gibbs' inequality immediately gives

A useful consequence is "conditioning reduces entropy": from $I(X;Y) = H(X) - H(X\mid Y) \ge 0$ we get $H(X\mid Y) \le H(X)$ — on average, side information never hurts. (It can increase entropy for a specific value $Y=y$, but not on average.)

Data-processing inequality (statement)

If $X \to Y \to Z$ forms a Markov chain (i.e. $Z$ depends on $X$ only through $Y$, so $p(z\mid x,y) = p(z\mid y)$), then

Post-processing cannot create information. No deterministic or randomized transformation of $Y$ can increase what it tells you about $X$ — you can only lose or preserve information by processing. This single inequality underlies converse bounds in coding, the impossibility of "boosting" a noisy channel by local post-processing, and (in its quantum form) the monotonicity of quantum relative entropy under channels — a cornerstone of quantum Shannon theory [Wil].

Source coding (Shannon's first theorem) — intuition

Entropy is not merely a formula; it is an operational limit. The source-coding theorem [CT, §5] (Shannon, 1948) says: a source emitting i.i.d. symbols $X$ can be compressed losslessly to an average of $H(X)$ bits per symbol, and no lossless scheme can do better in the limit of long blocks.

The intuition is the asymptotic equipartition property (AEP): for large $n$, the probability of a typical length-$n$ sequence concentrates around $2^{-nH(X)}$, so there are effectively only $\approx 2^{nH(X)}$ "typical" sequences worth encoding (out of $|\mathcal X|^n$ possible). Indexing just those costs $\log_2(2^{nH(X)}) = nH(X)$ bits, i.e. $H(X)$ bits per symbol. A biased coin with $H_b(0.1)\approx 0.469$ bits compresses to under half a bit per flip; a fair coin ($H_b(0.5)=1$) cannot be compressed at all. Entropy is the incompressible core of a source — and its quantum analog, via Schumacher's theorem, replaces $H$ with the von Neumann entropy $S(\rho)$ and "bits" with "qubits."

Quantum forward-reference. Everything here has a density-matrix counterpart. Shannon entropy $H(X) \to$ von Neumann entropy $S(\rho) = -\mathrm{Tr}(\rho\log\rho)$; the classical mutual information $\to$ quantum mutual information $I(A;B) = S(\rho_A)+S(\rho_B)-S(\rho_{AB})$; and KL divergence $\to$ quantum relative entropy. We build these on Term 1.5 · The Density Operator. A striking divergence: for an entangled pure state, $S(\rho_{AB})=0$ yet $S(\rho_A)>0$, so the conditional "entropy" $S(A\mid B) = S(\rho_{AB})-S(\rho_B)$ can be negative — impossible classically, and a signature of entanglement.

Worked Examples

Example 1 — Entropy of a biased coin and a binary symmetric channel

(a) A coin lands heads with probability $p = 0.25$. Its entropy is

So a long stream of such flips compresses to $\approx 0.811$ bits per flip — you cannot do better.

(b) Send a uniform bit $X$ ($\mathbb P(X=0)=\tfrac12$) through a binary symmetric channel that flips it with probability $f = 0.1$, producing $Y$. By symmetry $Y$ is also uniform, so $H(Y)=1$. The channel's leftover noise is $H(Y\mid X) = H_b(f) = H_b(0.1) \approx 0.469$ bits. The information that survives the channel is

This $I(X;Y)$ is exactly the kind of quantity whose maximization over input distributions gives the channel capacity — the maximum reliable bits per channel use.

Example 2 — KL divergence is asymmetric, and the cost of the wrong code

Let $p = (0.5, 0.5)$ (true) and $q = (0.9, 0.1)$ (assumed). Compute both directions.

They differ — $0.737 \ne 0.531$ — confirming KL is not symmetric. Operationally, $D(p\Vert q) = 0.737$is the *excess* bits per symbol you waste if the data are really fair coins ($p$) but you compress with a code optimized for the skewed $q$. Both are non-negative, as Gibbs' inequality guarantees, and both would be $0$ only if $p=q$.

Hands-on (Python)

We compute entropy, mutual information, and KL divergence directly from distributions, with care around the $0\log 0$ convention.

import numpy as np

# --- Base-2 entropy with the 0*log0 = 0 convention handled safely. ---
def entropy(p):
    """Shannon entropy H(p) in BITS for a probability vector p."""
    p = np.asarray(p, dtype=float)
    assert np.isclose(p.sum(), 1.0) and (p >= -1e-12).all(), "not a valid PMF"
    nz = p[p > 0]                       # drop zeros: 0*log0 := 0
    return float(-(nz * np.log2(nz)).sum())

def binary_entropy(p):
    return entropy([p, 1 - p]) if 0 < p < 1 else 0.0

print(f"H(fair coin)      = {binary_entropy(0.5):.4f} bits")   # 1.0000
print(f"H(p=0.25 coin)    = {binary_entropy(0.25):.4f} bits")  # 0.8113
print(f"H(uniform over 4) = {entropy([0.25]*4):.4f} bits")     # 2.0000  (= log2 4)

# --- KL divergence D(p || q) in bits.  Asymmetric by design. ---
def kl_divergence(p, q):
    p = np.asarray(p, dtype=float)
    q = np.asarray(q, dtype=float)
    mask = p > 0                         # terms with p=0 contribute 0
    if np.any((q[mask] == 0)):           # p>0 but q=0  ->  divergence is infinite
        return np.inf
    return float((p[mask] * np.log2(p[mask] / q[mask])).sum())

p = np.array([0.5, 0.5])
q = np.array([0.9, 0.1])
print(f"\nD(p||q) = {kl_divergence(p, q):.4f} bits")   # 0.7370
print(f"D(q||p) = {kl_divergence(q, p):.4f} bits")   # 0.5310  -> asymmetric!
print(f"D(p||p) = {kl_divergence(p, p):.4f} bits")   # 0.0     -> Gibbs equality
assert kl_divergence(p, q) >= 0 and kl_divergence(q, p) >= 0  # Gibbs: D >= 0

# --- Joint, conditional, mutual information from a JOINT distribution P[x, y]. ---
def mutual_information(Pxy):
    """I(X;Y) in bits from a joint PMF matrix Pxy (rows=x, cols=y)."""
    Pxy = np.asarray(Pxy, dtype=float)
    assert np.isclose(Pxy.sum(), 1.0), "joint PMF must sum to 1"
    Px = Pxy.sum(axis=1, keepdims=True)         # marginal p(x)
    Py = Pxy.sum(axis=0, keepdims=True)         # marginal p(y)
    indep = Px @ Py                              # product of marginals p(x)p(y)
    mask = Pxy > 0
    return float((Pxy[mask] * np.log2(Pxy[mask] / indep[mask])).sum())

# Binary symmetric channel, uniform input, flip prob f=0.1 (Example 1b).
f = 0.1
# joint p(x,y): P(x)=1/2 each; P(y|x) = 1-f on the diagonal, f off-diagonal.
Pxy = 0.5 * np.array([[1 - f, f],
                      [f, 1 - f]])
I_xy = mutual_information(Pxy)

# Cross-check against the entropy identity  I = H(X) + H(Y) - H(X,Y).
Px = Pxy.sum(axis=1); Py = Pxy.sum(axis=0)
H_X = entropy(Px); H_Y = entropy(Py); H_XY = entropy(Pxy.ravel())
print(f"\nI(X;Y) direct (KL form)      = {I_xy:.4f} bits")
print(f"I = H(X)+H(Y)-H(X,Y)         = {H_X + H_Y - H_XY:.4f} bits")
print(f"1 - H_b(f)  (theory)         = {1 - binary_entropy(f):.4f} bits")
assert np.isclose(I_xy, H_X + H_Y - H_XY)        # the identity holds
assert I_xy >= -1e-12                             # I(X;Y) >= 0 (Gibbs)

Expected output:

H(fair coin)      = 1.0000 bits
H(p=0.25 coin)    = 0.8113 bits
H(uniform over 4) = 2.0000 bits

D(p||q) = 0.7370 bits
D(q||p) = 0.5310 bits
D(p||p) = 0.0000 bits

I(X;Y) direct (KL form)      = 0.5310 bits
I = H(X)+H(Y)-H(X,Y)         = 0.5310 bits
1 - H_b(f)  (theory)         = 0.5310 bits

The three independent computations of $I(X;Y)$ agree — a good habit: derive an information quantity two ways and assert they match. The same entropy routine, applied to the eigenvalues of a density matrix $\rho$, will compute the von Neumann entropy $S(\rho)$ in Term 1.5; classical information theory is the literal warm-up for the quantum version.

Exercises

1. (Easy) Entropy bounds. Without computing, order these by entropy and then verify numerically: a fair 8-sided die; a fair coin; a coin with $p=0.99$; a deterministic source.

2. (Easy) Entropy is additive for independent variables. Show that if $X \perp Y$ then $H(X,Y) = H(X) + H(Y)$.

3. (Medium) Mutual information is symmetric. Prove $I(X;Y) = I(Y;X)$ directly from the entropy identities.

4. (Medium) KL divergence between two Bernoullis. Derive a closed form for $D(\text{Bern}(p)\,\Vert\,\text{Bern}(q))$, then evaluate at $p=0.5,\ q=0.9$ and confirm it matches Example 2's $D(p\Vert q)$.

5. (Hard) Conditioning reduces entropy — but only on average. Prove $H(X\mid Y) \le H(X)$ from $I(X;Y)\ge0$. Then give an explicit joint distribution where for a specific value $y_0$, $H(X\mid Y=y_0) > H(X)$, showing the inequality fails pointwise.

6. (Hard) Data-processing in action. Let $X\to Y\to Z$ with $X$ a uniform bit, $Y$ the output of a BSC with flip $f_1=0.1$, and $Z$ the output of a second BSC (applied to $Y$) with flip $f_2=0.2$. Compute $I(X;Y)$ and $I(X;Z)$ and verify $I(X;Y)\ge I(X;Z)$. (Hint: composing two BSCs gives a BSC with flip $f = f_1(1-f_2) + (1-f_1)f_2$.)

import numpy as np
def Hb(p): return 0.0 if p in (0,1) else -p*np.log2(p)-(1-p)*np.log2(1-p)
f1, f2 = 0.1, 0.2
f = f1*(1-f2) + (1-f1)*f2
print(1 - Hb(f1), 1 - Hb(f))   # 0.531..., 0.173...  -> I(X;Y) >= I(X;Z)

Checkpoint

1. Why is the surprise of an outcome of probability $p$ defined as $-\log p$? What property forces the logarithm?
2. Write the chain rule for entropy and interpret each term in words.
3. State Gibbs' inequality and the single calculus fact ($\ln t \le t-1$) its proof rests on.
4. Give three equivalent expressions for $I(X;Y)$ and explain why $I(X;Y)\ge 0$ with equality iff independence.
5. State the data-processing inequality and what it forbids.
6. What does the source-coding theorem say entropy operationally is, and what replaces $H(X)$ in the quantum theory?

Further Reading

• [CT, Ch. 2] Cover & Thomas — entropy, relative entropy, mutual information; the canonical treatment this lesson follows.
• [CT, §2.8, Ch. 5] Cover & Thomas — data-processing inequality and source coding (AEP, Shannon's first theorem).
• [Wil, Ch. 10–11] Wilde — classical entropies as the bridge to von Neumann entropy and quantum mutual information.
• [NC, §11.1–11.3] Nielsen & Chuang — Shannon entropy then von Neumann entropy; the explicit classical→quantum map.
• C. E. Shannon, "A Mathematical Theory of Communication", Bell Syst. Tech. J. 27 (1948) — the founding paper; the source-coding and channel-coding theorems originate here.

← Prev: Random Variables & Expectation · Up: Term 0 · Next: Complex Numbers & Functions →