Online Variance
by Joshua Burkholder
online_variance.pdf
online_variance.docx

Let $n$ be the number of values, $v_n$ be the biased sample variance of the first $n$ values, $v_{n-1}$ be the biased sample variance for the first $n-1$ values, $x_n$ be the $n$-th value, ${\overline{x}}_n$ be the sample mean of the first $n$ values, and ${\overline{x}}_{n-1}$ be the sample mean of the first $n-1$ values. Then, the recurrence equation for the biased sample variance (a.k.a. online variance) is:

$v_n=v_{n-1}-\frac{v_{n-1}-\left(x_n-{\overline{x}}_n\right)\left(x_n-{\overline{x}}_{n-1}\right)}{n}$

 

Proof:

The definition of the biased sample variance of the first $n$ values is defined as:

$v_n=\frac{{\displaystyle \sum _{i=1}^n{\left(x_i-{\overline{x}}_n\right)}^2}}{n}$

If we expand this definition, we have:

$\begin{array}{c}{v}_n=\frac{{\displaystyle \sum _{i=1}^n\left(x_i^2-2x_i{\overline{x}}_n+{\overline{x}}_n^2\right)}}{n}\\ v_n=\frac{{\displaystyle \sum _{i=1}^{n-1}\left(x_i^2-2x_i{\overline{x}}_n+{\overline{x}}_n^2\right)}+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\end{array}$

Since the recurrence equation for the sample mean is:

${\overline{x}}_n={\overline{x}}_{n-1}-\frac{{\overline{x}}_{n-1}-x_n}{n}$,

then we also have:

$\begin{array}{c}{\overline{x}}_n^2={\left({\overline{x}}_{n-1}-\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\\ {\overline{x}}_n^2={\overline{x}}_{n-1}^2-2{\overline{x}}_{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\end{array}$

With these, we have:

$\begin{array}{c}{v}_n=\frac{{\displaystyle \sum _{i=1}^{n-1}\left(x_i^2-2x_i\left({\overline{x}}_{n-1}-\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+\left({\overline{x}}_{n-1}^2-2{\overline{x}}_{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\right)\right)}+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{{\displaystyle \sum _{i=1}^{n-1}\left(x_i^2-2x_i{\overline{x}}_{n-1}+2x_i\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\overline{x}}_{n-1}^2-2{\overline{x}}_{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\right)}+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{{\displaystyle \sum _{i=1}^{n-1}\left(x_i^2-2x_i{\overline{x}}_{n-1}+{\overline{x}}_{n-1}^2+2x_i\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)-2{\overline{x}}_{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\right)}+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{{\displaystyle \sum _{i=1}^{n-1}\left({\left(x_i-{\overline{x}}_{n-1}\right)}^2+2x_i\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)-2{\overline{x}}_{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\right)}+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{{\displaystyle \sum _{i=1}^{n-1}{\left(x_i-{\overline{x}}_{n-1}\right)}^2}+{\displaystyle \sum _{i=1}^{n-1}\left(2x_i\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)-2{\overline{x}}_{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\right)}+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\end{array}$

Since the biased sample variance for the first $n-1$ values is:

$v_{n-1}=\frac{{\displaystyle \sum _{i=1}^{n-1}{\left(x_i-{\overline{x}}_{n-1}\right)}^2}}{n-1}$,

then we also have:

${\displaystyle \sum _{i=1}^{n-1}{\left(x_i-{\overline{x}}_{n-1}\right)}^2}=\left(n-1\right)v_{n-1}$.

With this, we have:

$\begin{array}{c}{v}_n=\frac{\left(n-1\right)v_{n-1}+{\displaystyle \sum _{i=1}^{n-1}\left(2x_i\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)-2{\overline{x}}_{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)+{\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}^2\right)}+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left({\displaystyle \sum _{i=1}^{n-1}\left(2x_i-2{\overline{x}}_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\right)}\right)+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left({\displaystyle \sum _{i=1}^{n-1}\left(2x_i\right)}+{\displaystyle \sum _{i=1}^{n-1}\left(-2{\overline{x}}_{n-1}\right)}+{\displaystyle \sum _{i=1}^{n-1}\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)}\right)+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(2{\displaystyle \sum _{i=1}^{n-1}\left(x_i\right)}-2{\overline{x}}_{n-1}{\displaystyle \sum _{i=1}^{n-1}\left(1\right)}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right){\displaystyle \sum _{i=1}^{n-1}\left(1\right)}\right)+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(2{\displaystyle \sum _{i=1}^{n-1}\left(x_i\right)}-2{\overline{x}}_{n-1}\left(n-1\right)+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(n-1\right)\right)+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\end{array}$

Since the definition of the sample mean for the first $n-1$ values is:

${\overline{x}}_{n-1}=\frac{{\displaystyle \sum _{i=1}^{n-1}{x}_i}}{n-1}$,

then we also have:

${\displaystyle \sum _{i=1}^{n-1}{x}_i}=\left(n-1\right){\overline{x}}_{n-1}$.

With this, we have:

$\begin{array}{c}{v}_n=\frac{\left(n-1\right)v_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(2\left(n-1\right){\overline{x}}_{n-1}-2{\overline{x}}_{n-1}\left(n-1\right)+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(n-1\right)\right)+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(\cancel{2\left(n-1\right){\overline{x}}_{n-1}}\cancel{-2\left(n-1\right){\overline{x}}_{n-1}}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(n-1\right)\right)+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(\frac{{\overline{x}}_{n-1}-x_n}{n}\right)\left(n-1\right)+x_n^2-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\left(n-1\right)\left(\frac{{\overline{x}}_{n-1}^2-2x_n{\overline{x}}_{n-1}+x_n^2}{n^2}\right)-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n^2}-\frac{2\left(n-1\right)x_n{\overline{x}}_{n-1}}{n^2}+\frac{\left(n-1\right)x_n^2}{n^2}-2x_n{\overline{x}}_n+{\overline{x}}_n^2}{n}\end{array}$

Since the recurrence equation for the sample mean is:

${\overline{x}}_n={\overline{x}}_{n-1}-\frac{{\overline{x}}_{n-1}-x_n}{n}$,

then we also have:

$\begin{array}{c}{\overline{x}}_n=\frac{n{\overline{x}}_{n-1}-{\overline{x}}_{n-1}+x_n}{n}\\ {\overline{x}}_n=\frac{\left(n-1\right){\overline{x}}_{n-1}+x_n}{n}\end{array}$

Moreover, we have:

$\begin{array}{c}{\overline{x}}_n^2={\left(\frac{\left(n-1\right){\overline{x}}_{n-1}+x_n}{n}\right)}^2\\ {\overline{x}}_n^2=\frac{{\left(\left(n-1\right){\overline{x}}_{n-1}+x_n\right)}^2}{n^2}\\ {\overline{x}}_n^2=\frac{{\left(n-1\right)}^2{\overline{x}}_{n-1}^2+2\left(n-1\right)x_n{\overline{x}}_{n-1}+x_n^2}{n^2}\\ {\overline{x}}_n^2=\frac{{\left(n-1\right)}^2{\overline{x}}_{n-1}^2}{n^2}+\frac{2\left(n-1\right)x_n{\overline{x}}_{n-1}}{n^2}+\frac{x_n^2}{n^2}\end{array}$

With this, we have:

$\begin{array}{c}{v}_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n^2}-\frac{2\left(n-1\right)x_n{\overline{x}}_{n-1}}{n^2}+\frac{\left(n-1\right)x_n^2}{n^2}-2x_n{\overline{x}}_n+\left(\frac{{\left(n-1\right)}^2{\overline{x}}_{n-1}^2}{n^2}+\frac{2\left(n-1\right)x_n{\overline{x}}_{n-1}}{n^2}+\frac{x_n^2}{n^2}\right)}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n^2}\cancel{-\frac{2\left(n-1\right)x_n{\overline{x}}_{n-1}}{n^2}}+\frac{\left(n-1\right)x_n^2}{n^2}-2x_n{\overline{x}}_n+\frac{{\left(n-1\right)}^2{\overline{x}}_{n-1}^2}{n^2}\cancel{+\frac{2\left(n-1\right)x_n{\overline{x}}_{n-1}}{n^2}}+\frac{x_n^2}{n^2}}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\frac{{\left(n-1\right)}^2{\overline{x}}_{n-1}^2}{n^2}+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n^2}+\frac{\left(n-1\right)x_n^2}{n^2}+\frac{x_n^2}{n^2}-2x_n{\overline{x}}_n}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\left({\left(n-1\right)}^2+\left(n-1\right)\right)\left(\frac{{\overline{x}}_{n-1}^2}{n^2}\right)+\left(\left(n-1\right)+1\right)\left(\frac{x_n^2}{n^2}\right)-2x_n{\overline{x}}_n}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\left(\left(n-1\right)\left(\left(n-1\right)+1\right)\right)\left(\frac{{\overline{x}}_{n-1}^2}{n^2}\right)+\left(n\right)\left(\frac{x_n^2}{n^2}\right)-2x_n{\overline{x}}_n}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\left(\left(n-1\right)\left(n\right)\right)\left(\frac{{\overline{x}}_{n-1}^2}{n^2}\right)+\left(n\right)\left(\frac{x_n^2}{n^2}\right)-2x_n{\overline{x}}_n}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2+\left(n-1\right)\left(\frac{{\overline{x}}_{n-1}^2}{n}\right)+\frac{x_n^2}{n}-2x_n{\overline{x}}_n}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n}+\frac{x_n^2}{n}-x_n{\overline{x}}_n}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n}-\frac{n{x}_n{\overline{x}}_n}{n}+\frac{x_n^2}{n}}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n}-\frac{n{x}_n{\overline{x}}_n-x_n^2}{n}}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n}-\frac{\left(n{\overline{x}}_n-x_n\right)x_n}{n}}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n}-\left(\frac{n-1}{n-1}\right)\left(\frac{\left(n{\overline{x}}_n-x_n\right)x_n}{n}\right)}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n}-\left(\frac{\left(n-1\right)x_n}{n}\right)\left(\frac{n{\overline{x}}_n-x_n}{n-1}\right)}{n}\end{array}$

As previously noted, the recurrence equation for the sample mean can be rewritten as:

${\overline{x}}_n=\frac{\left(n-1\right){\overline{x}}_{n-1}+x_n}{n}$,

then we have:

$\begin{array}{c}\frac{\left(n-1\right){\overline{x}}_{n-1}+x_n}{n}={\overline{x}}_n\\ \left(n-1\right){\overline{x}}_{n-1}+x_n=n{\overline{x}}_n\\ \left(n-1\right){\overline{x}}_{n-1}=n{\overline{x}}_n-x_n\\ {\overline{x}}_{n-1}=\frac{n{\overline{x}}_n-x_n}{n-1}\end{array}$

With this, we have:

$\begin{array}{c}{v}_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\frac{\left(n-1\right){\overline{x}}_{n-1}^2}{n}-\left(\frac{\left(n-1\right)x_n}{n}\right)\left({\overline{x}}_{n-1}\right)}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\left(\frac{\left(n-1\right){\overline{x}}_{n-1}}{n}-\left(\frac{n{x}_n-x_n}{n}\right)\right)\left({\overline{x}}_{n-1}\right)}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\left(\frac{\left(n-1\right){\overline{x}}_{n-1}}{n}-\frac{\cancel{n}{x}_n}{\cancel{n}}+\frac{x_n}{n}\right)\left({\overline{x}}_{n-1}\right)}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\left(\left(\frac{\left(n-1\right){\overline{x}}_{n-1}+x_n}{n}\right)-x_n\right)\left({\overline{x}}_{n-1}\right)}{n}\end{array}$

Since the recurrence equation of the sample mean can be rewritten as:

${\overline{x}}_n=\frac{\left(n-1\right){\overline{x}}_{n-1}+x_n}{n}$,

then we have:

$\begin{array}{c}{v}_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+\left({\overline{x}}_n-x_n\right)\left({\overline{x}}_{n-1}\right)}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n+{\overline{x}}_n{\overline{x}}_{n-1}-x_n{\overline{x}}_{n-1}}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+x_n^2-x_n{\overline{x}}_n-x_n{\overline{x}}_{n-1}+{\overline{x}}_n{\overline{x}}_{n-1}}{n}\\ v_n=\frac{\left(n-1\right)v_{n-1}+\left(x_n-{\overline{x}}_n\right)\left(x_n-{\overline{x}}_{n-1}\right)}{n}\\ v_n=\frac{n{v}_{n-1}-v_{n-1}+\left(x_n-{\overline{x}}_n\right)\left(x_n-{\overline{x}}_{n-1}\right)}{n}\\ v_n=\frac{\cancel{n}{v}_{n-1}}{\cancel{n}}+\frac{-v_{n-1}+\left(x_n-{\overline{x}}_n\right)\left(x_n-{\overline{x}}_{n-1}\right)}{n}\\ v_n=v_{n-1}-\frac{v_{n-1}-\left(x_n-{\overline{x}}_n\right)\left(x_n-{\overline{x}}_{n-1}\right)}{n}\end{array}$

Therefore, the recurrence equation for the biased sample variance (a.k.a. online variance) is:

$v_n=v_{n-1}-\frac{v_{n-1}-\left(x_n-{\overline{x}}_n\right)\left(x_n-{\overline{x}}_{n-1}\right)}{n}$

---

Example C++ code that computes the online variance:
// Filename: main.cpp
#include <iostream>
#include <iomanip>
 
int main () {
    
    double x;
    double n = 0;
    double mean = 0;
    double variance = 0;
    double prev_mean; // previous mean
    double prev_variance; // previous variance
    
    if ( std::cin >> x ) {
        ++n;
        mean = x;
        variance = 0;
        while ( std::cin >> x ) {
            prev_mean = mean;
            prev_variance = variance;
            ++n;
            mean = prev_mean - ( prev_mean - x ) / n;
            variance = prev_variance - ( prev_variance - ( x - mean ) * ( x - prev_mean ) ) / n;
        }
    }
    
    std::cout << "n:        " << n << '\n';
    std::cout << "mean:     " << std::setprecision( 17 ) << mean     << '\n';
    std::cout << "variance: " << std::setprecision( 17 ) << variance << '\n';
    
}

Example of data.txt:
6867.55961097
32890.8902819
18178.8157597
.
.
.

Command Line:
g++ -o main.exe main.cpp -std=c++11 -march=native -O3 -Wall -Wextra -Werror -static
./main.exe < data.txt

Note: Mathematica's Variance[] function computes the unbiased sample variance, not the biased sample variance; therefore, the biased sample variance is computed in Mathematica as:

( ( Length[ list ] - 1 ) / Length[ list ] ) * Variance[ list ]