1.2.1 Asymptotic Equipartition Property

The (noiseless) fixed-length source coding theorem states that, except for outcomes in a set of vanishing probability, a source can be encoded at its entropy but not more efficiently. Since Shannon (1948) and MacMillan (1953), the Asymptotic Equipartition Property (AEP) has been known to be a sufficient condition for a source to be encodable at its entropy. The AEP states that the set {of n-strings whose log-probabilities are roughly equal to minus the n-block entropy} exhausts all the probability as n goes to infinity. Not all sources satisfy the AEP, and some sources require encoding rates higher or lower than the entropy.

S. Verdú and T. S. Han, "The Role of the Asymptotic Equipartition Property in Noiseless Source Coding,"
IEEE Trans. on Information Theory, May 1997.

shows that the AEP is not only a sufficient condition for the validity of the source coding theorem, but it is, in fact, a necessary condition, in the setting of nonzero-entropy finite-alphabet sources. For more general information sources, the AEP is a necessary condition for the validity of the strong source coding theorem (in which the probability of error of any code with rate below the entropy goes to 1). We show that any source that satisfies the strong converse must also satisfy the direct part. For nonzero-entropy finite-alphabet sources, we show that the (weak) converse is always satisfied and that the strong converse is satisfied if and only if the direct part is satisfied.

Showing that the AEP is equivalent to the validity of the source coding theorem reinforces the prominent role played by the AEP in information theory, which is due to the insight it offers into the behavior of information sources as well as the fact that it is generally much easier to verify whether the AEP holds for a particular source than to check whether the source can be encoded at its entropy but not more efficiently. It is somewhat surprising that the full role of the AEP in noiseless data compression had not been discovered before. A key step in our results is to show that the classical statement of the AEP is redundant, in the sense that the property is equivalent to the probability of the set of atypically big masses vanishing asymptotically.

Stationarity/Ergodicity is a well-known sufficient condition for the AEP. However, it does not encompass nonserial information sources of interest such as the empirical distribution of an n-string, the final value of a random walk or the number of Poisson points with growing mean. A new sufficient condition for the AEP (the flat-top property) is introduced to handle those sources.