# 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](../../term-1-quantum-mechanics/c05-density-matrices/01-density-operator.md).
---
## 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:
$$
H(X) := -\sum_{x\in\mathcal X} p(x)\log p(x) = \mathbb E\big[-\log p(X)\big] .
$$
**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
$$
H_b(p) = -p\log p - (1-p)\log(1-p),
$$
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
$$
H(X,Y) := -\sum_{x,y} p(x,y)\log p(x,y),
$$
and the **conditional entropy** of $Y$ given $X$ is the expected entropy of $Y$ once $X$ is known:
$$
H(Y\mid X) := \sum_x p(x)\,H(Y\mid X=x) = -\sum_{x,y} p(x,y)\log p(y\mid x).
$$
**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)$:
$$
H(X,Y) = -\sum_{x,y}p(x,y)\big[\log p(x) + \log p(y\mid x)\big] = H(X) + H(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:
$$
H(X_1,\dots,X_n) = \sum_{i=1}^n H(X_i \mid X_1,\dots,X_{i-1}).
$$
### Relative entropy (KL divergence) and Gibbs' inequality
The **relative entropy** (Kullback–Leibler divergence) from $p$ to $q$, two PMFs on the same
alphabet, is
$$
D(p\,\Vert\,q) := \sum_x p(x)\log\frac{p(x)}{q(x)},
$$
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$,
$$
D(p\,\Vert\,q) \ge 0, \qquad\text{with equality iff } 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\}$,
$$
-D(p\,\Vert\,q) = \sum_{x\in S} p(x)\ln\frac{q(x)}{p(x)}
\;\le\; \sum_{x\in S} p(x)\left(\frac{q(x)}{p(x)} - 1\right)
= \sum_{x\in S} q(x) - \sum_{x\in S} p(x)
= \sum_{x\in S} q(x) - 1 \le 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
$$
0 \le D(p\,\Vert\,u) = \sum_x p(x)\log\frac{p(x)}{1/|\mathcal X|}
= \log|\mathcal X| - H(X),
$$
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:
$$
I(X;Y) := D\big(p(x,y)\,\Vert\,p(x)p(y)\big) = \sum_{x,y}p(x,y)\log\frac{p(x,y)}{p(x)p(y)} .
$$
It measures how far $(X,Y)$ is from being independent. Expanding the log gives the **entropy
identities**, all equivalent definitions:
$$
I(X;Y) = H(X) - H(X\mid Y) = H(Y) - H(Y\mid X) = H(X) + H(Y) - H(X,Y).
$$
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
$$
I(X;Y) \ge 0, \qquad\text{with equality iff } X \perp Y \ (p(x,y)=p(x)p(y)).
$$
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
$$
I(X;Y) \ge I(X;Z).
$$
**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](../../term-1-quantum-mechanics/c05-density-matrices/01-density-operator.md).
> 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
$$
H_b(0.25) = -0.25\log_2 0.25 - 0.75\log_2 0.75 = 0.25(2) + 0.75(0.415) \approx 0.811 \text{ bits}.
$$
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
$$
I(X;Y) = H(Y) - H(Y\mid X) = 1 - 0.469 = 0.531 \text{ bits per use}.
$$
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.
$$
D(p\,\Vert\,q) = 0.5\log_2\frac{0.5}{0.9} + 0.5\log_2\frac{0.5}{0.1}
= 0.5(-0.848) + 0.5(2.322) = 0.737 \text{ bits}.
$$
$$
D(q\,\Vert\,p) = 0.9\log_2\frac{0.9}{0.5} + 0.1\log_2\frac{0.1}{0.5}
= 0.9(0.848) + 0.1(-2.322) = 0.763 - 0.232 = 0.531 \text{ bits}.
$$
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.
```python
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)
```
```python
# --- 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
```
```python
# --- 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:
```text
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.
Solution
By $H \le \log_2|\mathcal X|$ and $H=0$ iff deterministic: deterministic $(0)$ < coin $p=0.99$
$(H_b(0.99)\approx0.0808)$ < fair coin $(1)$ < fair 8-die $(\log_2 8 = 3)$. The fair die maximizes
entropy among these because it is uniform over the largest alphabet.
**2. (Easy) Entropy is additive for independent variables.** Show that if $X \perp Y$ then
$H(X,Y) = H(X) + H(Y)$.
Solution
Independence gives $p(x,y) = p(x)p(y)$, so $\log p(x,y) = \log p(x) + \log p(y)$. Then
$$
H(X,Y) = -\sum_{x,y}p(x)p(y)\big[\log p(x)+\log p(y)\big]
= -\sum_x p(x)\log p(x) - \sum_y p(y)\log p(y) = H(X)+H(Y),
$$
using $\sum_y p(y) = 1$ and $\sum_x p(x) = 1$. (Equivalently: $H(Y\mid X)=H(Y)$ when independent, so
the chain rule gives the result; and $I(X;Y)=0$, consistent with independence.)
**3. (Medium) Mutual information is symmetric.** Prove $I(X;Y) = I(Y;X)$ directly from the entropy
identities.
Solution
From the joint-entropy form, $I(X;Y) = H(X) + H(Y) - H(X,Y)$. This expression is manifestly
symmetric under swapping $X \leftrightarrow Y$ since $H(X,Y)=H(Y,X)$. Hence $I(X;Y)=I(Y;X)$.
Equivalently, $H(X)-H(X\mid Y) = H(Y)-H(Y\mid X)$ follows from the two chain-rule expansions of
$H(X,Y)$. The symmetry is why we say $X$ and $Y$ *share* $I(X;Y)$ bits.
**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)$.
Solution
$$
D(\text{Bern}(p)\,\Vert\,\text{Bern}(q)) = p\log_2\frac{p}{q} + (1-p)\log_2\frac{1-p}{1-q}.
$$
At $p=0.5,\ q=0.9$: $0.5\log_2\frac{0.5}{0.9} + 0.5\log_2\frac{0.5}{0.1} = 0.5(-0.848)+0.5(2.322) =
0.737$ bits — matching Example 2. (This is also $D(p\Vert q)$ for the $2$-symbol vectors there.)
**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.
Solution
*On average:* $I(X;Y) = H(X) - H(X\mid Y) \ge 0$ (mutual information is a KL divergence, Gibbs), so
$H(X\mid Y)\le H(X)$.
*Pointwise counterexample.* Let $X\in\{0,1\}$ with $p(X{=}0)=0.9$ (so $H(X)=H_b(0.9)\approx0.469$).
Let $Y\in\{a,b\}$ be coupled so that $p(X{=}0\mid Y{=}a)=0.5$. Then $H(X\mid Y{=}a)=H_b(0.5)=1 >
0.469 = H(X)$. Learning $Y=a$ specifically made us *more* uncertain about $X$. The average
$H(X\mid Y)=\sum_y p(y)H(X\mid Y{=}y)$ is still $\le H(X)$, because other values of $Y$ (e.g. $Y=b$
making $X$ nearly certain) more than compensate. Side information helps *on average*, not always.
**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$.)
Solution
For a uniform-input BSC with flip $f$, $I = 1 - H_b(f)$. First channel: $I(X;Y) = 1 - H_b(0.1) =
1-0.469 = 0.531$ bits. Composite flip: $f = 0.1(0.8) + 0.9(0.2) = 0.08 + 0.18 = 0.26$, so
$I(X;Z) = 1 - H_b(0.26) = 1 - 0.827 = 0.173$ bits. Indeed $0.531 \ge 0.173$ — cascading a second
noisy channel *destroyed* information about $X$; post-processing $Y$ into $Z$ could never increase
it. Numerically:
```python
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?
Answers
1. We require surprise to be *additive over independent events*: the surprise of two independent
outcomes should sum. Since their probabilities multiply, the only (continuous) function turning
products into sums is the logarithm, so surprise $\propto -\log p$ (negative so it's positive and
decreasing in $p$). Base 2 fixes the unit as bits.
2. $H(X,Y) = H(X) + H(Y\mid X)$: total uncertainty in the pair = uncertainty in $X$ + the uncertainty
in $Y$ that remains once $X$ is known.
3. $D(p\Vert q)\ge 0$ with equality iff $p=q$. Proof uses $\ln t \le t-1$ (tangent-line bound on the
concave $\ln$, equality at $t=1$) applied to $t = q(x)/p(x)$.
4. $I(X;Y) = H(X)-H(X\mid Y) = H(Y)-H(Y\mid X) = H(X)+H(Y)-H(X,Y)$. It equals
$D(p(x,y)\Vert p(x)p(y))$, a KL divergence, so Gibbs gives $I\ge0$, with equality iff
$p(x,y)=p(x)p(y)$, i.e. $X\perp Y$.
5. If $X\to Y\to Z$ is a Markov chain then $I(X;Y)\ge I(X;Z)$: processing $Y$ (deterministically or
randomly) cannot increase the information it carries about $X$.
6. Entropy is the minimum average number of bits per symbol to losslessly compress an i.i.d. source —
the incompressible core. In the quantum theory $H(X)$ is replaced by the von Neumann entropy
$S(\rho) = -\mathrm{Tr}(\rho\log\rho)$ (Schumacher compression, in qubits).
---
## 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](02-random-variables-expectation.md) · Up: [Term 0](../README.md) · Next: [Complex Numbers & Functions](../c03-fourier-methods/01-complex-numbers-functions.md) →