I'm trying to adapt an algorithm to calculate covariance to work over a rolling window on the data. Wikipedia has an algorithm for online covariance:
def online_covariance(data1, data2): mean1 = mean2 = 0 M12 = 0 for x, y in zip(data1, data2): n += 1 delta1 = (x - mean1) / n mean1 += delta1 delta2 = (y - mean2) / n mean2 += delta2 M12 += (n - 1) * delta1 * delta2 - M12 / n return n / (n - 1) * M12
But I need this to work over an arbitrarily sized rolling window. I've already adapted a different algorithm on that Wikipedia page for variance to work on a rolling window, but I'm getting stuck doing it for covariance.
The below pseudo-code is what I have so far. Assume the
window function returns an enumerable over a structure that contains the elements entering and leaving the window (
def online_covariance(data1, data2, windowSize): mean1 = mean2 = 0 M12 = 0 i = 0 covars =  for x, y in zip(window(data1, windowSize), window(data2, windowSize)): if(n < windowSize) n += 1 delta1 = (i < windowSize ? x.Entered - mean1 : x.Entered - x.Exited) / n mean1 += delta1 delta2 = (i < windowSize ? y.Entered - mean2 : y.Entered - y.Exited) / n mean2 += delta2 // Up to this point I can verify the algorithm is correct- // it keeps the correct means for each data set // This next line is where I'm stuck- // it needs to be modified to remove the value that // just left the window M12 += (n - 1) * delta1 * delta2 - M12 / n covars.Add(n / (n - 1) * M12) i++ return covars