# Average codeword length in a Huffman tree is $\Omega(\log n)$

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?

• You did not use the probabilities of the characters? Most probable characters have the shortest code. 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}.$$

• 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. 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.