Last modified: 2026-11-07 21:35:35 (PST)
Definition 1 (Binary code) Let \(X\) be a discrete random variable. A binary code for \(X\) assigns each value \(x\) a codeword, a finite string of binary digits, of length \(\ell(x)\).
Definition 2 (Uniquely decodable code) A binary code is uniquely decodable if every finite sequence of codewords, written one after another, can be split back into codewords in only one way.
Definition 3 (Expected length) The expected length of a binary code for \(X\), where \(X\) has probability mass function \(p(x) \stackrel{\text{def}}{=}\mathbb{P}(X=x)\), is
\[L \stackrel{\text{def}}{=}{\mathbb{E}\mathopen{}\left[\ell(X)\right]\mathclose{}} = \sum_{x} p(x) \, \ell(x).\]
Remark 1 (Short codewords for common values). A code with a small expected length gives frequent values short codewords and rare values long ones, since each value’s length counts in \(L\) in proportion to its probability.
Theorem 1 (Source coding theorem) Let \(X\) be a discrete random variable that takes finitely many values, at least two of them with positive probability, and let \(H_2(X)\) be its entropy with base-2 logarithms.
Every uniquely decodable binary code for \(X\) has expected length \(L \ge H_2(X)\).
Some uniquely decodable binary code for \(X\) has expected length \(L < H_2(X) + 1\).
Coding blocks of \(n\) independent copies of \(X\) at a time, some uniquely decodable binary code spends, on average, fewer than \(H_2(X) + 1/n\) binary digits per copy.
Remark 2 (Where the theorem comes from). Shannon (1948) proved that entropy is the limit on how far the output of a source can be compressed. Cover and Thomas (2006, sec. 5.3 to 5.5) prove each part of Theorem 1. For part 2, they give each value \(x\) with \(p(x) > 0\) the length \(\ell(x) = \lceil -\log_2 p(x) \rceil\), its surprisal in bits rounded up; the Kraft inequality (Cover and Thomas 2006, sec. 5.2) guarantees that a code with these lengths exists.
Theorem 2 (The cost of coding with the wrong distribution) Let \(X\) take finitely many values, with probability mass function \(p\), and let \(q\) be a probability mass function, possibly different from \(p\), with \(q(x) > 0\) wherever \(p(x) > 0\). Suppose a code gives each value \(x\) with \(p(x) > 0\) the length \(\ell(x) = \lceil -\log_2 q(x) \rceil\). Then its expected length \(L\) under \(p\) satisfies
\[H_2(p, q) \le L < H_2(p, q) + 1,\]
where \(H_2(p, q)\) is the cross-entropy of \(q\) relative to \(p\), with base-2 logarithms.
Proof. Every sum here runs over the values \(x\) with \(p(x) > 0\). Rounding up adds less than one binary digit, so for each such \(x\)
\[-\log_2 q(x) \le \ell(x) < -\log_2 q(x) + 1.\]
Multiply each part by \(p(x) > 0\) and sum. Since \(\sum_{x} p(x) = 1\),
\[ -\sum_{x} p(x) \log_2 q(x) \le \sum_{x} p(x) \, \ell(x) < -\sum_{x} p(x) \log_2 q(x) + 1. \]
The middle sum is \(L\), and the outer sums are \(H_2(p, q)\).
Theorem 3 (Cross-entropy is entropy plus divergence) Let \(p\) and \(q\) be probability mass functions on the values \(x_1, \ldots, x_n\), with \(q(x) > 0\) wherever \(p(x) > 0\). Write \(H_2(p)\) for the entropy of \(p\), \(H_2(p, q)\) for the cross-entropy of \(q\) relative to \(p\), and \(D_2(p \,\|\, q)\) for the Kullback–Leibler divergence of \(q\) from \(p\), all with base-2 logarithms. Then
\[H_2(p, q) = H_2(p) + D_2(p \,\|\, q).\]
Proof. Every sum here runs over the values \(x\) with \(p(x) > 0\). For every such \(x\),
\[ -\log_2 q(x) = -\log_2 p(x) + \log_2 \frac{p(x)}{q(x)}. \]
Multiply by \(p(x)\) and add over \(x\):
\[ -\sum_x p(x) \log_2 q(x) = -\sum_x p(x) \log_2 p(x) + \sum_x p(x) \log_2 \frac{p(x)}{q(x)}. \]
Reading left to right, these are \(H_2(p, q)\), \(H_2(p)\) and \(D_2(p \,\|\, q)\).
Example 1 (Cross-entropy, entropy and divergence for a uniform code)
Let \(p = (1/2, 1/4, 1/4)\) be the probability mass function of a three-valued random variable, and let \(q = (1/3, 1/3, 1/3)\) assign \(1/3\) to each of the three values. The code below computes the cross-entropy, the entropy and the divergence in bits.
p <- c(1 / 2, 1 / 4, 1 / 4)
q <- rep(1 / 3, 3)
cross_entropy <- -sum(p * log2(q))
shannon_entropy <- -sum(p * log2(p))
divergence <- sum(p * log2(p / q))
c(
cross_entropy = cross_entropy,
shannon_entropy = shannon_entropy,
divergence = divergence
)
#> cross_entropy shannon_entropy divergence
#> 1.5849625 1.5000000 0.0849625The cross-entropy is \(H_2(p, q) = 1.585\) bits. The entropy is \(H_2(p) = 1.5\) bits, and the divergence is \(D_2(p \,\|\, q) = 0.085\) bits. They satisfy Theorem 3: 1.5 + 0.085 = 1.585.
Remark 3 (Cross-entropy is the cost of the wrong code). Theorem 3 splits the cross-entropy into the entropy and the divergence. By Theorem 1, no uniquely decodable code averages fewer than \(H_2(p)\) bits. By Theorem 2, a code built for \(q\) costs about \(D_2(p \,\|\, q)\) bits per value more than that. By the divergence theorem, the excess vanishes only when the code was built for \(p\) (Cover and Thomas 2006, sec. 2.6; Yeung 2008, sec. 2.5). Cover and Thomas (2006, sec. 5.4) state Theorem 2 in this form, with \(H_2(p) + D_2(p \,\|\, q)\) in place of \(H_2(p, q)\).
Remark 4 (Why models are fit by minimizing cross-entropy). Fitting a classifier by minimizing cross-entropy chooses the model’s distribution \(q\) so that a code built for \(q\) would spend as few bits as possible on the observed labels. By Remark 3, that pushes \(q\) toward the distribution the labels came from.
For a single labeled example, let \(e\) be the distribution that puts all its mass on the observed label. Then \(H_2(e) = 0\) (as for a coin that always lands heads), so the example’s cross-entropy loss \(H_2(e, q)\) equals \(D_2(e \,\|\, q)\): every bit the loss reports is a wasted one.