10
$\begingroup$

$\newcommand{\E}{\mathbb{E}}$$\newcommand{\P}{\mathbb{P}}$The Central Limit Theorem (CLT) states that for $X_1,X_2,\dots$ independent and identically distributed (iid) with $\E[X_i]=0$ and $\operatorname{ Var} (X_i)<\infty$, the sum converges to a normal distribution as $n\to\infty$: $$ \sum_{i=1}^n X_i \to N\left(0, \sqrt{n}\right). $$

Assume instead that $X_1,X_2,\dots$ form a finite-state Markov chain with a stationary distribution $\P_\infty$ with expectation 0 and bounded variance. Is there a simple extension of CLT for this case?

The papers I've found on CLT for Markov Chains generally treat much more general cases. I would be very grateful for a pointer to the relevant general result and an explanation of how it applies.

$\endgroup$
1
  • 1
    $\begingroup$ Lin and Tegmark's paper Critical Behavior from Deep Dynamics goes into some depth about the "limitations* of Markov processes and analysis ... available here ...ai2-s2-pdfs.s3.amazonaws.com/5ba0/… $\endgroup$ Nov 13, 2016 at 20:20

2 Answers 2

11
$\begingroup$

Alex R.'s answer is almost sufficient, but I add a few more details. In On the Markov Chain Central Limit Theorem – Galin L. Jones, if you look at theorem 9, it says,

If $X$ is a Harris ergodic Markov chain with stationary distribution $\pi$, then a CLT holds for $f$ if $X$ is uniformly ergodic and $E[f^2] < \infty$.

For finite state spaces, all irreducible and aperiodic Markov chains are uniformly ergodic. The proof for this involves some considerable background in Markov chain theory. A good reference would be Page 32, at the bottom of Theorem 18 here.

Hence, the Markov chain CLT would hold for any function $f$ that has a finite second moment. The form the CLT takes is described as follows.

Let $\bar{f}_n$ be the time averaged estimator of $E_{\pi}[f]$, then as Alex R. points out, as $n \to \infty$, $$\bar{f}_n = \frac{1}{n} \sum_{i=1}^n f(X_i) \overset{\text{a.s.}}{\to} E_\pi[f].$$

The Markov chain CLT is $$\sqrt{n} (\bar{f}_n - E_\pi[f]) \overset{d}{\to} N(0, \sigma^2), $$

where $$\sigma^2 = \underbrace{\operatorname{Var}_\pi(f(X_1))}_\text{Expected term} + \underbrace{2 \sum_{k=1}^\infty \operatorname{Cov}_\pi(f(X_1), f(X_{1+k}))}_\text{Term due to Markov chain}. $$

A derivation for the $\sigma^2$ term can be found on Page 8 and Page 9 of Charles Geyer's MCMC notes here

$\endgroup$
6
  • 1
    $\begingroup$ Thanks, that's very clear! Is there an easy argument why finite state, irreducible, and aperiodic Markov chains are uniformly ergodic? (not that I don't trust you ^^). $\endgroup$ Nov 15, 2016 at 5:42
  • $\begingroup$ @tom4everitt Unfortunately, the definition of "easy" is subjective. If you are familiar with drift and minorization conditions for Markov chains, then the argument is easy. If not, then it would be a long argument. I will try and find a reference instead. Might take a while. $\endgroup$ Nov 15, 2016 at 5:53
  • $\begingroup$ That would be awesome. If you don't find any, a couple of sentences hinting at the main steps would still be helpful. $\endgroup$ Nov 17, 2016 at 0:52
  • 1
    $\begingroup$ @tom4everitt Added a reference to the answer. Hope that is sufficient. $\endgroup$ Nov 17, 2016 at 2:01
  • 1
    $\begingroup$ @LeastSquaresWonderer You can find a somewhat clear explanation of the formula on page 8 and 9 in Charles Geyer's MCMC notes. $\endgroup$ Jun 10, 2018 at 14:36
8
$\begingroup$

The "usual" result for Markov Chains is the Birkhoff Ergodic Theorem, which says that

$$\frac{1}{n}\sum_{i=1}^nf(X_i)\rightarrow E_{\pi}[f],$$

where $\pi$ is the stationary distribution, and $f$ satisfies $E|f(X_1)|<\infty$, and the convergence is almost-sure.

Unfortunately the fluctuations of this convergence are generally quite difficult. This is mainly due to the extreme difficulty of figuring out total variation bounds on how quickly $X_i$ converge to the stationary distribution $\pi$. There are known cases where the fluctuations are analogous to the CLT, and you can find some conditions on the drift which make the analogy hold: On the Markov Chain Central Limit Theorem -- Galin L. Jones (See Theorem 1).

There are also stupid situations, for example a chain with two states, where one is absorbing (i.e. $P(1\rightarrow 2)=1$ and $P(2\rightarrow 1)=0$. In this case there are no fluctuations, and you get convergence to a degenerate normal distribution (a constant).

$\endgroup$
2
  • 2
    $\begingroup$ I don't think he's asking about almost sure convergence. I think he wants a sort of 'translation' of some of the CLTs on general spaces: probably an explanation of what the required assumptions mean in the specific context of finite state space chains $\endgroup$
    – Taylor
    Nov 3, 2016 at 5:23
  • $\begingroup$ Thanks. Would a normal, nice, finite-state Markov chain trivially satisfy the drift condition? I would even be happy knowing it for just a two-state chain, but it's far from obvious to me how to prove it. $\endgroup$ Nov 3, 2016 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.