BrevFeed
Sign in

60. Entropy

🎬 Video · 14 min
💡 Every code box below is live — edit it and hit Run.

Variance measures spread in numeric terms — it needs the values to be numbers you can subtract. But how uncertain is a distribution over {cat, dog, bird}? Subtraction is meaningless there, yet the uncertainty is real.

Entropy measures uncertainty using only the probabilities.

The definition

For a discrete distribution p:

H(X) = -\sum_x p(x)\log p(x) = E\left[\log\frac{1}{p(X)}\right]

With \log_2 the units are bits; with \ln they are nats. Bits are the usual choice, and we'll use them here.

By convention 0\log 0 = 0, justified by \lim_{p\to 0}p\log p = 0 — impossible outcomes contribute nothing.

Reading the formula

The quantity \log\frac{1}{p(x)} is the surprise (or information content) of outcome x:

  • p(x) = 1 → surprise 0. A certainty tells you nothing.
  • p(x) = 1/2 → surprise 1 bit.
  • p(x) = 1/1024 → surprise 10 bits.

Rare events are surprising; certain events are not. And entropy is simply the expected surprise — the average information you gain from one observation.

Why the logarithm specifically? Because information from independent sources should add, while their probabilities multiply. The log is the unique function turning products into sums, so $\log\frac{1}{p_1p_2} = \log\frac{1}{p_1} + \log\frac{1}{p_2}$.

Properties

Non-negative: H(X) \ge 0, with equality iff X is deterministic.

Maximised by uniformity: for k outcomes,

H(X) \le \log_2 k

with equality iff every outcome has probability 1/k. Maximum uncertainty is maximum ignorance — nothing is more unpredictable than "anything could happen, equally".

Additive for independence: H(X, Y) = H(X) + H(Y) when X \perp Y.

Conditioning cannot increase it: H(X \mid Y) \le H(X), with equality iff they're independent. Information never hurts — on average, learning Y can only reduce your uncertainty about X.

That "on average" is essential. A particular value of Y can leave you more confused than before; the average across all values cannot.

Why it's the right measure

Entropy isn't an arbitrary formula. It is the unique function (up to a constant) satisfying three reasonable axioms:

  1. Continuity in the probabilities.
  2. Maximum at uniform, increasing in the number of equally likely outcomes.
  3. Grouping: splitting a choice into stages doesn't change the total uncertainty.

Shannon proved that these force H = -K\sum p\log p. There is no competing measure that satisfies them.

The coding interpretation

This is what makes entropy concrete rather than philosophical.

Shannon's source coding theorem: the minimum average number of bits needed to encode symbols from p is H(p) bits per symbol. You cannot compress below it, and you can get arbitrarily close.

So entropy is literally the size of the data after optimal compression.

The mechanism is intuitive: give short codes to likely symbols and long codes to rare ones. A symbol of probability p deserves about \log_2(1/p) bits, and averaging those lengths gives exactly H. That's what Huffman and arithmetic coding do.

A corollary worth knowing: truly random data cannot be compressed. A uniform distribution over 256 byte values has H = 8 bits — exactly the size of a byte, so there is nothing to remove. Files that compress well do so because their symbol distribution is skewed.

Continuous entropy

For a density f, the analogue is differential entropy:

h(X) = -\int f(x)\log f(x)\,dx

Two warnings, because it's less well behaved than it looks:

  • It can be negative. A Uniform(0, 1/2) has h = \log_2(1/2) = -1 bit.
  • It isn't invariant under change of variables. Rescaling X shifts h by \log|a|, so it depends on your units — measuring in metres versus centimetres changes the answer.

Differential entropy is useful in differences (which is why KL divergence and mutual information behave well) but shouldn't be read as "the information content" of a continuous variable.

One useful fact: among all densities with a given variance, the Normal has maximum entropy. That's another reason the Normal appears everywhere — it's the least-committal distribution consistent with a known spread.

Worked example

Compare the entropy of a fair coin, a biased coin, and a fair die.

Fair coin:

H = -\left(\tfrac12\log_2\tfrac12 + \tfrac12\log_2\tfrac12\right) = 1 \text{ bit}

One bit — the definition of a bit, in fact.

Biased coin, p = 0.9:

H = -(0.9\log_2 0.9 + 0.1\log_2 0.1) = -(0.9)(-0.152) - (0.1)(-3.322) = 0.469 \text{ bits}

Less than half a bit. A predictable coin carries little information, and a long sequence of such flips compresses to under half its naive size.

Fair die:

H = \log_2 6 \approx 2.585 \text{ bits}

More outcomes, more uncertainty.

The binary entropy function H(p) = -p\log_2 p - (1-p)\log_2(1-p) is worth knowing by shape: 0 at p = 0 and p = 1, peaking at 1 bit when p = 0.5, and symmetric about it. A coin biased to 0.9 and one biased to 0.1 are equally informative — it's the predictability that matters, not which way.

Doing it in Python

Entropy from the definition:

import numpy as np
from scipy.stats import entropy

def H(probs, base=2):
    p = np.asarray(probs, dtype=float)
    p = p[p > 0]                      # 0 log 0 = 0
    return -np.sum(p * np.log(p) / np.log(base))

cases = {
    "fair coin":        [0.5, 0.5],
    "biased coin 0.9":  [0.9, 0.1],
    "biased coin 0.99": [0.99, 0.01],
    "certain":          [1.0, 0.0],
    "fair die":         [1/6] * 6,
    "loaded die":       [0.5, 0.1, 0.1, 0.1, 0.1, 0.1],
}
print(f"{'distribution':>20} {'H (bits)':>10} {'max':>8}")
for name, p in cases.items():
    print(f"{name:>20} {H(p):>10.4f} {np.log2(len(p)):>8.4f}")

# scipy agrees
print("\nscipy check:", round(float(entropy([0.9, 0.1], base=2)), 4))

The binary entropy curve:

import numpy as np

def H_binary(p):
    if p in (0.0, 1.0):
        return 0.0
    return -(p * np.log2(p) + (1 - p) * np.log2(1 - p))

print(f"{'p':>6} {'H(p)':>8}   {'':<40}")
for p in np.arange(0, 1.01, 0.1):
    h = H_binary(round(p, 2))
    print(f"{p:>6.1f} {h:>8.4f}   {'#' * int(h * 40)}")

print("\nPeaks at exactly 1 bit when p = 0.5; symmetric about it.")

Entropy as compressed size — the source coding theorem, verified:

import numpy as np
import zlib
from collections import Counter

rng = np.random.default_rng(0)
n = 200_000

def empirical_entropy(data):
    counts = np.array(list(Counter(data).values()), dtype=float)
    p = counts / counts.sum()
    return -np.sum(p * np.log2(p))

sources = {
    "uniform over 256":   rng.integers(0, 256, n),
    "skewed (geometric)": np.minimum(rng.geometric(0.05, n), 255),
    "very skewed":        np.minimum(rng.geometric(0.5, n), 255),
    "constant":           np.zeros(n, dtype=int),
}
print(f"{'source':>20} {'H (bits/sym)':>14} {'zlib bits/sym':>15}")
for name, data in sources.items():
    raw = bytes(data.astype(np.uint8))
    compressed_bits = len(zlib.compress(raw, 9)) * 8 / n
    print(f"{name:>20} {empirical_entropy(data):>14.4f} {compressed_bits:>15.4f}")

print("\nCompressed size tracks entropy. Uniform data cannot be compressed at all")
print("(8 bits in, ~8 bits out); skewed data compresses toward its entropy.")

Conditioning never increases entropy on average — but can for a single outcome:

import numpy as np

def H(p):
    p = np.asarray(p, float)
    p = p[p > 0]
    return -np.sum(p * np.log2(p))

# Joint distribution of X (rows) and Y (columns)
joint = np.array([[0.30, 0.05],
                  [0.10, 0.20],
                  [0.05, 0.30]])

px = joint.sum(axis=1)
py = joint.sum(axis=0)

print(f"H(X)      = {H(px):.4f} bits")
print(f"H(Y)      = {H(py):.4f} bits")

# H(X|Y) = sum_y p(y) H(X | Y=y)
print(f"\n{'y':>4} {'p(y)':>8} {'H(X | Y=y)':>12}")
h_cond = 0.0
for j in range(joint.shape[1]):
    cond = joint[:, j] / py[j]
    h = H(cond)
    h_cond += py[j] * h
    print(f"{j:>4} {py[j]:>8.4f} {h:>12.4f}")

print(f"\nH(X|Y)    = {h_cond:.4f} bits  <= H(X) = {H(px):.4f}")
print("Learning Y reduced uncertainty about X, on average.")

Your turn

1. What is the entropy of a fair 8-sided die?

2. A source emits A with probability 0.5, B with 0.25, C with 0.125, D with 0.125. Find H and design an optimal code.

3. Why is H(X) = 0 when X is constant?

Solutions

1. For k equally likely outcomes, H = \log_2 k:

H = \log_2 8 = 3 \text{ bits}

Which makes sense: 8 outcomes need exactly 3 binary digits to label, and with uniform probabilities no cleverer scheme exists.

2.

H = -\left(\tfrac12\log_2\tfrac12 + \tfrac14\log_2\tfrac14 + \tfrac18\log_2\tfrac18 + \tfrac18\log_2\tfrac18\right)

= \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 \text{ bits}

An optimal code assigns \log_2(1/p) bits to each symbol:

Symbol p Bits needed Code
A 0.5 1 0
B 0.25 2 10
C 0.125 3 110
D 0.125 3 111

Average length: 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 bits — exactly the entropy. The bound is achieved here because every probability is a power of 1/2, so each ideal length is a whole number.

The code is also prefix-free: no codeword starts another, so a stream decodes unambiguously without separators.

Compare with a naive fixed-length code: 4 symbols need 2 bits each, so this saves 12.5%.

3. Because there is no uncertainty to measure.

If X = c always, then p(c) = 1 and every other probability is 0:

H(X) = -1 \times \log_2 1 - \sum_{x \ne c} 0 \times \log_2 0 = -1 \times 0 - 0 = 0

using \log_2 1 = 0 and the convention 0\log 0 = 0.

The interpretations all agree: observing X delivers zero surprise, since you already knew the answer; and the coding view says a constant stream needs zero bits per symbol beyond stating the constant once.

This is the lower bound of the entropy scale, and it's attained only by degenerate distributions — any genuine randomness gives H > 0.

Check yourself in code

Compute entropies for several distributions and confirm the uniform maximum.

Print exactly this:

fair coin 1.0
biased 0.9 0.469
fair die 2.585
uniform is maximal: True

Use base-2 logarithms and round to 3 decimal places. Confirm the uniform claim by checking that a fair die's entropy is at least that of a loaded die with probabilities [0.5, 0.1, 0.1, 0.1, 0.1, 0.1].

import numpy as np

def H(probs):
    p = np.asarray(probs, dtype=float)
    p = p[p > 0]
    return -np.sum(p * np.log2(p))

print("fair coin", round(H([0.5, 0.5]), 3))

# Print the biased 0.9 coin and the fair die, then check that the fair die's
# entropy is at least that of the loaded die [0.5, 0.1, 0.1, 0.1, 0.1, 0.1].

import numpy as np

def H(probs):
    p = np.asarray(probs, dtype=float)
    p = p[p > 0]
    return -np.sum(p * np.log2(p))

print("fair coin", round(H([0.5, 0.5]), 3))
print("biased 0.9", round(H([0.9, 0.1]), 3))
print("fair die", round(H([1/6] * 6), 3))
print("uniform is maximal:", bool(H([1/6] * 6) >= H([0.5, 0.1, 0.1, 0.1, 0.1, 0.1])))

Entropy is the expected surprise, -\sum p\log p, and it measures uncertainty using only probabilities — so it works where variance can't. It is zero for certainties, maximal for uniform distributions, and by Shannon's theorem it is exactly the number of bits per symbol an optimal compressor needs.

Next: what happens when you compress using the wrong distribution.

← Previous Next →