Variance of Markov Chain Monte Carlo

In a previous post, I discussed the bias of Markov Chain Monte Carlo (MCMC) simulation. In this post I will discuss the variance. Please see the previous post for information about the notation that I use.
If \begin{equation*} S =\frac{1}{N} \sum_{t=1}^N f(X_t) \end{equation*} then for large $N$, the variance of $S$ is \begin{equation}\label{eq:20170501a} \text{Var} S = \frac{1}{N} ( \text{Var} f + 2 A ) \end{equation} with \begin{equation*} \text{Var} f = \sum_a \pi_a f(a)^2 - \left( \sum_a \pi_a f(a) \right)^2 \end{equation*} and \begin{equation*} A = \lim_{N \to \infty} \frac{1}{N}\sum_{t = 1}^N \sum_{k=1}^{\infty} \text{Cov}( f(X_t) , f(X_{t+k})) \end{equation*} For direct MC simulation, one would have instead of \eqref{eq:20170501a} \begin{equation}\label{eq:20170501b} \text{Var} S = \frac{1}{N} \text{Var} f \end{equation} The extra term $A$ comes from the autocorrelation of the sample points $f(X_t)$. After diagonalization of the transition matrix, $A$ can be written as \begin{equation}\label{eq:20170501c} \sum_a \sum_{\lambda \neq 1} f(a) \pi_a \langle f | \lambda \rangle \langle \lambda |a \rangle \frac{\lambda}{1 - \lambda} \end{equation} I test formulas \eqref{eq:20170501a} - \eqref{eq:20170501c} on an example. I work on the circle $a = 0, 1, \ldots, M-1 , M = 0$ and use the Markov process $X_t$ which moves left or right, each with probability $1/2$. For this example \begin{equation*} A = \sum_{a,b=1}^M \sum_{k=1}^{M-1} \frac{f(a) f(b)}{M^2} e^{ i 2 \pi k ( a - b)/M } \frac{ \cos (2 \pi k /M )}{1 - \cos (2 \pi k /M )} \end{equation*}
Case 1: the function is $f(a) = \sqrt{a}$.
In this case $A = 232.0723$. Because $A$ is positive, the variance of the MCMC simulation is thus larger than the variance of the direct MC simulation. In the graph below, the circles are the standard deviation of Monte Carlo simulation as function of $N$ (red: direct MC, black: MCMC). I have estimated this standard deviation by running the MC simulation 1,000 times. The black straight line is the square root of formula \eqref{eq:20170501a}, the red straight line is the square root of formula \eqref{eq:20170501b}. The numerical data fits the formulas above very well.

Case 2: the function is $f(a) = (-1)^a$.
In this case $A = -0.33321$. Because $A$ is negative, the variance of the MCMC simulation is smaller than the variance of the direct MC simulation. This is also illustrated in the graph below.

References and comments

• The motivation of this post was the first lecture on statistical mechanics on Coursera. I first thought that the variance of MCMC is always larger than the variance of direct MC, but the second example above shows that this is not the case.
• I also like the lecture notes on Computer Simulations by Evertz.