<p>$S_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S_δ$ but it is not necessarily a member of the typical set.</p>

<p>The only reason to use the typical set instead of $S_δ$ is to make the proof of the source coding theorem easier. (See the paragraph at the top of page 84 in your book.) The typical set along with the asymptotic equipartition property makes it easy to count the size of the typical set and to put bounds on the probability of each element in the set. This is not so easy to do when working with $S_δ$</p>

CC BY-SA 3.0
2014-09-29T01:32:26.417Z
Also, do you accept that as N increases, $S_\delta$ approahces typical set, such that these two set end up being equivalent?
kuku
CC BY-SA 3.0
2014-09-28T18:33:34.417Z
2014-09-28T18:33:34.417Z
Aaron
<p>I was following the textbook by David Mackay: <a href="http://www.cs.toronto.edu/~mackay/itprnn/book.pdf" rel="nofollow"><em>Information theory inference and learning algorithms</em></a>.</p>

<p>I have question on asymptotic equiparition' principle:</p>

<blockquote>
  <p>For an ensemble of $N$ $i.i.d$ random variables $X^N=(X_1,X_2....X_N),$ with $N$ sufficiently large, the outcome $x=(x_1,x_2...x_N)$ is almost certain to belong to a subset of $|A_x^N|$ having only $2^{NH(x)}$ members, with each member having probability  "close-to" $2^{-NH(x)}$.</p>
</blockquote>

<p>And then in the textbook, it also says that <strong>typical set doesn't necessarily contain the most probable element set.</strong> </p>

<p>Because the "smallest-sufficient set" $S_{\delta}$ which is defined as:</p>

<blockquote>
  <p>the smallest subset of of $A_x$ satisfying  $P(x\epsilon S_{\delta})\ge 1-\delta $, for $0\leq{\delta}\leq1. $  In other words, $S_{\delta}$ is constructed by taking the most probable elements in $A_x$, then the second probable......until the total probabily is  $\ge1-{\delta}$.</p>
</blockquote>

<p>My question is, <strong>as $N$ increases, does $S_{\delta}$ approaches typical set such that these two sets will end up being equivalent of each other?</strong> If the size of the typical set is identical to the size of $|S_{\delta}|$,  then why are we even bother with $S_{\delta}$? Why can't we just take the typical set as our compression scheme instead?</p>

CC BY-SA 3.0
2014-10-03T15:27:51.947Z
Cross-posted on cs.se: http://cs.stackexchange.com/questions/30372/typical-set-in-shannons-source-coding-theorem
Yuval Filmus
<it.information-theory><coding-theory><encoding>
Question about "typical set" in Shannon's source coding theorem
kuku
# Question about "typical set" in Shannon's source coding theorem

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

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 asymptotic equiparition' principle:

> For an ensemble of $N$ $i.i.d$ random variables $X^N=(X\_1,X\_2....X\_N),$ with $N$ sufficiently large, the outcome $x=(x\_1,x\_2...x\_N)$ is almost certain to belong to a subset of $|A\_x^N|$ having only $2^{NH(x)}$ members, with each member having probability "close-to" $2^{-NH(x)}$.

And then in the textbook, it also says that **typical set doesn't necessarily contain the most probable element set.**

Because the "smallest-sufficient set" $S\_{\delta}$ which is defined as:

> the smallest subset of of $A\_x$ satisfying $P(x\epsilon S\_{\delta})\ge 1-\delta $, for $0\leq{\delta}\leq1. $ In other words, $S\_{\delta}$ is constructed by taking the most probable elements in $A\_x$, then the second probable......until the total probabily is $\ge1-{\delta}$.

My question is, **as $N$ increases, does $S\_{\delta}$ approaches typical set such that these two sets will end up being equivalent of each other?** If the size of the typical set is identical to the size of $|S\_{\delta}|$, then why are we even bother with $S\_{\delta}$? Why can't we just take the typical set as our compression scheme instead?

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

> **Comments:**
> **username_1**: Cross-posted on cs.se: http://cs.stackexchange.com/questions/30372/typical-set-in-shannons-source-coding-theorem  

---

## 1 answers

### Answer by username_2 on 2014-09-28. Score: 3

$S\_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S\_δ$ but it is not necessarily a member of the typical set.

The only reason to use the typical set instead of $S\_δ$ is to make the proof of the source coding theorem easier. (See the paragraph at the top of page 84 in your book.) The typical set along with the asymptotic equipartition property makes it easy to count the size of the typical set and to put bounds on the probability of each element in the set. This is not so easy to do when working with $S\_δ$

> **Comments:**
> **username_0**: Also, do you accept that as N increases, $S_\delta$ approahces typical set, such that these two set end up being equivalent?  

---

