Derivation of Shannon's Result

Our derivation will follow directly from our earlier definition of information. Let $H(1/n, 1/n, \cdots, 1/n) = A(n)$ denote the information content of a source consisting of n equiprobable symbols.

Now we know $\forall s \ge t, \exists n: s^m \le t^n < s^{m+1}$

Then, $\forall s > t$,

$$\frac{m}{n} \le \frac{\log t}{\log s} < \frac{m+1}{n}$$

$$\Rightarrow \left\vert \frac{\log t}{\log s} - \frac{m}{n}\right\vert < \frac{1}{n}$$ (7)

Now consider three sources with s^m, tⁿ and s^m+1 equiprobable symbols respectively. Using property (3), A(s^m) = mA(s), A(tⁿ) = nA(t) and A(s^m+1) = (m+1)A(s). (Why? Discuss this.)

Since A must increase monotonically with the number of equiprobable choices (property 2),

$$A(s^m) \le A(t^n) < A(s^{m+1})$$

or equivalently using property (3) and dividing by nA(s),

$$\frac{m}{n} \le \frac{A(t)}{A(s)} < \frac{m+1}{n}$$

$$\Rightarrow \left\vert\frac{A(t)}{A(s)} - \frac{m}{n}\right\vert < \frac{1}{n}$$ (8)

(8) - (9) gives:

$$\left\vert\frac{\log t}{\log s} - \frac{A(t)}{A(s)}\right\vert < \frac{2}{n}$$

Since n is aribtrarily large,

$$A(s) = K\log s$$ (9)

Let p_i = n_i/N where the n_i are integers and $N = {\sum_{i=1}^m n_i}$.

Now consider a choice over N symbols. We can break this down into a choice over m symbols each with probability p_i as defined above and then within each choice i make a second choice over n_i equally likely symbols. Let $H = H(s_1, \cdots, s_m)$. Using (10), we can now write:

$$K\log N = H + K \sum_{i=1}^m p_i\log n_i$$

Hence,

$$H = K\left[ \log N - \sum_{i=1}^m p_i\log n_i \right]$$

Since $\sum_{i=1}^m p_i = 1$,

$$\begin{eqnarray*}H &=& K\left[ \sum_{i=1}^m p_i \log N - \sum_{i=1}^m p_i\log n_... ...i \log \frac{n_i}{N} \right]\\ &=& -K\sum_{i=1}^m p_i \log p_i \end{eqnarray*}$$

If the p_i are real numbers and not rational as per our above assumption, they can be approximated by rationals as closely as we please. And since H is a continuous function by property (1), the expression is valid for $p_i \in [0,1]$.

By analogy with thermodynamics, we call H the Entropy of the source. Note that we choose to interpret the entropy of the source as the amount of information contained in it.