I have an unbounded process which generates normal distributed values (could be ints, but lets assume floating points for now). These values are put into bins of fixed size (e.g. bin 9 gets values in range [900.0, 1000.0) ). In the bins the following values are stored: number of observations, min, max, mean and variance. The mean and variance are calculated using Knuth's algorithm:

$M_k = M_{k-1} + (x_k – M_{k-1})/k$

$S_k = S_{k-1} + (x_k – M_{k-1})*(x_k – M_k)$

Where $x$ is the input value, $M$ is the mean and the variance is calculated from $S \over {k-1}$.

Now, I COULD calculate the global mean and variance while adding the values, but I was wondering how I could do this when I only have the means and variances of the bins (the values themeselves are not stored). The mean is trivial, but I'm not sure how to calculate the variance of the underlying process. Can someone please show me how?

Thanks in advance!

  • $\begingroup$ 1. When you say "gets values from 900 to 999" this implies that the values are integer (because otherwise values between 999 and 1000 would not go into either bin 9 nor into bin 10). If the values are integer they are not normally distributed and if they are not integer you have incorrectly (/misleadingly) described what happens to the values. Please fix your description so that it is consistent with the actual situation. $\:$ 2. Many algorithms are named after Knuth. What algorithm is this? ... ctd $\endgroup$ – Glen_b Jul 9 '16 at 10:37
  • $\begingroup$ ctd... 3. You say you only have the means and variances in each bin. Is this actually true, or do you also have the count of how many values fell into each bin? $\endgroup$ – Glen_b Jul 9 '16 at 10:42
  • $\begingroup$ A formula is given at the linked duplicate (see the "unequal sample size formula"), since this is just a special case of calculating overall means and variance from grouped data. A derivation for it is here. $\endgroup$ – Glen_b Jul 9 '16 at 11:22
  • $\begingroup$ Ahh, "partitions" didn't occur to me. Thanks! $\endgroup$ – Managarm Jul 9 '16 at 11:29
  • $\begingroup$ It's one of those things everyone calls a different name. It's a hard thing to search for. $\endgroup$ – Glen_b Jul 9 '16 at 12:06

The formual you are looking for (I give it for two groups but it is easy to see how it can be extended.

$$ s_c = \sqrt{\frac{n_1 (m_1^2 + s_1^2) + n_2 (m_2^2 + s_2^2)}{n_1 + n_2} - m_c^2} $$

Where the subscript c means combined, $s$ is a standard deviation and $m$ is a mean.

Note that as @glen_b suggests in his comment you do need to store the $k$ in your calculation (I call them $n$)

| cite | improve this answer | |
  • $\begingroup$ That looks promising! Can you give me a source or some hints what I should have searched for to find this? $\endgroup$ – Managarm Jul 9 '16 at 11:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.