Last modified: 2026-11-12 01:08:55 (PST)
Definition 1 (Binary code) Let \(X\) be a discrete random variable. A binary code for \(X\) assigns each value \(x\) a codeword, a string of \(\ell(x)\) bits.
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 a discrete random variable \(X\) is the expectation of its codeword length:
\[L \stackrel{\text{def}}{=}{\mathbb{E}\mathopen{}\left[\ell(X)\right]\mathclose{}}.\]
Theorem 1 (Expected length as a sum over values) Let \(X\) be a discrete random variable with probability mass function \(p(x) \stackrel{\text{def}}{=}\mathbb{P}(X=x)\). The expected length of a binary code for \(X\) is
\[L = \sum_{x} p(x) \, \ell(x).\]
Proof. The codeword length \(\ell(X)\) is a random variable whose possible values are the codeword lengths \(\ell(x)\). By the definition of expectation,
\[L = \sum_{k} k \, \mathbb{P}(\ell(X) = k).\]
The event \(\ell(X) = k\) is the union of the disjoint events \(X = x\) over the values \(x\) with \(\ell(x) = k\). So \(\mathbb{P}(\ell(X) = k) = \sum_{x : \ell(x) = k} p(x)\), and
\[L = \sum_{k} \sum_{x : \ell(x) = k} k \, p(x).\]
On the inner sum \(k = \ell(x)\). Every value \(x\) lies in exactly one inner sum, so the double sum runs once over each value:
\[L = \sum_{x} \ell(x) \, p(x).\]
Example 1 (Expected length of a code for a three-valued variable)
Let \(X\) have probability mass function \(p = (1/2, 1/4, 1/4)\), and let a binary code for \(X\) have codeword lengths \(\ell = (1, 2, 2)\). The code below computes the expected length from its definition, as the expectation of \(\ell(X)\), and as the sum in Theorem 1.
p <- c(1 / 2, 1 / 4, 1 / 4)
len <- c(1, 2, 2)
lengths_seen <- sort(unique(len))
prob_of_length <- vapply(
lengths_seen,
function(k) sum(p[len == k]),
numeric(1)
)
from_definition <- sum(lengths_seen * prob_of_length)
from_sum <- sum(p * len)
c(from_definition = from_definition, from_sum = from_sum)
#> from_definition from_sum
#> 1.5 1.5Remark 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 \(\ell(x)\) counts in \(L\) weighted by its probability.
Theorem 2 (Source coding theorem) Let \(X\) be a discrete random variable that takes a finite number of values, at least two of them with nonzero probability, and let \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\) be its entropy with base-2 logarithms.
Every uniquely decodable binary code for \(X\) has expected length \(L \ge {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\).
Some uniquely decodable binary code for \(X\) has expected length \(L < {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + 1\).
Coding \(n\) independent copies of \(X\) at a time, some uniquely decodable binary code spends, on average, fewer than \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + 1/n\) bits per copy.
Remark 2 (Where the theorem comes from). Shannon (1948) proved that no compression of the output of a source can beat its entropy. Cover and Thomas (2006, sec. 5.3 to 5.5) prove each part of Theorem 2. 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; Kraft’s condition (Cover and Thomas 2006, sec. 5.2) guarantees that there is a code with these lengths.
Theorem 3 (The cost of coding with the wrong distribution) Let \(X\) take a finite number of values, with probability mass function \(p\), and let \(q\) be such a 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
\[{\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} \le L < {\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} + 1,\]
where \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\) 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\) by Theorem 1, and the outer sums are \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\).
Theorem 4 (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 \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}}\) for the entropy of \(p\), \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\) for the cross-entropy of \(q\) relative to \(p\), and \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\) for the Kullback–Leibler divergence of \(q\) from \(p\), all with base-2 logarithms. Then
\[{\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(p\right)\mathclose{}} + {{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}.\]
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 \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\), \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}}\) and \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\).
Example 2 (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 \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} = 1.585\) bits. The entropy is \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}} = 1.5\) bits, and the divergence is \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}} = 0.085\) bits. They satisfy Theorem 4: 1.5 + 0.085 = 1.585.
Remark 3 (Cross-entropy is the cost of the wrong code). Theorem 4 splits the cross-entropy into the entropy and the divergence. By Theorem 2, no uniquely decodable code averages fewer than \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}}\) bits. By Theorem 3, a code built for \(q\) costs about \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\) 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 3 in this form, with \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}} + {{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\) in place of \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\).
Remark 4 (Why models are fit by minimizing cross-entropy). Fitting a classifier by minimizing cross-entropy chooses the probabilities \(q\) the model assigns 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 probabilities the labels came from.
For a single labeled example, let \(e\) put all its mass on the observed label. Then \({\mathbb{H}\mathopen{}\left(e\right)\mathclose{}} = 0\) (as for a coin that always lands heads), so the example’s cross-entropy \({\mathbb{H}\mathopen{}\left(e, q\right)\mathclose{}}\) equals \({{D_{\mathrm{KL}}}\mathopen{}\left(e \,\Vert\, q\right)\mathclose{}}\): every bit it reports is a wasted one.