Typical Strings

Let be a discreet set.
Let be Random Variables taking values in
Let .
Then the sets of typical strings of length with entropy
are defined for each by:

where is the joint probability density function for

i.e. is the set of strings that occur with probability close to

Lemma

For any , any , and any :

Proof

Each has
Thus:

Lemma (AEP)

Let be a Source taking values in a discreet set
It satisfies the Asymptotic Equipartition Property with entropy
if and only if
for all :

Proof

Let .
Note that
if and only if:

which happens if and only if:

Also, satisfies AEP iff (by definition):

Thus the equivalence follows.