# Definition of autocorrelation time (for effective sample size)

I've found two definitions in the literature for the autocorrelation time of a weakly stationary time series:

$$\tau_a = 1+2\sum_{k=1}^\infty \rho_k \quad \text{versus} \quad \tau_b = 1+2\sum_{k=1}^\infty \left|\rho_k\right|$$

where $\rho_k = \frac{\text{Cov}[X_t,X_{t+h}]}{\text{Var}[X_t]}$ is the autocorrelation at lag $k$.

One application of the autocorrelation time is to find the "effective sample size": if you have $n$ observations of a time series, and you know its autocorrelation time $\tau$, then you can pretend that you have

$$n_\text{eff} = \frac{n}{\tau}$$

independent samples instead of $n$ correlated ones for the purposes of finding the mean. Estimating $\tau$ from data is non-trivial, but there are a few ways of doing it (see Thompson 2010).

The definition without absolute values, $\tau_a$, seems more common in the literature; but it admits the possibility of $\tau_a<1$. Using R and the "coda" package:

require(coda)
ts.uncorr <- arima.sim(model=list(),n=10000)         # white noise
ts.corr <- arima.sim(model=list(ar=-0.5),n=10000)    # AR(1)
effectiveSize(ts.uncorr)                             # Sanity check
# result should be close to 10000
effectiveSize(ts.corr)
# result is in the neighborhood of 30000... ???


The "effectiveSize" function in "coda" uses a definition of the autocorrelation time equivalent to $\tau_a$, above. There are some other R packages out there that compute effective sample size or autocorrelation time, and all the ones I've tried give results consistent with this: that an AR(1) process with a negative AR coefficient has more effective samples than the correlated time series. This seems strange.

Obviously, this can never happen in the $\tau_b$ definition of autocorrelation time.

What is the correct definition of autocorrelation time? Is there something wrong with my understanding of effective sample sizes? The $n_\text{eff} > n$ result shown above seems like it must be wrong... what's going on?

• Just to make sure I haven't misunderstood isn't that supposed to be $Cov(X_t,X_{t+k})$ instead of the $h$? – sachinruk Oct 23 '15 at 0:33
• I am interested in the second definition, i.e., $\tau_b$. Could you provide the literature where you found it? – Harry Jan 1 '16 at 0:25
• You are right @sachinruk, it should be indexed with k. – Bremsstrahlung Jan 16 at 18:57

First, the appropriate definition of "effective sample size" is IMO linked to a quite specific question. If $X_1, X_2, \ldots$ are identically distributed with mean $\mu$ and variance 1 the empirical mean $$\hat{\mu} = \frac{1}{n} \sum_{k=1}^n X_k$$ is an unbiased estimator of $\mu$. But what about its variance? For independent variables the variance is $n^{-1}$. For a weakly stationary time series, the variance of $\hat{\mu}$ is $$\frac{1}{n^2} \sum_{k, l=1}^n \text{cov}(X_k, X_l) = \frac{1}{n}\left(1 + 2\left(\frac{n-1}{n} \rho_1 + \frac{n-2}{n} \rho_2 + \ldots + \frac{1}{n} \rho_{n-1}\right) \right) \simeq \frac{\tau_a}{n}.$$ The approximation is valid for large enough $n$. If we define $n_{\text{eff}} = n/\tau_a$, the variance of the empirical mean for a weakly stationary time series is approximately $n_{\text{eff}}^{-1}$, which is the same variance as if we had $n_{\text{eff}}$ independent samples. Thus $n_{\text{eff}} = n/\tau_a$ is an appropriate definition if we ask for the variance of the empirical average. It might be inappropriate for other purposes.

With a negative correlation between observations it is certainly possible that the variance can become smaller than $n^{-1}$ ($n_{\text{eff}} > n$). This is a well known variance reduction technique in Monto Carlo integration: If we introduce negative correlation between the variables instead of correlation 0, we can reduce the variance without increasing the sample size.

• For anyone who wants to know more about the use of negative correlation in Monte Carlo simulation, try googling "antithetic variates". More info in course notes here or here. – andrewtinka Oct 21 '13 at 17:39
• In this estimate, we assume we know the true variance of the distribution. How would one write the variance of the sample mean in terms of the sample variance? Similar to the t-Student argument for IID processes but with n_eff? – Bremsstrahlung Jan 16 at 20:23

and

https://cran.r-project.org/web/packages/mcmcse/mcmcse.pdf

for effective sample size. I think the alternative formulation using the ratio of sample variance and asymptotic Markov chain variance via batch mean is more appropriate estimator.

• Could you expand on the content in those links? As it stand, sthis is too short for an answer by our standards! – kjetil b halvorsen May 18 '16 at 17:50