Theorem of Shannon, McMillan, Breiman

This appendix proves the Shannon–McMillan–Breiman theorem or Asymptotic Equipartition Property (AEP). We demonstrate it in the version Shannon presented in 1948 (Shannon, 1948). In his famous work of 1948, Shannon proved this property for independent and identically distributed processes and extended the result to stationary ergodic processes. McMillan (1953) and Breiman (1957) proved AEP for ergodic sources with a finite alphabet. Let |$X_1, X_2, ..., X_N$| be |$N$| independent variables and identically distributed (i.i.d.) with probability distribution |$p(x)$|⁠. It is possible to prove that: To prove it, it is sufficient to note that independent random variables’ functions are themselves random variables. Since |$X_i$| are i.i.d., so will |$\log_2 P(X_i)$| be. Therefore, by the law of large numbers, we have: as it was meant to prove. Let us now define the set of so-called typical sequences, |$A_{\epsilon}^{n}$|⁠, with respect to |$p(x)$|⁠, as the set of sequences |$(x_1, x_2, ..., x_n)$| such that: As a consequence of the AEP, it is possible to show that the set |$A_{\epsilon}^{n}$| satisfies the following properties: In practice, these properties indicate that the set of typical sequences has a probability close to unity, all its elements are about equiprobable, and the number of its components is about |$2^{nH}$|⁠. The demonstration of these properties comes easily from the definition of a typical sequence and from AEP. The demonstration can be found in Cover and Thomas (2006).