No σ for you!

[Albert Chan]

(11-26-2024 08:12 PM)dm319 Wrote:  

(11-25-2024 03:58 PM)carey Wrote:  It works, but working with absolute values in subsequent equations becomes unwieldly.

In what way?

Here, I look at computation part of deviation calculations, not their merit.

With absolute deviation, you can't start sum deviations without a final mean.
This implied we may need to scan data set in 2 passes.

Also, adding or removal a data point may require recalculations of all deviations.
(we can keep data sorted, but that is also expensive, both time and space)

With variance, you can add or remove element, for instant O(1) update.
If you only need {µ, σ} statistics, you don't even need to store the data.

You don't even need a 'final' mean, and can do running mean and variance.

John D. Cook, Accurately computing running variance

Σ defined from i = 1 to k-1
Let m = Σ(xi) / (k-1)
Let S = Σ(xi - m)^2

Now, we add a data xk to the mix, for new mean and variance.

mk = ((k-1)*m + xk)/k = (k*m + (xk-m))/k

Running mean: mk = m + z, where z = (xk - m) / k

Sk = Σ(xi - mk)^2     + (xk - mk)^2
     = Σ((xi-m)-z)^2    + (xk - mk)^2
     = S + (k-1)*z^2   + (xk - mk)^2            -- NOTE: Σ(xi - m) = 0
     = S +  k*z  * z      + (xk - mk)^2 - z^2
     = S + (xk - m) * z + (xk - m) * (xk - mk - z)

Running sample variance: Sk = S + (xk - m) * (xk - mk) --> s^2 = Sk / (k−1)

Formulas also work when we remove xk from data set. (back solve {m, S} from {mk, Sk})