A visual and mathematically rigorous introduction to information content, entropy, cross-entropy, and KL divergence — for readers who want the intuition and the derivations.
In the 1940s, Claude Shannon gave the informal idea of “information” a precise mathematical footing
This two-part post builds up the core machinery of information theory — entropy, cross-entropy, KL divergence, joint and conditional entropy, mutual information, and the entropy rate of a stochastic process — visually and rigorously at the same time. It closely follows two sources. The first is Christopher Olah’s essay Visual Information Theory, which builds intuition for entropy and related quantities through codes and areas rather than through the sums directly
Throughout, we assume only familiarity with basic probability: random variables, joint and conditional distributions, and expectation.
Gaining information means having your uncertainty about something reduced. If I tell you the outcome of a coin flip you haven’t seen, I’ve resolved all your uncertainty about it. If I tell you something you already knew for certain, I’ve given you no information at all.
Consider drawing a marble at random from an urn containing marbles of four colors, with replacement, where
\[p(\texttt{blue}) = \tfrac{1}{2}, \quad p(\texttt{gray}) = \tfrac{1}{4}, \quad p(\texttt{yellow}) = \tfrac{1}{8}, \quad p(\texttt{green}) = \tfrac{1}{8}.\]Suppose you learn that the marble drawn is not blue. That single fact rules out half of the probability mass, leaving a distribution renormalized over the remaining three colors. Learning a fact that was less likely to be true rules out more probability mass, and hence carries more information — this is precisely why rare events are more informative than common ones
We can make this quantitative. If ruling out half the probability mass corresponds to one unit of information, then the information content of an outcome \(x\) with probability \(p(x)\) is
\[I(x) = \log_2 \frac{1}{p(x)} \, ,\]measured in bits. An outcome with probability \(\tfrac12\) carries exactly 1 bit; an outcome with probability \(\tfrac18\) carries 3 bits, because learning it happened is equivalent to eliminating three successive halvings of the probability mass. The entropy of a random variable \(X\) is the probability-weighted average information content of its outcomes:
\[H(X) = \sum_{x \in \mathcal{X}} p(x) \log_2 \frac{1}{p(x)} \, .\]Entropy is the expected number of bits of surprise you get, on average, from observing \(X\). It is maximized when probability is spread as evenly as possible across outcomes, and it is zero exactly when the outcome is certain in advance (\(p(x) = 1\) for some \(x\))
Before going further, it helps to have a way of picturing distributions over two variables at once
When the variables interact, some cells of the grid swell with extra probability (it’s more likely to wear a coat when it’s raining) at the expense of others. The fundamental identity connecting joint and conditional probability, \(p(x,y) = p(x)\cdot p(y\mid x)\), lets us factor any joint distribution one variable at a time — and it is the seed from which joint entropy and conditional entropy (Part 2) will grow.
Entropy has a second, equally important interpretation: it is the shortest possible average length, in bits, of a code for a sequence of outcomes from a distribution
Suppose we want to communicate a sequence of words drawn from a small vocabulary — say, an imaginary friend who only ever says “dog,” “cat,” “fish,” or “bird,” with probabilities \(\tfrac12, \tfrac14, \tfrac18, \tfrac18\)
If every codeword has the same length, decoding is trivial — split the bitstream every \(k\) bits. But we’d like common words (like “dog”) to get short codewords, so the average message is short. This creates a subtlety: with variable-length codewords, how does the receiver know where one codeword ends and the next begins?
The answer is the prefix property: no codeword may be a prefix of another. A code with this property is called a prefix code, and it is always uniquely decodable — you can read a bitstream left to right and unambiguously identify each codeword as soon as its pattern is complete.
The prefix property has a cost. Choosing the codeword 01 forbids every longer codeword that starts with 01 — 010, 0110101, and so on — because they would be ambiguous with it. A quarter of all possible bitstrings begin with 01, so choosing it as a codeword “spends” a quarter of the total space of possible codewords. In general, a codeword of length \(L\) costs \(2^{-L}\) of the total space
The following binary tree shows one valid prefix code for the four-word vocabulary: 0 for dog, 10 for cat, 110 for fish, 111 for bird. Every codeword is a leaf, and no codeword is an ancestor of another — that’s the prefix property, drawn as a tree.
Think of building a code as spending a fixed budget: buying a codeword of length \(L\) costs \(2^{-L}\) of the total space of codewords, and using it costs us \(p(x) \cdot L\) extra bits in our average message length, since it’s used a \(p(x)\) fraction of the time. The natural strategy — spend a fraction \(p(x)\) of the budget on the codeword for \(x\) — turns out to be optimal, not merely reasonable
If we spend \(p(x)\) of the budget on the codeword for \(x\), and a codeword of length \(L\) costs \(2^{-L}\), then solving \(2^{-L} = p(x)\) for \(L\) gives the optimal codeword length:
\[L(x) = \log_2 \frac{1}{p(x)} \, .\]This is exactly the information content of \(x\) from the previous section — no coincidence. The optimal code assigns each outcome a codeword whose length equals its information content in bits.
The average codeword length under the optimal code is, by definition, the entropy:
\[H(X) = \sum_{x} p(x)\, L(x) = \sum_{x} p(x) \log_2 \frac{1}{p(x)} \, .\]For our dog/cat/fish/bird example this works out to \(\tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75\) bits — and no code, however clever, can do better on average
One wrinkle: optimal codeword lengths are frequently fractional (e.g. \(\log_2 \tfrac{1}{0.71} \approx 0.49\) bits), which is meaningless for a single codeword — you can’t send half a bit. But if you encode several draws jointly, ideal lengths add, and the rounding overhead per event shrinks toward zero as the number of jointly-encoded events grows
Entropy is maximized when probability is spread as evenly as possible over the outcome space \(\mathcal{X}\). In that case,
\[H_{\max}(\mathcal{X}) = \log_2 |\mathcal{X}| \, ,\]| where $$ | \mathcal{X} | $$ is the number of possible outcomes |
Redundancy quantifies how much shorter our messages become because the distribution is not uniform — the more concentrated the probability mass, the larger the redundancy, and the more compressible the source. A deterministic variable (\(p(x)=1\) for one outcome) has zero entropy and maximum possible redundancy; a uniform variable has zero redundancy, because there is nothing left to exploit.
Entropy governs a length-\(N\) i.i.d. sequence too: the total information content of \(N\) independent draws is \(N \cdot H(X)\) on average. But individual sequences vary enormously in actual information content — an all-blue sequence (the single most probable outcome) can be far cheaper to encode than a “typical” one, and far more expensive than a maximally rare one
A typical sequence is one whose information content is close to this average: for small \(\epsilon > 0\),
\[H(X) - \epsilon \ \le\ -\frac{1}{N}\log p(x_1, \ldots, x_N) \ \le\ H(X) + \epsilon \, .\]As \(N \to \infty\), the asymptotic equipartition property (AEP) kicks in: almost all of the probability mass concentrates onto the typical set, regardless of how small \(\epsilon\) is, and every typical sequence has probability \(\approx 2^{-NH(X)}\). Since probabilities sum to 1, there must be \(\approx 2^{NH(X)}\) typical sequences. This is precisely what makes lossless compression at rate \(H(X)\) achievable: a scheme that assigns a unique length-\(NH(X)\) binary string to every typical sequence, and ignores the (vanishingly probable) rest, is lossless in the limit — and no scheme can reliably do better
Now suppose two people communicate using the same words but different frequencies. Bob mostly talks about dogs; his wife Alice mostly talks about cats. Bob’s code — optimized for his own distribution \(p\) — is suboptimal when Alice uses it to encode her distribution \(q\), because it assigns short codewords to words Alice rarely uses
The average message length when encoding events from \(q\) using the code optimized for \(p\) is the cross-entropy:
\[H_p(q) = \sum_x q(x) \log_2 \frac{1}{p(x)} \, .\]Cross-entropy is not symmetric — \(H_p(q) \neq H_q(p)\) in general — and this asymmetry is not a technicality; it is the whole point. \(H_q(p)\) is large exactly when there’s an outcome common under \(p\) but rare under \(q\): that outcome gets an unnecessarily long codeword, which hurts badly because \(p\) uses it often. Whether the “large” direction is \(H_p(q)\) or \(H_q(p)\) depends on which distribution is doing the frequent using and which one built the code.
Cross-entropy is always at least the entropy of the distribution being encoded, \(H_p(q) \ge H(q)\), with equality iff \(p = q\). This makes it a natural, if asymmetric, measure of how different two distributions are — and it is why cross-entropy is the workhorse loss function for classification in machine learning: minimizing \(H_p(q)\) where \(q\) is the true label distribution and \(p\) is the model’s predicted distribution directly penalizes the model for being confidently wrong
The excess length caused by using the wrong code — the gap between cross-entropy and entropy — is the Kullback–Leibler (KL) divergence:
\[D_q(p) = H_q(p) - H(p) = \sum_x p(x) \log_2 \frac{p(x)}{q(x)} \, .\]KL divergence is zero exactly when \(p = q\) and grows as the two distributions diverge, which is why it behaves like a “distance” between distributions (though it is not symmetric and does not satisfy the triangle inequality, so it is not a metric in the strict sense)
We now have the vocabulary for a single random variable: information content, entropy, redundancy, cross-entropy, and KL divergence. Part 2 extends all of this to two or more variables — joint entropy, conditional entropy, and mutual information — and finishes with the entropy rate of a stochastic process, the natural generalization of entropy to sequences that aren’t independent and identically distributed.
For a fuller treatment than either source attempts, Shannon’s original paper remains remarkably readable
Here are some more articles you might like to read next: