1
$\begingroup$

$ $ 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.

$\endgroup$

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.