Source Information Rate

The information rate of a Source
is the infimum of all rates at which it is Reliably encodable

Lemma

The Source Information Rate of a Discrete Memoryless Source
is at most the expected word length of an Optimal Code.

Proof

Let be an optimal code
Let be codeword lengths when we encode
Let
Let

Then

by Weak Law of Large Numbers.

Now is injective, hence .
Making larger if necessary, we can assume
Taking logarithms

So the source is Reliably encodable at rate for all .
Hence the information rate is at most .

Corollary

A Discrete Memoryless Source has information rate less than .

Proof

Shannon’s noiseless coding theorem

Proposition

The information rate of a Discrete Memoryless Source is at most .

Proof

Encode in blocks of size .
Let etc.
Then if has information rate , has information rate
Apply the previous corollary:

to find so .