0
$\begingroup$

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?

enter image description here

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – greg
    Commented Sep 26, 2014 at 23:27

1 Answer 1

Reset to default
3
$\begingroup$

It's not clear exactly what your question is. What the textbook is talking about is the strong converse to Shannon's source coding theorem, but rate distortion theory is another part of information theory relevant to this.

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).

Rate distortion theory answers the question: I have a signal that I want to compress to a length that is shorter than its entropy. How small an amount of distortion can I introduce into the signal to ensure that I can recover it with high probability? You can use this theory with an arbitrary formula for distortion (and there is a nice formula if the distortion is given by a single-symbol equation).

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ yes，this is what I am asking. You answered my question. However, can I please ask one more question on the "typical set" and "smallest sufficient set"? $\endgroup$
    – kuku
    Commented Sep 28, 2014 at 3:01
  • $\begingroup$ The way this site works, if you want to ask a new question, don't ask it by editing the old one. Start a new question and ask it. $\endgroup$
    – Peter Shor
    Commented Sep 28, 2014 at 3:03

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.