Typical Set - (Weakly) Typical Sequences (weak Typicality, Entropy Typicality)

(Weakly) Typical Sequences (weak Typicality, Entropy Typicality)

If a sequence x₁, ..., x_n is drawn from an i.i.d. distribution X defined over a finite alphabet, then the typical set, A_ε(n)(n) is defined as those sequences which satisfy:

Where

is the information entropy of X. The probability above need only be within a factor of 2nε.

It has the following properties if n is sufficiently large, can be chosen arbitrarily small so that:

1. The probability of a sequence from X being drawn from A_ε(n) is greater than 1 − ε, i.e.
2. Most sequences are not typical. If the distribution over is not uniform, then the fraction of sequences that are typical is

as n becomes very large, since

For a general stochastic process {X(t)} with AEP, the (weakly) typical set can be defined similarly with p(x₁, x₂, ..., x_n) replaced by p(x₀τ) (i.e. the probability of the sample limited to the time interval ), 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. For example, suppose that X is an i.i.d Bernoulli random variable with p(0)=0.1 and p(1)=0.9. In n independent trials, since p(1)>p(0), the most likely sequence of outcome is the sequence of all 1's, (1,1,...,1). Here the entropy of X is H(X)=0.469, while

So this sequence is not in the typical set because its average logarithmic probability cannot come arbitrarily close to the entropy of the random variable X no matter how large we take the value of n. For Bernoulli random variables, the typical set consists of sequences with average numbers of 0s and 1s in n independent trials. For this example, if n=10, then the typical set consist of all sequences that has a single 0 in the entire sequence. In case p(0)=p(1)=0.5, then every possible binary sequences belong to the typical set.