Shannon Entropy as the Expected Cost of an Outcome

An outcome that occurs with probability 1/8 conveys three bits. An outcome with probability 1/1000 conveys about ten. Those numbers are not a convention imposed on the world; they follow from a single requirement about how information should behave when independent things happen together, and everything else in information theory inherits the consequences of that requirement.

Self-information fixes the scale

Learning that two independent events both occurred should tell us as much as learning about each of them separately, summed. Probabilities of independent events multiply, so the information measure must convert a product into a sum. Among continuous functions, only the logarithm does that, and this is the whole justification for the shape of the formula. For an outcome $x$ with probability $p(x)$:

$$I(x) = \log_2 \frac{1}{p(x)} = -\log_2 p(x)$$

The base fixes the unit. Base 2 gives bits, which matters because a binary digit is the physical resource that storage and transmission actually spend. Natural logarithms give nats, and one nat is $1/\ln 2 \approx 1.4427$ bits; base 10 gives hartleys, used occasionally in older literature. A fair coin toss yields exactly one bit, eight equiprobable outcomes yield three bits, and a thousand equiprobable outcomes yield $\log_2 1000 \approx 9.97$ bits.

Self-information is a strictly decreasing function of probability and is zero for an event that is certain. Note that it is unbounded above: an outcome of probability $2^{-100}$ costs a hundred bits, which is a statement about how surprising it would be, not about how much storage its description requires.

Entropy is the average of that quantity

A source emits symbols from an alphabet according to some distribution. Entropy is the expected self-information of one symbol, and it is the quantity that Prefix Codes, the Kraft Inequality, and Why Huffman Is Optimal turns into an actual code:

$$H(X) = -\sum_{x} p(x)\log_2 p(x) = \mathbb{E}[I(X)]$$

For a fair coin, $H = 1$ bit. For a coin biased 0.9 toward heads, $H \approx 0.469$ bits: the outcome is still binary, but it is worth less than half of one fair bit because it is predictable. For a uniform byte, $H = 8$ bits. For a constant, $H = 0$.

Three properties do most of the work later. Entropy is concave in the distribution, so for a $k$-symbol alphabet no distribution achieves more entropy than the uniform one. It is maximized by the uniform distribution at $\log_2 |\mathcal{X}|$, so an alphabet of 256 symbols can never carry more than 8 bits per symbol under any distribution. And it is zero exactly when the distribution is degenerate.

The term $0 \log 0$ is defined as zero. This is not an arbitrary patch: $x \log x \to 0$ as $x \to 0$, and the definition preserves continuity, which matters when probabilities are estimated and some symbols are never observed.

The formula extends to sources with memory only after taking a limit, which is the subject of Entropy Rate of a Markov Source and the Value of Context.

Entropy describes the distribution, not any particular sample. A specific message drawn from a high-entropy source can look highly structured in hindsight; the formula reports an average over the ensemble, and the average is what the coding theorems bound.

Conditioning, the chain rule, and mutual information

For two variables, the joint entropy satisfies the chain rule exactly:

$$H(X,Y) = H(X) + H(Y \mid X) = H(Y) + H(X \mid Y)$$

where $H(Y \mid X) = \sum_x p(x) H(Y \mid X = x)$ is an average of the entropies of the conditional distributions, weighted by how often each condition occurs. Two independent fair bits have joint entropy 2. If the second bit equals the first, the joint entropy is 1, and the conditional entropy $H(Y \mid X)$ is 0.

Conditioning never increases entropy: $H(Y \mid X) \le H(Y)$, with equality only when the variables are independent. The intuition is that knowing something cannot make a remaining uncertainty larger, and the proof is Jensen’s inequality applied to the concave logarithm. Equivalently, $H(X) \le H(X,Y)$: adding variables adds uncertainty.

Mutual information measures the overlap:

$$I(X;Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X,Y)$$

It is symmetric, nonnegative, and zero exactly when $X$ and $Y$ are independent. For the two-bit example where $Y = X$, it is 1 bit. Mutual information is the quantity that channel capacity maximizes, as Mutual Information and Channel Capacity develops in detail.

A further constraint is the data processing inequality. If $X \to Y \to Z$ forms a Markov chain, so that $Z$ depends on $X$ only through $Y$, then $I(X;Z) \le I(X;Y)$. No function applied to $Y$ can create information about $X$ that $Y$ did not already contain. This is why lossy preprocessing before a detector cannot improve the detector’s theoretical limit, and why the inequality is used to prove converses throughout the subject.

Estimating the number from data

In practice the distribution is unknown and entropy is estimated from counts. The plug-in estimator replaces $p(x)$ with the observed frequency $\hat{p}(x)$. It is biased downward, and the bias is not small for short samples.

The mechanism is simple: with $n$ samples, at most $n$ distinct values can be observed, so the estimate can never exceed $\log_2 n$ bits regardless of the true alphabet. A source uniform over $2^{32}$ symbols cannot show more than $\log_2 n$ bits from $n$ draws. For the maximum-likelihood estimator the leading bias term is about $(K-1)/(2n \ln 2)$ bits, where $K$ is the size of the full alphabet and $n$ the number of samples; adding that estimate back is the Miller–Madow correction. The correction helps but does not remove the dependence on the alphabet size, because $K$ is unknown or unknowable for a continuous signal, which is why estimating the entropy of text or of an analogue waveform is a genuinely difficult statistical problem rather than a one-line calculation.

import math
from collections import Counter

def entropy(symbols):
    n = len(symbols)
    counts = Counter(symbols)
    h = 0.0
    for c in counts.values():
        p = c / n
        h -= p * math.log2(p)   # 0 log 0 never occurs: counts are positive
    return h

def entropy_smoothed(symbols, alphabet, alpha=0.5):
    # Add-alpha smoothing; alphabet is the assumed set of symbols, not the observed one
    n = len(symbols)
    counts = Counter(symbols)
    total = n + alpha * len(alphabet)
    h = 0.0
    for s in alphabet:
        p = (counts.get(s, 0) + alpha) / total
        h -= p * math.log2(p)
    return h

The two functions differ in what they assume. The first treats unobserved symbols as impossible, which biases the estimate low and can report zero entropy for a source that merely happened not to repeat a value. The second assigns mass to the whole declared alphabet, which biases in the other direction when that alphabet is chosen too large. Neither is a neutral measurement; both encode a prior.

Where the number stops describing anything

Entropy is routinely confused with three neighbouring quantities.

Entropy is not Kolmogorov complexity. Under a uniform model over $n$-bit strings, every string has self-information $n$, including the string of all zeros and a string produced by a pseudorandom generator. Kolmogorov complexity instead measures the length of the shortest program that outputs a particular string, so the all-zero string is cheap and the pseudorandom one is not. Shannon entropy is a property of a source distribution and is computable from it; Kolmogorov complexity is a property of an individual object and is not computable at all.

Differential entropy is not a bit count. For a continuous variable with density $f$, the analogue is $h(X) = -\int f \log_2 f$, which can be negative: a uniform density on an interval of length $1/2$ has $h = -1$ bit. It also shifts by $\log_2 |a|$ under scaling by $a$, so it is only meaningful relative to a coordinate choice. It appears in the Gaussian rate-distortion formula and in channel capacity for continuous inputs, always in differences or as a maximum, never as an absolute count of bits.

Entropy is relative to a model. The same data yields different entropies under different assumed distributions, and the model that assigns high probability to what actually occurs reports the lower entropy. This is not a defect; it is the reason compression is possible at all. It also means that a reported entropy figure without the model is uninterpretable.

What entropy deliberately does not measure is significance. An outcome that matters and an outcome that does not, at equal probability, carry identical self-information. Shannon’s theory is about the cost of distinguishing among possibilities, and the cost depends only on how many possibilities there are and how likely each is.

Boundary conditions that change the answer

Three edge cases cause most practical mistakes.

Zero probabilities make the logarithm undefined, and every implementation must choose a convention. Smoothing avoids the undefined value but changes the quantity being estimated, sometimes by more than the signal being measured.

The alphabet partition matters. If symbols are grouped, the entropy of the group label plus the conditional entropy within groups equals the original entropy exactly: $H(X) = H(g(X)) + H(X \mid g(X))$. A gross partition keeps almost nothing, since most of the entropy sits in the conditional term, and collapsing two rare symbols into one label removes only the small amount their distinction was worth. Comparing entropy figures computed over different alphabets is meaningless.

Deterministic transformations cannot increase entropy: $H(f(X)) \le H(X)$ for any function $f$, with equality when $f$ is injective on the support. This is the discrete form of the data processing inequality, and it is the reason preprocessing that discards distinctions also discards capacity. The bound is tight only for injective maps, which is a useful test when a transformation is claimed to have increased the information content of its input.