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