<p>Judging by the $H(p) \leq \ldots \leq H(p)+1$ bound, I believe you intended to ask a different question ... or you just didn't specify how you take the "average". So I'll answer both. The answer is no to both questions.</p>

<p>First, if you define average code length using a uniform distribution over code words and take $2^{-q}$ as the upper bound on probability of any one element, then consider the code of length $q+k$ where $2^{q-1}$ code words have length $q$ and the remaining $2^{q+k-1}$ have length $q+k$. For the distribution perfectly encoded by this code, the average length approaches $q+k$, unless you also have a lower bound for probability of one element, while the entropy is $q+\frac{k}{2}$.</p>

<p>Now let us consider the "average length" meaning the average codeword length when the Huffman code is used to code for $p$. Here, the bound is tight, and an example distribution achieving it in the limit is one in which each element occurs with probability $2^{q\pm 1/2}$ for $q \in {\mathbb Z}.$ (The final element is assigned any leftover probability, but it will make no difference asymptotically).</p>

<p>For example, consider $q = 7.$ Then</p>

<p>$A + B = 128, A\sqrt{2}+B/\sqrt{2}\leq 128, \max_{A \in {\mathbb Z}} A$ yields $A = 52, B = 76$. Our distribution has $52$ elements with probability $2^{-6.5}$, $76$ with probability $2^{-7.5}$, and one element gets the leftovers.</p>

<p>Then $H(X) = (52\cdot 6.5 + 76 \cdot 7.5)/128 = 7.09375$, while the Huffman code achieves $(52 \cdot 0.5 - 76 \cdot 0.5)/128 \approx 0.99436$ entropy loss.
(Incidentally, the entropy loss has a name, whether you do Huffman coding or arbitrary coding for $Q$: the Kullback-Liebler divergence $D(P\Vert Q) = \sum p_i \log \frac{p_i}{q_i} + \sum (1-p_i) \log \frac{1-p_i}{1-q_i}$. Using it, I discovered a few days ago, leads to tighter double-sided Chernoff bounds, as you can see on Wikipedia for Chernoff bounds.)</p>

CC BY-SA 2.5
2011-02-20T19:00:07.527Z
I am somewhat baffled by this second example. If you have 128 codewords, then there is a code with average word length 7 (in fact, all the word lengths have 7), which contradicts your statement that the entropy is 7.09375. The entropy of this distribution (which you get by taking a weighted average of $-\log_2 p_i$ and not an average) is 6.88, while the average length of the Huffman code is 7. This gives a gap (or Kullback-Liebler divergence) of around 0.12, which seems to be quite a bit better than my example, but not close to 1.
Peter Shor 
CC BY-SA 2.5
2011-02-20T19:10:32.977Z
And indeed, you are right. I intended to ask about the expected codeword length under the probability distribution $p$.
Peter Shor 
CC BY-SA 2.5
2011-02-20T19:37:43.100Z
Oops, I miscalculated about $A$ vs $B$. We still want $A\sqrt{2}+B/\sqrt{2}$ slightly less than $2^k$, but something like $A+2B=2^k$, to force the lesser entries into the lower row. This gives $A = \frac{2-1/\sqrt{2}}{\sqrt{2}-1}B.$
Carl
CC BY-SA 2.5
2011-02-20T20:14:05.317Z
Actually that would be $2A+B$ ... but this system of equations doesn't have a positive solution -- it seems we can't force everything to be half-integer powers of $2$. So instead of $\sqrt{2}$ and $1/\sqrt{2}$ we can consider, e.g. $(1+x)/2^k$ for half of the Huffman code and $(1-x)/2^{k+1}$ for the rest, giving $3*2^k$ entries ...
Carl
CC BY-SA 2.5
2011-02-20T20:24:10.150Z
So, try this (not optimal -- I suppose that depends on how you decide to round down or up). $64$ entries with probability $1/128$ and $128$ entries with probability $1/256$ has entropy $7.5$. Instead change that to $64$ entries with probability $1/128\sqrt{2}$ and $128$ entries with probability $1/256(2-1/\sqrt{2})$. Entropy of this distribution is $1/(2\sqrt{2})*7.5+(1-1/(2\sqrt(2)))*5.802$ which gives 6.4023, while entropy of the Huffman code is 7.5 under uniform, and $(1-2^{-1.5})*7+2^{-1.5}*8 = 7.3535.$ So unless I miscalculated (and I do often), this gives a gap of about $0.95$.
Carl
CC BY-SA 2.5
2011-02-20T20:27:26.823Z
So, I'm new here. After we verify corrections to the math and the problem statement, should I edit the original answer so it is correct and simple, but leave the comments?
Carl
CC BY-SA 2.5
2011-02-20T20:33:37.420Z
I think it's ok to edit the answer, with a note that it's been updated. since it's possible to look at the history, there's no confusion.
Suresh Venkat
CC BY-SA 2.5
2011-02-20T21:01:48.420Z
@Suresh: Great, I'll try that. But my current example isn't correct, so I'll fix that first.
Carl
CC BY-SA 3.0
2011-02-20T17:19:31.590Z
2017-01-06T21:01:06.090Z
2017-01-06T21:01:06.090Z
Carl
<p>There are lots of papers that study exactly the problem you mention. The first in the series is a paper by Gallager, "Variations on a Theme by Huffman", IEEE-IT, vol. 24, 1978, pp. 668-674. He proves that the difference between the average codeword length of an Huffman code and the entropy  (he calls that quantity "redundancy") is always strictly less than $p$ (= largest probability in the probability distribution), in the case  $p\geq 1/2$, and it is less than $p+0.086$, if $p&lt;1/2$. Better bounds are known, you can find them in the numerous papers that quote Gallager work.</p>

CC BY-SA 3.0
2016-08-07T09:23:29.173Z
The optimal bound has been found by Manstetten, *Tight bounds on the redundancy of Huffman codes*.
Yuval Filmus
CC BY-SA 2.5
2011-02-20T22:04:05.193Z
2011-02-20T22:04:05.193Z
Ugo
<p>The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a well-known theorem that the average length per symbol of the Huffman code is between $H(p)$ and $H(p)+1$, where $H(p) = -\sum_i \, p_i \log_2 p_i$ is the Shannon entropy of the probability distribution. </p>

<p>The canonical bad example, where the average length exceeds the Shannon entropy by almost 1, is a probability distribution such as $\{.999, .001\}$, where the entropy is nearly 0, and the average codeword length is 1. This gives a gap between the entropy and the codeword length of almost $1$.</p>

<p>But what happens when there is a bound on the largest probability in the probability distribution? Suppose, for example, that all the probabilities are less than $\frac{1}{2}$. The largest gap I could find in this case is for a probability distribution such as $\{.499, .499, .002\}$, where the entropy is slightly more than 1 and the average codeword length is slightly less than 1.5, giving a gap approaching $0.5$. Is this the best you can do? Can you give an upper bound on the gap that is strictly less than 1 for this case?</p>

<p>Now, let's consider the case where all the probabilities are very small. Suppose you choose a probability distribution over $M$ letters, each having probability $1/M$. In this case, the largest gap occurs if you choose $M \approx 2^k \ln 2$. Here, you get a gap of around
$$ \frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607. $$
Is this the best you can do in the situation where all the probabilities are small?</p>

<p>This question was inspired by this <a href="https://cstheory.stackexchange.com/questions/4935/why-does-the-fibonacci-sequence-produce-a-worst-case-huffman-encoding">TCS Stackexchange question</a>.</p>

<optimization><it.information-theory><coding-theory>
How good is the Huffman code when there are no large probability letters?
Peter Shor 
# How good is the Huffman code when there are no large probability letters?

(Asked by: username_0 on 2011-02-19)

The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p\_i \ell\_i$, where $\ell\_i$ is the length of the $i$th codword. It is a well-known theorem that the average length per symbol of the Huffman code is between $H(p)$ and $H(p)+1$, where $H(p) = -\sum\_i \, p\_i \log\_2 p\_i$ is the Shannon entropy of the probability distribution.

The canonical bad example, where the average length exceeds the Shannon entropy by almost 1, is a probability distribution such as $\{.999, .001\}$, where the entropy is nearly 0, and the average codeword length is 1. This gives a gap between the entropy and the codeword length of almost $1$.

But what happens when there is a bound on the largest probability in the probability distribution? Suppose, for example, that all the probabilities are less than $\frac{1}{2}$. The largest gap I could find in this case is for a probability distribution such as $\{.499, .499, .002\}$, where the entropy is slightly more than 1 and the average codeword length is slightly less than 1.5, giving a gap approaching $0.5$. Is this the best you can do? Can you give an upper bound on the gap that is strictly less than 1 for this case?

Now, let's consider the case where all the probabilities are very small. Suppose you choose a probability distribution over $M$ letters, each having probability $1/M$. In this case, the largest gap occurs if you choose $M \approx 2^k \ln 2$. Here, you get a gap of around
$$ \frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607. $$
Is this the best you can do in the situation where all the probabilities are small?

This question was inspired by this [TCS Stackexchange question](https://cstheory.stackexchange.com/questions/4935/why-does-the-fibonacci-sequence-produce-a-worst-case-huffman-encoding).

**Tags:** optimization, it.information-theory, coding-theory


---

## 2 answers

### Answer by username_3 on 2011-02-20. Score: 19 | Accepted answer

There are lots of papers that study exactly the problem you mention. The first in the series is a paper by Gallager, "Variations on a Theme by Huffman", IEEE-IT, vol. 24, 1978, pp. 668-674. He proves that the difference between the average codeword length of an Huffman code and the entropy (he calls that quantity "redundancy") is always strictly less than $p$ (= largest probability in the probability distribution), in the case $p\geq 1/2$, and it is less than $p+0.086$, if $p<1/2$. Better bounds are known, you can find them in the numerous papers that quote Gallager work.

> **Comments:**
> **username_4**: The optimal bound has been found by Manstetten, *Tight bounds on the redundancy of Huffman codes*.  

---

### Answer by username_1 on 2011-02-20. Score: 2

Judging by the $H(p) \leq \ldots \leq H(p)+1$ bound, I believe you intended to ask a different question ... or you just didn't specify how you take the "average". So I'll answer both. The answer is no to both questions.

First, if you define average code length using a uniform distribution over code words and take $2^{-q}$ as the upper bound on probability of any one element, then consider the code of length $q+k$ where $2^{q-1}$ code words have length $q$ and the remaining $2^{q+k-1}$ have length $q+k$. For the distribution perfectly encoded by this code, the average length approaches $q+k$, unless you also have a lower bound for probability of one element, while the entropy is $q+\frac{k}{2}$.

Now let us consider the "average length" meaning the average codeword length when the Huffman code is used to code for $p$. Here, the bound is tight, and an example distribution achieving it in the limit is one in which each element occurs with probability $2^{q\pm 1/2}$ for $q \in {\mathbb Z}.$ (The final element is assigned any leftover probability, but it will make no difference asymptotically).

For example, consider $q = 7.$ Then

$A + B = 128, A\sqrt{2}+B/\sqrt{2}\leq 128, \max\_{A \in {\mathbb Z}} A$ yields $A = 52, B = 76$. Our distribution has $52$ elements with probability $2^{-6.5}$, $76$ with probability $2^{-7.5}$, and one element gets the leftovers.

Then $H(X) = (52\cdot 6.5 + 76 \cdot 7.5)/128 = 7.09375$, while the Huffman code achieves $(52 \cdot 0.5 - 76 \cdot 0.5)/128 \approx 0.99436$ entropy loss.
(Incidentally, the entropy loss has a name, whether you do Huffman coding or arbitrary coding for $Q$: the Kullback-Liebler divergence $D(P\Vert Q) = \sum p\_i \log \frac{p\_i}{q\_i} + \sum (1-p\_i) \log \frac{1-p\_i}{1-q\_i}$. Using it, I discovered a few days ago, leads to tighter double-sided Chernoff bounds, as you can see on Wikipedia for Chernoff bounds.)

> **Comments:**
> **username_0**: I am somewhat baffled by this second example. If you have 128 codewords, then there is a code with average word length 7 (in fact, all the word lengths have 7), which contradicts your statement that the entropy is 7.09375. The entropy of this distribution (which you get by taking a weighted average of $-\log_2 p_i$ and not an average) is 6.88, while the average length of the Huffman code is 7. This gives a gap (or Kullback-Liebler divergence) of around 0.12, which seems to be quite a bit better than my example, but not close to 1.  
> **username_0**: And indeed, you are right. I intended to ask about the expected codeword length under the probability distribution $p$.  
> **username_1**: Oops, I miscalculated about $A$ vs $B$. We still want $A\sqrt{2}+B/\sqrt{2}$ slightly less than $2^k$, but something like $A+2B=2^k$, to force the lesser entries into the lower row. This gives $A = \frac{2-1/\sqrt{2}}{\sqrt{2}-1}B.$  
> **username_1**: Actually that would be $2A+B$ ... but this system of equations doesn't have a positive solution -- it seems we can't force everything to be half-integer powers of $2$. So instead of $\sqrt{2}$ and $1/\sqrt{2}$ we can consider, e.g. $(1+x)/2^k$ for half of the Huffman code and $(1-x)/2^{k+1}$ for the rest, giving $3*2^k$ entries ...  
> **username_1**: So, try this (not optimal -- I suppose that depends on how you decide to round down or up). $64$ entries with probability $1/128$ and $128$ entries with probability $1/256$ has entropy $7.5$. Instead change that to $64$ entries with probability $1/128\sqrt{2}$ and $128$ entries with probability $1/256(2-1/\sqrt{2})$. Entropy of this distribution is $1/(2\sqrt{2})*7.5+(1-1/(2\sqrt(2)))*5.802$ which gives 6.4023, while entropy of the Huffman code is 7.5 under uniform, and $(1-2^{-1.5})*7+2^{-1.5}*8 = 7.3535.$ So unless I miscalculated (and I do often), this gives a gap of about $0.95$.  
> **username_1**: So, I'm new here. After we verify corrections to the math and the problem statement, should I edit the original answer so it is correct and simple, but leave the comments?  
> **username_2**: I think it's ok to edit the answer, with a note that it's been updated. since it's possible to look at the history, there's no confusion.  
> **username_1**: @Suresh: Great, I'll try that. But my current example isn't correct, so I'll fix that first.  

---

