I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website.

I have question on the source coding theorem (emphasis mine):

Shannon's source coding theorem (p81): $N$ i.i.d. random variables each with entropy $H(x)$ can be compressed into more than $N \cdot H(x)$ bits with negligible risk of information loss, as $N \to \infty$; conversely if they are compressed into fewer than $N \cdot H(x)$ bits it is virtually certain that information will be lost.

My question is the emphasised part of the above, what happens when you go below $N \cdot H(x)$ bits?

There is an example in the textbook (p77), which he shows that, as $N$ increases, the average entropy per symbol approaches $H(X)$, for the risk tolerance between $0< \delta< 1$. (So it becomes more flat as indicate on the diagram).

Plot of average entropy per symbol against risk tolerance for different numbers of random variables.

Therefore, $N \cdot H(x)$ is the number of bits you can compress no matter how much risk tolerance you are willing to take. In the theorem above, however, it is saying that information will be lost if you go below $N \cdot H(X)$. My question is, how much information will be lost?

  • $\begingroup$ If you're sending i.i.d. copies using $H$ bits on average, then you're sending roughly $H$ bits of information per copy. $\endgroup$ Commented Sep 24, 2014 at 4:29
  • 1
    $\begingroup$ see: rate distortion theory $\endgroup$ Commented Dec 9, 2014 at 23:19

1 Answer 1


For each bit that you compress beyond the entropy limit you lose one bit of information. Keep in mind that this theorem deals with random variables. If you want to know what happens to a specific input then you need a different kind of analysis.

  • $\begingroup$ so you are saying that, if you insist to compress below N*H(x) bits for the entire N symbol string, then all information will be lost as N becomes very large. $\endgroup$
    – kuku
    Commented Sep 26, 2014 at 6:03
  • $\begingroup$ Nope. Say you want to send sequences of two coin flips. Then H(x) = 2. The entropy limit would be 2 * N. If you compress to just 1.5 * N bits then you will have lost 0.5 * N bits of information, or half a bit per 2 coin-flip sequence. $\endgroup$
    – Aaron
    Commented Sep 26, 2014 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.