I find entropy to be extremely fascinating. But, matching the formula $\sum p_i\log \frac{1}{p_i}$ to its “intuitive” explanations related to prefix free codes and information content is elusive, at least for me. Here, I want to go over a few ways to independently arrive at the idea.

Properties of Information

Suppose we want to define a function $I$, which represents the information content of an event. Abstracting away the specifics of the event, one measure we could use to compare one event to another is their probabilities of occuring. So, $I$ could be a mapping from a probability $p\in [0,1]$ to $\mathbb{R}$. Given this framing, the following requirements are sensible:

1. $I(1)=0$. If an event definitely occurs, it’s not very interesting and gives us little information.

2. $I$ should be monotonically decreasing on $[0,1]$. A more common event is less informative.

3. Two independent events with probabilities $p$ and $q$ should have information $I(p)+I(q)$

The last requirement is the most telling. The probability of two independent events occuring is $pq$. So

$$I(pq)=I(p)+I(q)$$

which only holds for

$$I(p)=c\log p.$$

If we want $I$ to be monotonically decreasing,

$$\frac{dI}{dp}=c/p$$

must be negative. Since $p>0$, $c<0$. Letting $c^{\prime }=|c|$

$$I(p)=c^{\prime }\log \frac{1}{p}$$

Since ${\log }_{a}b=\frac{\log b}{\log a}$, we can think of $c^{\prime }$ as encoding the base of the logarithm. For convenience, we let $c^{\prime }$ be 1.

Entropy is simply the expected value of $I$, over a distribution $\mathbf{p}=(p_1,p_2,\dots ,p_n)$

$$H(\mathbf{p})=\sum _{i=1}^n{p}_i\log \frac{1}{p_i}$$

We also assume that $H(0)=0\log \frac{1}{0}=0$, motivated by continuity.

Prefix-free codes

Suppose we have a set of symbols $\mathcal{X}=\{X_1,\dots ,X_M\}$ that we want to transmit over a binary channel. We construct the channel such that we can send either a $1$ or a $0$ at a time. We want to find an optimal encoding scheme for $\mathcal{X}$, with one requirement: it is prefix-free.

Let’s define an encoding function $f:\mathcal{X}\to \{0,1{\}}^{+}$, which maps symbols to binary strings of length $\ge 1$. We say an encoding is prefix-free if no codeword is a prefix of another. For example, $\{0,01\}$ is not prefix free because $0$ is a prefix of $01$. However, $\{0,10\}$ is.

A prefix free code implies that the code is uniquely decodable without additional delimiters in between symbols, which is a desirable property.

Also note that a binary prefix code is uniquely defined by a binary tree:

where the root-to-symbol path determines the codeword, and symbols are always leaves. Convince yourself that any construction like this results in a prefix code.

We will now show that the expected codeword length $L$ of any prefix code over $X$ is bounded by

$$H(X)\le L<H(X)+1.$$

Kraft’s Inequality

Suppose that $l_i$ is the length of the $i$th codeword. If the code is prefix-free:

$$\sum _{i=1}^M{2}^{-l_i}\le 1$$

Proof:

Let $l_{\text{max}}$ be the length of the longest codeword. We notice that:

1. There is at most $2^{l_{\text{max}}}$ nodes at level $l_{\text{max}}$
2. For any codeword of length $l_i$, there are $2^{l_{\text{max}}-l_i}$ descendents at level $l_{\text{max}}$.
3. The sets of descendents of each codeword are disjoint (since one codeword is never a descendent of another)

These imply

$$\begin{array}{rl}& \sum _i{2}^{l_{\text{max}}-l_i}\le 2^{l_{\text{max}}}\\ ⟹& \sum _i{2}^{-l_i}\le 1.\end{array}$$

Why $\le$ instead of equality? Because it is possible that a node at level $l_{\text{max}}$ is not a descendent of any codeword (consider the tree of the code $\{10,11\}$)!

Lower bound for L

Now, let’s consider the expected codeword length

$$L=\sum _i{p}_i{l}_i$$

We will show that entropy is a lower bound for $L$, or

$$H(X)\le L⟺L-H(X)\ge 0$$

Proof:

$$\begin{array}{rl}L-H(X)& =\sum _i{p}_i{l}_i+\sum _i{p}_i\log p_i\\ & =-\sum _i{p}_i\log 2^{-l_i}+\sum _i{p}_i\log p_i\\ & =-\sum _i{p}_i\log 2^{-l_i}+\sum _i{p}_i\log p_i+\sum _i{p}_i\log \left(\sum _j{2}^{-l_j}\right)-\sum _i{p}_i\log \left(\sum _j{2}^{-l_j}\right)\\ & =\sum _i{p}_i\log \frac{p_i}{2^{-l_i}/{\sum }_j{2}^{-l_j}}-\sum _i{p}_i\log \left(\sum _j{2}^{-l_j}\right)\\ & =D_{KL}[p||q]+\log \frac{1}{c}\\ & \ge 0\end{array}$$

Where the final inequality is due to 1) KL divergence being non-negative and 2) to $c\le 1$ due to Kraft’s inequality. One thing to note is that if $l_i=-\log p_i$, $L=H(X)$. The reason we cannot always achieve this is because $-\log p_i$ may not be an integer.

An Upper Bound for L

Notice that it is possible to construct a prefix code with lengths

$$l_i=\lceil -\log p_i\rceil$$

since they satisfy Kraft’s Inequality:

$$\sum _i{2}^{-l_i}\le \sum _i{2}^{\log p_i}=1$$

By the definition of the ceiling function

$$-\log p_i\le l_i<-\log p_i+1$$

Taking the expectation over $p$, we get

$$\begin{array}{rl}& -\sum p_i\log p_i\le \sum p_i{l}_i<-\sum p_i\log p_i+1\\ & ⟹H(X)\le L<H(X)+1\end{array}$$

This shows that $H(X)+1$ is an upper bound for L!

In summary, entropy is a lower bound, and a reasonable estimate, for the average number of bits it takes to encode a distribution as a prefix code.