Bounding the Average Length of Optimal Source Codes via Majorization Theory

We consider the problem of bounding the average length of an optimal (Huffman) source code when only limited knowledge of the source symbol probability distribution is available. For instance, we provide tight upper and lower bounds on the average length of optimal source codes when only the largest or the smallest source symbol probability is known. Our results rely on basic results of majorization theory and on the Schur concavity of the minimum average length of variable-length source codes for discrete memoryless sources. In the way to prove our main result we also give closed formula expressions for the average length of Huffman codes for several classes of probability distributions