A Characterization of Entropy in Terms of Information Loss

Baez, Fritz, Leinster · 2011 · arXiv:1106.1791

Assumes you've seen 🍞 Markov categories. 5 minutes.

Information loss

When a stochastic function processes a distribution, some information is lost. The question is: how do you measure that loss? Shannon defined entropy in 1948. Baez, Fritz, and Leinster proved that Shannon's definition is the only one that satisfies three natural properties.

; Shannon entropy: H(p) = -Σ p·log₂(p)
(define (log2 x) (/ (log x) (log 2)))

(define (entropy probs)
  (- (apply + (map (lambda (p)
    (if (> p 0) (* p (log2 p)) 0))
  probs))))

(display "Uniform over 4: H = ")
(display (entropy '(0.25 0.25 0.25 0.25)))
(newline)
(display "Fair coin:      H = ")
(display (entropy '(0.5 0.5)))
(newline)
(display "Certain:        H = ")
(display (entropy '(1.0)))

import math

def entropy(dist):
    return -sum(p * math.log2(p) for p in dist.values() if p > 0)

# Uniform distribution: maximum entropy (maximum surprise)
uniform = {1: 0.25, 2: 0.25, 3: 0.25, 4: 0.25}
print(f"Uniform over 4: H = {entropy(uniform):.2f} bits")

# Certain outcome: zero entropy (no surprise)
certain = {1: 1.0}
print(f"Certain:        H = {entropy(certain):.2f} bits")

# Biased coin: between 0 and 1
biased = {"H": 0.9, "T": 0.1}
print(f"Biased coin:    H = {entropy(biased):.2f} bits")

# Fair coin: exactly 1 bit
fair = {"H": 0.5, "T": 0.5}
print(f"Fair coin:      H = {entropy(fair):.2f} bits")

print()
print("More surprise = more entropy.")
print("Certain = 0 bits. Fair coin = 1 bit.")

Functoriality — the key constraint

The paper's theorem: Shannon entropy is the unique measure of information loss that is functorial. Functorial means: the loss of a composite equals the sum of the losses of the parts.

If you process data in two steps, the total information lost is the loss from step 1 plus the loss from step 2. No other definition of "loss" has this property (up to a constant factor).

; Functoriality: loss of composite = sum of losses
(define (log2 x) (/ (log x) (log 2)))

(define (entropy probs)
  (- (apply + (map (lambda (p)
    (if (> p 0) (* p (log2 p)) 0)) probs))))

; Step 1: 4 uniform -> 2 uniform (merge pairs). Loss = 1 bit.
; Step 2: 2 uniform -> 1 certain. Loss = 1 bit.
; Total: 2 bits = 1 + 1. Functorial.

(define h-before (entropy '(0.25 0.25 0.25 0.25)))
(define h-after1 (entropy '(0.5 0.5)))
(define h-after2 (entropy '(1.0)))

(display "H(input) = ") (display h-before) (newline)
(display "H(step1) = ") (display h-after1) (newline)
(display "H(step2) = ") (display h-after2) (newline)
(display "Loss 1 = ") (display (- h-before h-after1)) (newline)
(display "Loss 2 = ") (display (- h-after1 h-after2)) (newline)
(display "Total  = ") (display (- h-before h-after2)) (newline)
; Total = Loss 1 + Loss 2. That's functoriality.

import math

def entropy(dist):
    return -sum(p * math.log2(p) for p in dist.values() if p > 0)

input_dist = {1: 0.25, 2: 0.25, 3: 0.25, 4: 0.25}
after1 = {"A": 0.5, "B": 0.5}
after2 = {"X": 1.0}

h0, h1, h2 = entropy(input_dist), entropy(after1), entropy(after2)
print(f"Loss 1: {h0-h1:.2f}, Loss 2: {h1-h2:.2f}, Total: {h0-h2:.2f}")
print(f"Functorial: {h0-h2:.2f} = {(h0-h1)+(h1-h2):.2f} ✓")

Data processing inequality

A corollary: information can only decrease through processing. You can't create information by computing — you can only lose it or preserve it. This is the data processing inequality (DPI), proved categorically.

; DPI: H(output) <= H(input). Always.
(define (log2 x) (/ (log x) (log 2)))

(define (entropy probs)
  (- (apply + (map (lambda (p)
    (if (> p 0) (* p (log2 p)) 0)) probs))))

(define h-in (entropy '(0.1 0.2 0.3 0.4)))
(define h-lossy (entropy '(0.3 0.7)))  ; merge 1,2 and 3,4

(display "H(input) = ") (display h-in) (newline)
(display "H(lossy) = ") (display h-lossy) (newline)
(display "Lost: ") (display (- h-in h-lossy)) (newline)
; H(output) <= H(input). You can't gain bits by computing.

import math

def entropy(dist):
    return -sum(p * math.log2(p) for p in dist.values() if p > 0)

h_in = entropy({1: 0.1, 2: 0.2, 3: 0.3, 4: 0.4})
h_lossy = entropy({"low": 0.3, "high": 0.7})

print(f"H(input) = {h_in:.3f}, H(lossy) = {h_lossy:.3f}")
print(f"Lost: {h_in - h_lossy:.3f} bits. DPI holds ✓")

The uniqueness theorem

The paper's main result (Theorem 4): any function F that assigns a real number to a morphism in FinProb (finite probability distributions) and satisfies:

1. Functoriality — F(g ∘ f) = F(f) + F(g)
2. Convex linearity — F respects mixtures of distributions
3. Continuity — small changes in probabilities → small changes in F

...must be F(f) = c · (H(input) − H(output)) for some constant c ≥ 0. That's Shannon entropy, up to scale. There is no other option.

; Uniqueness: F(f) = c · (H(input) - H(output))
; Shannon entropy is the ONLY such F (up to scale).
(define (log2 x) (/ (log x) (log 2)))

(define (entropy probs)
  (- (apply + (map (lambda (p)
    (if (> p 0) (* p (log2 p)) 0)) probs))))

(define h-in  (entropy '(0.25 0.25 0.25 0.25)))
(define h-out (entropy '(0.5 0.5)))
(define F (- h-in h-out))

(display "F(f) = H(in) - H(out) = ") (display F) (newline)
; This is the ONLY measure that is:
; 1. Functorial  2. Convex-linear  3. Continuous
; Shannon didn't choose entropy. The axioms forced it.

import math

def entropy(dist):
    return -sum(p * math.log2(p) for p in dist.values() if p > 0)

h_in = entropy({1: 0.25, 2: 0.25, 3: 0.25, 4: 0.25})
h_out = entropy({"A": 0.5, "B": 0.5})
print(f"F(f) = {h_in:.2f} - {h_out:.2f} = {h_in - h_out:.2f} bits")
print("The only functorial, convex-linear, continuous measure.")

Notation reference

Translation notes

All examples use finite distributions with explicit probabilities. The paper's theorem holds over FinProb (finite probability distributions with morphisms that preserve total mass). For example: the DPI example on this page merges four outcomes into two and checks that entropy decreases. In the paper, the same inequality applies to a noisy communication channel transmitting continuous signals — the entropy of the received signal is always less than or equal to the entropy of the transmitted signal, regardless of the channel's noise model. The inequality is identical. The distributions are not.

The uniqueness result requires all three axioms — dropping any one allows other measures. Every example is Simplified.

Framework connection: Shannon entropy is the unique measure of the Natural Framework pipeline's information budget — DPI governs how bits flow through each stage. (The Natural Framework)

Ready for the real thing? Read the paper. Start at Theorem 4 (p.8) for the uniqueness result. Short paper — 15 pages.