The Redundancy Theorem and New Bounds of the Expected Length of the Huffman Code

We introduce the Redundancy Theorem as a tool to lower bound the expected length of prefix codes. It is shown that virtually all the previously known lower bounds of the expected length of the Huffman code can be obtained via applications of the Redundancy Theorem, and we demonstrate an application of the theorem which yields new lower bounds. We also obtain a new upper bound of the expected length of the Huffman code which depends on the entropy of the source and the two smallest probabilities of the distribution.