Recursive formula for variance

Question

I'd like to know how I can recursively (iteratively) compute variance, so that I may calculate the standard deviation of a very large dataset in javascript. The input is a sorted array of positive integers.

Answer 1

Recall that, for every $n\geqslant1$, $$ \bar x_n=\frac1n\sum_{k=1}^nx_k, $$ and $$ \bar\sigma^2_n=\frac1n\sum_{k=1}^n(x_k-\bar x_n)^2=\frac1n\sum_{k=1}^nx_k^2-(\bar x_n)^2. $$ Hence simple algebraic manipulations starting from the identities $$ (n+1)\bar x_{n+1}=n\bar x_n+x_{n+1}, $$ and $$ (n+1)(\bar\sigma^2_{n+1}+(\bar x_{n+1})^2)=n(\bar\sigma^2_n+(\bar x_n)^2)+x_{n+1}^2, $$ lead to $$ \bar x_{n+1}=\bar x_n+\frac{x_{n+1}-\bar x_n}{n+1}, $$ and $$ \bar\sigma^2_{n+1}=\bar\sigma^2_n+(\bar x_n)^2-(\bar x_{n+1})^2+\frac{x_{n+1}^2-\bar\sigma^2_n-(\bar x_n)^2}{n+1}. $$ Thus, $(n,\bar x_n,x_{n+1})$ yield $\bar x_{n+1}$ and $(n,\bar\sigma^2_n,\bar x_n,\bar x_{n+1},x_{n+1})$ yield $\bar\sigma^2_{n+1}$.

Answer 2

I ended up using this incremental approach:

function mean(array) {
  var i = -1, j = 0, n = array.length, m = 0;
  while (++i < n) if (a = array[i]) m += (a - m) / ++j;
  return j ? m : undefined;
}

function variance(array, mean_value) {
  if (!mean_value) return undefined;
  var i = -1, j = 0, n = array.length, v = 0;
  while (++i < n) {
    a = Math.pow((array[i] - mean_value), 2)
    v += (a - v) / ++j;
  }
  return v * (n/(n-1));
}