2
$\begingroup$

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?

$\endgroup$
  • $\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$ – Yuval Filmus Sep 24 '14 at 4:29
  • 1
    $\begingroup$ see: rate distortion theory $\endgroup$ – john mangual Dec 9 '14 at 23:19
2
$\begingroup$

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.

$\endgroup$
  • $\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 Sep 26 '14 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 Sep 26 '14 at 16:56

Your Answer

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

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