Autocorrelation Estimators¶

Functions¶

Naive summation of the empirical autocorrelation function results in a catastrophic error from the tail of the integral. There are variety of different estimators in the literature for $\tau_{inf}$ . This module implements a few of them.

Theory¶

The autocorrelation time quantifies the rate of convergence of the sample mean of a function of an (aperiodic / stationary / ergodic, recurrent) Markov chain. Suppose that our Markov chain, $X = {X_1, X_2, \ldots X_n}$ in the state space $\Omega$ has invariant distribution $\pi$ . For some function, $g$ , the goal is to estimate $\mu \equiv \int_\Omega g(x) \pi (dx)$ . The ergodic theorem guarentees (if $E_\pi |g| < \infty$ )

$\newcommand{\cov}{\mathop{\rm Cov}\nolimits} \newcommand{\var}{\mathop{\rm Var}\nolimits}$

$\bar{g}_n \equiv \frac{1}{n} \sum_{i=1}^n g(X_i) \rightarrow \pi.$

Assume that we run our Markov chain for $n$ iterations. How accurate is $\bar{g}_n$ ?

Define the autocovariance, $C_g(t) = \cov(g(X_s), g(X_{s+t}))$ , and the autocorrelation $\rho_g(t) = C_g(t)/C_g(0)$ . Then,

$\begin{split}\var(\bar{g}_n) &= \frac{1}{n^2} \sum_{i,j=1}^n \cov(g(X_i), g(X_j)) \\ &\approx \frac{1}{n} \tau_{int} C_g(0) \hspace{1em}\text{for}\hspace{2pt} n \gg \tau\end{split}$

Where

$\tau_{int} = 1 + 2\sum_{t=1}^\infty \rho_g(t)$

If each iteration of the chain was i.i.d, the asymptotic variance would be $C_g(0)/n$ , so $\tau_{int}$ can be thought of as a reduction in the effective number of independent samples due to autocorrelation,

$n_{effective} = \frac{n}{\tau_{int}}.$

This quantity is also referred to as the statistical inefficiency, IAT, or IACT.

Autocorrelation Estimators¶

Functions¶

Theory¶

References¶