# Source Coding Theorem: what happen when we go below N*H(x) bits?

I was following the textbook by David Mackay: Information theory inference and learning algorithms.

I have question on 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 bold part of the above: what happens when you go below $N \cdot H(x)$ bits?

There is an example in the textbook (p77), where he shows that, as $N$ increases, the average entropy per symbol approaches $H(X)$, for a risk tolerance $0 \lt \delta \lt 1$. (So it becomes flatter as indicated on the diagram.) 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 definition 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?

I found something on the web regarding this question: http://www.kim-bostroem.de/Library/Notes/Shannon.pdf

It is saying that for each symbol, if you compress below $H(x)$ bits, then for $N \to\infty$, we will lose all the information. Can someone please confirm this?

• It's not clear what you mean when you ask "how much information will be lost?". The answer to your question is probably that if you're compressing into $K$ bits, then you'll lose at least $N \cdot H(x) - K$ bits of information. But it's not trivial to define what this number is actually measuring. Sep 26, 2014 at 23:27

The strong converse says that if you try to compress information to fewer bits than the entropy, the probability that all of the information is restored correctly goes to zero as $N$ goes to $\infty$ (the theorem also gives you a bound on this probability).
And of course, if you compress the source to $K$ bits, than you can choose $K/H(X)$ symbols of the original to keep and discard all the others.