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

<p>The <em>strong converse</em> says that if you try to compress information to fewer bits than the entropy, the probability that <em>all</em> of the information is restored correctly goes to zero as $N$ goes to $\infty$ (the theorem also gives you a bound on this probability).</p>

<p><em>Rate distortion theory</em> 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). </p>

<p>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.</p>

CC BY-SA 3.0
2014-09-28T03:01:08.273Z
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"?
kuku
CC BY-SA 3.0
2014-09-28T03:03:42.440Z
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.
Peter Shor 
CC BY-SA 3.0
2014-09-27T21:02:10.770Z
2014-09-27T23:33:27.803Z
2014-09-27T23:33:27.803Z
Peter Shor 
<p>I was following the textbook by David Mackay: <a href="http://www.cs.toronto.edu/~mackay/itprnn/book.pdf" rel="nofollow noreferrer"><em>Information theory inference and learning algorithms</em></a>.</p>

<p>I have question on Shannon's source coding theorem (p81):</p>

<blockquote>
  <p>$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$; <strong>conversely if they are compressed into fewer than $N \cdot H(x)$ bits it is virtually certain that information will be lost.</strong></p>
</blockquote>

<p>My question is the bold part of the above: what happens when you go below $N \cdot H(x)$ bits?</p>

<p>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.</p>

<p>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?</p>

<p><img src="https://i.sstatic.net/nRWBw.png" alt="enter image description here"></p>

<hr>

<p>I found something on the web regarding this question: <a href="http://www.kim-bostroem.de/Library/Notes/Shannon.pdf" rel="nofollow noreferrer">http://www.kim-bostroem.de/Library/Notes/Shannon.pdf</a></p>

<p>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?</p>

CC BY-SA 3.0
2014-09-26T23:27:10.640Z
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.
greg
<it.information-theory><coding-theory>
Source Coding Theorem: what happen when we go below N*H(x) bits?
kuku
# Source Coding Theorem: what happen when we go below N*H(x) bits?

(Asked by: username_0 on 2014-09-25)

I was following the textbook by David Mackay: [*Information theory inference and learning algorithms*](http://www.cs.toronto.edu/~mackay/itprnn/book.pdf).

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](https://i.sstatic.net/nRWBw.png)

---

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?

**Tags:** it.information-theory, coding-theory

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-09-27. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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"?  
> **username_2**: 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.  

---

