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. the notion of typicality is only concerned with the probability of a sequence and not the actual sequence itself. this has great use in compression theory as it provides a theoretical means for compressing data, allowing us to represent any sequence x'n using nh(x) bits on average, and, hence, justifying the use of entropy as a measure of information from a source. the aep can also be proven for a large class of stationary ergodic processes, allowing typical set to be defined in more general cases. ==(weakly) typical sequences (weak typicality, entropy typicality)== if a sequence x1,&nbsp;...,&nbsp;x'n is drawn from an i.i.d. distribution x defined over a finite alphabet \mathcal{x}, then the typical set, a'Îµ(n)\in\mathcal{x}(n) is defined as those sequences which satisfy: : 2^{-n[h(x)+\varepsilon]} \leqslant p(x_1, x_2, \dots , x_n) \leqslant 2^{-n[h(x)-\varepsilon]} where : h(x) = - \sum_{y \isin \mathcal{x}}p(y)\log_2 p(y) is the information entropy of&nbsp;x. the probability above need only be within a factor of 2nÎµ. it has the following properties if n is sufficiently large, \epsilon>0 can be chosen arbitrarily small so that: #the probability of a sequence from x being drawn from a'Îµ(n) is greater than 1&nbsp;&minus;&nbsp;Îµ, i.e. pr[x^{(n)} \in a_\epsilon^{(n)}] \geq 1 - \epsilon #\left| {a_\varepsilon}^{(n)} \right| \leqslant 2^{n(h(x)+\varepsilon)} #\left| {a_\varepsilon}^{(n)} \right| \geqslant (1-\varepsilon)2^{n(h(x)-\varepsilon)} #most sequences are not typical. if the distribution over \mathcal{x} is not uniform, then the fraction of sequences that are typical is ::\frac{|a_\epsilon^{(n)}|}{|\mathcal{x}^{(n)}|} \equiv \frac{2^{nh(x)}}{2^{n\log|\mathcal{x}|}} = 2^{-n(\log|\mathcal{x}|-h(x))} \rightarrow 0 ::as n becomes very large, since h(x) < \log|\mathcal{x}|. for a general stochastic process {x(t)} with aep, the (weakly) typical set can be defined similarly with p(x1,&nbsp;x2,&nbsp;...,&nbsp;x'n) replaced by p(x0Ï) (i.e. the probability of the sample limited to the time interval [0,&nbsp;Ï]), n being the degree of freedom of the process in the time interval and h(x) being the entropy rate. if the process is continuous-valued, differential entropy is used instead. counter-intuitively, most likely sequence is often not a member of the typical set. 
Information_theory Probability_theory