4
$\begingroup$

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?

$\endgroup$
4
+50
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ Godt forslag professor $\endgroup$
    – Mikkel Rev
    Aug 3 '17 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.