The Asymptotic Equipartition Property
Thomas M. Cover, Joy A. Thomas · 2001
In information theory, the analog of the law of large numbers is the Asymptotic Equipartition Property (AEP). It is a direct consequence of the weak law of large numbers. The law of large numbers states that for independent, identically distributed (i.i.d.) random variables, is close to its expected value EX for large values of n. The AEP states that is close to the entropy H, where X1,X2,…,Xn are i.i.d. random variables and p(X1,X2,…,Xn) is the probability of observing the sequence X1,X2,…,Xn. Thus the probability p(X1,X2,…,Xn) assigned to an observed sequence will be close to 2−nH. This enables us to divide the set of all sequences into two sets, the typical set, where the sample entropy is close to the true entropy, and the non-typical set, which contains the other sequences. Most of our attention will be on the typical sequences. Any property that is proved for the typical sequences will then be true with high probability and will determine the average behavior of a large sample.