# 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\))

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,

Where

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,

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

## References¶

- Sokal, A. D. “Monte Carlo Methods in Statistical Mechanics Foundations and New Algorithms”
- Flegal, J. M., M. Haran, and G. L. Jones. “Markov chain Monte Carlo: Can we trust the third significant figure?.” Statistical Science (2008): 250-260.
- J. D. Chodera, W. C. Swope, J. W. Pitera, C. Seok, and K. A. Dill. “Use of the weighted histogram analysis method for the analysis of simulated and parallel tempering simulations.” JCTC 3(1):26-41, 2007.
- Plummer, M, N. Best, K. Cowles, and K. Vines (2006). CODA: convergence diagnosis and output analysis for MCMC. R News, 6(1) pp. 7-11.
- Geyer, C. J. “Practical markov chain monte carlo.” Statistical Science (1992): 473-483.
- Heidelberger, P, and P D. Welch. “A spectral method for confidence interval generation and run length control in simulations.” Communications of the ACM 24.4 (1981): 233-245.
- Thompson, M. B. “A Comparison of Methods for Computing Autocorrelation Time” arXiv preprint arXiv:1011.0175 (2010).