# Estimate the asymptotic efficiency of a Markov chain sampling by the method of batching

In the paper Efficient Metropolis Jumping Rules, the author is writing that he used "the method of batching" for the estimation of $$\operatorname{eff}_{\overline\theta_i}$$ in Table 1 (on page 605). Could somebody explain to me what he is actually meaning? By the answer to my other question, it is clear to me how we can compute the autocorrelation of a one-dimensional set of samples at any lag. How do we estimate $$\operatorname{eff}_{\overline\theta_i}$$ from that?

I assume the authors are talking about the "batch means estimators" which are very popular in steady state simulation and MCMC.

Suppose $$X_1, X_2, \dots X_N$$ are from a Markov chain with stationary distribution $$\pi$$ with mean $$\theta$$ and variance $$\tau^2$$. Let $$\bar{\theta}$$ be the sample average. Then if the samples had been iid, the variance of $$\bar{\theta}$$ would have been $$\tau^2/N$$. But since they are not iid, the variance is something else, dentoed by $$V_{\bar{\theta}}$$. Specifically $$\lim_{N \to \infty} N \text{Var}(\bar{\theta}) = V_{\bar{\theta}}$$

So $$V_{\bar{\theta}}$$ is the asymptotic variance of $$\bar{\theta}$$. In other words, if a Markov chain CLT holds, then $$\sqrt{N}(\bar{\theta} - \theta) \overset{d}{\to} N(0, V_{\bar{\theta}})$$

The authors then define $$\text{eff}_{\bar{\theta}} = \dfrac{\tau^2}{V_{\bar{\theta}}}\,,$$ as an assessment of how well the Markov chain is mixing. (Note, this efficiency is very similar to effective sample size )

In order to estimate $$\text{eff}_{\bar{\theta}}$$, we need an estimate of $$\tau^2$$ and $$V_{\bar{\theta}}$$. Note that since $$\tau^2$$ is the variance of the target distribution $$\pi$$, the sample variance is the default estimator of $$\tau^2$$. Thus, the main difficulty is in estimating $$V_{\bar{\theta}}$$.

From the paper it can be easily concluded that $$V_{\bar{\theta}}$$ has the following specific form: $$V_{\bar{\theta}} = \tau^2 + 2 \sum_{k=1}^{\infty} \text{Cov}(X_1, X_{1+k})\,.$$

You would think that according to the structure of $$V_{\bar{\theta}}$$, we must estimate each of the lag covariances $$\text{Cov}(X_1, X_{1+k})$$, up until some finite $$K$$, and then sum them up. However, this is unknown to be a highly variable estimator. To stabilize the estimator, one can weight the covariances and then add them up, and that leads to the spectral variance estimators (also highly popular).

However, a simple estimator is the batch means estimator, which makes use of the idea that means inside each batch mimic the overall mean. That is, let's break the sample into $$a$$ number of batches, each of size $$b$$ $$(N = ab)$$. $$\underbrace{X_1, \dots X_b}_{\bar{Y}_1}, \underbrace{X_{b+1}, \dots X_{2b}}_{\bar{Y}_2} \dots \underbrace{X_{(a-1)b+1}, \dots X_{ab}}_{\bar{Y}_a}\,.$$

Inside each batch, calculate the average of the batch, $$\bar{Y}_ii = 1, \dots, a$$. Then note that each $$\bar{Y}_i$$ is a Monte Carlo estimator of $$\theta$$, and if $$b$$ increases with $$N$$, each batch mean also has a Markov chain CLT. So $$\sqrt{b}(\bar{Y}_i - \theta) \overset{d}{\to}N(0, V_{\bar{\theta}})\,,$$ The limiting variance is the same because at infinite samples $$\bar{Y}_i$$ is indistinguishable from $$\bar{\theta}$$.

Thus, now we have $$\bar{Y}_1, \dots, \bar{Y}_a$$ all dependent (but almost independent for large $$b$$), with mean $$\theta$$ and variance $$V_{\bar{\theta}}/b$$. So to estimate $$V_{\bar{\theta}}$$, we can get the sample variance of the batch means and rescale by $$b$$. That is

$$BM_{\theta} = \dfrac{b}{a-1} \sum_{i=1}^{a} (\bar{Y}_i - \bar{\theta})^2\,.$$

This is called the batch means estimator. The role of $$b$$ is essentially the same as the role of $$K$$, both of which must grow with $$N$$ for strong consistency of estimators. You can find details of the estimators, results and conditions of consistency all here.