$ $ Hi, everyone. I am recently reading the lecture note of EE376a : Information Theory course from Stanford University. This note introduces that we can prove the Asymptotic Equipartition Property (or the Shannon-McMillan-Breiman Theorem) for the case that the given stochastic process $\left\{ X_n \right\}$ is a time-invariant discrete-time Markov chain with a finite state space $\mathcal{X}$ such that every $X_n$ is identically distributed over $\mathcal{X}$ with the distributuion $p$. The following is the statement. :

$$-\frac{1}{n} \log p(X_1, \cdots, X_n) \rightarrow H(X_2|X_1)$$

in probability as $n \rightarrow \infty$. The note introduces the proof of this statement by using Weak Law of Large Numbers for weak dependency. :

Let $\{ Y_n \}$ be a sequence of identically distributed random variables such that $$\lim_{n \rightarrow \infty} \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} Cov[Y_i, Y_j] = 0.$$ Then, $\frac{1}{n} \sum_{i=1}^{n} Y_i \rightarrow \mathbb{E}[Y_1]$ in probability as $n \rightarrow \infty$.

Thus, we let $Y_k := \log p(X_k |X_{k-1})$ for $k \geq 2$ and $Y_1 := \log p(X_1)$. Therefore, it suffices to verify that $$\lim_{n \rightarrow \infty} \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} Cov[Y_i, Y_j] = 0 \ \cdots (\star)$$ and the statement comes from the WLLN for weak dependency. Now, here is my question. How can I prove the part $(\star)$? Please, share some good ideas for this problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.