online-autocovariance

Usage

``javascript
const Autocov = require('.')

const ac1 = Autocov(3)
const ac2 = Autocov(3)

;[1, 2, 3, 4, 5, 6, 7].forEach(v => { ac1(v) })

;[5, 1, 4, 7, 8, 1, -4, 0, 3, 7].forEach(v => { ac2(v) })
console.log(ac1.values, ac1.n) // ~> [ 4, 2.286, 0.714, -0.571 ]
console.log(ac2.values, ac2.n)

// Also works when calling with array argument:
// Keep in mind, it updates already defined ac1 values
console.log(ac1([8, 9, 10])) // ~> [8.25, 5.775, 3.4, 1.225]
``

How it works

Autocovariance online algorithm

Start with a formula for auto-covariance approximation:

> cov_k = (1 / n) Σ_i=1..n-k(x_i+k - μ)(x_i - μ)

Then multiply values in brackets:
> cov_k = (1 / n) Σ_i=1..n-k(x_i+kx_i + μ² - μx_i - μx_i+k)

Multiply the result with (n-k)/(n-k) to get rid of Σ:
> cov_k = α(β + μ² - μμ_i - μμ_i+k)) = α(β + μ(μ - μ_i - μ_i+k))

Where:
> α = (n - k) / n

> β = (Σ_i=1..n-k(x_i+kx_i)) / (n - k) = avg(x_i+kx_i)

> μ_i = (Σ_i=1..n-k x_i) / (n - k)

> μ_i+k = (Σ_i=1..n-k x_i+k) / (n - k)

> μ is constant here so (Σ_i=1..n-k μ) / (n - k) = μ

Using the resulting formula, for each lag k from 0 to K we only need to accumulate:
* μ - average of full (0, N) data interval; don't depend on k
* μ_i - average of (0, N-k)
* μ_i+k - average of (k, N) interval
* β - average of the product of x_i+k and x_i

To update μ iteratively we can just use a simple algorithm: online-mean

μ_i is just a lagged (t-k) value of μ:

◆◆◆◆◆ μ_i(0, N-k), k=0

◆◆◆◆◇ μ_i(0, N-k), k=1

◆◆◆◇◇ μ_i(0, N-k), k=2

To update μ_i we just calculate μ and push it to μ_i and shift all its values to the right.

μ_i+k and β are "delayed":

◆◆◆◆◆ μ_i+k(k, N), k=0

◇◆◆◆◆ μ_i+k(k, N), k=1

◇◇◆◆◆ μ_i+k(k, N), k=2

To update their values we need to track last k observations of x (xlag) and their weights (wlag) using online-lag module

xlag: [x[t], x[t-1], x[t-2], ...]

wlag: [w[t], w[t-1], w[t-2], ...]

Until we get non-zero weight wlag[k], μ_i+k and β are zero. Each observation adds its weight to the wlag object shifting its values. So after, let's say 3 observation, 3rd weight in wlag will be 1, that gives us non-zero value for corresponding lag. I definitely should rewrite this to make everything more clear :)