Typical set
The
typical set is the set of sequences whose
probability is near to the
entropy of their source distribution and is a consequence of the
asymptotic equipartition property.
[This does not make sense. How can a set be a consequence of anything? A set is not a proposition.]
If a sequence is drawn from an i.i.d. distribution then the typical set, is defined as those sequences which satisfy:
It has the following properties if is sufficiently large:
- The probability of a sequence from being drawn from
This has great use in
compression theory as it provides a theoretical means for compressing data, allowing us to represent any sequence using bits on average.
See also: algorithmic complexity theory