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