Information theory · The Lumenary

MotivationH

Bits, noise and two questions

Morse code gives the most frequent letter of English, E, the shortest signal: a single dot. A text message sent from Lagos to Jakarta is compressed before it travels and protected against errors as it crosses radio links and cables; deep-space probes such as Voyager send their pictures home through extraordinary noise, protected by error-correcting codes; every QR code can be read even when part of it is torn off. Behind all of these is a 1948 paper by Claude Shannon, A Mathematical Theory of Communication, which asked two questions and answered both with numbers:

Compression. A source emits random symbols. How many bits per symbol are needed, on average, to describe its output without loss? Answer: the entropy $H$ .
Transmission. A channel corrupts what it carries. How many bits per use can be sent with arbitrarily small probability of error? Answer: the capacity $C$ .

Both answers are limits that can be approached but not beaten — theorems, not engineering rules of thumb. Shannon deliberately set meaning aside: "These semantic aspects of communication are irrelevant to the engineering problem." Information, in his sense, is resolved uncertainty. This lesson builds on probability theory, in particular expectation and the weak law of large numbers.

IntuitionH

Twenty questions and surprise

Someone picks a whole number from $1$ to $64$ . Each yes/no question can at best halve the remaining possibilities, so $6 = \log_2 64$ questions are needed and enough. More generally, singling out one of $N$ equally likely possibilities takes $\log_2 N$ bits. If an outcome has probability $p$ , it is "one of $1/p$ " possibilities, and learning that it happened gives

\log_2\frac1p \text{ bits of information (its **surprisal**)}.

Rare events are surprising and informative; certain events tell us nothing. The entropy of a random variable is its average surprisal. For a coin with $P(\text{heads}) = p$ it is the binary entropy $H_2(p) = -p\log_2 p - (1 - p)\log_2(1 - p)$ : one full bit for a fair coin, less for a biased one, and zero for a coin that always lands heads.

Uncertainty and capacity

The entropy of a coin is largest when it is fair. A channel that flips each bit with probability p can carry 1 − H₂(p) bits per use: nothing at p = 1/2, and a full bit at p = 1, since a channel that always flips is as good as one that never does.

binary entropy H₂(p)
capacity 1 − H₂(p) of a channel flipping bits with probabili

Trace along xx = 1

binary entropy H₂(p): y = undefined here
capacity 1 − H₂(p) of a channel flipping bits with probabili: y = undefined here

DefinitionsH

Definitions

All random variables here take finitely many values. Logarithms are to base $2$ (units: bits) unless stated; with natural logarithms the unit is the nat, and $1$ nat $= \log_2 e \approx 1.443$ bits. We use the convention $0\log 0 = 0$ (justified by $p\log p \to 0$ as $p \to 0$ ).

Definition— entropy, joint and conditional entropy

The entropy of $X$ with mass function $p$ is $H(X) = -\sum_x p(x)\log p(x) = E[-\log p(X)]$ . For a pair $(X, Y)$ with joint mass function $p(x, y)$ , the joint entropy is $H(X, Y) = -\sum_{x,y}p(x, y)\log p(x, y)$ , and the conditional entropy is

H(Y \mid X) = \sum_x p(x)\,H(Y \mid X = x) = -\sum_{x,y}p(x, y)\log p(y \mid x).

Definition— relative entropy and mutual information

For distributions $p, q$ on the same finite set, the relative entropy (Kullback–Leibler divergence) is $D(p \,\|\, q) = \sum_x p(x)\log\frac{p(x)}{q(x)}$ (infinite if $q(x) = 0 < p(x)$ for some $x$ ). The mutual information of $X$ and $Y$ is

I(X; Y) = H(X) - H(X \mid Y),

the reduction in uncertainty about $X$ from learning $Y$ .

Definition— prefix code

A binary code for a set $\mathcal X$ assigns to each symbol $x$ a codeword $c(x) \in \{0, 1\}^*$ of length $\ell(x)$ . It is a prefix code (prefix-free) if no codeword is a prefix of another; then a concatenation of codewords can be decoded on the fly, without separators. Its expected length for a source with distribution $p$ is $L = \sum_x p(x)\ell(x)$ .

Definition— channel, rate and capacity

A discrete memoryless channel has input alphabet $\mathcal X$ , output alphabet $\mathcal Y$ and transition probabilities $W(y \mid x)$ ; each use is independent of the others. A code of block length $n$ and rate $R$ consists of $M = 2^{nR}$ codewords in $\mathcal X^n$ and a decoding rule $\mathcal Y^n \to \{1, \dots, M\}$ . The capacity of the channel is

C = \max_{p(x)} I(X; Y),

the maximum over input distributions of the mutual information between one input and its output.

Worked examplesH

Examples

Example— Dice, coins and text

A fair die has $H = \log_2 6 \approx 2.585$ bits; a coin with $P(\text{heads}) = 0.2$ has $H_2(0.2) \approx 0.722$ bits. A source emitting $A, B, C, D$ with probabilities $\tfrac12, \tfrac14, \tfrac18, \tfrac18$ has $H = \tfrac12\cdot 1 + \tfrac14\cdot 2 + \tfrac18\cdot 3 + \tfrac18 \cdot 3 = 1.75$ bits, and the prefix code $A \mapsto 0$ , $B \mapsto 10$ , $C \mapsto 110$ , $D \mapsto 111$ achieves exactly $1.75$ bits per symbol on average. The single-letter frequencies of English give about $4.1$ bits per letter, but letters depend on their neighbours, and Shannon's 1951 experiments with human predictors suggested roughly $1$ bit per letter once context is used.

The prefix code 0, 10, 110, 111 as a binary tree: left branches are 0, right branches 1, and codewords are leaves. No codeword lies on the path to another, so the code is prefix-free; the leaf at depth $\ell$ takes up $2^{-\ell}$ of the tree, and the four leaves fill it exactly — Kraft's equality $\tfrac12 + \tfrac14 + \tfrac18 + \tfrac18 = 1$.

Example— Mutual information of a noisy bit

Let $X$ be a fair bit and $Y$ the same bit sent through a channel that flips it with probability $\tfrac14$ . Then $Y$ is also a fair bit, $H(X) = 1$ , and given $Y$ the remaining uncertainty about $X$ is that of the flip: $H(X \mid Y) = H_2(\tfrac14) \approx 0.811$ . So $I(X; Y) \approx 0.189$ bits: each received bit tells us less than a fifth of a bit about what was sent. Repeating the transmission helps, at a cost in rate — the trade-off the channel coding theorem resolves.

ProofH

Gibbs' inequality and its consequences

Everything rests on one inequality, which comes from $\ln t \le t - 1$ (with equality only at $t = 1$ ): the tangent line at $t = 1$ lies above the concave function $\ln$ .

Theorem— Theorem (Gibbs' inequality)

For distributions $p$ and $q$ on a finite set, $D(p \,\|\, q) \ge 0$ , with equality if and only if $p = q$ . More generally, if $q \ge 0$ with $\sum_x q(x) \le 1$ , then $\sum_x p(x)\log\frac{q(x)}{p(x)} \le 0$ .

Proof

We may assume $q(x) > 0$ whenever $p(x) > 0$ (otherwise $D = \infty$ ). Working in nats, for each $x$ with $p(x) > 0$ , $\;p(x)\ln\frac{q(x)}{p(x)} \le p(x)\Big(\frac{q(x)}{p(x)} - 1\Big) = q(x) - p(x)$ , and terms with $p(x) = 0$ contribute $0 \le q(x)$ . Summing,

\sum_x p(x)\ln\frac{q(x)}{p(x)} \le \sum_x q(x) - \sum_x p(x) \le 1 - 1 = 0 .

Equality forces $\frac{q(x)}{p(x)} = 1$ wherever $p(x) > 0$ and $\sum_x q(x) = 1$ , hence $p = q$ . Changing the base of the logarithm multiplies everything by a positive constant.

∎

Theorem— Corollary (bounds and chain rule)

$0 \le H(X) \le \log|\mathcal X|$ , with $H(X) = 0$ iff $X$ is constant and $H(X) = \log|\mathcal X|$ iff $X$ is uniform.
Chain rule: $H(X, Y) = H(X) + H(Y \mid X)$ .
$I(X; Y) = H(X) + H(Y) - H(X, Y) = D\big(p_{XY} \,\big\|\, p_Xp_Y\big)$ . Hence $I(X; Y) = I(Y; X) \ge 0$ , with equality iff $X$ and $Y$ are independent; equivalently $H(X \mid Y) \le H(X)$ — conditioning reduces entropy on average.

Proof

(1) Each term $-p\log p$ is $\ge 0$ for $0 \le p \le 1$ , and vanishes only at $p \in \{0, 1\}$ . For the upper bound apply Gibbs with $q$ uniform: $0 \ge \sum_x p(x)\log\frac{1}{|\mathcal X|p(x)} = H(X) - \log|\mathcal X|$ , with equality iff $p$ is uniform.

(2) Write $p(x, y) = p(x)p(y \mid x)$ and take $-E[\log(\cdot)]$ : $H(X, Y) = E[-\log p(X)] + E[-\log p(Y \mid X)] = H(X) + H(Y \mid X)$ .

(3) By the chain rule (with the roles of $X$ and $Y$ swapped), $H(X \mid Y) = H(X, Y) - H(Y)$ , so $I(X; Y) = H(X) + H(Y) - H(X, Y)$ , which is symmetric. Writing the three entropies as expectations, $I(X; Y) = E\Big[\log\frac{p(X, Y)}{p(X)p(Y)}\Big] = D(p_{XY} \,\|\, p_Xp_Y)$ , and Gibbs' inequality finishes the proof.

∎

Theorem— Theorem (data-processing inequality)

If $X \to Y \to Z$ is a Markov chain ( $Z$ depends on $X$ only through $Y$ ), then $I(X; Z) \le I(X; Y)$ : no processing of $Y$ , deterministic or random, can increase the information it carries about $X$ .

Proof

Define conditional mutual information $I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z) \ge 0$ (Gibbs again, conditionally on each value of $Z$ ). The chain rule gives $I(X; Y, Z) = I(X; Z) + I(X; Y \mid Z) = I(X; Y) + I(X; Z \mid Y)$ . The Markov property makes $X$ and $Z$ conditionally independent given $Y$ , so $I(X; Z \mid Y) = 0$ , and therefore $I(X; Z) \le I(X; Y)$ .

∎

Why this formula for entropy, and not another? Shannon showed, and Khinchin (1953) made rigorous, that any function of probability vectors that is continuous, maximal at the uniform distribution, unchanged by adding impossible outcomes, and additive in the sense of the chain rule must be a positive multiple of $-\sum p\log p$ . The choice of base is the choice of unit.

ProofH

Prefix codes, Kraft and Huffman

A binary word $w$ of length $\ell$ corresponds to the dyadic interval $J(w) = [0.w,\ 0.w + 2^{-\ell})$ of $[0, 1)$ , where $0.w$ is the binary fraction with digits $w$ ; and $u$ is a prefix of $v$ exactly when $J(v) \subseteq J(u)$ . Two dyadic intervals are either nested or disjoint, so a code is prefix-free exactly when its intervals are pairwise disjoint.

Theorem— Theorem (Kraft's inequality, 1949)

A binary prefix code with codeword lengths $\ell_1, \dots, \ell_k$ exists if and only if $\sum_{i=1}^k 2^{-\ell_i} \le 1$ .

Proof

Necessity. The intervals $J(c_i)$ of a prefix code are disjoint subsets of $[0, 1)$ with lengths $2^{-\ell_i}$ , so their total length is at most $1$ . (The Lean proof argues instead by induction on the maximal length, splitting the code by its first bit.)

Sufficiency. Order the lengths $\ell_1 \le \cdots \le \ell_k$ and put $a_i = \sum_{j < i}2^{-\ell_j}$ . Since $\ell_j \le \ell_i$ for $j < i$ , $a_i$ is a multiple of $2^{-\ell_i}$ , and $a_i + 2^{-\ell_i} \le \sum_j 2^{-\ell_j} \le 1$ ; so $a_i = 0.c_i$ for a word $c_i$ of exactly $\ell_i$ digits, and $J(c_i) = [a_i, a_{i+1})$ . These intervals are disjoint, so the code is prefix-free.

∎

McMillan (1956) showed that the same inequality holds for every uniquely decodable code, so nothing is lost by insisting on prefix codes.

Theorem— Theorem (source coding bounds)

The minimal expected length $L^*$ of a binary prefix code for a source $X$ satisfies $H(X) \le L^* < H(X) + 1$ .

Proof

Lower bound. Given a prefix code, put $q(x) = 2^{-\ell(x)}$ , so $\sum_x q(x) \le 1$ by Kraft. Gibbs' inequality gives $\sum_x p(x)\log_2\frac{2^{-\ell(x)}}{p(x)} \le 0$ , that is, $H(X) - L \le 0$ .

Upper bound. Take Shannon's lengths $\ell(x) = \lceil -\log_2 p(x)\rceil$ (for $p(x) > 0$ ). Then $2^{-\ell(x)} \le p(x)$ , so $\sum_x 2^{-\ell(x)} \le 1$ and by Kraft a prefix code with these lengths exists; and $\ell(x) < -\log_2 p(x) + 1$ , so $L < H(X) + 1$ .

∎

Coding blocks of $n$ symbols at once spreads the " $+1$ " over $n$ symbols: for an i.i.d. source, $H(X^n) = nH(X)$ , so the optimal code for blocks has $H(X) \le L^*_n/n < H(X) + \frac1n$ . The entropy is the exact price of lossless description. Shannon's lengths are not optimal, though; the optimal code comes from a simple greedy algorithm.

Huffman's algorithm (1952). Take the two least probable symbols, make them siblings — their codewords will differ only in the last bit — and replace them by a single symbol whose probability is their sum. Repeat until one symbol remains; reading the merges backwards builds the code tree.

Theorem— Theorem (Huffman codes are optimal)

A Huffman code has the smallest expected length among all binary prefix codes for the given distribution.

Proof

Induction on the number $k$ of symbols; $k = 2$ is clear (lengths $1, 1$ ). Let $x, y$ be the two least probable symbols.

Step 1: some optimal code has $x$ and $y$ as sibling leaves at maximal depth. In an optimal code, if $p(a) > p(b)$ then $\ell(a) \le \ell(b)$ (otherwise swapping their codewords lowers $L$ ). The code tree of an optimal code is full — every internal node has two children — since otherwise a codeword could be shortened. So a deepest leaf has a sibling leaf; exchanging codewords so that $x$ and $y$ occupy these two leaves does not increase $L$ , because they are the least probable.

Step 2: merging. Replace $x, y$ by one symbol $z$ with $p(z) = p(x) + p(y)$ . Codes for the original source in which $x, y$ are siblings correspond to codes for the merged source (delete the last bit of their codewords to get $z$ 's), and $L = L' + p(x) + p(y)$ . So an optimal code for the merged source, extended by one bit, is optimal among codes with $x, y$ siblings — hence, by Step 1, optimal. Huffman's algorithm does exactly this, and by induction it produces an optimal code for the merged source.

∎

A Huffman tree is full, so its lengths satisfy Kraft with equality. The first experiment below builds one for a real sentence and checks every bound.

ExplanationH

Typical sequences and Shannon's source coding theorem

For an i.i.d. source, $-\log_2 p(X_1, \dots, X_n) = \sum_{i=1}^n -\log_2 p(X_i)$ is a sum of i.i.d. terms with mean $H(X)$ , so by the weak law of large numbers:

Theorem— Theorem (asymptotic equipartition property)

If $X_1, X_2, \dots$ are i.i.d. with entropy $H$ , then $-\frac1n\log_2 p(X_1, \dots, X_n) \to H$ in probability.

So with high probability the sequence that occurs has probability close to $2^{-nH}$ . Fix $\varepsilon > 0$ and let the typical set $T_\varepsilon^{(n)}$ consist of the sequences with $2^{-n(H + \varepsilon)} \le p(x_1, \dots, x_n) \le 2^{-n(H - \varepsilon)}$ . Then (i) $P(T_\varepsilon^{(n)}) \to 1$ ; (ii) $|T_\varepsilon^{(n)}| \le 2^{n(H + \varepsilon)}$ , because each of its elements has probability at least $2^{-n(H+\varepsilon)}$ and the total is at most $1$ ; and (iii) $|T_\varepsilon^{(n)}| \ge (1 - \varepsilon)2^{n(H - \varepsilon)}$ for large $n$ . Almost all the probability sits on about $2^{nH}$ roughly equiprobable sequences — a vanishing fraction of all $|\mathcal X|^n$ sequences when $H < \log|\mathcal X|$ .

Theorem— Theorem (Shannon's source coding theorem)

For an i.i.d. source with entropy $H$ : for every $R > H$ there are codes mapping blocks of $n$ symbols to $nR$ bits whose probability of decoding error tends to $0$ as $n \to \infty$ ; for every $R < H$ , the probability of error of any such codes tends to $1$ .

Sketch. Index the typical set with $n(H + \varepsilon) + 1$ bits and give up on the rest; the error probability is $1 - P(T_\varepsilon^{(n)}) \to 0$ . Conversely, $2^{nR}$ codewords with $R < H$ can cover at most $2^{nR}$ typical sequences, whose total probability is at most $2^{nR}2^{-n(H - \varepsilon)} \to 0$ , plus the vanishing probability outside the typical set. The second experiment below measures typical sets exactly for a biased coin.

ProofH

Channels and capacity

Theorem— Theorem (capacity of the binary symmetric channel)

The binary symmetric channel with crossover probability $p$ (each bit flipped independently with probability $p$ ) has capacity $C = 1 - H_2(p)$ bits per use, attained by the uniform input.

Proof

Let $P(X = 1) = s$ . Given $X = x$ , the output is $x$ or $1 - x$ with probabilities $1 - p$ and $p$ , so $H(Y \mid X = x) = H_2(p)$ for both $x$ , and $H(Y \mid X) = H_2(p)$ . The output is $1$ with probability $s(1 - p) + (1 - s)p$ , so

I(X; Y) = H(Y) - H(Y \mid X) = H_2\big(s(1-p) + (1-s)p\big) - H_2(p) \le 1 - H_2(p),

since a binary variable has entropy at most $1$ bit. For $s = \frac12$ the output probability is $\frac12$ and equality holds.

∎

Similarly, the binary erasure channel, which delivers each bit correctly with probability $1 - \varepsilon$ and otherwise replaces it by "?", has capacity $1 - \varepsilon$ : an erasure is known to the receiver, and with feedback one could simply resend; Shannon's theorem says the same rate is achievable without feedback.

A message

W

(one of

2^{nR}

) is encoded as

n

channel inputs, corrupted by the channel (dashed: random), and decoded as

\hat W

. The chain

W \to X^n \to Y^n \to \hat W

is a Markov chain, so the data-processing inequality applies.

Theorem— Theorem (noisy-channel coding theorem, Shannon 1948)

Let $C$ be the capacity of a discrete memoryless channel.

Achievability. For every $R < C$ and $\varepsilon > 0$ , for all sufficiently large $n$ there is a code of block length $n$ and rate at least $R$ whose maximal probability of decoding error is at most $\varepsilon$ .
Converse. For every sequence of codes with rate $R > C$ , the average probability of error is bounded away from $0$ (indeed $P_e^{(n)} \ge 1 - \frac CR - \frac{1}{nR}$ ).

Sketch of the proof. Converse: for a uniformly random message $W$ of $nR$ bits, Fano's inequality bounds the leftover uncertainty, $H(W \mid \hat W) \le 1 + P_e\,nR$ ; the data-processing inequality and memorylessness give $I(W; \hat W) \le I(X^n; Y^n) \le nC$ ; and $nR = H(W) = H(W \mid \hat W) + I(W; \hat W) \le 1 + P_e\,nR + nC$ , which rearranges to the stated bound. Achievability: Shannon's astonishing idea was to choose the codebook at random — $2^{nR}$ codewords drawn independently from the capacity-achieving input distribution — and to decode by looking for the unique codeword jointly typical with the output. The AEP shows that the true codeword is jointly typical with high probability, while any particular wrong codeword is jointly typical with probability about $2^{-nI(X;Y)}$ ; with $2^{nR}$ wrong codewords and $R < I(X; Y)$ , the union bound makes a confusion unlikely. Since the average over random codebooks has small error, some codebook does too, and discarding its worst half bounds the maximal error. Full proofs: Cover and Thomas, Chapter 7.

The theorem is an existence theorem. Repetition codes achieve small error only by letting the rate $1/n$ go to zero; the Hamming $(7, 4)$ code (1950) sends $4$ bits in $7$ and corrects any single error. Codes that approach capacity with practical decoding took decades: low-density parity-check codes (Gallager, 1962; rediscovered in the 1990s), turbo codes (Berrou, Glavieux and Thitimajshima, 1993) and polar codes (Arıkan, 2009), now used in mobile networks. The third experiment compares repetition codes and the Hamming code with the capacity.

Formal mathematicsF

Information theory in Lean and Mathlib

Mathlib works in nats: Real.negMulLog x = −x log x and the binary entropy Real.binEntropy p use natural logarithms, so log 2 nats is one bit. The module defines entropy for distributions on a finite type and proves the lesson's core inequalities.

Entropy and Gibbs' inequality, proved as in the lesson from log t ≤ t − 1, and the bound $H \le \log|\mathcal X|$ :

entropyLean 4Formally verified

/-- The **Shannon entropy** of a distribution `p` on a finite set, in nats:
`H(p) = −∑ p(x) log p(x) = ∑ negMulLog (p x)`. (Lean's convention `log 0 = 0` gives the
usual `0 log 0 = 0`.) -/
noncomputable def entropy (p : S → ℝ) : ℝ := ∑ x, negMulLog (p x)