2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "So I should find a code with the expected length very close to entropy...." plus one, no? $\endgroup$ – leonbloy Jan 21 '18 at 21:18
  • $\begingroup$ "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. $\endgroup$ – leonbloy Jan 21 '18 at 21:23
  • $\begingroup$ 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. $\endgroup$ – kubicwerke Jan 22 '18 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.