Shannon Entropy: The Exact Lower Bound on How Many Bits You Need

The core idea: surprise, averaged

Shannon started from a single demand: the information in an event should equal its surprise. An event of probability p carries self-information I(x) = −log₂ p(x), measured in bits. Three axioms force this exact form: information is non-negative, a certain event (p=1) carries zero information, and the information of two independent events adds — I(x,y) = I(x) + I(y) — which demands a logarithm, since log turns the product p(x)·p(y) into a sum.

Entropy is the expected self-information of a random variable X over an alphabet of n symbols:

H(X) = E[−log₂ p(X)] = −Σ p(xᵢ)·log₂ p(xᵢ)   (i = 1..n)

By convention 0·log₂ 0 = 0 (the limit as p→0⁺), so zero-probability symbols contribute nothing. The unit depends on the log base: bits for log₂, nats for the natural log, dits/hartleys for log₁₀. A fair coin has H = −(½·log₂ ½ + ½·log₂ ½) = 1 bit. A fair 8-sided die has H = log₂ 8 = 3 bits — you need exactly 3 yes/no questions to identify the face.

Two invariants: the 0 ≤ H ≤ log₂ n envelope

Entropy is bracketed by two tight bounds, and both extremes have a clean meaning:

• Lower bound H = 0 holds iff the distribution is a point mass — one symbol has p=1, the rest 0. No surprise, no information, nothing to encode. This follows because −p·log₂ p ≥ 0 for every term (since 0 ≤ p ≤ 1 makes log₂ p ≤ 0), and a sum of non-negative terms is zero only if each is.
• Upper bound H = log₂ n is achieved uniquely by the uniform distribution p(xᵢ) = 1/n. This is the maximum-entropy principle: absent any constraint, the flattest distribution is the most uncertain. It follows from Jensen's inequality applied to the concave log, or equivalently from D(p‖uniform) ≥ 0.

Entropy is concave in p, permutation-invariant (renaming symbols doesn't change it), and continuous. Adding an impossible symbol (p=0) leaves H unchanged. These properties are exactly what you want from a 'measure of uncertainty,' and Shannon proved this functional form is the only one satisfying his axioms up to the choice of log base (the constant sets the unit).

Why it's the true limit: the Source Coding Theorem

The reason entropy matters operationally is Shannon's Source Coding Theorem (1948). Suppose you emit i.i.d. symbols from distribution p and want a uniquely decodable binary code with expected codeword length L̄. Then:

H(X) ≤ L̄ < H(X) + 1        (per symbol, best code)

The lower bound L̄ ≥ H is a hard floor — no lossless scheme can average fewer than H bits per symbol. The proof combines the Kraft inequality (Σ 2⁻ℓᵢ ≤ 1 for any prefix code) with Gibbs' inequality (−Σ p·log₂ q ≥ H(p), with equality iff q=p). The ideal codeword length for symbol xᵢ is ℓᵢ = −log₂ p(xᵢ), which is non-integer in general — the '+1' slack is the rounding penalty ⌈−log₂ p⌉.

Huffman coding gets within that 1 bit and is provably optimal among integer-length prefix codes. To crush the gap toward zero, block k symbols together: encoding k-tuples gives L̄/k → H as k → ∞. Arithmetic coding and range coding sidestep the integer-length limitation entirely and reach essentially H bits per symbol without blocking — which is why they, not Huffman, sit at the entropy-coding stage of modern codecs.

Computing entropy: an O(n) pass, and the estimation trap

Given probabilities p₁..pₙ, computing H is a straightforward reduction:

function entropy(p[1..n]):        # p is a probability vector
    H = 0.0
    for i = 1 to n:
        if p[i] > 0:              # skip 0·log0, avoid log(0) = −∞
            H -= p[i] * log2(p[i])
    return H                       # in bits

• Time: Θ(n), one pass over the alphabet. Space: O(1) beyond the input.
• From raw data of length m over n symbols, first histogram in O(m) time and O(n) space, normalize counts to probabilities, then run the sum — total O(m + n).
• Numerical care: guard p[i] > 0 to avoid log(0); use a stable log2. For log-domain inputs, compute via a log-sum-exp-style reduction to avoid underflow.

The subtle failure is estimation bias. Plugging empirical frequencies into H (the 'plug-in' or maximum-likelihood estimator) systematically underestimates true entropy, because finite samples miss rare symbols and look artificially predictable. The bias is roughly −(n−1)/(2m·ln2) bits. Corrections — Miller–Madow, the NSB estimator, or Bayesian priors — matter when the alphabet n is comparable to the sample size m (common in genomics and NLP with huge vocabularies).

Where it runs at scale: compression, ML, and channels

Entropy is not a blackboard curiosity — it is a load-bearing number in production systems:

• Lossless compression. gzip/DEFLATE (LZ77 + Huffman), PNG, JPEG, H.264/H.265, and Zstandard all end in an entropy-coding stage. Modern codecs use arithmetic/range coding or ANS (Asymmetric Numeral Systems, used in Zstd, LZFSE, and the JPEG-XL pipeline) to hit the H limit closely and cheaply.
• Decision trees. ID3, C4.5, and the split criterion in random forests and gradient boosting pick the feature maximizing information gain = H(parent) − Σ weighted H(children) = mutual information I(X;Y). (Gini impurity is the cheaper second-order cousin.)
• Neural network training. The cross-entropy loss −Σ p·log q is the workhorse classification objective; minimizing it minimizes KL(p‖q) since H(p,q) = H(p) + D(p‖q) and H(p) is fixed. The softmax output is the natural partner.
• Channel capacity. Shannon's noisy-channel theorem sets the max reliable rate via mutual information; capacity C = B·log₂(1 + S/N) governs Wi-Fi, LTE/5G, DSL, and the Voyager deep-space link.
• Security & systems. Password/key strength is measured in bits of entropy; /dev/random tracks an entropy pool; hashing and load balancing want high-entropy inputs.

Pitfalls, edge cases, and the variants you'll actually meet

Entropy is easy to misapply. The traps that bite in practice:

• Independence assumption. H(X) = −Σ p·log p assumes i.i.d. symbols. Real data has structure: English text has ~4.7 bits/char under a unigram model but drops to roughly 1.0–1.3 bits/char once you condition on context (Shannon's own estimate). The right object is the entropy rate lim H(Xₙ | X₁..Xₙ₋₁), which is why context-modeling compressors (PPM, LZMA, LLMs) crush order-0 Huffman.
• Units. Mixing nats and bits is a factor of ln2 ≈ 0.693. ML libraries default to nats (natural log); coding theory uses bits. Report the base.
• Continuous variables. Differential entropy h(X) = −∫ f·log f dx is not a limit of discrete H — it can be negative and is not scale-invariant. Use it with care; it does not measure absolute bits.
• Generalizations. Rényi entropy Hₐ = (1/(1−α))·log Σ pᵢᵅ parametrizes a family: α→1 recovers Shannon, α=2 gives collision entropy (used in hashing/privacy), α→∞ gives min-entropy H∞ = −log max pᵢ (the security-relevant worst case for guessing). Tsallis entropy is the non-extensive physics cousin.

Rule of thumb: entropy tells you the floor; the gap between your compressor and H measures how much structure your model is still leaving on the table.

Entropy and its close relatives — what each quantity measures

Quantity	Formula	Measures	Minimum	Key use
Entropy H(X)	−Σ p·log₂ p	Avg bits to encode source p	0 (deterministic)	Compression limit
Cross-entropy H(p,q)	−Σ p·log₂ q	Avg bits using code for q	H(p) when q=p	ML loss function
KL divergence D(p‖q)	Σ p·log₂(p/q)	Extra bits from wrong model q	0 (p=q)	Distribution distance
Conditional H(X|Y)	Σ p(y)·H(X|Y=y)	Residual uncertainty given Y	0 (Y fixes X)	Info gain / feature splits
Mutual info I(X;Y)	H(X) − H(X|Y)	Bits Y reveals about X	0 (independent)	Feature selection