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.