This paper has a footnote that says

The sum of the auto-correlation coefficients from $-\infty$ to $\infty$ is an estimate of the mixing time.

What is the rationale for this? The author calls this the "effective correlation length" in another paper, but I haven't gotten much success in finding an explanation for this.


1 Answer 1


This is a consequence of a CLT established by Kipnis and Varadhan (1986):

If the Markov chain $(X_n)$ is aperiodic, irreducible, and reversible with invariant distribution $\pi$, the CLT applies when $$ 0 < \gamma_g^2 =\mathbb{E}_{\pi}[{\overline g}^2(X_0)] + 2 \; \sum_{k=1}^{\infty} \; \mathbb{E}_{\pi}[{\overline g}(X_0) {\overline g}(X_k)] < +\infty. $$ with $$ {1\over \sqrt{N}}\; \sum_{n=1}^N\; \{g(X_n)-\mathbb{E}_{\pi}[g(X)]\} = {1\over \sqrt{N}}\; \sum_{n=1}^N\; {\overline g}(X_k) \buildrel \cal L\over \leadsto {\cal N}(0,\gamma^2_g) \;. $$

See also the answers to this question on X validated.

  • 2
    $\begingroup$ I'm afraid I'm not able to find the above in the linked Kipnis' paper. Is it somewhere around Corollary 1.5? Also, I understand that the autocorrelation sum appears in the expression $\mathbb{E}_{\pi}[{\overline g}^2(X_0)] + 2 \; \sum_{k=1}^{\infty} \; \mathbb{E}_{\pi}[{\overline g}(X_0) {\overline g}(X_k)]$, which is the variance for the limit of ${1\over \sqrt{N}}\; \sum_{n=1}^N\; {\overline g}(X_k)$, but how does this relate to the mixing time? $\endgroup$
    – peco
    Nov 1, 2017 at 17:36

Your Answer

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

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