Typical set
|
|
In information theory, the typical set is 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 (AEP) which is a kind of law of large numbers.
If a sequence x1, ..., xn is drawn from an i.i.d. distribution <math>X<math> then the typical set, <math>{A_\epsilon}^{(n)}<math> is defined as those sequences which satisfy:
- <math>
2^{-n(H(X)+\epsilon)} \leq p(x_1, x_2, ..., x_n) \leq 2^{-n(H(X)-\epsilon)} <math>
The probability above need only be within a factor of <math>2^{n\epsilon}<math>.
It has the following properties if n is sufficiently large:
- The probability of a sequence from <math>X<math> being drawn from <math>{A_\epsilon}^{(n)}<math> is greater than <math>1-\epsilon<math>
- <math>\left| {A_\epsilon}^{(n)} \right| \leq 2^{n(H(X)+\epsilon)}<math>
- <math>\left| {A_\epsilon}^{(n)} \right| \geq (1-\epsilon)2^{n(H(X)-\epsilon)}<math>
This has great use in compression theory as it provides a theoretical means for compressing data, allowing us to represent any sequence <math>X^n<math> using <math>nH(X)<math> bits on average.
The AEP can also be proven for a large class of stationary ergodic processes.
See also: algorithmic complexity theory