2
$\begingroup$

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$)?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Pseudonym Jun 24 '16 at 14:37
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.