Does Huffman coding always produce shorter codes than the Shannon code?

Question

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

Answer 1

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.