$\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.

  • 1
    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/… – DJohnson Nov 13 '16 at 20:20
up vote 9 down vote accepted

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 = \dfrac{1}{n} \sum_{i=1}^{n} f(X_i) \overset{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{\text{Var}_{\pi}(f(X_1))}_{Expected\,term} + \underbrace{2 \sum_{k=1}^{\infty} \text{Cov}_{\pi}(f(X_1), f(X_{1+k}))}_{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

  • 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 ^^). – tom4everitt Nov 15 '16 at 5:42
  • @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. – Greenparker Nov 15 '16 at 5:53
  • That would be awesome. If you don't find any, a couple of sentences hinting at the main steps would still be helpful. – tom4everitt Nov 17 '16 at 0:52
  • @tom4everitt Added a reference to the answer. Hope that is sufficient. – Greenparker Nov 17 '16 at 2:01
  • Much appreciated! Thanks! – tom4everitt Nov 21 '16 at 6:54

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).

  • 2
    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 – Taylor Nov 3 '16 at 5:23
  • 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. – tom4everitt Nov 3 '16 at 6:05

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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