Information and average information (entropy)

Information

The amount of information in an event measures the uncertainty it removes: the less likely the event, the more information its occurrence gives. For a symbol $x_k$ with probability $p_k$, the self-information is

$$I(x_k) = \log_2 \frac{1}{p_k} = -\log_2 p_k\ \text{bits}$$

Properties:

• $I = 0$ when $p_k = 1$ (a certain event gives no information).
• $I \ge 0$, and $I(x_j) > I(x_k)$ if $p_j < p_k$.
• For independent events, information adds: $I(x_j x_k) = I(x_j) + I(x_k)$.

Units: bits (base 2), nats (base $e$) or decits (base 10). Example: a fair coin toss gives $\log_2 2 = 1$ bit.

Average information (entropy) of a long sequence

Consider a discrete memoryless source with alphabet $\{x_1, x_2, \dots, x_M\}$ and probabilities $\{p_1, p_2, \dots, p_M\}$, where $\sum p_k = 1$. The symbols are statistically independent.

Step 1. Take a long message of $N$ symbols ($N \to \infty$). By the law of large numbers, symbol $x_k$ occurs about

$$n_k = p_k N \text{ times}$$

Step 2. Each occurrence of $x_k$ carries $\log_2 (1/p_k)$ bits. So the information from all occurrences of $x_k$ is

$$I_k = n_k \log_2 \frac{1}{p_k} = N p_k \log_2 \frac{1}{p_k}$$

Step 3. The symbols are independent, so the information adds. The total information in the message is

$$I_{total} = \sum_{k=1}^{M} I_k = N \sum_{k=1}^{M} p_k \log_2 \frac{1}{p_k}$$

Step 4. The average information per symbol, called the entropy, is

$$H = \frac{I_{total}}{N} = \sum_{k=1}^{M} p_k \log_2 \frac{1}{p_k} = -\sum_{k=1}^{M} p_k \log_2 p_k\ \text{bits/symbol}$$

Information rate: if the source emits $r$ symbols/s, then $R = rH$ bits/s.

Properties of entropy

• $0 \le H \le \log_2 M$.
• $H = 0$ when one symbol has $p = 1$ (no uncertainty).
• $H = \log_2 M$ (the maximum) when all symbols are equally likely.
• For a binary source with $P(1) = p$: $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$, which peaks at 1 bit when $p = 0.5$.

Example: a source with probabilities $\tfrac12, \tfrac14, \tfrac18, \tfrac18$ has

$$H = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75\ \text{bits/symbol}$$