Entropy

Shannon's measure of the uncertainty of a random variable, with every property proved. Surprisal and its average, bits and nats, the bounds 0 and the logarithm of the alphabet size, joint and conditional entropy, the chain rule, why conditioning lowers entropy only on average, entropy of a function and the grouping identity, concavity, and a full proof of Shannon's theorem that three requirements leave no other formula. The running example is the character sequence of the Tiny Shakespeare text, where a plug-in estimate is also shown failing on shuffled text. Worked problems on Shannon's three-outcome decomposition, the binary entropy function, the geometric distribution and three consecutive characters.

The Tiny Shakespeare text that the site's language model walkthrough trains on is a file of 1,115,394 characters drawn from an alphabet of 65: the letters in both cases, the space, the newline and eleven other symbols. A model that knows nothing would treat the 65 as equally likely. A model that knows only how often each character occurs can do better, because a space is far more likely than a Z. How much uncertainty about the next character is left once the frequencies are known? The answer is 4.78 bits, against 6.02 bits for 65 equally likely characters, and the quantity that produces both numbers is entropy.

The entropy of a random variable $X$ with possible values $x$ and probabilities $p(x)$ is

$$H(X) = -\sum_{x} p(x)\log p(x),$$

the average of $-\log p(x)$ over the outcomes. It depends only on the probabilities, not on what the outcomes are, so it is also written $H(p)$. Shannon (1948, Section 6) introduced it as a measure of "how much 'choice' is involved in the selection of the event or of how uncertain we are of the outcome".

First we build the formula from the surprise of a single outcome and fix the two units, bits and nats. Then we prove its bounds. Next come joint and conditional entropy, the chain rule that connects them, and the theorem that conditioning lowers entropy on average. Then we treat functions of a variable, grouping and concavity, and prove Shannon's theorem that three requirements force this formula. Finally an experiment shows where estimating entropy from counts goes wrong. The article assumes expectation for discrete random variables (Expectation, Variance and Covariance).

This article is the home of entropy on this site. The pages that use it, among them Classification Trees, feature selection, evaluating clusterings and the bigram language model, rely on the definitions and properties proved here. The rest of the Information Theory unit builds on it.

Notation and scope

Random variables are written with capitals, $X$, $Y$, $Z$. Each takes values in a finite set, its alphabet, written $\mathcal{X}$ for $X$, with $|\mathcal{X}|$ elements. The probability mass function of $X$ is $p(x) = P(X = x)$. For two variables, $p(x, y) = P(X = x, Y = y)$ is the joint mass function, and $p(y \mid x) = p(x, y)/p(x)$ is the conditional one, defined where $p(x) > 0$. The argument tells which function is meant, so $p(x)$ and $p(y)$ are different functions. The support of $p$ is the set of outcomes with $p(x) > 0$.

Two conventions are needed. A term with $p(x) = 0$ contributes nothing to a sum: $0 \log 0$ is taken as 0, which is the limit of $x \log x$ as $x$ decreases to 0 (shown in the proof of the uniqueness theorem below). And $\log$ written without a base stands for a logarithm to any fixed base greater than 1. It is used only in statements that hold in every base.

Alphabets are finite throughout, except in one worked problem. On a countably infinite alphabet the same sum defines the entropy, but it can be infinite (MacKay, 2003, Section 2.4, notes this), and the proofs below that sum over the alphabet would need care about convergence. Variables with densities are the subject of Differential Entropy and the Gaussian, where several of the properties proved here fail.

Surprise and its average

Here is the idea in plain words. Seeing a likely outcome tells us little, and seeing an unlikely one tells us much. We put a number on the surprise of each outcome, and entropy is the surprise we should expect before looking.

The surprisal of an outcome $x$ is $-\log p(x) = \log\frac{1}{p(x)}$. MacKay (2003, Section 2.4) calls it the Shannon information content of the outcome. Three properties make the logarithm the right function of the probability.

  • It is 0 for a certain outcome, since $\log 1 = 0$, and positive otherwise.
  • It grows as the probability falls.
  • It adds over independent outcomes. If $X$ and $Y$ are independent, $p(x, y) = p(x)\,p(y)$, so $-\log p(x, y) = -\log p(x) - \log p(y)$. Two independent surprises are worth their sum.

With logarithms to base 2 the unit is the bit. An outcome of probability $\tfrac12$ has a surprisal of 1 bit, and one of probability $\tfrac18$ has 3 bits, as much as three fair coin flips.

The table gives the surprisal of six characters of the text. Probabilities are the shares of the 1,115,394 characters.

Character Count Share (%) Surprisal (bits)
space 169,892 15.23 2.71
e 94,611 8.48 3.56
t 67,009 6.01 4.06
q 609 0.05 10.84
Z 198 0.02 12.46
$ 1 0.00 20.09

The dollar sign occurs once in the file. Its surprisal is $\log_2 1{,}115{,}394 = 20.09$ bits, the largest any character of this text can have.

Entropy is the expected value of the surprisal,

$$H(X) = E\big[-\log p(X)\big] = \sum_{x} p(x)\,\log\frac{1}{p(x)}.$$

For the character drawn from the text, each of the 65 surprisals is weighted by its share, and the sum is $H(X) = 4.7794$ bits. The space contributes $0.1523 \times 2.71 = 0.41$ bits of that, more than any other character. The dollar sign contributes $20.09/1{,}115{,}394$, about 0.00002 bits. A rare outcome is very surprising, but it is so seldom seen that it adds little to the average.

Example (what the entropy describes here). The 4.7794 bits are a property of the list of 65 shares, computed exactly from the counts. They are the entropy of the experiment "pick one position of this file at random and read the character there". They are not an estimate of the entropy of English, of Shakespeare, or of the next character given what came before. The last of these is a conditional entropy, taken up below, and it is much smaller.

Bits and nats

Changing the base of the logarithm multiplies every surprisal, and so the entropy, by a constant: $\log_b x = \ln x / \ln b$. The base is a choice of unit. Shannon (1948, Introduction) put it this way: "The choice of a logarithmic base corresponds to the choice of a unit for measuring information." He attributes the word bits for the base-2 unit to J. W. Tukey. With natural logarithms the unit is the nat. The two convert by

$$H_{\text{bits}} = \frac{H_{\text{nats}}}{\ln 2}, \qquad 1 \text{ nat} = 1.4427 \text{ bits}, \qquad 1 \text{ bit} = 0.6931 \text{ nats}.$$

The character entropy of the text is 4.7794 bits, or $4.7794 \times 0.6931 = 3.3128$ nats. The ceiling for 65 characters, met in the next section, is $\log_2 65 = 6.0224$ bits or $\ln 65 = 4.1744$ nats.

This unit follows the practice of the pages it serves, and every number carries its unit.

The bounds: zero and the logarithm of the alphabet size

How small and how large can entropy be? It is smallest, zero, when the outcome is certain, and largest when all outcomes are equally likely.

Theorem (bounds). For a random variable $X$ on an alphabet of $n$ elements, $0 \le H(X) \le \log n$. The lower bound is attained exactly when one outcome has probability 1. The upper bound is attained exactly when $p(x) = 1/n$ for every $x$.

The lower bound needs nothing beyond the definition. The upper bound is the first of three results in this article that rest on one inequality, which belongs to the next article and is borrowed here.

Gibbs' inequality (borrowed). For two mass functions $p$ and $q$ on the same alphabet, with $q(x) > 0$ wherever $p(x) > 0$,

$$D(p \,\|\, q) = \sum_{x} p(x)\log\frac{p(x)}{q(x)} \ge 0,$$

with equality exactly when $p = q$. The sum runs over the support of $p$. The quantity $D(p \,\|\, q)$ is the Kullback–Leibler divergence. Cross-Entropy and Kullback–Leibler Divergence proves the inequality in its section "Gibbs' inequality". That proof uses the inequality $\ln x \le x - 1$ and nothing from this article, so borrowing it creates no circle.

Proof of the bounds. Lower bound. Each term $p(x)\log\frac{1}{p(x)}$ is zero when $p(x)$ is 0 or 1, and positive when $0 < p(x) < 1$, because then $\frac{1}{p(x)} > 1$. So $H(X) \ge 0$, with equality exactly when every $p(x)$ is 0 or 1. Since the probabilities sum to 1, that means exactly one of them is 1.

Upper bound. Let $u(x) = 1/n$ be the uniform mass function. Then

$$D(p \,\|\, u) = \sum_{x} p(x)\log\big(n\,p(x)\big) = \log n\sum_x p(x) + \sum_x p(x)\log p(x) = \log n - H(X).$$

By Gibbs' inequality this is at least 0, and it is 0 exactly when $p = u$. $\square$

For the text, $n = 65$ and $\log_2 65 = 6.0224$ bits. The character entropy of 4.7794 bits is 0.794 of that ceiling. The difference, $6.0224 - 4.7794 = 1.2430$ bits, is the divergence of the character distribution from the uniform one, by the identity in the proof.

The upper bound gives entropy a second reading. A uniform distribution on $m$ outcomes has entropy $\log_2 m$ bits, so $2^{H}$ is the number of equally likely outcomes that would be as uncertain as $X$. For the text $2^{4.7794} = 27.46$. Guessing a character from its frequency is as hard as guessing among about 27 equally likely characters, not 65. The number $2^H$ is the perplexity of Perplexity and Source Coding, which also proves the coding interpretation: no uniquely decodable code can record the outcomes of $X$ in fewer than $H(X)$ binary digits each on average, and some code needs less than one digit more.

Joint and conditional entropy

A language model does not predict a character from nothing. It sees what came before. Describing that needs the entropy of two variables together and of one given the other.

The joint entropy of $X$ and $Y$ is the entropy of the pair $(X, Y)$ regarded as one random variable:

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

Nothing new is defined here. A pair is a random variable on the alphabet of pairs, and the bounds above apply to it.

The conditional entropy of $Y$ given $X$ is built in two steps. For a fixed value $x$ with $p(x) > 0$, the conditional mass function $p(y \mid x)$ is a distribution on the alphabet of $Y$, and it has an entropy,

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

The conditional entropy is the average of these over $x$:

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

The second form follows from $p(x)\,p(y \mid x) = p(x, y)$. Shannon (1948, Section 6) defines it the same way, as "the average of the entropy of $y$ for each value of $x$, weighted according to the probability of getting that particular $x$". Two facts are immediate. Each $H(Y \mid X = x)$ is an entropy, so $H(Y \mid X) \ge 0$. And $H(Y \mid X) = 0$ exactly when every $H(Y \mid X = x)$ is 0, that is, when each $x$ with $p(x) > 0$ leaves only one possible $y$: when $Y$ is a function of $X$.

The running example. Let $(X_1, X_2)$ be a pair of adjacent characters, at a position chosen at random among the 1,115,393 positions that have a successor. Of the $65^2 = 4{,}225$ possible pairs, 1,403 occur. The conditional entropy $H(X_2 \mid X_1)$ averages, over the first character, the entropy of what follows it. The table shows some of the 65 terms.

First character Times Entropy of the next character (bits)
space 169,892 4.528
newline 39,999 4.390
e 94,611 3.801
. 7,885 0.674
: 10,316 0.642
q 609 0.000

After a space a new word begins, and almost anything can follow. After a colon the next character is nearly always a newline, because colons end the speaker names. After q the next character is u all 609 times, so that term is exactly zero. Weighted by how often each first character occurs, the 65 terms average to $H(X_2 \mid X_1) = 3.5383$ bits, or 2.4526 nats. The next article shows that this is the lowest loss any model that sees only the previous character can reach on this text.

The chain rule

How are the three entropies of a pair related? The uncertainty of the pair is the uncertainty of the first variable plus what remains of the second once the first is known.

Theorem (chain rule). $H(X, Y) = H(X) + H(Y \mid X)$.

Proof. For every pair with $p(x, y) > 0$, $p(x, y) = p(x)\,p(y \mid x)$, so $\log p(x, y) = \log p(x) + \log p(y \mid x)$. Multiply by $-p(x, y)$ and sum over the pairs:

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

In the first sum, $\log p(x)$ does not depend on $y$, and $\sum_y p(x, y) = p(x)$, so the sum is $-\sum_x p(x)\log p(x) = H(X)$. The second sum is $H(Y \mid X)$ by definition. $\square$

The proof is the additivity of surprisal, averaged: the surprisal of a pair is the surprisal of $x$ plus the surprisal of $y$ once $x$ is known. Exchanging the roles of the variables gives $H(X, Y) = H(Y) + H(X \mid Y)$ as well.

For the adjacent characters, the first character has entropy $H(X_1) = 4.7794$ bits, and $4.7794 + 3.5383 = 8.3177$ bits. The script computes the joint entropy directly from the 1,403 pair counts and finds $H(X_1, X_2) = 8.3177$ bits.

Corollary (chain rule for several variables). For random variables $X_1, \dots, X_k$,

$$H(X_1, \dots, X_k) = H(X_1) + H(X_2 \mid X_1) + H(X_3 \mid X_1, X_2) + \cdots + H(X_k \mid X_1, \dots, X_{k-1}).$$

Proof. By induction on $k$. For $k = 1$ there is nothing to prove. Suppose the formula holds for $k - 1$ variables. Apply the chain rule to the pair formed by $X = (X_1, \dots, X_{k-1})$ and $Y = X_k$: $H(X_1, \dots, X_k) = H(X_1, \dots, X_{k-1}) + H(X_k \mid X_1, \dots, X_{k-1})$. Replacing the first term by the formula for $k - 1$ variables gives the formula for $k$. $\square$

Conditioning lowers entropy, on average

The conditional entropy of the second character, 3.5383 bits, is below its unconditional entropy. That is a theorem, not an accident of this text.

Theorem (conditioning reduces entropy). $H(Y \mid X) \le H(Y)$, with equality exactly when $X$ and $Y$ are independent.

The idea: the difference $H(Y) - H(Y \mid X)$ can be written as a divergence between two distributions on pairs, the true joint distribution and the one that would hold under independence. Gibbs' inequality then says the difference is not negative.

Proof. Write $H(Y) = -\sum_y p(y)\log p(y) = -\sum_{x, y} p(x, y)\log p(y)$, using $\sum_x p(x, y) = p(y)$. Then

$$H(Y) - H(Y \mid X) = \sum_{x, y} p(x, y)\big[\log p(y \mid x) - \log p(y)\big] = \sum_{x, y} p(x, y)\log\frac{p(x, y)}{p(x)\,p(y)}.$$

The last expression is $D(p \,\|\, q)$ for the two mass functions on pairs $p(x, y)$ and $q(x, y) = p(x)\,p(y)$. The second is a mass function, since $\sum_{x,y} p(x)p(y) = 1$, and it is positive wherever $p(x, y)$ is, since $p(x) \ge p(x, y)$ and $p(y) \ge p(x, y)$. By Gibbs' inequality the divergence is at least 0, and it is 0 exactly when $p(x, y) = p(x)\,p(y)$ for all pairs, which is independence. $\square$

The difference $H(Y) - H(Y \mid X)$ is the mutual information of $X$ and $Y$, the subject of Mutual Information. For adjacent characters it is $4.7793 - 3.5383 = 1.2410$ bits. (The second character has entropy 4.7793 bits, not 4.7794, because the pairs leave out the first character of the file as a second character, as they leave out the last one as a first.)

Corollary (subadditivity). $H(X, Y) \le H(X) + H(Y)$, with equality exactly when $X$ and $Y$ are independent. More generally $H(X_1, \dots, X_k) \le H(X_1) + \cdots + H(X_k)$, with equality exactly when $X_1, \dots, X_k$ are mutually independent. In particular the entropy of independent variables is the sum of their entropies.

Proof. By the chain rule and the theorem, $H(X, Y) = H(X) + H(Y \mid X) \le H(X) + H(Y)$, with the same condition for equality. For $k$ variables, each term $H(X_j \mid X_1, \dots, X_{j-1})$ of the chain rule is at most $H(X_j)$, by the theorem applied to $Y = X_j$ and $X = (X_1, \dots, X_{j-1})$. Equality in the sum requires equality in every term, that is, each $X_j$ independent of the vector $(X_1, \dots, X_{j-1})$. Then $p(x_1, \dots, x_j) = p(x_1, \dots, x_{j-1})\,p(x_j)$ for every $j$, and multiplying these out gives $p(x_1, \dots, x_k) = p(x_1)\cdots p(x_k)$, which is mutual independence. Conversely, mutual independence makes each $X_j$ independent of the variables before it. $\square$

Shannon (1948, Section 6) lists this as his third property of $H$: "The uncertainty of a joint event is less than or equal to the sum of the individual uncertainties."

Example (one observation can raise the entropy). The theorem might be read as saying that learning something never makes us less certain. It says so only on average. In the Reuters-21578 training set used by feature selection, 433 of 7,769 stories are about grain, so the class has entropy 0.3103 bits. Among the 243 stories that contain the term wheat, 227 are about grain, and the entropy of the class within them is 0.3502 bits, which is higher. Learning that a story contains wheat moves the class from "very probably not grain" to "probably grain, but not certainly", a less certain state. Among the 7,526 stories without the term the entropy is 0.1810 bits, and the average over both groups, weighted by their sizes, is 0.1863 bits, below 0.3103 as the theorem requires. (These figures are computed in Problem 3 of that article.) In the Shakespeare text no single preceding character raises the entropy of the next one: the largest of the 65 conditional entropies is the 4.528 bits after a space, below 4.7793. That is an observation about this text, not a theorem.

Longer contexts. The chain rule for several variables splits the entropy of a block of $k$ consecutive characters into increments, the $k$th being the entropy of a character given the $k - 1$ before it. Computed from the counts of all blocks of each length in the text:

$k$ Entropy of a block of $k$ (bits) Increment: the $k$th character given the $k-1$ before it (bits)
1 4.7794 4.7794
2 8.3177 3.5383
3 11.0697 2.7520
4 13.2307 2.1610
5 14.9979 1.7672

Each increment is smaller than the one before. All five rows are exact for this file. How much the later rows say about the predictability of the text, as opposed to the size of the file, is examined by the experiment near the end of this article.

Functions and grouping

What happens to entropy when outcomes are merged? Folding capitals into lowercase letters turns the 65 characters into 39. The folded character is a function of the original one, and a function cannot be more uncertain than its argument.

Theorem (entropy of a function). For any function $g$ on the alphabet of $X$, $H(g(X)) \le H(X)$, and more precisely

$$H(X) = H(g(X)) + H(X \mid g(X)).$$

Equality $H(g(X)) = H(X)$ holds exactly when $g$ is one-to-one on the support of $X$.

Proof. Apply the chain rule to the pair $(X, g(X))$ in both orders:

$$H(X, g(X)) = H(X) + H(g(X) \mid X) = H(g(X)) + H(X \mid g(X)).$$

Since $g(X)$ is a function of $X$, $H(g(X) \mid X) = 0$, by the remark after the definition of conditional entropy. That leaves the displayed identity. The term $H(X \mid g(X))$ is at least 0, and it is 0 exactly when $X$ is a function of $g(X)$, that is, when no two outcomes of positive probability share a value of $g$. $\square$

For the text, the folded character has entropy $H(g(X)) = 4.4219$ bits. The remainder, $H(X \mid g(X)) = 4.7794 - 4.4219 = 0.3574$ bits (computed from unrounded values), is the average uncertainty about the case of a character once its folded form is known. The script computes that remainder from its own definition, letter by letter, and the two agree.

Written out for a function that sorts outcomes into groups, the theorem is the property Shannon used to single out his formula.

Corollary (grouping). Let the alphabet be divided into groups $G_1, \dots, G_m$, let $w_j = \sum_{x \in G_j} p(x)$ be the probability of group $j$, and suppose every $w_j > 0$. Then

$$H(p) = H(w_1, \dots, w_m) + \sum_{j=1}^{m} w_j\,H\!\left(\frac{p(x)}{w_j} : x \in G_j\right),$$

where the last $H$ is the entropy of the distribution within group $j$.

Proof. Let $g(x)$ be the index of the group containing $x$. Then $g(X)$ has mass function $(w_1, \dots, w_m)$, and given $g(X) = j$ the conditional mass function of $X$ is $p(x)/w_j$ on $G_j$. The identity $H(X) = H(g(X)) + H(X \mid g(X))$ is the statement. $\square$

In words: choosing an outcome is as uncertain as first choosing its group and then choosing within the group, the second choice counted with the probability that it has to be made. On the text, with four groups:

Group Characters Count Share $w_j$ Entropy within (bits) Product
Lowercase letters 26 762,324 0.6835 4.1705 2.8504
Space and newline 2 209,892 0.1882 0.7027 0.1322
Capital letters 26 88,754 0.0796 4.2664 0.3395
Other symbols 11 54,424 0.0488 2.5692 0.1254

The four shares have entropy 1.3319 bits. The products sum to 3.4474 bits (3.4475 if the rounded entries of the table are added). Together they make 4.7794 bits, the entropy of a character. Of the 4.78 bits, 1.33 settle what kind of character it is and 3.45 settle which one of that kind.

Concavity

Suppose a distribution is a blend of two others. Is the blend more or less uncertain than its parts? It is at least as uncertain as their average, because not knowing which part an outcome came from adds uncertainty.

Theorem (concavity). For mass functions $p$ and $q$ on the same alphabet and $0 \le \lambda \le 1$, let $m = \lambda p + (1 - \lambda)q$. Then

$$H(m) \ge \lambda H(p) + (1 - \lambda)H(q),$$

and for $0 < \lambda < 1$ equality holds exactly when $p = q$.

Proof. For $\lambda = 0$ or $1$ both sides are equal. Let $0 < \lambda < 1$. Then $m(x) \ge \lambda p(x)$ and $m(x) \ge (1-\lambda) q(x)$, so $m$ is positive wherever $p$ or $q$ is, and the divergences $D(p \,\|\, m)$ and $D(q \,\|\, m)$ are defined. Expanding them,

$$\lambda D(p \,\|\, m) + (1-\lambda) D(q \,\|\, m) = \lambda\sum_x p(x)\log p(x) + (1-\lambda)\sum_x q(x)\log q(x) - \sum_x \big[\lambda p(x) + (1-\lambda)q(x)\big]\log m(x).$$

The first two sums are $-\lambda H(p)$ and $-(1-\lambda)H(q)$. The bracket in the third is $m(x)$, so the third term is $+H(m)$. Hence

$$H(m) - \lambda H(p) - (1-\lambda)H(q) = \lambda D(p \,\|\, m) + (1-\lambda) D(q \,\|\, m) \ge 0$$

by Gibbs' inequality. Equality requires both divergences to vanish, so $p = m$ and $q = m$, that is $p = q$. $\square$

The proof gives more than the inequality: the gap is exactly the weighted sum of the two divergences from the blend. On the text, the walkthrough's training split is the first 1,003,854 characters and its validation split the last 111,540, so the character distribution of the whole file is the blend of the two with $\lambda = 0.9000$. In nats, the splits have entropies 3.3091 and 3.3373, whose weighted average is 3.3119, and the whole file has 3.3128. The gap is 0.0009 nats, and the script confirms that it equals the weighted sum of the two divergences. It is small because the two splits have nearly the same character frequencies.

Concavity is why entropy can serve as a node impurity in Classification Trees: a parent node's class distribution is the blend of its children's, weighted by their sizes, so a split never raises the weighted entropy. That article states the requirement for impurity measures in general.

Why this formula: Shannon's uniqueness theorem

Other functions of the probabilities are zero for a certain outcome and largest for a uniform one. The Gini index is one. What singles out $-\sum p\log p$? Shannon (1948, Section 6) answered with three requirements on a measure of uncertainty, and proved in his Appendix 2 that only one family of functions meets them. This section states the requirements precisely and gives the proof in full, following Shannon's argument and filling in its steps.

Suppose that for every $n \ge 1$ a number $H(p_1, \dots, p_n)$ is assigned to every list of $n$ probabilities, $p_i \ge 0$ with $\sum_i p_i = 1$. Write $A(n) = H\!\left(\tfrac1n, \dots, \tfrac1n\right)$ for its value on $n$ equally likely outcomes. The requirements are:

  1. Continuity. For each $n$, $H(p_1, \dots, p_n)$ is a continuous function of $(p_1, \dots, p_n)$.
  2. Monotonicity. $A(n)$ is strictly increasing in $n$: with equally likely outcomes, more outcomes mean more uncertainty.
  3. Grouping. If the list is cut into $m$ consecutive groups with total probabilities $w_1, \dots, w_m$, all positive, then $H(p_1, \dots, p_n) = H(w_1, \dots, w_m) + \sum_{j} w_j\,H(\text{the probabilities in group } j, \text{ each divided by } w_j)$.

Shannon states the third as "If a choice be broken down into two successive choices, the original $H$ should be the weighted sum of the individual values of $H$", and illustrates it with the example $H\!\left(\tfrac12, \tfrac13, \tfrac16\right) = H\!\left(\tfrac12, \tfrac12\right) + \tfrac12 H\!\left(\tfrac23, \tfrac13\right)$, worked in Problem 1 below. Requirement 3 as written here is that statement for any number of groups. Only consecutive groups are needed, and no symmetry of $H$ in its arguments is assumed. For the second requirement Shannon asks that $H$ be "a monotonic increasing function of $n$"; it is read here as strictly increasing, which is what makes the constant in the theorem positive.

Theorem (Shannon, 1948, Theorem 2). A function $H$ satisfies requirements 1 to 3 if and only if

$$H(p_1, \dots, p_n) = -K\sum_{i=1}^{n} p_i\log p_i$$

for some constant $K > 0$.

The constant $K$ is the choice of unit, equivalently of the base of the logarithm. The plan of the proof: grouping forces $A$ to turn products into sums; with monotonicity that makes $A(n)$ a multiple of $\log n$; grouping then gives the formula for rational probabilities; and continuity extends it to all.

Proof that the formula satisfies the requirements. Let $F(p_1, \dots, p_n) = -K\sum_i p_i\log p_i$. The function $x\log x$ is continuous on $(0, 1]$, and it tends to 0 as $x \to 0^+$ (shown in step 4 below), so with the convention $0\log 0 = 0$ it is continuous on $[0, 1]$. So $F$ is continuous. On $n$ equally likely outcomes, $F = K\log n$, which is strictly increasing because $K > 0$. Requirement 3 is the grouping corollary proved above, in the section on functions and grouping, multiplied by $K$. $\square$

Proof that the requirements force the formula. Let $H$ satisfy the three requirements.

Step 1: $A(mn) = A(m) + A(n)$. Take $mn$ equally likely outcomes and cut them into $m$ consecutive groups of $n$. Each group has probability $w_j = n/(mn) = 1/m$, and within a group the $n$ outcomes have probability $(1/mn)/(1/m) = 1/n$ each. Requirement 3 gives

$$A(mn) = A(m) + \sum_{j=1}^{m}\frac1m A(n) = A(m) + A(n).$$

With $m = n = 1$ this reads $A(1) = 2A(1)$, so $A(1) = 0$. By induction on $r$, $A(s^r) = r\,A(s)$ for all integers $s \ge 1$ and $r \ge 0$: it holds for $r = 0$ because $A(1) = 0$, and $A(s^{r+1}) = A(s^r) + A(s)$.

Step 2: $A(n) = K\log n$ with $K > 0$. Fix integers $s \ge 2$ and $t \ge 2$. By requirement 2, $A(s) > A(1) = 0$. Let $a$ be any positive integer, to be used as an exponent, and let $m$ be the largest integer with $s^m \le t^a$, so that

$$s^m \le t^a < s^{m+1}.$$

(For $s = 2$, $t = 3$ and $a = 10$: $2^{15} \le 3^{10} < 2^{16}$, so $m = 15$.) Taking logarithms and dividing by $a\log s > 0$,

$$\frac{m}{a} \le \frac{\log t}{\log s} < \frac{m}{a} + \frac1a.$$

Applying $A$ to the same three integers, requirement 2 gives $A(s^m) \le A(t^a) < A(s^{m+1})$, which by step 1 is $m\,A(s) \le a\,A(t) < (m+1)\,A(s)$. Dividing by $a\,A(s) > 0$,

$$\frac{m}{a} \le \frac{A(t)}{A(s)} < \frac{m}{a} + \frac1a.$$

The two numbers $\frac{\log t}{\log s}$ and $\frac{A(t)}{A(s)}$ lie in the same interval of length $\frac1a$, so they differ by less than $\frac1a$. Neither depends on $a$, and $a$ was arbitrary, so they are equal: $\frac{A(t)}{\log t} = \frac{A(s)}{\log s}$. Call the common value $K$. It is positive because $A(s) > 0$ and $\log s > 0$. So $A(n) = K\log n$ for every $n \ge 2$, and also for $n = 1$, where both sides are 0. In the example, $\log 3/\log 2 = 1.585$ lies between $15/10$ and $16/10$.

Step 3: rational probabilities. From here on the list has $r$ probabilities, $p_1, \dots, p_r$, to keep the letter $n$ out of it. Let $p_i = c_i/N$ with positive integers $c_1, \dots, c_r$ summing to $N$. Take $N$ equally likely outcomes and cut them into consecutive groups of sizes $c_1, \dots, c_r$. Group $i$ has probability $c_i/N = p_i$, and within it the $c_i$ outcomes are equally likely. Requirement 3 gives

$$A(N) = H(p_1, \dots, p_r) + \sum_{i} p_i\,A(c_i).$$

By step 2, and using $\sum_i p_i = 1$ to write $K\log N = K\sum_i p_i\log N$,

$$H(p_1, \dots, p_r) = K\log N - K\sum_i p_i\log c_i = -K\sum_i p_i\log\frac{c_i}{N} = -K\sum_i p_i\log p_i.$$

So $H = F$ on every list of positive rational probabilities.

Step 4: all probabilities. First, $x\log x \to 0$ as $x \to 0^+$. It is enough to show it for the natural logarithm. For $0 < x \le 1$, write $y = 1/\sqrt{x} \ge 1$. By the inequality $\ln y \le y - 1$ (proved in the next article, in the section on Gibbs' inequality),

$$0 \le -x\ln x = 2x\ln y \le 2x(y - 1) < 2xy = 2\sqrt{x},$$

which tends to 0. So $F$ is continuous on all lists of probabilities, including those with zeros.

Now let $(p_1, \dots, p_r)$ be any list of probabilities. For each positive integer $k$ define

$$p_i^{(k)} = \frac{\lfloor k p_i\rfloor + 1}{\sum_{j}\lfloor k p_j\rfloor + r},$$

where $\lfloor\cdot\rfloor$ rounds down to an integer. These are positive rational numbers summing to 1. Since $k p_i - 1 < \lfloor k p_i\rfloor \le k p_i$, the numerator divided by $k$ tends to $p_i$ and the denominator divided by $k$ tends to $\sum_j p_j = 1$, so $p_i^{(k)} \to p_i$ as $k \to \infty$. By step 3, $H(p^{(k)}) = F(p^{(k)})$ for every $k$. Both $H$ (requirement 1) and $F$ are continuous, so letting $k \to \infty$ gives $H(p) = F(p)$. $\square$

Shannon was careful about how much weight the theorem should carry. Directly after stating it he writes: "This theorem, and the assumptions required for its proof, are in no way necessary for the present theory. It is given chiefly to lend a certain plausibility to some of our later definitions. The real justification of these definitions, however, will reside in their implications." The implications that follow in his paper are its coding theorems. The bound behind the first of them is proved in Perplexity and Source Coding.

Estimating entropy from counts: an experiment

Every entropy in this article was computed by putting observed shares into the formula. That is called the plug-in estimate when the shares stand in for the probabilities of a source that produced the data. The table of longer contexts raised a doubt about it, and the following experiment tests it.

Shuffle the 1,115,394 characters of the text into a random order. The character counts are unchanged, so the first-order entropy is still 4.7794 bits. In a shuffled text the characters before a position carry almost no information about the character at it. (Not exactly none: the counts are fixed, so a character that has been used is slightly less likely to come next.) An honest measure of the uncertainty of a character given the $k - 1$ before it should therefore stay close to 4.78 bits for every $k$. The table shows what the plug-in increments give, for the text and for 30 shuffles of it (seeds 0 to 29; median and interquartile range).

$k$ Text (bits) Shuffled text: median (bits) Interquartile range
1 4.7794 4.7794 4.7794 to 4.7794
2 3.5383 4.7768 4.7768 to 4.7769
3 2.7520 4.6841 4.6839 to 4.6844
4 2.1610 3.7990 3.7981 to 3.8000
5 1.7672 1.7017 1.7013 to 1.7021

For $k = 2$ the shuffled text loses 0.0025 bits, a negligible amount, and the 3.5383 bits measured on the real text reflect real structure: which character follows which. By $k = 4$ the shuffled text shows a drop of 0.98 bits that corresponds to nothing, and at $k = 5$ its increment is 1.7017 bits, where about 4.78 would be right. That is within 0.0655 bits of the real text's 1.7672, so a figure of that size cannot by itself be taken as evidence of structure.

The cause is counting. A block of five characters can take $65^5$ values, more than a billion, and the file has about 1.1 million positions. A context of four characters that has been seen only once has been seen with only one successor, and the plug-in conditional entropy counts that as certainty. In the first shuffle (seed 0) this is so at 29.6 percent of the positions. Most of the other contexts have been seen only a few times, and a context seen $c$ times contributes at most $\log_2 c$ bits, however unpredictable its successor is. That cap is reached when all $c$ successors differ, which is the usual case in a shuffle: 90.3 percent of the distinct blocks of five occur exactly once, and they cover 77.8 percent of the positions. For $k = 4$, where the context is three characters, only 2.6 percent of the positions have a context seen once, and the damage is smaller. The real text repeats itself far more than a shuffle does. Only 1.4 percent of its positions have a four-character context that occurs once, and 5.6 percent lie in a block of five that occurs once. Its fifth increment is therefore less contaminated than the shuffled one, but this experiment does not say by how much.

So in this experiment the plug-in estimate was accurate at $k = 2$, where there are 4,225 possible pairs for 1.1 million positions. It was 0.095 bits low at $k = 3$, with 274,625 possible blocks, and biased downward severely from $k = 4$ on. The increments for $k \ge 4$ in the real text mix real structure with this artifact, and this article does not separate the two. The same caution applies to any entropy computed from a table with many sparsely filled cells. Chance-adjusted clustering measures subtract the analogous bias from a mutual information, and Mutual Information measures it on this text.

What is proved, what is cited, what the experiment shows

Proved here: the bounds $0 \le H \le \log n$ with their cases of equality, the chain rule for two and for several variables, that conditioning reduces entropy on average, subadditivity, the entropy of a function, the grouping identity, concavity with the exact size of the gap, and Shannon's uniqueness theorem in both directions.

Borrowed, with the proof on a linked page: Gibbs' inequality and the inequality $\ln x \le x - 1$, both proved in Cross-Entropy and Kullback–Leibler Divergence without using anything from this article.

Cited: the definitions and the uniqueness theorem are Shannon's (1948, Section 6 and Appendix 2); the proof given here follows his and supplies the steps he left out. The coding interpretation of entropy is proved in Perplexity and Source Coding. Cover and Thomas (2006) is the standard textbook for all of this material.

Shown by computation on one text: every number about the Tiny Shakespeare file (the training text distributed with Karpathy's char-rnn, 2015), which the script recomputes and asserts. The numbers describe that file. The shuffling experiment shows the plug-in estimate failing on that file at context lengths of four and five characters; it does not give a rule for when the estimate is safe in general.

Worked problems

These problems are posed for this article, on small exact cases and on the Tiny Shakespeare text, one for each main result. The script tools/experiments/statistics/entropy.py checks every number.

Problem 1 (Shannon's decomposition). Compute the entropy in bits of three outcomes with probabilities $\tfrac12$, $\tfrac13$ and $\tfrac16$, directly and by Shannon's two-stage decomposition $H\!\left(\tfrac12, \tfrac13, \tfrac16\right) = H\!\left(\tfrac12, \tfrac12\right) + \tfrac12 H\!\left(\tfrac23, \tfrac13\right)$.

Solution. Both give 1.4591 bits. Directly,

$$H = \tfrac12\log_2 2 + \tfrac13\log_2 3 + \tfrac16\log_2 6 = 0.5000 + 0.5283 + 0.4308 = 1.4591.$$

In closed form, with $\log_2 6 = 1 + \log_2 3$, the sum is $\tfrac12 + \tfrac16 + \left(\tfrac13 + \tfrac16\right)\log_2 3 = \tfrac23 + \tfrac12\log_2 3$, and $\log_2 3 = 1.5850$.

By stages: group the second and third outcomes. The groups have probabilities $\tfrac12$ and $\tfrac12$, with entropy $H\!\left(\tfrac12, \tfrac12\right) = 1$ bit. Within the second group the probabilities are $\tfrac13 / \tfrac12 = \tfrac23$ and $\tfrac16 / \tfrac12 = \tfrac13$, with entropy $\tfrac23\log_2\tfrac32 + \tfrac13\log_2 3 = 0.9183$ bits. The first group has one outcome and entropy 0. By the grouping corollary, $H = 1 + \tfrac12 \times 0 + \tfrac12 \times 0.9183 = 1.4591$ bits. The second choice is needed only half the time, so it is counted with weight $\tfrac12$.

Problem 2 (the binary entropy function). For a variable with two outcomes of probabilities $\theta$ and $1 - \theta$, the entropy is $H_{\mathrm{b}}(\theta) = -\theta\log_2\theta - (1-\theta)\log_2(1-\theta)$ bits. Show that it is symmetric about $\tfrac12$, find its derivative and its maximum, and evaluate it for the grain class of Reuters, $\theta = 433/7{,}769$. What share of the stories would give half a bit?

Solution. Exchanging $\theta$ and $1 - \theta$ exchanges the two terms, so $H_{\mathrm{b}}(\theta) = H_{\mathrm{b}}(1 - \theta)$. For $0 < \theta < 1$, differentiate with $\frac{d}{d\theta}\,\theta\log_2\theta = \log_2\theta + \frac{1}{\ln 2}$:

$$H_{\mathrm{b}}'(\theta) = -\log_2\theta - \frac{1}{\ln 2} + \log_2(1-\theta) + \frac{1}{\ln 2} = \log_2\frac{1-\theta}{\theta}.$$

The derivative is positive for $\theta < \tfrac12$, zero at $\tfrac12$ and negative beyond, so the maximum is $H_{\mathrm{b}}\!\left(\tfrac12\right) = 1$ bit, in agreement with the upper bound $\log_2 2$. The derivative is the logarithm of the odds against the first outcome, and it grows without bound as $\theta \to 0$: near a certain outcome, a small change in probability changes the entropy a great deal. For grain, $\theta = 0.0557$ and $H_{\mathrm{b}} = 0.3103$ bits, the ceiling that feature selection places on the mutual information of any term with that class. A class does not need to be common to be uncertain. The equation $H_{\mathrm{b}}(\theta) = \tfrac12$ has two solutions, $\theta = 0.1100$ and, by symmetry, $\theta = 0.8900$ (found by bisection; the function increases on $[0, \tfrac12]$, so there is one root on each side). A class holding 11 percent of the stories, or 89 percent, has half a bit. This is the entropy curve drawn in Classification Trees, whose root node for the 23 Challenger flights has $H_{\mathrm{b}}(7/23) = 0.8865$ bits.

Problem 3 (a countable alphabet: the geometric distribution). A trial succeeds with probability $\theta$, independently each time, and $X$ is the number of trials up to and including the first success, so $P(X = k) = (1-\theta)^{k-1}\theta$ for $k = 1, 2, \dots$ Find $H(X)$, and evaluate it for a fair coin and for rolling a die until a six appears.

Solution. $H(X) = H_{\mathrm{b}}(\theta)/\theta$: 2 bits for the coin, and 3.9001 bits for the die. The alphabet is infinite, so the entropy is a series. The surprisal of the outcome $k$ is $-(k-1)\log_2(1-\theta) - \log_2\theta$, and its expectation is

$$H(X) = -\big(E[X] - 1\big)\log_2(1-\theta) - \log_2\theta.$$

The mean of the geometric distribution is $E[X] = 1/\theta$. (The series $\sum_k k(1-\theta)^{k-1}\theta$ is $\theta$ times the derivative of $\sum_k r^k = \frac{r}{1-r}$ at $r = 1 - \theta$, which is $\theta \cdot \frac{1}{\theta^2}$. All terms are positive, so the rearrangement is allowed.) Therefore

$$H(X) = -\frac{1-\theta}{\theta}\log_2(1-\theta) - \log_2\theta = \frac{-(1-\theta)\log_2(1-\theta) - \theta\log_2\theta}{\theta} = \frac{H_{\mathrm{b}}(\theta)}{\theta}.$$

The formula has the form of the chain rule. Each trial is a variable with entropy $H_{\mathrm{b}}(\theta)$, and on average $1/\theta$ trials are made. For the coin, $H_{\mathrm{b}}\!\left(\tfrac12\right)/\tfrac12 = 2.0000$ bits. For the die, $H_{\mathrm{b}}\!\left(\tfrac16\right) = 0.6500$ bits and $0.6500 \times 6 = 3.9001$ bits (from unrounded values). That exceeds $\log_2 6 = 2.5850$ bits, the entropy of one roll: on an infinite alphabet there is no ceiling of the form $\log n$. The script sums the series numerically and agrees.

Problem 4 (three consecutive characters). For three consecutive characters of the text, verify the chain rule for three variables, and compare the joint entropy with the bound of the subadditivity corollary.

Solution. The 11,556 distinct triples that occur have joint entropy $H(X_1, X_2, X_3) = 11.0697$ bits, computed from their counts. The three increments of the table of longer contexts are $H(X_1) = 4.7794$, $H(X_2 \mid X_1) = 3.5383$ and $H(X_3 \mid X_1, X_2) = 2.7520$, and $4.7794 + 3.5383 + 2.7520 = 11.0697$. The subadditivity bound is the sum of the three single-character entropies, $3 \times 4.7794 = 14.3381$ bits. (The three positions have the same distribution up to the first and last two characters of the file, which changes nothing at this precision.) The joint entropy is 3.2684 bits below the bound. That shortfall measures how far three consecutive characters are from independent. Per character, a block of three costs $11.0697/3 = 3.6899$ bits of uncertainty against 4.7794 for a single character.

What we have learned

Entropy is the expected surprisal of a random variable, $-\sum p\log p$, measured in bits or nats according to the base of the logarithm. It lies between 0, for a certain outcome, and the logarithm of the alphabet size, for equally likely outcomes. The entropy of a pair splits by the chain rule into the entropy of one variable and the conditional entropy of the other. Conditioning lowers entropy on average, though a single observation can raise it. A function of a variable has no more entropy than the variable, a blend of distributions has at least the average entropy of its parts, and Shannon's three requirements leave no formula but this one. On the Tiny Shakespeare text, a character has 4.7794 bits of entropy, and 3.5383 bits given the character before it. Estimates from counts hold up only while the counts are large compared with the number of cells.

Three proofs here leaned on Gibbs' inequality, and each time the entropy difference turned out to be a divergence between two distributions. Cross-Entropy and Kullback–Leibler Divergence proves that inequality and studies the divergence itself: what a model pays, in bits or nats, for using the wrong probabilities.

References

  • Cover, T. M., and Thomas, J. A. (2006). Elements of Information Theory, 2nd edition. Wiley. record · 8 pages
  • Karpathy, A. (2015). char-rnn [Software and data]. https://github.com/karpathy/char-rnn (the file data/tinyshakespeare/input.txt). record · 3 pages
  • MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Section 2.4, "Definition of entropy and related functions". record · 5 pages
  • Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423, and 27(4), 623–656. Section 6, "Choice, uncertainty and entropy", and Appendix 2. record · 6 pages