What's an intuitive proof for why Shannon's entropy poses a lower bound on the expected number of bits encoding a distribution?

Question

As I understand it, Shannon's entropy is $-\sum p\log p$ which represents an expectation of the self information $-\log p$ over a distribution.

The log function was chosen to fit 3 properties:

1. A guaranteed event conveys no information
2. Less likely events have more information
3. The information of independent events is the sum of the information of each event separately.

While this grounds information in an intuitive sense, it is not clear to me why it's the optimal expectation of the number of bits needed to encode the distribution. I would prefer an explanation in a noiseless environment to keep it simple.

Answer 1

In this setting, objects (which I will index with $i=1,2,\ldots$) are turned into strings of bits by emitting a string $x_i$ of length $b_i$ for object $i.$ In this way a random sequence of these objects becomes a binary message.

Decoding the message (to determine what the original sequence of messages was) is tantamount to traversing a binary tree: starting at its root, move to the left child when encountering a $0$ or move to the right child when encountering a $1.$ The string $x_i$ will lead you to the corresponding node in this tree, which is thereby labeled with $i.$ Thus, whenever you encounter a label you know the input was $x_i$ and you can jump back to the root to resume decoding the string generated by the next object.

After descending through $b_i \gt 0$ children in this tree traversal you will have determined one of the $2^{b_i}$ possible paths to that depth. Thus, applying the label $i$ to the node you're on effectively will remove a proportion $2^{-b_i}$ of the tree, making it unavailable for use in decoding any other object. Since the total proportion cannot exceed $1,$ we see

$$1\ \ge\ \sum_{i} 2^{-b_i} = g(\mathbf{b}),\tag{1}$$

where $\mathbf{b}$ is the vector $(b_i) = (b_1, b_2, \ldots).$

This is the key observation (and it provides excellent intuition). The rest is routine. I will sketch the analysis.

Let the chance of object $i$ appearing in the input be $p_i \gt 0.$ Define the random variable $B$ to be the number of bits used for this object, $B(i) = b_i.$ We would like to minimize its expectation,

$$E[B] = \sum_{i} p_i b_i = f(\mathbf{b}).\tag{2}$$

The method of Lagrange Multipliers will find the best positive real numbers $b_i$ that minimize $(2)$ subject to the constraint $(1).$ The critical points--candidates for the global minimum--occur when the derivative of the objective function is parallel to the derivative of the constraint; that is, there must be some number $\lambda$ for which

$$-\log(2) \left(2^{-b_i}\right) = \lambda \nabla g(\mathbf{b}) = \nabla f(\mathbf{b}) = \left(p_i\right).$$

It is immediate that at the optimum, the $b_i$ must be proportional to $\log_2{p_i}.$ That, together with the constraint $(1),$ readily leads to the conclusion that the expectation $(2)$ cannot be any less than the entropy.