Information and communication theory, circuits Theorem

Characterization of Shannon entropy

Builds on Probability distribution Continuous function Functional equation

Statement

For each integer $n \ge 2$ , let $\Delta_n$ be the set of probability vectors $(p_1, \dots, p_n)$ with $p_i \ge 0$ and $p_1 + \cdots + p_n = 1$ . Let $H$ be a function defined on $\bigcup_{n \ge 2} \Delta_n$ with real values. Assume:

The function $p \mapsto H(p, 1 - p)$ is continuous on $[0, 1]$ .
$H$ is symmetric: $H(p_1, \dots, p_n)$ does not change when the $p_i$ are permuted.
$H(\frac{1}{2}, \frac{1}{2}) = 1$ .
For all $n \ge 2$ , all $(p_1, \dots, p_n) \in \Delta_n$ with $p_n > 0$ , and all $q_1, q_2 \ge 0$ with $q_1 + q_2 = p_n$ , $H(p_1, \dots, p_{n-1}, q_1, q_2) = H(p_1, \dots, p_n) + p_n \, H\left(\frac{q_1}{p_n}, \frac{q_2}{p_n}\right).$

Then for every $n \ge 2$ and every $(p_1, \dots, p_n) \in \Delta_n$ , $H(p_1, \dots, p_n) = -\sum_{i=1}^{n} p_i \log_2 p_i,$ with the convention $0 \log_2 0 = 0$ . Conversely, this function has properties 1 to 4.

Remarks

The formula is the Shannon entropy of a finite probability distribution, measured in bits. This set of axioms is due to Faddeev; Shannon and Khinchin gave earlier characterizations with stronger hypotheses. The proof first studies $F(n) = H(\frac{1}{n}, \dots, \frac{1}{n})$ : property 4 gives $F(mn) = F(m) + F(n)$ , and the remaining properties force $F(n) = \log_2 n$ . Grouping equal masses then gives the formula for rational probabilities, and continuity extends it to all probability vectors. The normalization 3 only fixes the unit; without it, $H$ is a constant multiple $c$ of the Shannon entropy.

Going deeper

For a student

The theorem is a solution of a functional equation: setting $f(p) = H(p, 1 - p)$ , the properties reduce to the fundamental equation of information $f(x) + (1 - x) f\left(\frac{y}{1 - x}\right) = f(y) + (1 - y) f\left(\frac{x}{1 - y}\right)$ for $x, y \in [0, 1)$ with $x + y \le 1$ . It explains why the logarithm, and no other function, appears in the entropy formula. Dropping or changing the recursivity axiom leads to other entropies, such as the Rényi entropies. Similar axiomatic characterizations exist for relative entropy and mutual information.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Continuous function concept
Functional equation concept
Probability distribution concept
Characterization of Shannon entropy statement

Tag	`3TERJ5C8QK`
URI	`m2://3TERJ5C8QK`
Kind	statement, theorem
Writing	W0 stub
MSC	94A17, 39B22
Status	This copy of the site has no build data. Run `m2 status 3TERJ5C8QK`.
About	Probability distribution
Uses	Probability distribution, Continuous function, Functional equation

Characterization of Shannon entropy

Statement

Remarks

Going deeper

For a student

Reading path

Further reading

What this page needs for W1

What links here