Shannon's noiseless coding theorem

Let be a Discrete Memoryless Source with values in
Let be an Optimal Code for
Then its Expected word length satisfies:

where ,
and is the Mathematical Entropy.

Proof

The lower bound is given by combining Gibbs’ inequality and Kraft’s inequality.
Take where is just the normalizing factor.

Where by Kraft’s inequality.
Hence:

We get equality iff for some integers .

For the upper bound, let
We have

So by McMillan’s Theorem
there is a prefix-free code with word lengths .
Also