Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$. Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and let $L(C)$ be the expected length of the code. The Shannon code produces a prefix code $C_{Sh}$ with the lengths of the codewords $l_i =\lceil \log_2 \frac{1}{p(i)}\rceil $. The Huffman code produces a prefix code $C_{Hu}$ which is minimal in expected length, but with non-explicit individual codeword lengths. Let $H(X)$ be the entropy of $X$. We have $$H(X)\leq L(C_{Hu}) \leq L(C_{Sh})\leq H(X)+1.$$

My Question: Though Huffman code produces expected lengths at least as low as the Shannon code, are all of it's individual codewords shorter?

Follow-up Question: If not, do the lengths of all the codewords in a Huffman code at least satisfy the inequality: $$ l^{Hu}_i<\log_2 \left(\frac{1}{p_i}\right)+1 ? $$

(I'm looking for proofs/counterexamples.)

  • 1
    $\begingroup$ Why the downvote? $\endgroup$ – Christian Bueno Feb 8 '16 at 4:14

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample.

And if you want a really nice counterexample, consider the many non-isomorphic Huffman trees you can make when you have probabilities proportional to $$1,1,1,2,3,5,8,13,21,34$$ (the Fibonacci series with an extra 1). Figure out what the maximum and minimum depths are for a Huffman tree with this probability distribution. This calculation will lead to a counterexample for your follow-up question.

| cite | improve this answer | |
  • $\begingroup$ Fibonacci frequencies were a very nice and crisp counterexample. Many thanks! $\endgroup$ – Christian Bueno Feb 8 '16 at 4:06

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.