Calculating the average with Limited memory and without using the count

Question

I am having a flow of numbers on an embedded device, and I cannot store the flow of numbers and would like to calculate the average.

I have checked around and found one way was to do like this : $$ Avg= \frac{(N \times AvgOld) + NewValue }{N+1} $$ The issue I have with the above method is that I need to calculate the (N x AvgOld) which by the time shall overflow (I dont have a solution for the overflow)

So I have tried another method :

$$ Avg= \frac{AvgOld+ NewValue}{2} $$

For wich I discovered the disadvantage of being highly affected by the latest value.

I'd appreciate if anyone could help me.

Answer 1

Let $X_n$ denote the average of the first $n$ values of the sequence $\{Y_k\}_{k\in\mathbb{N}}$. In order to avoid the overflow problem you could try to calculate as following $$ X_{n+1} = \frac{1}{n+1}(nX_n + Y_{n+1}) = \frac{n}{n+1}X_n + \frac{1}{n+1}Y_{n+1}. $$ By splitting like this you avoid the very big number $nX_n$, because you divide by $n+1$ first.

Note that if the numbers come from some distibution then one can possibly apply a law of large numbers, to deduce that $\lim_{n\rightarrow\infty}X_n$ exists and thus that after a certain point, updating the average changes the result very little.