Entropy

Entropy can be understood as the minimum amount of data needed to be transmitted in order to communicate a piece of information. Concretely, this is the average number of bits needed to encode a message. For example, imagine a spaceship sends a status code every minute to indicate if it has found any alien civilization. The code is any letter from the English alphabet, with $A$ meaning “nothing new”, and some other letter describing the alien. For example $F$ means the alien is friendly, and $B$ means the alien is blue, etc. For simplicity assume every code is only 1-letter long. Then we can simply encode this status code with $\log(26)$ bits, where $A = 0 \dots 0, B = 0\dots 1, \dots$. However, we can be a little clever because we know most of the time the spaceship won’t be finding new civilizations. In that case, the satellite can remain silent to indicate “nothing new”; otherwise it sends the status code with our original encoding ¹.

Then we only need to send on average little more than 0 bit per minute. In general, we can save some bits if we know certain messages occur with high/low probability. In other words, the minimum commucation cost depends on the probability distribution of the data. Entropy precisely formalizes this intuition. Formally, if $X$ is a random variable with outcomes $x_1, \dots, x_N$ each of probabilities $p_1, \dots, p_N$, then its entropy is defined as:

H(X) = \sum_i p_i \log \frac{1}{p_i}

This matches our intuition: when $X$ is uniform and $|X| = N$, $H(X)=N(1/N \log N)=\log N$; when $X$ is almost always a certain message, say $A$, then $H(X)= p_A \log \frac{1}{p_A} + \sum_{i \not = A} p_i \log \frac{1}{p_i} = 0.99999 \log \frac{1}{0.99999} + \delta \approx 0$. For a more general case, suppose message $A$ occurs half of the time, $B$ one quarter of the time, $C$ one eighth and so on. Then we can use one bit $1$ to indiate that $A$ occurs; otherwise we first send one bit $0$ to indicate it’s not $A$, then send one bit $1$ if $B$ occurs and $0$ otherwise, and so on. On average we need $p_A \times 1 + p_B \times 2 + \dots = p_A \times \log(\frac{1}{p_A}) + p_B \times \log(\frac{1}{p_B}) + \dots = H(X)$ bits.