<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2016-02-08T04:06:28.353Z
Fibonacci frequencies were a very nice and crisp counterexample. Many thanks!
Christian Bueno
CC BY-SA 3.0
2016-02-08T02:24:58.277Z
2016-02-17T15:15:01.117Z
2016-02-17T15:15:01.117Z
Peter Shor 
<p>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.$$</p>

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

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

<p><em>(I'm looking for proofs/counterexamples.)</em></p>

CC BY-SA 3.0
2016-02-08T04:14:54.080Z
Why the downvote?
Christian Bueno
<it.information-theory><prefix-free-code><huffman><shannon>
Does Huffman coding always produce shorter codes than the Shannon code?
Christian Bueno
# Does Huffman coding always produce shorter codes than the Shannon code?

(Asked by: username_0 on 2016-02-06)

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

**Tags:** it.information-theory, prefix-free-code, huffman, shannon
> **Comments:**
> **username_0**: Why the downvote?  

---

## 1 answers

### Answer by username_1 on 2016-02-08. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: Fibonacci frequencies were a very nice and crisp counterexample. Many thanks!  

---

