Understanding Asymptotic Equipartition Property

Question

I have some problems in understanding the precise meaning of the Asymptotic Equipartition Property, related to a large number n of independent and identically distributed random variables (X1, X2, ..., Xn). Here an example is shown (here you may find the complete material):

I do not understand the precise difference between the sentences:

• "Clearly, it is not true that all 2n sequences of length n have the same probability."

• "One might be able, however, to predict the probability of the sequence that is actually observed. The question is: what is the probability p(X1,X2,...,Xn) of the outcomes X1,X2,..., Xn, where X1,X2,..., Xn are i.i.d. according to p(x)"

• "the typical set has probability close to 1, all the elements of the typical set have same probability"

Then I read this sentence, which increases the confusion in my mind.

Answer 1

The sentences you've mentioned in your question all have a quite different meaning. Let me try to explain them one by one:

Clearly, it is not true that all $2^n$ sequences of length $n$ have the same probability.

This refers to the example of a sequence of binary i.i.d. random variables. If $p(1)\neq p(0)$ then it is clear that sequences with different numbers of ones and zeros must have different probabilities, i.e., not all sequences have the same probability.

One might be able, however, to predict the probability of the sequence that is actually observed. The question is: what is the probability $p(X_1,X_2,...,X_n)$ of the outcomes $X_1,X_2,\ldots, X_n$, where $X_1,X_2,\ldots, X_n$ are i.i.d. according to $p(x)$?

This question is answered by the asymptotic equipartition property (AEP). It turns out that the typical sequences do have approximately the same probability as $n$ gets large, namely $2^{-nH}$.

The typical set has probability close to 1, all the elements of the typical set have [the] same probability.

That's also what the AEP says. As mentioned before, the typical sequences have approximately the same probability, and the aggregate probability of the typical set approaches $1$ as $n$ gets large.

Finally, the statement

The concept of a typical set is generally different from that of a high probability set.

is indeed confusing. What is meant is the fact that there can exist individual sequences that are not part of the typical set but which have a higher probability than the typical sequences. Still, the aggregate probability of the typical set approaches $1$ for increasing $n$, and there are too few atypical sequences with high probability to have any significance.