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?
