3
$\begingroup$

In Knuth, the following method for computing an average is presented: \begin{align*} M_{n} = M_{n-1} + (x_{n} - M_{n-1})/n \end{align*} (See here, if you don't have TAOCP.)

Assuming the samples all lie a bounded distance away from the average, then as $n \to \infty$, $(M_{n-1}-x_n)/n$ becomes very small, and eventually $M_{n-1} \oplus (x_{n}\ominus M_{n-1}) \oslash n$ becomes bitwise equal to $M_{n-1}$. The average computed by this formula then stops evolving in response to new data.

What are the known techniques to avoid this?

Update: I believe that this scheme has error $|\hat{M}_n -M_{n}| \le n\mu_{M} \underline{M}_{n}$, where \begin{align*} \underline{M}_{n} := \frac{1}{n} \sum_{i=0}^{n-1} |x_{i}|, \end{align*} and $\mu_{M}$ is the unit roundoff, but I couldn't prove it. This won't directly answer the question, but might put me on the track to get improvements. Any ideas?

$\endgroup$
  • 1
    $\begingroup$ If you have a lot of data then the averge does NOT change by much when you add more. Where is the problem? $\endgroup$ – Philip Roe Feb 23 '18 at 1:50
  • $\begingroup$ The problem is that it doesn't change at all, not that it doesn't change much. $\endgroup$ – user14717 Feb 23 '18 at 2:14
  • $\begingroup$ Example: Float precision, after 10^7 data points, no change to average unless there's a huge outlier. If there are 10^9 data points (totally reasonable), it's stuck after 10^7, and the average is unlikely to be correct. $\endgroup$ – user14717 Feb 23 '18 at 2:17
  • $\begingroup$ The mean of a random sample of 10^7 points from a population of 10^9 points is likely to be a very good estimate of the population mean. What we don't know from the question posed is how 'good' a random sample the first 10^7 points represent. $\endgroup$ – High Performance Mark Feb 23 '18 at 8:17
  • $\begingroup$ I should clarify: The first 10^7 samples are not assumed to be random nor somehow representative of the entire population. $\endgroup$ – user14717 Feb 23 '18 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.