1
$\begingroup$

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):

enter image description here

enter image description here

enter image description here

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. enter image description here

$\endgroup$
  • 1
    $\begingroup$ Have you read "Element of Information Theory", Cover & Thomas ? Especially its chapter 3 Asymptotic Equipartition Property (2nd edition) ? IMHO, it contains the answer for all of your questions. $\endgroup$ – AlexTP Dec 5 '19 at 9:33
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.