01 - Shannon Entropy

How many bits, on average, does it take to tell someone which outcome of a random experiment occurred? It depends on how predictable the outcome was: if I already know it will come up heads, I don't need to tell you anything; if the coin is fair, I need exactly one bit.

Shannon entropy puts this reasoning into a formula: for a source that produces symbol x with probability p(x), it is H(X) = Σ p(x) · log₂(1/p(x)) bits, the mean of the "surprise" log₂(1/p(x)) of each outcome. For the fair coin it is 1 bit, for a coin that comes up heads 90% of the time it is 0.469 bits, for a certain outcome it is zero.

This article builds the definition, tests it on numbers, derives joint and conditional entropy with the chain rule, and closes with two traps that the formulas alone do not show: estimation from data and the entropy of real numbers.

Every listing was run twice with identical output, using Python 3.14.4, numpy 2.3.5, scipy 1.16.3 and sympy 1.14.0, with no network and fixed seeds for random numbers. Shannon's formulas are checked against the original text (A Mathematical Theory of Communication) and against MacKay's book, both listed at the end.

The surprise of an event and its average

An event of probability 1/8 surprises you more than one of probability 1/2, and it makes sense to measure the surprise by the number of yes/no questions needed to identify it: three for 1/8 (is it in the left half? the left half of that one? ...), one for 1/2.

This is the quantity log₂(1/p), which with base 2 is measured in bits: Shannon credits the name to J. W. Tukey in the introduction of the paper. With the natural logarithm the unit is the nat, and 1 nat equals 1/ln 2 ≈ 1.4427 bits: changing base only changes a constant, and this article always uses bits.

Entropy is the expected value of the surprise: each outcome contributes its own surprise, weighted by how often it happens. The listing computes it for five sources.

The line with if x > 0 implements the convention 0·log 0 = 0: it is the right convention because x·log x tends to zero as x tends to zero, and without that if an impossible outcome would raise a domain error. Writing log2(1/x) instead of -x * log2(x) keeps the certain outcome from printing the annoying "-0.0000".

The second, independent calculation redoes the sums with exact fractions and sympy symbolic logarithms, and the largest gap between the two is of the order of the rounding error.

from math import log2
import sympy as sp


def entropia(p):
    """Shannon entropy in bits; the 0·log 0 = 0 convention is the if."""
    return sum(x * log2(1 / x) for x in p if x > 0)


casi = {
    "fair coin": [0.5, 0.5],
    "90-10 coin": [0.9, 0.1],
    "three-sided die": [1 / 3] * 3,
    "certain outcome": [1.0, 0.0],
    "five articles": [0.4, 0.25, 0.2, 0.1, 0.05],
}
for nome, p in casi.items():
    print(f"{nome:17s} {entropia(p):.4f} bit")

# second, independent calculation: exact fractions and sympy symbolic logarithms
R = sp.Rational
esatti = [
    [R(1, 2), R(1, 2)],
    [R(9, 10), R(1, 10)],
    [R(1, 3)] * 3,
    [R(2, 5), R(1, 4), R(1, 5), R(1, 10), R(1, 20)],
]
numerici = [casi[k] for k in ("fair coin", "90-10 coin", "three-sided die", "five articles")]
scarto = max(
    abs(float(sp.N(sum(q * sp.log(1 / q, 2) for q in pe), 30)) - entropia(pn))
    for pe, pn in zip(esatti, numerici)
)
print(f"largest gap between the two calculations: {scarto:.1e}")

# Output:
# fair coin         1.0000 bit
# 90-10 coin        0.4690 bit
# three-sided die   1.5850 bit
# certain outcome   0.0000 bit
# five articles     2.0414 bit
# largest gap between the two calculations: 4.4e-16

The 90% coin has entropy 0.469 bits: almost half that of the fair one, because only one toss in ten surprises you. The three-sided die is worth log₂ 3 ≈ 1.585 bits, the maximum possible with three outcomes.

The fifth row concerns a distribution invented for the example (five Italian articles with frequencies 0.40, 0.25, 0.20, 0.10 and 0.05; it is not a measurement on a real corpus): it gives 2.0414 bits, between zero and the maximum log₂ 5 = 2.3219, because the distribution is unbalanced but not concentrated on a single outcome.

Why this formula

Shannon's choice is not arbitrary, but it is not forced either, and the original paper says so honestly. In section 6, "Choice, uncertainty and entropy", he asks that a measure H(p₁, ..., p_n) of "uncertainty" have three properties, listed here in abbreviated form.

• Continuity: H is a continuous function of the probabilities.
• Monotonicity on the uniform distribution: if all n outcomes are equally likely, H grows with n (more choice, more uncertainty).
• Decomposition: if a choice is split into two successive choices, the original H is the weighted sum of the H of the parts.

Theorem 2 of the paper states that the only H with these three properties has the form −K Σ p_i log p_i, with K a positive constant that fixes the unit of measure. There are three, not four: symmetry under permutation and the maximum on the uniform distribution follow from the form found, they are not assumptions.

Right after, Shannon writes that the theorem and the assumptions it rests on are in no way necessary to the theory and serve to make the definitions plausible: the real justification lies in their consequences, that is, in the coding theorems of the following articles. He also notes that the form coincides with that of entropy in statistical mechanics, the one in Boltzmann's H theorem, but he introduces it starting from communication and not from physics.

The third property can be checked on the paper's own example, with three outcomes of probability 1/2, 1/3 and 1/6: choosing among three is equivalent to first choosing between two equiprobable outcomes and, if the second comes up (half the time), choosing between two outcomes with probability 2/3 and 1/3.

The first part of the next listing verifies exactly with sympy that H(1/2, 1/3, 1/6) = H(1/2, 1/2) + ½ · H(2/3, 1/3).

The other two parts test numerically properties that will recur: over 100,000 random distributions with 2-8 outcomes the entropy never leaves the interval [0, log₂ n], and it respects concavity H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q), that is, mixing two distributions never decreases the average uncertainty. The distributions are drawn from a Dirichlet with parameters 1 and seed 2026; the smallest margin observed is positive, 7·10⁻¹¹ bits. It is not a proof, but any sign error in the formulas would have made it fail immediately.

import numpy as np
import sympy as sp
from math import log2

R = sp.Rational
# Shannon's third assumption in his own example: H(1/2,1/3,1/6) = H(1/2,1/2) + 1/2 H(2/3,1/3)
H = lambda p: -sum(q * sp.log(q, 2) for q in p)
sinistra = H([R(1, 2), R(1, 3), R(1, 6)])
destra = H([R(1, 2), R(1, 2)]) + R(1, 2) * H([R(2, 3), R(1, 3)])
print("exact grouping:", sp.simplify(sinistra - destra) == 0)

rng = np.random.default_rng(2026)


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


viol_limiti = viol_conc = 0
margine_min = np.inf
for _ in range(100_000):
    n = int(rng.integers(2, 9))
    p, q = rng.dirichlet(np.ones(n)), rng.dirichlet(np.ones(n))
    lam = rng.random()
    h = ent(p)
    viol_limiti += not (-1e-12 <= h <= log2(n) + 1e-12)
    gap = ent(lam * p + (1 - lam) * q) - (lam * h + (1 - lam) * ent(q))
    margine_min = min(margine_min, gap)
    viol_conc += gap < -1e-12
print("violations of 0 <= H <= log2 n:", viol_limiti, "out of 100000")
print("violations of concavity:       ", viol_conc, "out of 100000")
print(f"smallest concavity margin: {margine_min:.2e} bit")

# chain rule on 20000 random 3x4 joint distributions
massimo = 0.0
for _ in range(20_000):
    J = rng.dirichlet(np.ones(12)).reshape(3, 4)
    px = J.sum(axis=1)
    h_y_dato_x = sum(px[i] * ent(J[i] / px[i]) for i in range(3))
    massimo = max(massimo, abs(ent(J.ravel()) - ent(px) - h_y_dato_x))
print(f"largest chain-rule gap: {massimo:.1e} bit")

# Output:
# exact grouping: True
# violations of 0 <= H <= log2 n: 0 out of 100000
# violations of concavity:        0 out of 100000
# smallest concavity margin: 6.82e-11 bit
# largest chain-rule gap: 1.3e-15 bit

Joint entropy, conditional entropy and the chain rule

With two random variables, the joint entropy H(X, Y) is the entropy of the pair, computed on p(x, y). The conditional entropy H(Y|X) is the uncertainty that remains about Y when X is known, averaged over all values of X: H(Y|X) = Σ_x p(x) · H(Y|X=x).

The chain rule says that the uncertainty of the pair is that of the first element plus that of the second given the first: H(X, Y) = H(X) + H(Y|X), and it is symmetric when the roles are swapped.

The proof takes three steps. From the definition of conditional probability, p(x, y) = p(x) · p(y|x), and the logarithm of a product is the sum of the logarithms: −Σ p(x, y) log p(x, y) splits into −Σ p(x, y) log p(x) and −Σ p(x, y) log p(y|x).

In the first term the logarithm does not depend on y, so summing over y leaves Σ_x p(x) log p(x), that is, H(X). The second term is, by definition, H(Y|X).

For three variables the rule is applied twice, and in general H(X₁, ..., X_n) is the sum of the entropies of each variable given everything that precedes it.

The listing tests the rule on a small joint distribution: two words of an imaginary text, the subject (cat or dog) and the verb (runs or sleeps), with probabilities 0.4, 0.1, 0.3 and 0.2 chosen for the example. H(Y|X) is computed twice: from the definition (weighted mean of the entropies of the conditionals, printed one by one) and as the difference H(X, Y) − H(X).

from math import log2

joint = {
    ("cat", "runs"): 0.4, ("cat", "sleeps"): 0.1,
    ("dog", "runs"): 0.3, ("dog", "sleeps"): 0.2,
}


def H(ps):
    return -sum(p * log2(p) for p in ps if p > 0)


px, py = {}, {}
for (x, y), p in joint.items():
    px[x] = px.get(x, 0) + p
    py[y] = py.get(y, 0) + p

H_x, H_y, H_xy = H(px.values()), H(py.values()), H(joint.values())

# H(Y|X) from the definition: the mean, weighted by p(x), of the entropies of p(y|x)
H_y_dato_x = 0.0
for x in px:
    h = H([joint[(x, y)] / px[x] for y in py])
    print(f"H(Y|X={x}) = {h:.4f} bit")
    H_y_dato_x += px[x] * h

print(f"H(X)={H_x:.4f}  H(Y)={H_y:.4f}  H(X,Y)={H_xy:.4f}")
print(f"H(Y|X) from the definition = {H_y_dato_x:.4f}")
print(f"H(X,Y) - H(X) (chain rule) = {H_xy - H_x:.4f}")

H_x_dato_y = sum(
    py[y] * H([joint[(x, y)] / py[y] for x in px]) for y in py
)
print(f"H(X|Y) = {H_x_dato_y:.4f}   H(X,Y) - H(Y) = {H_xy - H_y:.4f}")

# Output:
# H(Y|X=cat) = 0.7219 bit
# H(Y|X=dog) = 0.9710 bit
# H(X)=1.0000  H(Y)=0.8813  H(X,Y)=1.8464
# H(Y|X) from the definition = 0.8464
# H(X,Y) - H(X) (chain rule) = 0.8464
# H(X|Y) = 0.9651   H(X,Y) - H(Y) = 0.9651

The two ways give 0.8464 bits, and the same holds for H(X|Y) = 0.9651.

Look at the two lines on the conditionals by value: if the subject is "cat" the uncertainty about the verb drops to 0.7219 bits, but if it is "dog" it rises to 0.9710, more than the 0.8813 bits of H(Y) without a condition. Knowing a specific value of X can therefore increase the uncertainty about Y. What it can never do is increase it on average: H(Y|X) ≤ H(Y), here 0.8464 against 0.8813, with equality only if X and Y are independent.

The average gain, 0.0349 bits, is the mutual information covered in article 02 of the series. The third part of the properties listing above verified the chain rule on 20,000 random 3×4 joint distributions (largest gap 1.3·10⁻¹⁵ bits, that is, rounding).

What entropy says, and what it does not

The properties that really matter are four, and the order in which you list them does not change the meaning.

• H(X) ≥ 0, with equality only if one outcome has probability 1 (this is property 1 in Shannon's paper).
• H(X) ≤ log₂ |X|, with equality only if the outcomes are equally likely: 3 bits for eight symbols, at most.
• Entropy is a concave function of the probabilities, as verified above.
• If X and Y are independent, H(X, Y) = H(X) + H(Y): it is the chain rule with H(Y|X) = H(Y).

The first and the second are the two extremes needed when comparing with codes: entropy is the minimum average cost of description, and it makes no sense to expect to go below zero or above log₂ |X|, because with equiprobable symbols a fixed-length code is already optimal.

One thing entropy does not say is how "informative" a single message is in the sense of meaning: it only measures the statistical unpredictability of the source, and for this reason its value depends on the probabilistic model you attribute to it, not on the data themselves.

Estimating entropy from data: the estimate is biased

In practice the probabilities are not known, they are estimated from frequencies. Replacing the probabilities with the observed frequencies is the obvious approach, called the plug-in estimator, and it has a systematic flaw: on average it underestimates the entropy. The observed frequency has the true probability as its mean, entropy is concave, and by Jensen's inequality the mean of the entropy of the frequencies does not exceed the entropy of the mean. The listing measures it on a coin with p = (0.7, 0.3), whose true entropy is 0.8813 bits, drawing 4000 samples for each of the four sizes n and reporting the mean of the estimates with its standard error.

import numpy as np
from math import log, log2

rng = np.random.default_rng(12345)
p = np.array([0.7, 0.3])
vera = float(-(p * np.log2(p)).sum())
print(f"true entropy: {vera:.4f} bit")
print("      n   mean est.   std. error   bias          theory -(k-1)/(2n ln2)")
for n in (10, 100, 1000, 10000):
    stime = []
    for _ in range(4000):
        c = np.bincount(rng.choice(2, size=n, p=p), minlength=2) / n
        c = c[c > 0]
        stime.append(float(-(c * np.log2(c)).sum()))
    s = np.array(stime)
    err = s.std(ddof=1) / np.sqrt(len(s))
    print(f"{n:7d}   {s.mean():.4f}      {err:.4f}        {s.mean() - vera:+.4f}       {-1 / (2 * n * log(2)):+.4f}")

# Output:
# true entropy: 0.8813 bit
#       n   mean est.   std. error   bias          theory -(k-1)/(2n ln2)
#      10   0.8033      0.0033        -0.0780       -0.0721
#     100   0.8738      0.0009        -0.0075       -0.0072
#    1000   0.8811      0.0003        -0.0002       -0.0007
#   10000   0.8812      0.0001        -0.0000       -0.0001

With 10 draws the mean estimate is 0.8033: it is off by 0.078 bits, almost 9% of the value. With 100 draws the bias falls to −0.0075, with 1000 it is of the order of the error (−0.0002 ± 0.0003) and with 10,000 it vanishes.

The last column is the first-order correction −(k−1)/(2n ln 2), with k the number of outcomes: I used it as an order of magnitude and did not prove it here; it matches the measurement for n = 100, for n = 1000 it stays within two standard errors and for n = 10 it slightly underestimates (−0.072 against −0.078), because with so few data the approximation does not hold.

The practical lesson holds for everything that estimates entropies, mutual informations or divergences from counts: with few data and many symbols the number obtained is systematically too low, and a comparison between samples of different size is distorted.

The entropy of real numbers can be negative

For a continuous variable with density f(x) the differential entropy is defined as h(X) = −∫ f(x) log₂ f(x) dx. It is not the natural extension of discrete entropy, and the sign is the proof: for the Gaussian of variance σ² it equals ½ log₂(2πeσ²), and with σ = 0.01 the logarithm contains a number smaller than 1, so h is negative.

The listing computes that value in three ways (closed form, the entropy function of scipy.stats, numerical integral with quad) and then discretises the same Gaussian into cells of width Δ to see what happens to the discrete entropy.

import numpy as np
from math import log2, pi, e
from scipy import integrate, stats

sigma = 0.01
chiusa = 0.5 * log2(2 * pi * e * sigma**2)                  # closed form, in bits
scipy_ = stats.norm(0, sigma).entropy() / np.log(2)          # library (returns nats)
f = lambda x: stats.norm.pdf(x, 0, sigma)
numerica, _ = integrate.quad(lambda x: -f(x) * np.log2(f(x)), -10 * sigma, 10 * sigma, points=[0])
print(f"h(N(0, 0.01^2)): closed form {chiusa:.4f}  scipy {scipy_:.4f}  integral {numerica:.4f} bit")

# same Gaussian, discretised into cells of width delta: the entropy is discrete, and positive
for delta in (1e-2, 1e-3, 1e-4):
    bordi = np.arange(-10 * sigma, 10 * sigma + delta, delta)
    p = np.diff(stats.norm.cdf(bordi, 0, sigma))
    p = p[p > 0]
    H_disc = float(-(p * np.log2(p)).sum())
    print(f"delta={delta:g}: discrete H {H_disc:8.4f}   h - log2(delta) = {chiusa - log2(delta):8.4f}")

# changing the unit of measure (x -> a·x) adds log2(a) to the differential entropy
print("h with sigma 0.01:", round(chiusa, 4), "  h with sigma 10 (a = 1000):",
      round(0.5 * log2(2 * pi * e * 10.0**2), 4), "  difference:", round(log2(1000), 4))

# Output:
# h(N(0, 0.01^2)): closed form -4.5968  scipy -4.5968  integral -4.5968 bit
# delta=0.01: discrete H   2.1048   h - log2(delta) =   2.0471
# delta=0.001: discrete H   5.3696   h - log2(delta) =   5.3690
# delta=0.0001: discrete H   8.6910   h - log2(delta) =   8.6910
# h with sigma 0.01: -4.5968   h with sigma 10 (a = 1000): 5.369   difference: 9.9658

The three calculations give −4.5968 bits.

The reason for the sign is that f(x) is a density and can exceed 1: a narrow Gaussian has a peak of 40, and log₂ 40 is positive, so its contribution to the integral is negative.

The rows with the discretisation show what h really measures: the discrete entropy of the cells is positive and grows by one bit each time the cells are halved, and it is close to h − log₂ Δ (5.3696 against 5.3690 for Δ = 0.001, and 8.6910 in both calculations for Δ = 0.0001; for Δ = 0.01 the cell is as wide as σ and the difference rises to 0.06 bits).

Changing the unit of measure multiplies x by a and adds log₂ a to h: taking σ from 0.01 to 10 moves it from −4.5968 to 5.3690, with a difference of 9.9658 = log₂ 1000. This is why h makes sense mainly in differences: h(X) and h(X|Y) change by the same constant and the mutual information, which subtracts them, does not depend on the unit. To describe a real signal in bits you discretise it and state the cell width.

Typical mistakes

• Saying that a symbol "costs" H(X) bits. H is an average: a rare symbol costs many bits (log₂(1/p)), a frequent one few.
• Comparing entropies in different bases. 0.693 nats are 1 bit: if two numbers do not match, check the unit first.
• Estimating entropy on few data and trusting it. With the bias above, a small value can be the sign of a small sample.
• Forgetting that it depends on the model. The entropy of a text is different if the symbols are letters, words or pairs of letters: the uncertainty belongs to the source as you described it.

The third mistake is the one the code does not flag: no exception warns that the number is too low, and the value looks plausible. The others are avoided with discipline about units and about the definition of the problem. All of them stem from the same idea: entropy is a property of a probability distribution, not of a message.

What you can do now

You can compute the entropy of a distribution and verify it with a second calculation, you can say which three properties determine it and why Shannon himself regards them as a plausibility argument, you can prove the chain rule and use it to compute H(Y|X) without starting from the definition, and you can recognise that conditioning on a value can increase uncertainty while on average it cannot. You also know that estimating an entropy from counts is biased for small samples, and that the entropy of real numbers can be negative without contradiction.

The next step is to measure how much uncertainty two variables share, and how well one distribution approximates another: article 02 of the series defines mutual information and Kullback-Leibler divergence. The list of all the articles is on the series page; for conditional probability and discrete distributions, the prerequisite is Discrete random variables.

Later in the series you will also find article 04 on the noisy channel, article 05 on error-correcting codes and article 06 on lossy compression.