Asymptotic equipartition property

rdf:langString Asymptotic equipartition property

rdf:langString * Let x denote some measurable set for some * Parameterize the joint probability by n and x as * Parameterize the conditional probability by i, k and x as * Take the limit of the conditional probability as k → ∞ and denote it as * Argue the two notions of entropy rate exist and are equal for any stationary process including the stationary ergodic process X. Denote it as H. * Argue that both where i is the time index, are stationary ergodic processes, whose sample means converge almost surely to some values denoted by and respectively. * Define the k-th order Markov approximation to the probability as * Argue that is finite from the finite-value assumption. * Express in terms of the sample mean of and show that it converges almost surely to Hk * Define the probability measure * Express in terms of the sample mean of and show that it converges almost surely to H∞. * Argue that as k → ∞ using the stationarity of the process. * Argue that H = H∞ using the Lévy's martingale convergence theorem and the finite-value assumption. * Show that which is finite as argued before. * Show that by conditioning on the infinite past and iterating the expectation. * Show that using the Markov's inequality and the expectation derived previously. * Similarly, show that which is equivalent to * Show that limsup of are non-positive almost surely by setting α = nβ for any β > 1 and applying the Borel–Cantelli lemma. * Show that liminf and limsup of are lower and upper bounded almost surely by H∞ and Hk respectively by breaking up the logarithms in the previous result. * Complete the proof by pointing out that the upper and lower bounds are shown previously to approach H as k → ∞.

rdf:langString Proof

rdf:langString 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 data compression. Roughly speaking, the theorem states that although there are many series of results that may be produced by a random process, the one actually produced is most probably from a loosely defined set of outcomes that all have approximately the same chance of being the one actually realized. (This is a consequence of the law of large numbers and ergodic theory.) Although there are individual outcomes which have a higher probability than any outcome in this set, the vast number of outcomes in the set almost guarantees that the outcome will come from the set. One way of intuitively understanding the property is through Cramér's large deviation theorem, which states that the probability of a large deviation from mean decays exponentially with the number of samples. Such results are studied in large deviations theory; intuitively, it is the large deviations that would violate equipartition, but these are unlikely. In the field of pseudorandom number generation, a candidate generator of undetermined quality whose output sequence lies too far outside the typical set by some statistical criteria is rejected as insufficiently random. Thus, although the typical set is loosely defined, practical notions arise concerning sufficient typicality.