An ergodic theorem for Markov chains is as follows.

If a Markov chain $(X_n)_{n \ge 0}$ is irreducible and has an invariant distribution $\pi$, then $$\frac{1}{n} \sum_{k=0}^{n-1} f(X_k) \to \overline{f}:=\sum_{i \in I} \pi_i f(i)$$ almost surely as $n \to \infty$, for any bounded function $f:I \to \mathbb{R}$.

I have attached the proof that appears in Norris's text below. Here, $V_i(n):= \sum_{k=0}^{n-1} \mathbf{1}_{\{X_k=i\}}$ denotes the number of visits to state $i$ before time $n$.

  1. I do not understand the step $$\sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \sum_{i \notin J} \left(\frac{V_i(n)}{n}+\pi_i\right)\le 2\sum_{i \in J}\left|\frac{V_i(n)}{n}-\pi_i\right| + 2 \sum_{i \notin J} \pi_i.$$ After rearranging, I see that this is equivalent to showing that $$\sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| \ge \sum_{i \notin J} \left(\frac{V_i(n)}{n}-\pi_i\right),$$ but I don't see why this is true either.
  2. Why was it necessary to examine a subset $J \subset I$? What is wrong with the following? $$\left|\frac{1}{n}\sum_{k=0}^{n-1} f(X_k)-\overline{f}\right| \le \sum_{i \in I} \left|\frac{V_i(n)}{n}-\pi_i\right|<\epsilon,$$ for $n$ large enough?

Norris's proof.

enter image description here


1 Answer 1


I was able to figure it out eventually...


\begin{align*} &\sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \sum_{i \notin J} \left(\frac{V_i(n)}{n}+\pi_i\right)\\ &= \sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \left(1-\sum_{i \in J} \frac{V_i(n)}{n}\right)+\sum_{i \notin J}\pi_i & \sum_{i \in I} V_i(n)=n\\ &= \sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \sum_{i \in J}\left(\pi_i- \frac{V_i(n)}{n}\right)+2\sum_{i \notin J}\pi_i & \sum_{i \in I} \pi_i=1\\ &\le 2\sum_{i \in J}\left|\frac{V_i(n)}{n}-\pi_i\right| + 2 \sum_{i \notin J} \pi_i. \end{align*} 2. We need $J$ to be finite in order to choose $N$ such that the difference $\left|\frac{V_i(n)}{n}-\pi_i\right|$ is small.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .