# Monte Carlo and Sampling

Suppose that we have a finite state space $$E$$ and a distribution $$\pi:E \rightarrow (0,1)$$ with $$\pi(x) >0$$. The idea behind Monte Carlo is that we generate a Markov chain $$X=(X_n,n\in \mathbb{N})$$ with transition matrix $$p$$ such that $$p$$ is ergodic (irreducible and aperiodic) and that $$\pi$$ is the unique invariant distribution of $$p$$, so that the total variation $$||p^n(x,y) -\pi(y)||_{TV} \rightarrow 0$$ as $$n\rightarrow \infty$$.

Question.

However, I'm a little confused about the rigorous justification behind sampling. Suppose that we want to compute the expectation $$\mathbb{E}f(Y)$$ where $$Y$$ is a random variables with distribution $$\pi$$. Then I understand that $$\mathbb{E}^x f(X_n) \rightarrow \mathbb{E} f(Y)$$ for bounded $$f$$. But how do we approximate $$\mathbb{E}^x f(X_n)$$? I would assume that we would like to apply the strong law in "some way" with respect to the Markov chain $$X$$ so that almost surely, we have $$\frac{1}{n} \sum_{k=1}^n f(X_k) \rightarrow \mathbb{E}f(Y), \qquad n\rightarrow \infty$$ Of course, this is not properly justified, since $$X_1,...$$ are not pairwise independent and identically distributed so we can't use the strong law.

It has that if $$X_1, X_2,...$$ is a stationary real-valued stochastic process that is ergodic, and $$E(X_i) = \mu$$, then $$\bar{X} \rightarrow \mu$$ almost surely.
• After some reading about ergodic theory, it seems that by Birkhoff, we do not require that $p$ is aperiodic. It seems that as long as $p$ is irreducible and has invariant distribution $\pi$, then we can compute expectation $\mathbb{E}^\pi f(X_0)$ using the sample mean. Is this true? May 17, 2020 at 2:37