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
Royalist

... the more specific uses of the term, the most common include: 1. A supporter of King Charles I of England during the English Civil War. 2. In the UK, a believer in ...

 
 
 
This page was created in 36.2 ms