# How to maximise the difference between entropy and expected length of an Huffman code?

I'm studying Information Theory and Coding from famous book of MacKay, "Information Theory, Inference and Learning Algorithms".

I have a problem with solving question 5.26 (p:103) although the answer is given.

Question is:

Make ensembles for which the difference between the entropy and the expected length of the Huffman code is as big as possible.

Here is my thinking:

I know that Huffman code lies in this region:

$H(X)\leq L(X)\leq H(X)+1\$

So I should find a code with the expected length very close to entropy.

Expected Length is:

$L(X)= \sum_i p_il_i$

and entropy is:

$H(X)= \sum_i p_ilog_2(1/p_i)$

We get +1 sign on the right-hand side of the equation because we use ceiling function to use integer values for the length of symbols (proof of this theorem at p:98). So, in order to prevent this, I need probability distribution such that $log_2(1/p_i)=\left \lceil log_2(1/p_i) \right \rceil$. Since that is only possible for $p_i=0$ and $p_i=1$, I have tried close probabilities.

Let say $p_a=0.9$ , $p_b=0.1$ and I transmit 2 bits according to Huffman.

• AA | P("AA")=0.81 Transmitting: 1

• AB | P("AB")=0.09 Transmitting: 01

• BA | P("BA")= 0.09 Transmitting: 001

• BB | P("BB")= 0.01 Transmitting: 000

L(X)= 1.29 bit

H(X)= 0.9380 bit

The difference is 0.352

Is my intuition right? Can I do it better?

• "So I should find a code with the expected length very close to entropy...." plus one, no? Commented Jan 21, 2018 at 21:18
• "I transmit 2 bits according to Huffman" You lost me there. If the source has two symbols, then the Huffman code is always the trivial (A->0 B->1). If you instead use the extension of order two, then you actually have four symbols, and you must compute the probability of those four extended symbols. Commented Jan 21, 2018 at 21:23
• thanks, @leonbloy . Yes, you are right, it should be close to plus one, my mistake. In the second one I mean alphabet A={AA,AB,BA,BB} with probabilities P={0.81, 0.09, 0.09, 0.01} respectively. I applied Huffman algorithm to those probabilities. Commented Jan 22, 2018 at 22:18

I have a very simple answer (kind of trivial). Assume two source symbols $$A$$ and $$B$$. Of course the huffman code will be $$A:0$$ and $$B:1$$.
The expected length is $$L(C) = p_A \times 1 + p_B \times 1 = 1$$. The entropy is $$H(S) = -p_A \log p_A - p_B \log p_B$$. We know that if $$p_A$$ approaches 0, then $$H(S)$$ approaches 0 too.
So $$L(C)-H(S)$$ approaches 1.