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.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 353 |
Nodes: | 16 (2 / 14) |
Uptime: | 34:12:25 |
Calls: | 7,648 |
Files: | 12,809 |
Messages: | 5,698,979 |