# Average prefix code length of every 4-sized frequency vector is bounded at 2

I'm trying to show that for every frequency vector $(p_1, p_2, p_3, p_4)$ such that $\sum_{i=1}^4 p_i=1$, the average word length outputted by Huffman algorithm is bounded at 2: If $(w_1,w_2,w_3,w_4)$ is the outputted code, then $\sum_{i=1}^4 p_i |w_i| \le 2$.

I've tried looking at the tree that is generated by Huffman algorithm, but the thing is that several different tree structures match different 4-sized frequency vectors and I can't tell something general about all of them.

Also, is there a more general theorem for $k, n$ (here $k=4, n=2$)?

• If you assume without loss of generality that $p_1 \ge p_2 \ge p_3 \ge p_4$, there are only two possible Huffman trees that you can generate up to symmetry. Hence, only two cases to check. – Pseudonym Jun 24 '16 at 14:37

Hint: The code generated by Huffman's algorithm has the minimal average word length, and in particular is at least as good as any other code. Show that there is a "universal" code (of length $n=4$) whose average code length is exactly $2$ on any distribution.
The more general theorem states that the average word length for a code over an alphabet of size at most $2^a+b$ is at most $a + \frac{b}{2^a+b}$; to get the best bound for a specific $n$, write $n = 2^a+b$ with $a$ as large as possible. When $b=0$ there is even a universal code as in your particular case.