3
$\begingroup$

Let $\Sigma$ be a source alphabet with a probability distribution over its symbols $P$. Then, the Shannon entropy of $\Sigma$ is $$-\sum p_j \times \mbox{log}_2(p_j)$$ where $p_j$ is the probability of the j'th symbol. We know, thanks to the Shannon's source coding theorem, that this entropy is a (very close) lower bound of the minimum weighted average codeword length, i.e. the weighted average length of the codewords obtained with the Huffman algorithm.

The question: Let $P_1$ and $P_2$ be different probability distributions of the symbols of a given alphabet such that the shannon entropy of $P_1$ is smaller than the shannon entropy of $P_2$. Does this imply that the mininmum weighted average codeword length that we will be able to find for $P_1$ will be at most as large as the minimum weighted average codeword length that we will be able to find for $P_2$?

I am looking for either a counter-example of this or a proof that this is always the case.

Note: this is indeed true when the shannon entropy of $P_1$ is $\leq$ than the shannon entropy of $P_2 + 1$, as the Shannon's source coding theorem tells us that the entropy + 1 is an upper bound of the minimum weighted average codeword length. But when this is not the case (i.e. the difference is less than 1), it is not clear.

$\endgroup$
  • $\begingroup$ What are A and B? $\endgroup$ – CL. May 5 '14 at 13:45
  • $\begingroup$ Meant to say $P_1$ and $P_2$. I corrected it. $\endgroup$ – N1992 May 5 '14 at 22:11

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.