Typical set
In information theory, the typical set is a a set of sequences whose probability is close to two raised to the negative power of the entropy of their source distribution. That this set has total probability close to one is a consequence of the asymptotic equipartition property which is a kind of law of large numbers.
If a sequence 'x1, ..., xn is drawn from an i.i.d. distribution  then the typical set,  is defined as those sequences which satisfy:
The probability above need only be within a factor of  .
It has the following properties if n 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.
The A.E.P. can also be proven for a large class of stationary ergodic processes.
See also: algorithmic complexity theory
Referenced By
List of mathematical topics (S-U) | List of probability topics
|
