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


$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_δ$

| cite | improve this answer | |
  • $\begingroup$ Also, do you accept that as N increases, $S_\delta$ approahces typical set, such that these two set end up being equivalent? $\endgroup$ – kuku Sep 29 '14 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.