Asymptotic Equipartition Property

Let be a Random Variables taking values in a discrete set Let be the joint distribution of :

for all . (using notation ) Then we say that satisfies AEP with entropy if:

where means Convergence in Probability and is Random Probability of Random Variable

Note

There are alternative definitions (e.g. based on Typical Strings > Lemma (AEP)) However, this definition made the most sense to me, so I’m using it as main. Note also that I’m making no assumptions about . We can, however, prove that Discrete Memoryless Source satisfies AEP. I am also not saying anything about although I call it entropy, to hint that it should be Mathematical Entropy Interpretation of Asymptotic Equipartition Property

Theorem

Suppose satisfies AEP with entropy . Then the smallest sets of strings such that:

have sizes .

More precisely, the following lemmata:

Lemma 1

For every there is a sequence of sets with such that:

Proof

Let . Take , the sets of Typical Strings with entropy . We know that

Also satisfies AEP thus by Typical Strings > Lemma (AEP):

Lemma 2

Let . Suppose for some we have:

Then for all large enough :

Proof

Let be the set of Typical Strings with entropy . By definition:

and thus:

Note that by assumption and by Typical Strings > Lemma (AEP) so using Inclusion-Exclusion Principle:

Thus, for large enough :

and the inequality follows.