21
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The optimal bound has been found by Manstetten, Tight bounds on the redundancy of Huffman codes. $\endgroup$
    – Yuval Filmus
    Aug 7, 2016 at 9:23
2
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Feb 20, 2011 at 19:00
  • $\begingroup$ And indeed, you are right. I intended to ask about the expected codeword length under the probability distribution $p$. $\endgroup$
    – Peter Shor
    Feb 20, 2011 at 19:10
  • $\begingroup$ 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.$ $\endgroup$
    – Carl
    Feb 20, 2011 at 19:37
  • $\begingroup$ 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 ... $\endgroup$
    – Carl
    Feb 20, 2011 at 20:14
  • $\begingroup$ 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$. $\endgroup$
    – Carl
    Feb 20, 2011 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.