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.

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