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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .