Extending entropy to two or more variables — joint entropy, conditional entropy, mutual information, fractional bits, and the entropy rate of a stochastic process.
Part 1 built up the vocabulary for a single random variable: the information content \(\log_2 \frac{1}{p(x)}\) of an outcome, entropy \(H(X)\) as its probability-weighted average, redundancy, cross-entropy, and KL divergence. All of it concerned one variable at a time. Most interesting questions, though, involve relationships between variables: how much does today’s weather tell us about tomorrow’s? How much do two random variables share? This post extends entropy to two (or more) variables, following the same two sources as Part 1 — Olah’s essay
The simplest extension is to ask how much information is needed to communicate the outcome of two variables together. If we flatten the joint distribution \(p(x,y)\) over the product space \(\mathcal{X} \times \mathcal{Y}\) and treat it as a distribution over a single combined variable, entropy applies unchanged:
\[H(X,Y) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y) \log_2 \frac{1}{p(x,y)} \, .\]This is the joint entropy — the average number of bits needed to communicate both \(X\) and \(Y\) using a code built for their joint distribution
Suppose you already know \(Y\). How much more information do you need, on average, to also learn \(X\)? This is the conditional entropy \(H(X \mid Y)\): the uncertainty remaining in \(X\) once \(Y\) is known.
Start at a single point: if we already know \(Y = y\), the information needed to learn \(X\) is the entropy of the conditional distribution \(p(x \mid y)\),
\[H(X \mid y) = \sum_{x \in \mathcal{X}} p(x \mid y) \log_2 \frac{1}{p(x \mid y)} \, .\]Averaging over all possible values of \(y\), weighted by how likely each is, gives the conditional entropy in its usual form:
\[H(X \mid Y) = \sum_{y \in \mathcal{Y}} p(y) \sum_{x \in \mathcal{X}} p(x \mid y) \log_2 \frac{1}{p(x \mid y)} = \sum_{x,y} p(x,y) \log_2 \frac{1}{p(x \mid y)} \, .\]A concrete example makes this tangible. Pinkard and Waller consider drawing objects with both a color (\(X\)) and a shape (\(Y\)) at random
Conditional entropy can never exceed the unconditional entropy: \(H(X \mid Y) \le H(X)\), with equality iff \(X\) and \(Y\) are independent. Combined with joint entropy, this gives a clean chain of inequalities,
\[H(X,Y) \ge H(X) \ge H(X \mid Y) \ge 0 \, ,\]and an identity that will anchor the next section: \(H(X,Y) = H(Y) + H(X \mid Y)\) — the information in both variables is the information in one, plus whatever’s left in the other after conditioning on it.
Joint entropy measures the total information in \(X\) and \(Y\) together; conditional entropy measures what’s left in one after learning the other. The information they have in common — how much observing \(Y\) reduces our uncertainty about \(X\) — is the mutual information:
\[I(X;Y) = H(X) + H(Y) - H(X,Y) \, .\]The intuition is a counting argument: \(H(X) + H(Y)\) counts the shared information twice (once as part of \(X\), once as part of \(Y\)), while \(H(X,Y)\) counts it once. The difference is exactly one copy of what’s shared
Just as entropy has a pointwise predecessor (information content), mutual information has a pointwise version. For a specific pair of outcomes \((x,y)\), the pointwise mutual information is
\[\log_2 \frac{p(x,y)}{p(x)p(y)} = \log_2\frac{1}{p(x)} - \log_2\frac{1}{p(x\mid y)} \, ,\]the surprise of \(x\) on its own, minus the (typically smaller) surprise of \(x\) once \(y\) is already known
This expression is worth pausing on, because it is exactly the KL divergence from Part 1 — specifically, the KL divergence between the true joint distribution \(p(x,y)\) and the “naive” product-of-marginals distribution \(p(x)p(y)\) that we’d get by (incorrectly) assuming independence
Joint entropy, conditional entropy, and mutual information are not independent concepts — they are different ways of partitioning the same total information, and it helps to see all four quantities laid out together, with area representing bits.
Reading the diagram: \(H(X,Y) = H(X) + H(Y\mid X) = H(Y) + H(X \mid Y)\), and the mutual information is exactly the amount by which \(H(X)\) and \(H(Y)\) overlap. All three of the following are algebraically equivalent expressions for mutual information, and each has its own reading:
\[I(X;Y) = H(X) - H(X\mid Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X,Y) \, .\]The first says mutual information is how much \(Y\) shrinks our uncertainty about \(X\); the second is the same statement with the roles reversed (consistent with symmetry); the third is the counting argument from before.
If mutual information measures what two variables share, its complement measures what they don’t: the variation of information,
\[V(X,Y) = H(X,Y) - I(X;Y) \, .\]Variation of information is a genuine metric — symmetric, non-negative, and satisfying the triangle inequality — on the space of jointly distributed variables
Part 1 flagged something odd: optimal codeword lengths are frequently fractional, which seems meaningless for a single message. Consider a distribution with two outcomes, \(a\) (probability 71%) and \(b\) (probability 29%). The ideal codeword lengths are \(\log_2\frac{1}{0.71}\approx 0.49\) bits for \(a\) and \(\log_2\frac{1}{0.29}\approx 1.79\) bits for \(b\) — neither a whole number
If we must send a single symbol, we’re forced to round, giving an average length of 1 bit (using codewords 0 and 1) rather than the entropy \(H \approx 0.87\) bits. But if we encode two draws jointly, something better happens. The four two-symbol outcomes have probabilities \(p(aa) = 0.504\), \(p(ab) = p(ba) = 0.206\), and \(p(bb) = 0.084\); assigning shorter codewords to the more probable pairs and rounding gives an average of about 1.8 bits for two symbols — 0.9 bits per symbol, already better than sending them independently (2 bits for two symbols)
(In practice, Huffman coding — essentially the scheme sketched here — needs this kind of symbol-grouping to approach the entropy limit gracefully; arithmetic coding handles fractional bits natively and is asymptotically optimal without grouping
Everything so far has assumed a sequence of independent and identically distributed random variables. Real sequences — text, weather, stock prices — are rarely independent: today’s value constrains tomorrow’s. An ordered sequence of random variables \(\mathbf{X} = X_1, X_2, \ldots\), without an independence assumption, is called a stochastic process
In the i.i.d. case, entropy is additive: \(H(X_1, \ldots, X_N) = N \cdot H(X)\), so the entropy rate — entropy per symbol — is just \(H(X)\). For a general stochastic process, we need a definition that doesn’t assume this factorization. There are two natural candidates.
The first treats entropy rate as the average uncertainty per draw, over all \(N\) draws jointly:
\[\frac{1}{N} H(X_1, X_2, \ldots, X_N) \, .\]The second treats it as the uncertainty about the next draw, given everything before it:
\[H(X_{N+1} \mid X_N, X_{N-1}, \ldots, X_1) \, .\]For a stationary process — one whose joint distribution is shift-invariant, \(p_{X_1,\ldots,X_N} = p_{X_{1+k},\ldots,X_{N+k}}\) for any \(k\) — both definitions converge to the same value as \(N \to \infty\)
Consider a “magical urn” version of our marble example: the first draw is uniform over four colors (\(H(X_1) = 2\) bits), but every draw after that is more likely to repeat the previous color — \(p(\text{same color}) = \tfrac58\), and \(\tfrac18\) for each of the other three colors, independent of \(N\) (a first-order Markov chain). Because each color is still marginally uniform, \(H(X_k) = 2\) bits for every \(k\) in isolation — but the joint entropy of consecutive draws is less than the sum of their individual entropies, because knowing \(X_N\) substantially reduces uncertainty about \(X_{N+1}\)
constant for every \(N \ge 1\), well below the unconditional 2 bits of the first draw. The two definitions of entropy rate — averaging the joint entropy, and the conditional entropy of the next draw given the past — both converge to this same \(\approx 1.549\) bits as \(N\) grows, exactly as stationarity predicts:
Moving from an i.i.d. sequence to a general stochastic process also forces us to revisit redundancy from Part 1, since it can no longer be defined variable-by-variable. The general definition accounts for the joint entropy against the maximum entropy of the full product space
In the marble-urn example, every individual draw is marginally uniform, so \(H(X_k) = H_{\max}(\mathcal{X})\) for each \(k\) in isolation — there is no redundancy variable-by-variable. But the joint distribution is far from the maximum-entropy (independent, uniform) joint distribution, because the outcome of one draw is highly informative about its neighbor. This is exactly why we can guess the next color far better than chance, given the previous one: the redundancy lives in the higher-order dependencies between draws, not in any single draw’s marginal distribution.
We’ve now built, from first principles, the core quantities of information theory: information content and entropy (Part 1); cross-entropy and KL divergence (Part 1); joint entropy, conditional entropy, and mutual information (this post); and the entropy rate of a stochastic process (this post). Two threads run through all of it. First, every one of these quantities has a coding interpretation — the expected length of some code under some scenario — which is what makes entropy feel inevitable rather than an arbitrary formula. Second, KL divergence quietly underlies more than it first appears to: cross-entropy is entropy plus a KL term, and mutual information is a KL divergence, between a joint distribution and the product of its marginals.
This is deliberately not the whole of information theory. Both source texts continue well beyond what we’ve covered here: Pinkard and Waller extend these ideas to continuous random variables and differential entropy, and go on to channel capacity and lossy compression — the second of the “two key problems” their tutorial sets out to address
Here are some more articles you might like to read next: