Markov chain central limit theorem explained

In the mathematical theory of random processes, the Markov chain central limit theorem has a conclusion somewhat similar in form to that of the classic central limit theorem (CLT) of probability theory, but the quantity in the role taken by the variance in the classic CLT has a more complicated definition. See also the general form of Bienaymé's identity.

Statement

Suppose that:

• the sequence $X\_1,X\_2,X\_3,\backslash ldots$ of random elements of some set is a Markov chain that has a stationary probability distribution; and
• the initial distribution of the process, i.e. the distribution of $X\_1$, is the stationary distribution, so that $X\_1,X\_2,X\_3,\backslash ldots$ are identically distributed. In the classic central limit theorem these random variables would be assumed to be independent, but here we have only the weaker assumption that the process has the Markov property; and
• $g$ is some (measurable) real-valued function for which

Now let^{[1] [2] [3]}

\begin{align} \mu & = \operatorname E(g(X _{1)),} \\ \widehat\mu _{n} & = (1)/(n) \sum ^{n} _{k =1} g(X ^{2} _{k)\\ \sigma} & : = \lim _{n\to} \operatorname{var}(\sqrt{n}\widehat\mu _{n)} = \lim _{n\to} n \operatorname{var}(\widehat\mu _{n)} = \operatorname{var}(g(X _{1))} + 2 \sum ^{inf ty} _{k =1} \operatorname{cov}( g(X _{1),} g(X _{1+k} )). \end{align} Then as $n\; \backslash to\backslash infty,$ we have^[4] \sqrt{n} (\hat{\mu} _{n} - \mu) \xrightarrow{ l{D}} Normal ( 0 , \sigma ^{2),} where the decorated arrow indicates convergence in distribution.

Monte Carlo Setting

The Markov chain central limit theorem can be guaranteed for functionals of general state space Markov chains under certain conditions. In particular, this can be done with a focus on Monte Carlo settings. An example of the application in a MCMC (Markov Chain Monte Carlo) setting is the following:

Consider a simple hard spheres model on a grid. Suppose

X = \{ 1 , \ldots, n _{1\}} x \{ 1 , \ldots, n _{2} \} \subseteq Z ^{2} . A proper configuration on X consists of coloring each point either black or white in such a way that no two adjacent points are white. Let \chi denote the set of all proper configurations on X , N _{\chi} (n _{1,} n _{2)} be the total number of proper configurations and π be the uniform distribution on \chi so that each proper configuration is equally likely. Suppose our goal is to calculate the typical number of white points in a proper configuration; that is, if W(x) is the number of white points in x \in \chi then we want the value ofE _{\pi} W = \sum _{x} (W(x))/(N _{\chil(n} _{1,n} _{2r)})

If

n _{1} and n _{2} are even moderately large then we will have to resort to an approximation to E _{\pi} W . Consider the following Markov chain on \chi . Fix p \in ( 0 , 1 ) and set X _{1} = x _{1} where x _{1} \in \chi is an arbitrary proper configuration. Randomly choose a point (x, y) \in X and independently draw U \sim Uniform ( 0 , 1 ) . If u \le p and all of the adjacent points are black then color (x, y) white leaving all other points alone. Otherwise, color (x, y) black and leave all other points alone. Call the resulting configuration X _{1} . Continuing in this fashion yields a Harris ergodic Markov chain \{X _{1} , X _{2} , X _{3} , \ldots\} having \pi as its invariant distribution. It is now a simple matter to estimate E _{\pi} W with \overline{w _{n}=\sum} ^{n} ^{i =1} W(X _{i)/n} . Also, since \chi is finite (albeit potentially large) it is well known that X will converge exponentially fast to \pi which implies that a CLT holds for \overline{w _{n}} .

Implications

Not taking into account the additional terms in the variance which stem from correlations (e.g. serial correlations in markov chain monte carlo simulations) can result in the problem of pseudoreplication when computing e.g. the confidence intervals for the sample mean.

Sources

• Gordin, M. I. and Lifšic, B. A. (1978). "Central limit theorem for stationary Markov processes." Soviet Mathematics, Doklady, 19, 392–394. (English translation of Russian original).
• Geyer, Charles J. (2011). "Introduction to MCMC." In Handbook of Markov Chain Monte Carlo, edited by S. P. Brooks, A. E. Gelman, G. L. Jones, and X. L. Meng. Chapman & Hall/CRC, Boca Raton, pp. 3–48.

Notes and References

1. On the Markov Chain Central Limit Theorem, Galin L. Jones, https://arxiv.org/pdf/math/0409112.pdf
2. Markov Chain Monte Carlo Lecture Notes Charles J. Geyer https://www.stat.umn.edu/geyer/f05/8931/n1998.pdf page 9
3. Note that the equation for \sigma ^{2} starts from Bienaymé's identity and then assumes that \lim _{n\to} \sum ^{n} _{k =1} ((n - k))/(n) \operatorname{cov}( g(X _{1),} g(X _{1+k} )) ≈ \lim _{n\to} \sum ^{n} _{k =1} \operatorname{cov}( g(X _{1),} g(X _{1+k} )) \to \sum ^{inf ty} _{k =1} \operatorname{cov}( g(X _{1),} g(X _{1+k} )) which is the Cesàro summation, see Greyer, Markov Chain Monte Carlo Lecture Notes https://www.stat.umn.edu/geyer/f05/8931/n1998.pdf page 9
4. Geyer, Charles J. (2011). Introduction to Markov Chain Monte Carlo. In Handbook of MarkovChain Monte Carlo. Edited by S. P. Brooks, A. E. Gelman, G. L. Jones, and X. L. Meng. Chapman & Hall/CRC, Boca Raton, FL, Section 1.8. http://www.mcmchandbook.net/HandbookChapter1.pdf