ConceptDBISAI-written · not yet proofread

Entropy

Also Shannon Entropy

The entropy H(X) = −∑ p_i log₂ p_i of a discrete random variable X is its average information content in bits per symbol and the lower bound on the expected code length of any prefix-free encoding of X.

Know these firstRandom Variable

Formula#

Two values with probabilities $p, 1 - p$ : $H(p) = -p \log_2 p - (1 - p) \log_2 (1 - p)$ .
Uniform distribution over $n$ symbols: $H = -n \cdot \frac{1}{n} \log_2 \frac{1}{n} = \log_2 n$ .

Properties#

$\log_2(1/p_i)$ is the information content of symbol $x_i$ : rare symbols carry more information. $H(X)$ is its expected value.
Lower bound for compression: every prefix-free code for $X$ has expected code length $\sum_i p_i L_i \geq H(X)$ , and Shannon’s source coding theorem gives one with $< H(X) + 1$ (Entropy-Optimal Code).
$0 \leq H(X) \leq \log_2 n$ , with $H(X) = 0$ iff one $p_i = 1$ .

ProofProof with Lagrange multipliers

Maximize $H = -\sum_i p_i \log_2 p_i$ subject to $\sum_i p_i - 1 = 0$ . Lagrangian: $\mathcal{L} = -\sum_{i=1}^{n} p_i \log_2 p_i + \lambda \left(\sum_{i=1}^{n} p_i - 1\right)$
With $\log_2 p = \frac{\ln p}{\ln 2}$ and $(p \ln p)' = 1 + \ln p$ : $\frac{\partial \mathcal{L}}{\partial p_i} = -\log_2 p_i - \frac{1}{\ln 2} + \lambda = 0 \iff \log_2 p_i = \lambda - \frac{1}{\ln 2}.$ The right-hand side is the same for all $i$ , so all $p_i$ are equal.
$\frac{\partial \mathcal{L}}{\partial \lambda} = \sum_i p_i - 1 = 0$ , so $p_i = 1/n$ .
Maximum, not minimum: $\frac{\partial^2 H}{\partial p_i^2} = -\frac{1}{p_i \ln 2} < 0$ and the mixed second derivatives vanish, so $H$ is concave. (The exam allows assuming this; WS 16/17 Task 6.3 asks for the second derivative.)
$H(1/n, \ldots, 1/n) = \log_2 n$ . $\blacksquare$

Two values (DBIS Exam WS1516 (not published), Task 6.3): $H'(p) = \frac{1}{\ln 2}\left(-(1 + \ln p) + (1 + \ln(1-p))\right) = \frac{1}{\ln 2} \ln\frac{1-p}{p} = 0 \iff p = \frac{1}{2}$ , and $H''(p) = -\frac{1}{\ln 2 \cdot p(1-p)} < 0$ , so $p = 1/2$ is the maximum, $H(1/2) = 1$ bit.

Example#

Sequence $A, B, A, A, B, C, A, D$ with relative frequencies $\Pr(A) = \frac{1}{2}$ , $\Pr(B) = \frac{1}{4}$ , $\Pr(C) = \Pr(D) = \frac{1}{8}$ (DBIS Exam WS1920 (not published), Task 2.1):

H = \tfrac{1}{2} \cdot 1 + \tfrac{1}{4} \cdot 2 + 2 \cdot \tfrac{1}{8} \cdot 3 = 0.5 + 0.5 + 0.75 = 1.75 \text{ bits per symbol.}

Uniform over $1, \ldots, 8$ : $H = \log_2 8 = 3$ bits (DBIS Exam WS1819 (not published), Task 2.1).

Sources#

DBIS Exam WS2223 (not published) Task 1.3 (maximum entropy via Lagrange), DBIS Exam WS1617 (not published) Task 6.3, DBIS Exam WS1516 (not published) Task 6.3 (two values)
DBIS Exam WS1819 (not published) Task 2.1, DBIS Exam WS1920 (not published) Task 2.1, DBIS Exam WS2122 (not published) Task 2.3 (entropy of concrete distributions)
Not lectured in WS 25/26.

Connections

Mentioned in inline links3

Entropy-Optimal Code
Let a prefix-free code assign symbol $i$ (probability $p_i$ ) a codeword of length $L_i$ . Its expected code length is $\bar L = \sum_{i=1}^{n} p_i L_i$ . The code is entropy-optimal for $(p_i)$ if $\bar L = H(X)$ , the Entropy of the distribu… §
Lagrange Multipliers
Maximize $H = -\sum_i p_i \log_2 p_i$ s.t. $\sum_i p_i = 1$ . $\partial\mathcal{L}/\partial p_i = -\log_2 p_i - 1/\ln 2 + \lambda = 0$ gives the same $p_i$ for all $i$ , so $p_i = 1/n$ : the uniform distribution maximizes the Entropy. §
Encodings and Compression
Entropy — lower bound on the expected code length of any prefix-free code §
From prefix-freeness to optimality. A code is only usable without separators if it is prefix-free. Kraft’s inequality $\sum_i 2^{-L_i} \le 1$ characterises the code lengths a prefix-free code can have. Among these, the expected length… §

Search in these mentions →