Asymptotic Equipartition Property - AEP For Discrete-time Finite-valued Stationary Ergodic Sources

AEP For Discrete-time Finite-valued Stationary Ergodic Sources

Consider a finite-valued sample space, i.e., for the discrete-time stationary ergodic process defined on the probability space . The AEP for such stochastic source, known as the Shannon-McMillan-Breiman theorem, can be shown using the sandwich proof by Algoet and Cover outlined as follows:

• Let denote some measurable set for some
• Parameterize the joint probability by and x as
• Parameterize the conditional probability by and as .
• Take the limit of the conditional probability as and denote it as
• Argue the two notions of entropy rate and exist and are equal for any stationary process including the stationary ergodic process . Denote it as .
• Argue that both and, where is the time index, are stationary ergodic processes, whose sample means converge almost surely to some values denoted by and respectively.
• Define the -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
• Define, which is a probability measure.
• Express in terms of the sample mean of and show that it converges almost surely to
• Argue that as using the stationarity of the process.
• Argue that 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 of both and are non-positive almost surely by setting for any and applying the Borel-Cantelli lemma.
• Show that and of are lower and upper bounded almost surely by and 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 as .