How to calculate iteratively the running weighted average so that last values to weight most?

Question

I want to implement an iterative algorithm, which calculates weighted average. The specific weight law does not matter, but it should be close to 1 for the newest values and close to 0 to the oldest.

The algorithm should be iterative. i.e. it should not remember all previous values. It should know only one newest value and any aggregative information about past, like previous values of the average, sums, counts etc.

Is it possible?

For example, the following algorithm can be:

void iterate(double value) {
   sum *= 0.99;
   sum += value;
   count++;
   avg = sum / count;
}

It will give exponential decreasing weight, which may be not good. Is it possible to have step decreasing weight or something?

EDIT 1

The the requirements for weighing law is follows:

1) The weight decreases into past 2) I has some mean or characteristic duration so that values older this duration matters much lesser than newer ones 3) I should be able to set this duration

EDIT 2

I need the following. Suppose v_i are values, where v_1 is the first. Also suppose w_i are weights. But w_0 is THE LAST.

So, after first value came I have first average

 a_1 = v_1 * w_0

After the second value v_2 came, I should have average

 a_2 = v_1 * w_1 + v_2 * w_0

With next value I should have

 a_3 = v_1 * w_2 + v_2 * w_1 + v_3 * w_0

Note, that weight profile is moving with me, while I am moving along value sequence.

I.e. each value does not have it's own weight all the time. My goal is to have this weight lower while going to past.

Answer 1

First a bit of background. If we were keeping a normal average, it would go like this:

average(a) = 11
average(a,b) = (average(a)+b)/2
average(a,b,c) = (average(a,b)*2 + c)/3
average(a,b,c,d) = (average(a,b,c)*3 + d)/4

As you can see here, this is an "online" algorithm and we only need to keep track of pieces of data: 1) the total numbers in the average, and 2) the average itself. Then we can undivide the average by the total, add in the new number, and divide it by the new total.

Weighted averages are a bit different. It depends on what kind of weighted average. For example if you defined:

weightedAverage(a,wa, b,wb, c,wc, ..., z,wz) = a*wa + b*wb + c*wc + ... + w*wz
 or
weightedAverage(elements, weights) = elements·weights

...then you don't need to do anything besides add the new element*weight! If however you defined the weighted average akin to an expected-value from probability:

weightedAverage(elements,weights) = elements·weights / sum(weights)

...then you'd need to keep track of the total weights. Instead of undividing by the total number of elements, you undivide by the total weight, add in the new element&astweight, then divide by the new total weight.

Alternatively you don't need to undivide, as demonstrated below: you can merely keep track of the temporary dot product and weight total in a closure or an object, and divide it as you yield (this can help a lot with avoiding numerical inaccuracy from compounded rounding errors).

In python this would be:

def makeAverager():
    dotProduct = 0
    totalWeight = 0

    def averager(newValue, weight):
        nonlocal dotProduct,totalWeight

        dotProduct += newValue*weight
        totalWeight += weight
        return dotProduct/totalWeight

    return averager

Demo:

>>> averager = makeAverager()
>>> [averager(value,w) for value,w in [(100,0.2), (50,0.5), (100,0.1)]]
[100.0, 64.28571428571429, 68.75]
>>> averager(10,1.1)
34.73684210526316
>>> averager(10,1.1)
25.666666666666668
>>> averager(30,2.0)
27.4