Surprise, bits and entropy

Before this lesson: discrete random variables and expectation (the probability track) and the rules of logarithms (Foundations 04). This is the first lesson of the track. Time: about 50 minutes, plus the notebook.

---

Why this matters #

A classifier or a language model is trained with the cross-entropy loss: the average surprisal of the true label (or the next token) under the model. The entropy of the data is the lowest value this loss can reach (lesson 04). Entropy is also the smallest average number of bits per symbol of any lossless compressor (lesson 05). Beyond losses, entropy appears directly in many algorithms: decision trees choose splits that lower the entropy of the labels, active learning asks for labels where the model's prediction has high entropy, soft actor-critic (SAC) rewards policies with high entropy, and the temperature of a language model controls the entropy of the next-token distribution. Every later lesson of this track builds on the definitions here.

1. Predict first #

2. The picture #

Surprise is measured with a logarithm #

Think of an outcome $x$ with probability $p(x)$. If $p(x) = 1$, seeing $x$ tells you nothing new. If $p(x)$ is small, seeing $x$ is surprising and tells you a lot. The surprisal (also called the information content or self-information) of $x$ is

Outcome	$p(x)$	Surprisal $-\log_2 p(x)$
a sure event	$1$	$0$ bits
heads with a fair coin	$1/2$	$1$ bit
two heads with two fair coins	$1/4$	$2$ bits
one card from 8 equally likely cards	$1/8$	$3$ bits
a six with a fair die	$1/6$	$2.585$ bits
a 1-in-1000 event	$1/1000$	$9.966$ bits

Why a logarithm? Take two independent events, for example two coin flips. Their probabilities multiply: two heads have probability $\frac12 \cdot \frac12 = \frac14$. The information should add: one bit for each flip, two bits in total. The logarithm is the function that turns products into sums:

A consequence: halving a probability adds exactly one bit, because $-\log_2(p/2) = -\log_2 p + 1$.

Interactive figure: loading…

The question game #

A friend picks one of 8 cards, all equally likely. You may ask only yes/no questions. Ask "Is it one of cards 1–4?": the answer removes half of the cards. Two more halving questions find the card. So you need $3 = \log_2 8$ questions. In general, finding one of $2^n$ equally likely items takes $n$ questions. With 20 questions you can find one item among $2^{20} \approx$ one million.

Now let the outcomes have different probabilities: $a$ with $\frac12$, $b$ with $\frac14$, $c$ with $\frac14$. Good strategy: ask about the likely outcome first.

1. Ask "Is it $a$?". Half of the time the answer is yes: 1 question.
2. If no, ask "Is it $b$?". This finds $b$ or $c$: 2 questions.

The average number of questions is $\frac12 \cdot 1 + \frac12 \cdot 2 = 1.5$. Look at the surprisals: $-\log_2 \frac12 = 1$ and $-\log_2 \frac14 = 2$. Each outcome needs as many questions as its surprisal. So the average number of questions is the average surprisal. This average is the entropy.

Interactive figure: loading…

When the probabilities are not powers of $\frac12$, the best question tree needs a little more than the entropy, but always less than the entropy plus one question. If you find many outcomes together (for example, ask about 10 die rolls at once), the average per outcome comes as close to the entropy as you want. Lesson 05 proves both facts.

Entropy is the average surprisal #

The entropy of a coin with $P(\text{heads}) = 0.9$:

The rare outcome is very surprising (3.3 bits), but it is rare. The common outcome is almost no surprise. On average you learn less than half a bit per flip.

Interactive figure: loading…

3. Definitions and main results #

Entropy #

Let $X$ be a discrete random variable with values in a finite set $\mathcal{X}$ of size $K$, and let $p(x) = P(X = x)$.

• The surprisal of a value $x$ with $p(x) > 0$ is $-\log p(x) = \log \frac{1}{p(x)}$.
• The entropy of $X$ is the expected surprisal:

• Convention: $0 \log 0 = 0$. The reason: $t \log t \to 0$ as $t \to 0^+$. An outcome with probability 0 never happens, so it adds nothing to the average.

We also write $H(p)$ for the entropy of a distribution $p = (p_1, \dots, p_K)$.

Entropy depends only on the list of probabilities. The values of $X$ do not enter the formula. A coin with values $\{0, 1\}$ and a variable with values $\{1, 1000\}$, each with probability $\frac12$, both have entropy 1 bit. Relabeling or reordering the outcomes does not change $H$. Adding an outcome with probability 0 does not change $H$ either.

Units: bits and nats #

Changing the base of the logarithm only multiplies $H$ by a constant, because $\log_2 t = \log t / \log 2$:

For example, the distribution $(\frac12, \frac14, \frac14)$ has entropy $1.5$ bits $= 1.5 \cdot 0.693 = 1.040$ nats.

The binary entropy #

A variable with two outcomes, with probabilities $p$ and $1 - p$, has the binary entropy

Its properties, read off the curve below:

• $H_b(0) = H_b(1) = 0$: a sure outcome has no uncertainty.
• $H_b(\frac12) = 1$ bit, the maximum.
• $H_b(p) = H_b(1 - p)$: swapping the two labels does not change the entropy.
• The curve is steep near $0$ and $1$: moving from $p = 0$ to $p = 0.1$ already gives $0.469$ bits. Some values: $H_b(0.1) = 0.469$, $H_b(0.2) = 0.722$, $H_b(0.3) = 0.881$ bits.

Interactive figure: loading…

Bounds on the entropy #

Theorem (bounds on entropy). Let $X$ take $K$ values. Then

$H(X) = 0$ if and only if $X$ is constant (one value has probability 1). $H(X) = \log K$ if and only if $X$ is uniform on all $K$ values.

Proof of the lower bound.

1. Every $p(x)$ lies in $[0, 1]$, so $\log p(x) \le 0$, and every term $-p(x) \log p(x)$ is $\ge 0$.
2. A sum of non-negative terms is non-negative, so $H(X) \ge 0$.
3. $H(X) = 0$ means every term is 0. The term $-t \log t$ is 0 only for $t = 0$ or $t = 1$. So every probability is 0 or 1: one value has probability 1. $\blacksquare$

Intuition for the upper bound. The uniform distribution is the hardest to guess: no outcome is more likely than another, so no question strategy can do better than halving. Any bias makes some outcomes easier to guess, which lowers the average number of questions.

The proof uses one simple inequality.

Lemma. $\ln t \le t - 1$ for all $t > 0$, with equality only at $t = 1$.

Proof. Let $f(t) = t - 1 - \ln t$. Then $f'(t) = 1 - 1/t$, which is negative for $t < 1$ and positive for $t > 1$. So $f$ has its minimum at $t = 1$, where $f(1) = 0$. Hence $f(t) \ge 0$, with equality only at $t = 1$. As a picture: the line $t - 1$ touches the curve $\ln t$ at $t = 1$ and lies above it everywhere else. $\blacksquare$

Proof of the upper bound.

1. Let $S = \{x : p(x) > 0\}$ be the support of $p$. Terms with $p(x) = 0$ are 0, so $H(X) = \sum_{x \in S} p(x) \ln \frac{1}{p(x)}$. Work in nats; bits only divide both sides by $\ln 2$.
2. Since $\sum_{x \in S} p(x) = 1$, we can write $\ln K = \sum_{x \in S} p(x) \ln K$. Subtract:

3. Apply the lemma with $t = \frac{1}{K p(x)}$ to every term:

because the support has at most $K$ elements.

4. Equality needs equality in both steps. The lemma is tight only when $\frac{1}{K p(x)} = 1$, that is $p(x) = \frac1K$ for every $x \in S$. The last step is tight only when $|S| = K$. Together: $p(x) = \frac1K$ for all $K$ values. $\blacksquare$

Lesson 03 gives a second view of the same fact: $\log K - H(p)$ is the KL divergence from $p$ to the uniform distribution, which is never negative.

Doubling the number of equally likely outcomes adds one bit: $\log_2(2K) = \log_2 K + 1$. A uniform choice among 1024 items has 10 bits; among 2048 items, 11 bits.

Why exactly the logarithm?

Suppose a measure of surprise $s(p)$ depends only on the probability $p \in (0, 1]$, is continuous, and adds for independent events: $s(pq) = s(p) + s(q)$. Put $g(u) = s(e^{-u})$ for $u \ge 0$. Then $g(u + v) = s(e^{-u}e^{-v}) = g(u) + g(v)$, and a continuous function with this property is linear (Cauchy's functional equation): $g(u) = c\,u$. So $s(p) = -c \ln p$. The constant $c$ only chooses the unit: $s(\frac12) = 1$ gives $c = 1/\ln 2$, that is, bits. For a positive surprise, $c > 0$.

Shannon (1948, Theorem 2) proved a similar statement for the entropy itself: the only continuous function of $(p_1, \dots, p_K)$ that grows with $K$ for uniform distributions and that obeys a natural "grouping" rule (one question at a time, as in the question game) is $-c\sum_i p_i \log p_i$.

A preview of coding #

A code writes each outcome as a string of bits. For $(\frac12, \frac14, \frac18, \frac18)$ on $a, b, c, d$, use $a = 0$, $b = 10$, $c = 110$, $d = 111$. The bits are the answers in the question game: 0 for "yes", 1 for "no". The average length is $\frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac18 \cdot 3 = 1.75$ bits, exactly the entropy: each codeword length equals the surprisal of its symbol. No code that can always be decoded does better on average than the entropy; this is the source coding theorem of lesson 05.

Answers to section 1. (1) Between 2 and 3. The entropy of a fair die is $\log_2 6 = 2.585$ bits. The best question tree for one die puts 2 faces at depth 2 and 4 faces at depth 3, so it needs $\frac{2 \cdot 2 + 4 \cdot 3}{6} = 2.667$ questions on average. Asking about many dice at once brings the average per die close to $2.585$ (lesson 05). (2) Less than both: $H_b(0.9) = 0.469$ bits. (3) No. Every term $-p(x)\log p(x)$ is $\ge 0$, so $H(X) \ge 0$.

4. Worked example #

(a) A weather forecast. Tomorrow is sunny with probability $\frac12$, cloudy with $\frac14$, rainy with $\frac18$ and snowy with $\frac18$.

1. Surprisals. $-\log_2 \frac12 = 1$, $-\log_2 \frac14 = 2$, $-\log_2 \frac18 = 3$, $-\log_2 \frac18 = 3$ bits.
2. Entropy in bits. Weight each surprisal by its probability: $H = \frac12 \cdot 1 + \frac14 \cdot 2 + \frac18 \cdot 3 + \frac18 \cdot 3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75$ bits.
3. In nats. Multiply by $\ln 2 = 0.693$: $1.75 \cdot 0.693 = 1.213$ nats.
4. Compare with the maximum. For $K = 4$, $\log_2 4 = 2$ bits. The forecast is less uncertain than a uniform choice among 4, because "sunny" is likely.
5. Question tree. Ask "sunny?", then "cloudy?", then "rainy?". The numbers of questions are 1, 2, 3, 3: equal to the surprisals. The average is 1.75 questions $= H$.

(b) Probabilities that are not powers of $\frac12$. $p = (0.7, 0.2, 0.1)$ on $a, b, c$.

1. Surprisals. $-\log_2 0.7 = 0.515$, $-\log_2 0.2 = 2.322$, $-\log_2 0.1 = 3.322$ bits.
2. Entropy. $H = 0.7 \cdot 0.515 + 0.2 \cdot 2.322 + 0.1 \cdot 3.322 = 0.360 + 0.464 + 0.332 = 1.157$ bits.
3. Best question tree. Ask "Is it $a$?", then "Is it $b$?". The numbers of questions are 1, 2, 2, so the average is $0.7 \cdot 1 + 0.3 \cdot 2 = 1.3$ questions.
4. Check the bounds. $1.157 \le 1.3 < 1.157 + 1$: the best tree is above the entropy but within one question of it. The maximum for $K = 3$ is $\log_2 3 = 1.585$ bits.

(c) Temperature in a softmax. A model outputs the logits $z = (2, 1, 0)$ for three classes. The probabilities are $q_i = e^{z_i / T} / \sum_j e^{z_j / T}$ with the temperature $T$.

1. $T = 1$: $q = (0.665, 0.245, 0.090)$, $H = 1.201$ bits.
2. $T = 0.5$ divides by a smaller number, so the gaps between logits grow: $q = (0.867, 0.117, 0.016)$, $H = 0.636$ bits.
3. $T = 2$ shrinks the gaps: $q = (0.506, 0.307, 0.186)$, $H = 1.472$ bits.

Higher temperature, higher entropy, closer to the maximum $\log_2 3 = 1.585$ bits.

5. In code #

NumPy computes the entropy of a probability vector. Skipping the zeros implements the convention $0 \log 0 = 0$; writing the terms as $p \log(1/p)$ makes the result exactly $0.0$ for a sure outcome.

import numpy as np
from scipy.stats import entropy

def H(p, base=2):
    """Entropy of a probability vector; terms with p = 0 are skipped (0 log 0 = 0)."""
    p = np.asarray(p, dtype=float)
    p = p[p > 0]
    return np.sum(p * np.log(1 / p)) / np.log(base)

weather = [1/2, 1/4, 1/8, 1/8]
print(-np.log2(weather))                    # [1. 2. 3. 3.]   surprisals in bits
print(H(weather), H(weather, base=np.e))    # 1.75 1.2130075659799042
print(entropy(weather, base=2))             # 1.75            SciPy agrees
print(H([0.9, 0.1]), H([0.7, 0.2, 0.1]))    # 0.46899559358928133 1.1567796494470395
print(H([1, 0, 0]), H(np.ones(8) / 8), H(np.ones(6) / 6))   # 0.0 3.0 2.584962500721156

def softmax(z, T=1.0):
    z = np.asarray(z, dtype=float) / T
    e = np.exp(z - z.max())                 # subtract the max for numerical safety
    return e / e.sum()

for T in [0.5, 1, 2]:
    q = softmax([2, 1, 0], T)
    print(T, q.round(3), round(H(q), 3))
# 0.5 [0.867 0.117 0.016] 0.636
# 1 [0.665 0.245 0.09 ] 1.201
# 2 [0.506 0.307 0.186] 1.472

scipy.stats.entropy(p) normalizes p first and uses nats unless you pass base. A plain np.sum(p * np.log(p)) returns nan when some p is 0, because 0 * log(0) is 0 * (-inf).

6. Where it shows up #

• Loss functions. The cross-entropy loss of a classifier is the average surprisal of the true label under the model. It can never go below the entropy of the labels given the inputs (lesson 02 and lesson 04). A language model's loss in bits per token is the average surprisal of the next token.
• Decision trees. The entropy of the class labels at a node measures how mixed the node is. ID3 and C4.5 choose the split with the largest information gain, the drop in entropy (lesson 02 and the decision-tree lesson of the ML fundamentals track, in preparation).
• Uncertainty of a prediction. The entropy of a classifier's predicted distribution is a simple uncertainty score. Uncertainty sampling in active learning asks for labels of the inputs with the highest predictive entropy.
• Reinforcement learning. Soft actor-critic (SAC) maximizes reward plus $\alpha$ times the entropy of the policy, and PPO often adds an entropy bonus. Both keep the policy random enough to explore (RL 08).
• Sampling from language models. Dividing the logits by a temperature $T > 1$ raises the entropy of the next-token distribution (more varied text); $T < 1$ lowers it (more predictable text) (the decoding lesson of the LLMs track, in preparation).
• ML for science. In biology, a sequence logo shows, for each position of aligned DNA or protein sequences, the information content $\log_2 N - H$, where $N$ is the alphabet size (4 for DNA, 20 for proteins) and $H$ is the entropy of the letters in that column. Conserved positions have low entropy and tall letters. In ecology, the entropy of species proportions is the Shannon diversity index.

7. Common mistakes #

• Mixing bits and nats. NumPy, SciPy (by default) and PyTorch use the natural log. Divide by $\ln 2 = 0.693$ to get bits.
• nan from $0 \log 0$. Skip the zero probabilities, or use scipy.special.xlogy. The convention is $0 \log 0 = 0$.
• "Entropy measures how spread out the values are." It does not use the values at all. $\{0, 1\}$ and $\{0, 1000\}$ with equal probabilities both have 1 bit. Spread of values is the variance.
• Confusing the average surprisal with the surprisal of the likely outcome. For $(0.9, 0.1)$ the likely outcome has surprisal $0.152$ bits, but the entropy is $0.469$ bits.
• Using counts instead of probabilities. The formula needs probabilities that sum to 1. Divide counts by their total first. (scipy.stats.entropy does this for you; a hand-written formula does not.)
• Expecting entropy to grow like $K$. The entropy of a uniform distribution grows like $\log K$: doubling the number of outcomes adds only one bit.

8. Check yourself #

1. What is the entropy of a fair six-sided die, in bits and in nats?
   Answer

   $\log_2 6 = 2.585$ bits and $\ln 6 = 1.792$ nats.
2. Which has more entropy: a coin with $P(\text{heads}) = 0.2$ or a coin with $P(\text{heads}) = 0.7$?
   Answer

   $H_b(0.2) = 0.722$ bits and $H_b(0.7) = H_b(0.3) = 0.881$ bits. The coin with $0.7$ is closer to $\frac12$, so it has more entropy.
3. Someone says a distribution on 5 outcomes has entropy 2.5 bits. Is this possible?
   Answer

   No. The maximum for 5 outcomes is $\log_2 5 = 2.322$ bits, reached by the uniform distribution.
4. A uniform distribution has entropy 5 bits. How many outcomes does it have? What is the entropy if you double the number of outcomes?
   Answer

   $\log_2 K = 5$ gives $K = 32$. With 64 equally likely outcomes, $H = 6$ bits: doubling adds one bit.
5. Prove that $H(X) = 0$ implies that one value of $X$ has probability 1.
   Answer

   Each term $-p(x)\log p(x)$ is $\ge 0$. If the sum is 0, every term is 0. The function $-t\log t$ is 0 on $[0, 1]$ only at $t = 0$ and $t = 1$. So every $p(x)$ is 0 or 1, and since they sum to 1, exactly one is 1.
6. A model gives the probabilities $(0.98, 0.01, 0.01)$ to three classes. Compute the entropy of its prediction in bits. Is the model confident?
   Answer

   $H = 0.98 \cdot 0.029 + 2 \cdot 0.01 \cdot 6.644 = 0.029 + 0.133 = 0.161$ bits, far below the maximum $\log_2 3 = 1.585$. The model is confident (whether it is also right is a different question).

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is the surprisal of an outcome with probability $p$?

   Show answer

2. Why is surprisal defined with a logarithm?

   Show answer

3. Define the entropy of a discrete random variable $X$.

   Show answer

4. How do you convert an entropy from nats to bits?

   Show answer

5. What is the entropy of a uniform distribution on $K$ outcomes?

   Show answer

6. When is $H(X) = 0$?

   Show answer

7. Compute the entropy of $(\frac12, \frac14, \frac14)$ in bits.

   Show answer

8. What is $H_b(0.5)$, and what is $H_b(0.1)$, in bits?

   Show answer

9. Why does the convention $0 \log 0 = 0$ make sense?

   Show answer

10. What does entropy have to do with yes/no questions?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "What is entropy, intuitively?" — The average surprise of the outcome, or the average number of yes/no questions needed to find it. Zero for a certain outcome, $\log K$ for $K$ equally likely outcomes.
• "Which distribution on $K$ outcomes has maximum entropy? Prove it." — The uniform one. Proof with $\ln t \le t - 1$ (section 3), or with $\log K - H(p) = \mathrm{KL}(p\,\|\,u) \ge 0$ (lesson 03).
• "Your cross-entropy loss is 0.69. What does that mean?" — PyTorch uses nats, so this is $0.69/0.693 \approx 1$ bit per example: the model is as uncertain as a fair coin about the true label, on average.
• "How does the temperature of a language model change its outputs?" — The logits are divided by $T$. A larger $T$ gives a flatter softmax with higher entropy (more diverse samples); a smaller $T$ gives a sharper one with lower entropy.
• "Why does a decision tree use entropy?" — The entropy of the labels at a node measures how mixed they are. A good split lowers the weighted entropy of the children (information gain).

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. Write surprisal(p, base) and entropy(p, base) with the convention $0 \log 0 = 0$, and check them against scipy.stats.entropy.
2. Plot the binary entropy $H_b(p)$ and find its maximum numerically.
3. Compute the entropy of the letters of a short English text from their counts.
4. Simulate the question game for $(\frac12, \frac14, \frac18, \frac18)$ and compare the average number of questions with $H$.
5. Compute the entropy of a softmax at several temperatures, and check that it grows with $T$.

11. Watch and read #

Reinventing Entropy | Compression is Intelligence Part 13Blue1Brown · 32 min

Builds entropy from the question game and from coding, the same path as this lesson.

Entropy (for data science) Clearly Explained!!!StatQuest with Josh Starmer · 17 min

Surprise as log(1/p) and entropy as expected surprise, with slow small examples.

Solving Wordle using information theory3Blue1Brown · 31 min

Choosing the guess with the largest expected information: the question game in a real puzzle.

Lecture 2: Entropy and Data Compression (I): Introduction to Compression, Inf.Theory and EntropyDavid MacKay · Information Theory, Pattern Recognition and Neural Networks (channel Jakob Foerster) · 51 min

MacKay's own lecture on information content, entropy and the weighing problem.

• David MacKay, Information Theory, Inference, and Learning Algorithms, free PDF: §2.4 (definition of entropy and its bounds) and §4.1 (the information content of an outcome, the weighing problem).
• Kevin Murphy, Probabilistic Machine Learning: An Introduction, free PDF: §6.1.1 (entropy of discrete random variables).
• Claude Shannon, A Mathematical Theory of Communication (1948), §6: the definition of entropy and Theorem 2 on why its form is unique.