Markov chain Monte Carlo

Remarks

By the ergodic theorem for irreducible chains with a stationary distribution, $\hat{\pi}_n(f) \to \pi(f)$ almost surely as $n \to \infty$, for every starting state. The usual way to obtain clause 1 is to impose detailed balance for $\pi$, as the Metropolis–Hastings algorithm does. In practice the first steps, the burn-in, are often discarded, and if the chain is also aperiodic then the law of $X_k$ tends to $\pi$ by the convergence theorem. Example: on $S = \Z$ with $\pi(x) \propto e^{-x^2}$, propose $x \pm 1$ with probability $1/2$ each and accept with probability $\min(1, \pi(y)/\pi(x))$. This chain is irreducible and satisfies detailed balance for $\pi$. Non-example: the simple random walk on the path $\set{1, \ldots, m}$, which moves to a uniform neighbour, has stationary law proportional to the degrees. So its averages estimate expectations under that law, not under the uniform law, and it fails clause 1 for uniform $\pi$ when $m \ge 3$.