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