Hi,
I studied the source coding theorem, chapter 4 of the MacKay's book,
but I have some perplexities.
The source coding theorem implies that, for large N, the cardinality
of the smallest delta-sufficient subset is about 2^(NH). So, in this
set we have the 2^(NH) most probable outcomes.
There is also the asymptotic equipartition principle, which implies
that, for large N, the typical set, whose elements have probability of
'about' 2^(-NH), contains almost all the probability. So, the typical
set has about 2^(NH) elements.
So, we have that the typical set and the smallest delta-sufficient
subset for large N have approximately the same cardinality, 2^(NH),
right?
But the typical set doesn't contain the most probable outcomes (as for
the other set), so I imagine it as the smallest delta-sufficient
subset "shifted" a bit towards the less probable outcomes, where
"shifted" refers to a picture in which the outcomes are represented as
points on segment, with probability increasing from left to right: the
smallest delta-sufficient subset is at the extreme right, while the
typical set is a bit more centered, right?
So, the book says that we can (and probably should) define a
compression algorithm that gives a distinct name of length NH bits to
each element of the typical set. That's ok, but my question is: why
the typical set and not the smallest delta-sufficient set? I know that
it should be equivalent, because both sets contains almost all the
probability, but why should we choose the typical set?
Thanks

I am studying this myself. Here is my take. A Typical subset is a
delta-sufficient subset. But not all delta-sufficient subsets are
typical. Why?  Because the elements of the typical subset have similar
probabilities, while the smallest delta-sufficient subset, for example,
is not typical (by construction. You chose the most probable elements).

On Wednesday, February 25, 2009 at 10:26:20 AM UTC-3, Simba wrote:

Hi,
I studied the source coding theorem, chapter 4 of the MacKay's book,
but I have some perplexities.