statistex icon indicating copy to clipboard operation
statistex copied to clipboard

Update `Statistex.variance` to use Welford's online algorithm

Open weaversam8 opened this issue 6 months ago • 2 comments

Earlier today I opened bencheeorg/benchee#472, and I started thinking about how Statistex could be used to accomplish this. Statistex already supports calculating several statistics while ignoring the list of samples, if the prerequisite parts are available to the caller (e.g. average can be called with :total and :sample_size)

One statistic that didn't support this today was variance (and by extension standard_deviation), since both require the entire list of samples to operate. Algorithms to calculate variance "on-line" exist, such as Welford's Online Algorithm, but they depend on a different statistic, m2. This statistic is "the running sum of squared differences from the current mean", and really only has a meaning in the context of computing variance.

In this PR, I've:

  • added this m2 statistic
  • updated the variance statistic to use m2 when calculating variance instead of average
  • I also exposed this m2 statistic on the top level Statistex struct, even if it's not a particularly useful statistic on its own.
    • (I figured the ability for users to incrementally update statistics like variance and standard_deviation was in keeping with Statistex's philosophy of avoiding recomputation.)

This PR also updates some typespecs to better capture the :ignored behavior for statistics that support it, and tweaks the last few digits of floating point results from the variance and standard_deviation statistic. I'm not a statistics expert, but I believe that my floating point tweaks represent a shift towards more accuracy, not less, given the notes about loss of precision on the above linked Wikipedia page:

[The Welford's online] algorithm is much less prone to loss of precision due to catastrophic cancellation, but might not be as efficient because of the division operation inside the loop.

I didn't open an issue before I opened this PR, so I know these changes might not be desired - if so, please let me know! I'd love to discuss better ways to handle what I described in bencheeorg/benchee#472 if this isn't the best approach.

weaversam8 avatar Jul 02 '25 22:07 weaversam8

Thanks for the detailed comments! No worries about the quantity, I also prefer detailed notes instead of one larger comment. I'll take a look at making some of these tweaks soon.

I was also curious about the benchmarking, and my first thought was to use Benchee. @PragTob would you be OK if I added some tests that benchmarked this library using Benchee? Even if that might make a circular dependency between Benchee and Statistex?

weaversam8 avatar Jul 07 '25 14:07 weaversam8

@weaversam8 if you can make the circular dependency work, for sure! Otherwise, a separate repo may be the solution. I've definitely benchmarked benchee using benchee :)

Also sorry for the silence... I'll appologize in some other thread :sweat_smile:

PragTob avatar Oct 05 '25 18:10 PragTob