Entropy

H(p) = −Σ p log p is the average surprise of a distribution — the minimum average bits per symbol — maximal when p is uniform.

5 min read443 wordscore5 viewsupdated 2026-10-03

Definition

Entropy H(X)=−∑xp(x)log⁡p(x)H(X)=-\sum_x p(x)\log p(x) is the expected surprise of a random variable XX with distribution pp: how uncertain its outcome is before you observe it, measured as the average number of bits an optimal code needs per outcome.

At a glance

Notation
H(X)H(X) or H(p)H(p); convention 0log⁡0=00\log 0=0
Units
bits with log⁡2\log_2, nats with ln⁡\ln; 1 nat=1/ln⁡2≈1.4431\text{ nat}=1/\ln2\approx1.443 bits
Range
0≤H(X)≤log⁡2K0\le H(X)\le\log_2 K for KK outcomes
Key property
zero iff the outcome is certain; maximal iff all outcomes are equally likely
Prerequisites
random variables & expectation, logarithms
Used in
decision-tree splits, cross-entropy loss, mutual information, compression, perplexity

The intuition

Learning that a certain event happened tells you nothing. Learning that a one-in-a-million event happened tells you a lot. So the information in an outcome should grow as its probability falls — and for two independent outcomes, the information should add. The logarithm is the function that does both: p(x)p(y)p(x)p(y) becomes −log⁡p(x)−log⁡p(y)-\log p(x)-\log p(y).

Entropy is that surprise, averaged over outcomes. A fair coin has 1 bit: one yes/no question settles it. A coin that lands heads 90% of the time has only 0.469 bits — you mostly know what is coming.

The math

I(x)=−log⁡2p(x),H(X)=E[I(X)]=−∑xp(x)log⁡2p(x)I(x)=-\log_2 p(x),\qquad H(X)=\mathbb{E}\big[I(X)\big]=-\sum_{x}p(x)\log_2 p(x)
I(x)I(x)
surprise (self-information) of outcome xx, in bits
p(x)p(x)
probability of outcome xx

Bounds. Each term is non-negative, so H≥0H\ge0, with equality only when one outcome has probability 1. By Jensen's inequality, H(X)=E[log⁡21p(X)]≤log⁡2E[1p(X)]=log⁡2KH(X)=\mathbb{E}[\log_2\tfrac{1}{p(X)}]\le\log_2\mathbb{E}[\tfrac{1}{p(X)}]=\log_2K, with equality only for the uniform distribution.

Coding. Shannon's source-coding theorem: no uniquely decodable code can use fewer than HH bits per symbol on average, and a Huffman code always gets within one bit:

H(X) ≤ LHuffman < H(X)+1,L=∑xp(x) ℓ(x)H(X)\ \le\ L_{\text{Huffman}}\ <\ H(X)+1,\qquad L=\sum_x p(x)\,\ell(x)
ℓ(x)\ell(x)
length in bits of the codeword for xx

Two variables. The chain rule H(X,Y)=H(X)+H(Y∣X)H(X,Y)=H(X)+H(Y\mid X) splits joint uncertainty into "what XX tells you" plus "what remains about YY". Conditioning never increases entropy on average, and the reduction is the mutual information:

I(X;Y)=H(Y)−H(Y∣X) ≥0,I(X;Y)=0  ⟺  X⊥YI(X;Y)=H(Y)-H(Y\mid X)\ \ge 0,\qquad I(X;Y)=0\iff X\perp Y

See it

uniform 1/41.00 bA0.502.00 bB0.253.00 bC0.133.00 bD0.13drag bar tops · orange = surprise −log₂ pᵢ (bits)
H(p) = 1.750 bitsmax log₂4 = 2.000

Huffman lengths: A1B2C3D3

avg code length L = 1.750 · H ≤ L < H + 1 ✓

symbols4preset

Set symbols to 2 to see the binary entropy curve.

fig.Drag the bars. Orange labels are each symbol's surprise. The skewed preset (½, ¼, ⅛, ⅛) has H = 1.75 bits, and its Huffman code (1, 2, 3, 3 bits) meets it exactly; with 2 symbols the inset traces H(p), peaking at 1 bit.

Worked example

p=(12,14,18,18)p=(\tfrac12,\tfrac14,\tfrac18,\tfrac18): H=12⋅1+14⋅2+18⋅3+18⋅3=1.75H=\tfrac12\cdot1+\tfrac14\cdot2+\tfrac18\cdot3+\tfrac18\cdot3=1.75 bits. The codewords 0, 10, 110, 111 have lengths equal to each symbol's surprise, so L=1.75L=1.75 — optimal. Uniform over 4 outcomes needs log⁡24=2\log_24=2 bits; skew saves 0.25 bits per symbol.

Information gain. A node with 5 positives and 5 negatives has H=1H=1 bit. A split sends (4+, 0−) left and (1+, 5−) right: HL=0H_L=0, HR=−16log⁡216−56log⁡256=0.650H_R=-\tfrac16\log_2\tfrac16-\tfrac56\log_2\tfrac56=0.650. Weighted child entropy =0.4⋅0+0.6⋅0.650=0.390=0.4\cdot0+0.6\cdot0.650=0.390, so the gain is 1−0.390=0.6101-0.390=0.610 bits.

In code

python
1import numpy as np
2from scipy.stats import entropy
3
4p = np.array([0.5, 0.25, 0.125, 0.125])
5-(p * np.log2(p)).sum() # 1.75 bits
6entropy(p, base=2) # 1.75 bits
7entropy(p) # 1.213 nats
8
9def info_gain(y, mask): # y: integer labels, mask: boolean split
10 H = lambda v: entropy(np.bincount(v), base=2)
11 w = mask.mean()
12 return H(y) - w * H(y[mask]) - (1 - w) * H(y[~mask])
scipy.stats.entropy normalizes its input, handles zeros, and uses nats unless you pass base=2.

Where it's used

Decision trees

ID3 / C4.5 and criterion="entropy" choose the split with the largest information gain.

Feature selection

Mutual information I(X;Y)I(X;Y) ranks features by how much they reduce uncertainty about the target — and, unlike correlation, catches nonlinear dependence.

Uncertainty sampling

Active learning labels the examples whose predicted class distribution has the highest entropy.

Reinforcement learning

An entropy bonus on the policy keeps it exploring instead of collapsing onto one action too early.

Check yourself

A fair 8-sided die has entropy…

Check yourself

Which distribution over 4 outcomes has the highest entropy?

Remember

  • ✓Surprise −log⁡p(x)-\log p(x); entropy is its average, −∑plog⁡p-\sum p\log p.
  • ✓0≤H≤log⁡2K0\le H\le\log_2K: zero when certain, maximal when uniform.
  • ✓HH is the floor on average code length; Huffman achieves H≤L<H+1H\le L<H+1.
  • ✓Information gain and mutual information are reductions in entropy.
← back to Mathematics roadmap