Shannon’s noiseless coding theorem

We are working with messages written in an alphabet of symbols x_{1}, …, x_{n} which occur with probabilities p_{1}, …, p_{n}. We have defined the entropy E of this set of probabilities to be

E = − ∑_{i=1}^{n} p_{i} log_{2} p_{i}.

Theorem For any uniquely decipherable encoding of x_{1}, …, x_{n} as binary code words (e.g. strings of 0s and 1s) the average length of a word must be greater than E.

Our proof of this theorem will involve two lemmas.

Lemma 1 (Gibbs’ inequality). Suppose p_{1}, …, p_{n} is a probability distribution (i.e. each p_{i} ≥ 0 and ∑_{i} p_{i} = 1). Then for any other probability distribution q_{1}, …, q_{n} with the same number of elements,

− ∑_{i=1}^{n} p_{i} log_{2} p_{i} ≤ − ∑_{i=1}^{n} p_{i} log_{2} q_{i}.

Proof: Since log_{2} p_{i} = \frac{ln p_{i}}{ln 2} and ln 2 > 0 it is enough to prove the inequality with log_{2} replaced by ln wherever it occurs.We use the following property of

the natural logarithm:

ln x ≤ x − 1 for all x > 0, and ln x = x − 1 only when x = 1.

In order to avoid zero denominators in the following calculation, we set I = {i|p_{i} > 0}, the set of indices for which p_{i} is non-zero. Then we write

− ∑_{i∈I} p_{i} ln \frac{q_{i}}{p_{i}} ≥ − ∑_{i∈I} p_{i}(\frac{q_{i}}{p_{i}} − 1) = − ∑_{i∈I} q_{i} + ∑_{i∈I} p_{i} = − ∑_{i∈I} q_{i} + 1 ≥ 0.

Since ln \frac{q_{i}}{p_{i}} = ln q_{i} − ln p_{i}, this last inequality becomes

− ∑_{i∈I} p_{i} ln q_{i} ≥ − ∑_{i∈I} p_{i} ln p_{i}.

Now − ∑_{i∈I} p_{i} ln p_{i} = − ∑_{i=1}^{n} p_{i} ln p_{i} since the new terms all have p_{i} = 0; and − ∑_{i∈I} p_{i} ln q_{i} ≤ − ∑_{i=1}^{n} p_{i} ln q_{i} since new terms are ≤ 0. I.e.

− ∑_{i=1}^{n} p_{i} ln q_{i} ≥ − ∑_{i∈I} p_{i} ln q_{i} ≥ − ∑_{i∈I} p_{i} ln p_{i} = − ∑_{i∈I} p_{i} ln p_{i}

yielding Gibbs’ inequality. 2