Asymptotic equipartition property

• Let x denote some measurable set ${\displaystyle x=X(A)}$ for some ${\displaystyle A\in B}$
• Parameterize the joint probability by n and x as
  $${\displaystyle j(n,x):=p\left(x_{0}^{n-1}\right).}$$

  
• Parameterize the conditional probability by i, k and x as
  $${\displaystyle c(i,k,x):=p\left(x_{i}\mid x_{i-k}^{i-1}\right).}$$

  
• Take the limit of the conditional probability as k → ∞ and denote it as
  $${\displaystyle c(i,x):=p\left(x_{i}\mid x_{-\infty }^{i-1}\right).}$$

  
• Argue the two notions of entropy rate
  $${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\mathrm {E} [-\log j(n,X)]\quad {\text{and}}\quad \lim _{n\to \infty }\mathrm {E} [-\log c(n,n,X)]}$$

  
  exist and are equal for any stationary process including the stationary ergodic process X. Denote it as H.
• Argue that both
  $${\displaystyle {\begin{aligned}c(i,k,X)&:=\left\{p\left(X_{i}\mid X_{i-k}^{i-1}\right)\right\}\\c(i,X)&:=\left\{p\left(X_{i}\mid X_{-\infty }^{i-1}\right)\right\}\end{aligned}}}$$

  
  where i is the time index, are stationary ergodic processes, whose sample means converge almost surely to some values denoted by ${\displaystyle H^{k}}$ and ${\displaystyle H^{\infty }}$ respectively.
• Define the k-th order Markov approximation to the probability ${\displaystyle a(n,k,x)}$ as
  $${\displaystyle a(n,k,x):=p\left(X_{0}^{k-1}\right)\prod _{i=k}^{n-1}p\left(X_{i}\mid X_{i-k}^{i-1}\right)=j(k,x)\prod _{i=k}^{n-1}c(i,k,x)}$$

  
• Argue that ${\displaystyle a(n,k,X(\Omega ))}$ is finite from the finite-value assumption.
• Express ${\displaystyle -{\frac {1}{n}}\log a(n,k,X)}$ in terms of the sample mean of ${\displaystyle c(i,k,X)}$ and show that it converges almost surely to H^k
• Define the probability measure
  $${\displaystyle a(n,x):=p\left(x_{0}^{n-1}\mid x_{-\infty }^{-1}\right).}$$

  
• Express ${\displaystyle -{\frac {1}{n}}\log a(n,X)}$ in terms of the sample mean of ${\displaystyle c(i,X)}$ and show that it converges almost surely to H^∞.
• Argue that ${\displaystyle H^{k}\searrow H}$ 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
  $${\displaystyle \mathrm {E} \left[{\frac {a(n,k,X)}{j(n,X)}}\right]=a(n,k,X(\Omega ))}$$

  
  which is finite as argued before.
• Show that
  $${\displaystyle \mathrm {E} \left[{\frac {j(n,X)}{a(n,X)}}\right]=1}$$

  
  by conditioning on the infinite past ${\displaystyle X_{-\infty }^{-1}}$ and iterating the expectation.
• Show that
  $${\displaystyle \forall \alpha \in \mathbb {R} \$$ :\ \Pr \left[{\frac {a(n,k,X)}{j(n,X)}}\geq \alpha \right]\leq {\frac {a(n,k,X(\Omega ))}{\alpha }}}

  
  using the Markov's inequality and the expectation derived previously.
• Similarly, show that
  $${\displaystyle \forall \alpha \in \mathbb {R} \$$ :\ \Pr \left[{\frac {j(n,X)}{a(n,X)}}\geq \alpha \right]\leq {\frac {1}{\alpha }},}

  
  which is equivalent to
  $${\displaystyle \forall \alpha \in \mathbb {R} \$$ :\ \Pr \left[{\frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}\geq {\frac {1}{n}}\log \alpha \right]\leq {\frac {1}{\alpha }}.}

  
• Show that limsup of
  $${\displaystyle {\frac {1}{n}}\log {\frac {a(n,k,X)}{j(n,X)}}\quad {\text{and}}\quad {\frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}}$$

  
  are non-positive almost surely by setting α = n^β for any β > 1 and applying the Borel–Cantelli lemma.
• Show that liminf and limsup of
  $${\displaystyle -{\frac {1}{n}}\log j(n,X)}$$

  
  are lower and upper bounded almost surely by H^∞ and H^k 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 → ∞.

The proof follows from a simple application of Markov's inequality (applied to second moment of ${\displaystyle \log(p(X_{i}))}$.

$${\displaystyle {\begin{aligned}\Pr \left[\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-{\overline {H}}(X)\right|>\varepsilon \right]&\leq {\frac {1}{n^{2}\varepsilon ^{2}}}\mathrm {Var} \left[\sum _{i=1}^{n}\left(\log(p(X_{i})\right)^{2}\right]\\&\leq {\frac {M}{n\varepsilon ^{2}}}\to 0{\text{ as }}n\to \infty \end{aligned}}}$$

It is obvious that the proof holds if any moment ${\displaystyle \mathrm {E} \left[|\log p(X_{i})|^{r}\right]}$ is uniformly bounded for r > 1 (again by Markov's inequality applied to r-th moment). Q.E.D.

Even this condition is not necessary, but given a non-stationary random process, it should not be difficult to test whether the asymptotic equipartition property holds using the above method.