Typical set

If a sequence <math>x_1, x_2, ..., x_n</math> 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>

It has the following properties if <math>n</math> is sufficiently large:

• The probability of a sequence from <math>X</math> being drawn from <math>{A_\epsilon}^{(n)} > 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.

See also: algorithmic complexity theory