Shannon Entropy

H(X) = - _x p(x) p(x) — the average surprise per draw.

The idea

Entropy is the standard measure of the uncertainty in a random variable.

Shannon built it from the surprise of a single outcome. An outcome of probability $p$ carries surprise $\log \frac{1}{p}$: a certain outcome, with $p = 1$, carries no surprise, and the rarer an outcome, the larger its surprise. Define the entropy of $X$ as the average surprise, each outcome weighted by its probability:

$H(X) = \sum_x p(x) \log \frac{1}{p(x)} = -\sum_x p(x) \log p(x).$

The definition never looks at what the outcomes are, only at how probability is divided among them, so relabelling the outcomes leaves $H(X)$ unchanged.

The base of the logarithm sets the unit. With $\log_2$ the entropy is measured in bits; with the natural logarithm it is measured in nats; and since $\log_2 x = \ln x / \ln 2$, the two differ by the constant factor $\ln 2$. Unless we say otherwise, logarithms are base $2$ and entropies are in bits.

Ways to work on it

• Walkthrough. Compute the entropy of fair and biased coins, and meet joint and conditional entropy.
• Practice. Compute the exact entropy in bits of a hand-friendly distribution.
• Hardest. Work with entropy in units other than bits, and find the distributions that maximize it.

Not sure where to start? Take the ten-question placement test.