# Proving that Markov Chain Monte Carlo converges

I actually asked the same question in https://math.stackexchange.com/ as well at https://math.stackexchange.com/questions/753105/proving-that-markov-chain-monte-carlo-converges but since the question is very related to this site, too, I am asking it here once again:

I am trying to understand how the very basic Markov Chain Monte Carlo approach works: We try to approximately calculate the expected value $E_{\pi(x)}[X]$ by drawing sequential samples from a Markov Chain $(x_0,x_1,...)$ with the stationary distribution $\pi(x)$ and transition matrix $T(x_i|x_{i-1})$. So, according to the MCMC approach, it should be $E_{\pi(x)}[X] \approx \frac{1}{N-N_0} \sum_{i=N_0}^{N} x_i$ where $N_0$ is the point where we assume that $p(x_{N_0})$ is close enough to the stationary distribution $\pi(x)$. We simulate the Markov Chain such that $x_0$ comes from an initial distribution $p(x_0)$ and each $x_i$ comes from $T(x_i|x_{i-1})$ .

I am trying to show that $\frac{1}{N-N_0} \sum_{i=N_0}^{N} x_i \rightarrow E_{\pi(x)}[X]$ as $N \rightarrow \infty$.

What I am doing currently is the following:

1-In order to simplify the problem I assume that $x_0$ comes already from the stationary distribution so we won't need a $N_0$ value. I have $S_N = \frac{1}{N} \sum_{i=0}^{N-1} x_i$ where $x_0$ comes from $\pi(x_0)$ and each $x_i$ comes from $T(x_i|x_{i-1})$ and $(x_0,x_1,...)$ is a Markov Chain.

2-The convergence of the regular Monte Carlo is shown with the Law of Large Numbers, so I try the same approach. By using the Weak Law of Large Numbers, I want to show that $P(|S_N - E_{\pi(x)}[X]| \geq \epsilon) \rightarrow 0$ as $N \rightarrow \infty$ where $\epsilon > 0$.

3-Weak Law of Large Numbers can be proven by using Chebyshev's Inequality. For $S_N$, I write the inequality as $P(|S_N - E[S_N]| \geq \epsilon) \leq \frac{V[S_N]}{\epsilon^2}$ where $V[S_N]$ is the variance of $S_N$ and again $\epsilon > 0$.

4-I first want to show that the expected value of $S_N$, $E[S_N]$ is equal to the expected value we are after: $E_{\pi(x)}[X]$. I showed this by using the fact that the marginal of each $x_i$ in the Markov Chain is equal to the stationary distribution $\pi(x)$: $E[S_N]=E[\frac{1}{N} (x_0 + x_1 + ... + x_{N-1})] = \frac{1}{N} (E[x_0] + E[x_1] + ... + E[x_{N-1}]) = \frac{1}{N} (E_{\pi(x)}[x] + E_{\pi(x)}[x] + ... + E_{\pi(x)}[x]) = E_{\pi(x)}[x]$

5-Now I need to evaluate the variance of $S_N$, $V[S_N]$ in order to complete the Chebyshev's Inequality. But I failed to form a closed form expression for $V[S_N]$ as I did for $E[S_N]$ and I became stuck.

I have actually two questions. First one: Is my way of proving the convergence of Markov Chain Monte Carlo is correct to begin with? Second one is, how can I carry on with the proof from the 5. step? It seems that the variance of the Monte Carlo sum doesn't have a closed form solution since $(x_0,x_1,...)$ are not i.i.d and come from a Markov Chain instead. Please note that I am a Computer Engineer, not exactly from a Mathematician background, so I could have done something very naive.