The theorem states that

$$ H(P)\leq\mathrm{MinACL}(P)<H(P)+1 $$

where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word length of any Huffman coding and $H$ means the entropy of the probability distribution $P$.

Now, the problem is how to show that for any $\epsilon>0$, there is a probability distribution $P$ s.t. $\mathrm{MinACL}(P) - H(P)\geq1-\epsilon$?

(I was given a hint that I can start with a source s.t. $H(P)=\mathrm{MinACL}(P)$ and try to change the probabilities in order to skew the code.}


Em…… I seem to have figured out how to construct a probability distribution to achieve $\mathrm{MinACL}$ as close to $H(P)+1$ as possible. Suppose, for the information source $(S,P)$ with $|S| = 2^l + 1$, $p_0 = 1 - \epsilon$, $p_i = \epsilon/2^l,1\leq i\leq2^l$, a valid Huffman tree could be constructed as follows: First build a full binary tree with $s_i,1\leq i\leq2^l$, as leaves and then make $s_0$ sibling of the root of this binary tree, and child of the Huffman tree root node. This scheme can be justified easily given $\epsilon\in(0,0.5)$. Then, $H(P) = -(1-\epsilon)\log(1-\epsilon)-(\epsilon/2^l)\log(\epsilon/2^l)$ and $\mathrm{MinACL}(P) = (l+1)\cdot\epsilon+1\cdot(1-\epsilon)$.

$$ \lim_{\epsilon\to0}\mathrm{MinACL}(P)-H(P) = 1 $$

(I haven't calculated the limit, but the graph below if of much evidence: enter image description here)

  • $\begingroup$ Take $l=0$ for a simple example. $\endgroup$ – Yuval Filmus Feb 9 at 2:59

You can take the distribution $P(0) = 1-\epsilon$, $P(1) = \epsilon$. This distribution has entropy $h(\epsilon) = O(\epsilon \log 1/\epsilon)$, but $\mathrm{MinACL}(P) = 1$. As $\epsilon$ tends to $0$, the gap tends to $1$, since $\lim_{\epsilon\to 0} h(\epsilon) = 0$.

  • $\begingroup$ Thank you very much. I started out in a strange way so I didn't think of this simplest example. $\endgroup$ – Miangu Feb 14 at 2:35

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.