Asymptotic equipartition property

In information theory, the asymptotic equipartition property (AEP) is a general property of the output samples of a stochastic source. It is fundamental to the concept of typical set used in theories of compression.Given a discrete-time stationary ergodic stochastic process X {displaystyle X}   on the probability space ( Ω , B , p ) {displaystyle (Omega ,B,p)}  , the asymptotic equipartition property is an assertion thatGiven X {displaystyle X}   is an i.i.d. source which may take values in the alphabet X {displaystyle {mathcal {X}}}  , its time series X 1 , … , X n {displaystyle X_{1},ldots ,X_{n}}   is i.i.d. with entropy H ( X ) {displaystyle H(X)}   in the discrete-valued case and differential entropy in the continuous-valued case. The weak law of large numbers gives the asymptotic equipartition property with convergence in probability,Consider a finite-valued sample space Ω {displaystyle Omega }  , i.e. | Ω | < ∞ {displaystyle |Omega |<infty }  , for the discrete-time stationary ergodic process X := { X n } {displaystyle X:={X_{n}}}   defined on the probability space ( Ω , B , p ) {displaystyle (Omega ,B,p)}  . The asymptotic equipartition property for such stochastic source, known as the Shannon–McMillan–Breiman theorem (due to Claude Shannon, Brockway McMillan, and Leo Breiman), can be shown using the sandwich proof by Algoet and Cover outlined as follows:The assumptions of stationarity/ergodicity/identical distribution of random variables is not essential for the asymptotic equipartition property to hold. Indeed, as is quite clear intuitively, the asymptotic equipartition property requires only some form of the law of large numbers to hold, which is fairly general. However, the expression needs to be suitably generalized, and the conditions need to be formulated precisely.Discrete-time functions can be interpolated to continuous-time functions. If such interpolation f is measurable, we may define the continuous-time stationary process accordingly as X ~ := f ∘ X {displaystyle { ilde {X}}:=fcirc X}  . If the asymptotic equipartition property holds for the discrete-time process, as in the i.i.d. or finite-valued stationary ergodic cases shown above, it automatically holds for the continuous-time stationary process derived from it by some measurable interpolation. i.e.A category theoretic definition for the equipartition property is given by Gromov Given a sequence of Cartesian powers P N = P × ⋯ × P {displaystyle P^{N}=P imes cdots imes P}   of a measure space P, this sequence admits an asymptotically equivalent sequence HN of homogeneous measure spaces (i.e. all sets have the same measure; all morphisms are invariant under the group of automorphisms, and thus factor as a morphism to the terminal object) .