# Lightweight estimation of $\sum_{i=0}^n \gamma(i)$, the sum of the auto-covariances

Suppose $X_1,\cdots,X_n$ are samples from a stationary time series and let $\gamma(i)$ denote the autocovariance $\gamma(i) = \mathrm{Cov}(X_{k},X_{k+i})$. Suppose $n$ is very large.

In a numerical method I am working on, the quantity $\sum_{i=0}^n \gamma(i)$ appears all the time. I am looking for a quick/lightweight way to guess/estimate this quantity from the data without computing $\sum_{i=0}^n \hat\gamma(i)$ because this is tedious for large $n$ (here $\hat\gamma(i)$ denote the sample autocovariance). It has to do the estimation in $O(n)$ time. Does there exist such a method/trick/insight?

Let $\dot X_i=X_i-\bar X$. Using the definition of the sample autocovariance function and rearranging the resulting double sum yields \begin{align} \sum_{k=0}^{n-1}\hat\gamma_k &=\sum_{k=0}^{n-1}\left(\frac1n\sum_{i=1}^{n-k}\dot X_i \dot X_{i+k}\right) \\&=\frac1n \sum_{i=1}^n \sum_{j=1}^i \dot X_i \dot X_j \\&=\frac1n \sum_{i=1}^n \left(\dot X_i \sum_{j=1}^i \dot X_j\right). \end{align} For example, for $n=3$ the sum can be written as $$\frac13(\dot X_1 \dot X_1 + \dot X_2 (\dot X_1 + \dot X_2) + \dot X_3 (\dot X_1 + \dot X_2 + \dot X_3).$$ This can be computed in $O(n)$ time without any nested for-loops by adding $\dot X_i$ to the last stored value of the inner sum to get its new value. This can be implemented in R using for-loops as

sumacf <- function(x) {
x <- x - mean(x)
n <- length(x)
innersum <- 0
outersum <- 0
for (i in 1:n) {
innersum <- innersum + x[i]
outersum <- outersum + x[i]*innersum
}
1/n*outersum
}


or, more efficiently, as

sumacf <- function(x) {
x <- x - mean(x)
mean(x*cumsum(x))
}


A small test against R's acf function to verify that this works:

> x <- rnorm(10)
> sumacf(x)
[1] 0.610785
> sum(acf(x,type="covariance")\$acf)
[1] 0.610785

• Godt forslag professor Aug 3 '17 at 21:42