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 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 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 Lemma (AEP)
so using Inclusion-Exclusion Principle:

Thus, for large enough :

and the inequality follows.