6_R

Online algorithm for the arithmetic mean

The main problem with naive approach is that it is not stable and can cause a loss of significance (catastrofic cancelation etc.) [1, 3].

Also depending on a task, the application might only need to keep and update the mean of the data. The naive approach usually requires to feed all the data and then compute the mean, which will require huge amount of memory to store the data and also to wait until all data is captured, which might not be the case for data stream.

Donald Knuth, in his book ‘The Art of Computer Programming’, proposed to estimate a weighted mean to update the value time to time:

def running_mean(data)
{
    mean = 0;
    for(int i = 0; i < data.size(); ++i)
    {
        mean += (data[i] - mean) / (i+1);
    }
}
    

Using this approach it is possible to compute a data-stream mean without any catastrophic cancellation [1, 2].

---

References

1. https://en.wikipedia.org/wiki/Loss_of_significance

2. https://statisticsforcs.wordpress.com/2017/10/24/best-algorithms-to-compute-the-online-data-stream-arithmetic-mean/

3. https://math.stackexchange.com/questions/1920525/why-is-catastrophic-cancellation-called-so