Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters.

My try:

I think that the worst case is when the tree is full and all the characters are in the highest level.

Therefore: $n=2^h \to h=\log n$, and the average codeword length is $\Omega(\log n)$.

Am I missing something?

  • $\begingroup$ You did not use the probabilities of the characters? Most probable characters have the shortest code. $\endgroup$ Jun 1 '19 at 12:11

This answer assumes that by average you mean just that – the sum of all codeword lengths divided by $n$.

Let us show that any prefix code satisfies your property. Consider any prefix code whose codewords have lengths $\ell_1,\ldots,\ell_n$. Kraft's inequality shows that $$ 2^{-\ell_1} + \cdots + 2^{-\ell_n} \leq 1. $$ The function $x \mapsto 2^{-x}$ is convex, hence $$ \frac{1}{n} \geq \frac{2^{-\ell_1} + \cdots + 2^{-\ell_n}}{n} \geq 2^{-(\ell_1+\cdots+\ell_n)/n}. $$ It follows that $$ \frac{\ell_1 + \cdots + \ell_n}{n} \geq \log_2 n. $$ Since $x \mapsto 2^{-x}$ is strictly convex, there can be equality only if $\ell_1 = \cdots = \ell_n$, that is, only if all codewords are of length exactly $\log_2 n$. That can only happen if $n$ is a power of 2. This leaves open the following question:

What is the minimum average codeword length of a prefix code on $n$ symbols?

(We note in passing that every prefix code satisfying Kraft's inequality tightly is a minimum redundancy code for some distribution, namely the one in which the probability of the $i$th symbol is $2^{-\ell_i}$.)

To answer this, let us note that convexity implies that if $a < b$ then $$ 2^{-a} + 2^{-b} \geq 2^{-(a+1)} + 2^{-(b-1)}. $$ (We can also see this directly: without loss of generality $a=0$, and then we need to prove $1 + 2^{-b} \geq 1/2 + 2 \cdot 2^{-b}$, that is, $1/2 \geq 2^{-b}$, which follows from $b \geq 1$.)

Applying this operation repeatedly starting at some arbitrary integer solution of Kraft's equation, we eventually reach a solution which involves at most two different values $\ell,\ell+1$. If $n = 2^k + m$, where $0 \leq m < 2^k$, then this solution must consist of $2^k - m$ many $k$'s and $2m$ many $k+1$'s. Hence the optimal average codeword length is $$ \frac{k(2^k-m)+(k+1)2m}{2^k+m} = k + \frac{2m}{2^k+m}. $$

  • 1
    $\begingroup$ You can describe any prefix code as a binary tree, where the root-to-leaf path of element $x$ spells the code of $x$. The binary tree corresponding to a Huffman code is a Huffman tree. $\endgroup$ Jan 3 at 20:44

If by average you mean the average length of the n codewords, then if the k-th symbol has probability $2^{-k}$, the length of the code words ranges from 1 to n-1, with average about n/2.

If by average you mean the average length of a codeword in a compressed message, then if the first symbol has probability 1-eps, and the others all have probability (1 - eps) / (n - 1), then the average length of a codeword in a compressed message is just a bit more than 1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.