2
$\begingroup$

How to prove that in case of an irreducible, aperiodic and positive recurrent Markov Chain time average along sample paths is equal to the ensemble average ? i.e.

$$\lim_{n\to \infty }\frac{1}{n}\sum _ {i=1} ^{n} X_{i} \rightarrow E[X_k] $$

where $E[X_k]$ is calculated from the steady state probability distribution.

Now each $X_i$'s are dependent because it is a Markov Chain. So, not possible to apply law of large numbers.

I posted this in math exchange, have not got any answer. So, posting here

$\endgroup$
2
  • 8
    $\begingroup$ One answer is that this is a special case of the Birkhoff ergodic theorem since Markov measures are ergodic. This doesn't require aperiodicity, just irreducibility and positive recurrence. (I guess you consider a Markov chain with countable state space?) For a stronger result, that uses irreducibility, you can look at the Perron-Frobenius theorem, which shows that in fact if $\mu_n$ is any sequence of probability distributions on the state space that evolves according to the Markov law, then $\mu_n$ converges to the stationary distribution, without the need for Cèsaro averages. $\endgroup$ Feb 23, 2013 at 5:14
  • $\begingroup$ @VaughnClimenhaga You mean "For a stronger result, that uses aperiodicity" right? $\endgroup$
    – guillefix
    Mar 22, 2019 at 23:12

1 Answer 1

2
$\begingroup$

You should be able to find a proof of this fact in any undergraduate stochastic processes books. Durrett's book Essentials of Stochastic Processes has a good proof of this.

I'll give an outline of how to prove it. Suppose that the Markov chain starts at $X_0=x$. Let $0 = R_0 < R_1 < R_2 < \ldots$ be the sequence of return times to the site $x$. Since the Markov chain is positive recurrent $E[R_n - R_{n-1}] = E[R_1] < \infty$. Next, let be the number of returns that have occurred by time $n$ (that is $R_{N_n} \leq n < R_{N_n+1}$). Finally, let $Y_k = \sum_{i=R_{k-1}+1}^{R_k} X_i$. With this notation then we have that $$ \frac{1}{n} \sum_{k=1}^{N_n} Y_k \leq \frac{1}{n} \sum_{i=1}^n X_i \leq \frac{1}{n} \sum_{k=1}^{N_n} Y_k + \frac{Y_{N_n+1}}{n}. $$

Next, note that the renewal theorem implies that $$ \lim_{n\rightarrow\infty} \frac{N_n}{n} = \frac{1}{E[R_1]}, $$ and so $$ \lim_{n\rightarrow \infty} \frac{1}{n} \sum_{k=1}^{N_n} Y_k = \lim_{n\rightarrow \infty} \frac{N_n}{n} \frac{1}{N_n} \sum_{k=1}^{N_n} Y_k = \frac{E[Y_1]}{E[R_1]}, $$ where the last equality also follows from the fact that the $Y_k$ are i.i.d. Now, it can also be shown that $Y_{N_n+1}/n \rightarrow 0$ and so the upper and lower bounds on $n^{-1} \sum_{i=1}^n X_i$ given above imply that $$ \lim_{n\rightarrow \infty} \frac{1}{n} \sum_{i=1}^n X_i = \frac{E[Y_1]}{E[R_1]}. $$

The last step of the proof is to show that $ \frac{E[Y_1]}{E[R_1]} = E^\pi[X_0]$, where $\pi$ is the unique stationary distribution. This can be shown by noting that the stationary distribution $\pi$ has the formula $$ \pi(y) = \frac{1}{E[R_1]} E\left[ \sum_{i=1}^{R_1} \mathbf{1}_{X_i = y} \right]. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.