# Typical set in Shannon's source coding theorem

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

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 nesscarry to contain the most probable element set.

On the other hand, "smallest-sufficient set" $S_{\delta}$ which defines to be:

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 be 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?

The elements in the typical set have typical probability, close to $2^{-NH(x)}$. An element with untypically large probability, say the one with maximal probability, may not satisfy this constraint. Same goes for the rest of $S_\delta$.
• So, in pratice, people takes $S_\delta$ for their compression scheme; the only useful information that the typical set contains is the size? – kuku Sep 29 '14 at 1:08
• Also, do you accept that as N increases, $S_\delta$ approahces typical set, such that these two set end up being equivalent? – kuku Sep 29 '14 at 1:31
• Since both the typical set and $S_\delta$ have probability $1-\delta$, their distance is at most $2\delta$, so they are close to one another; this has nothing to do with $N$, and it doesn't necessarily get better with $N$. Since the sets are similar, it doesn't matter which one you "take in a compression scheme", whatever that means. – Yuval Filmus Sep 29 '14 at 1:39
• Yes. So you mean $|S_\delta|$ $\approx$ size(typical set); however, the two sets might not be identical in element? – kuku Sep 29 '14 at 3:02