Encyclopedia > Typical set

  Article Content

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 <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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Springs, New York

... of age or older. The average household size is 2.57 and the average family size is 3.08. In the town the population is spread out with 22.3% under the age of 18, 6.3% ...

 
 
 
This page was created in 28.8 ms