How to efficiently calculate a moving Standard Deviation

Question

Below you can see my C# method to calculate Bollinger Bands for each point (moving average, up band, down band).

As you can see this method uses 2 for loops to calculate the moving standard deviation using the moving average. It used to contain an additional loop to calculate the moving average over the last n periods. This one I could remove by adding the new point value to total_average at the beginning of the loop and removing the i - n point value at the end of the loop.

My question now is basically: Can I remove the remaining inner loop in a similar way I managed with the moving average?

    public static void AddBollingerBands(SortedList<DateTime, Dictionary<string, double>> data, int period, int factor)
    {
        double total_average = 0;

        for (int i = 0; i < data.Count(); i++)
        {
            total_average += data.Values[i]["close"];

            if (i >= period - 1)
            {
                double total_bollinger = 0;
                double average = total_average / period;

                for (int x = i; x > (i - period); x--)
                {
                    total_bollinger += Math.Pow(data.Values[x]["close"] - average, 2);
                }

                double stdev = Math.Sqrt(total_bollinger / period);

                data.Values[i]["bollinger_average"] = average;
                data.Values[i]["bollinger_top"] = average + factor * stdev;
                data.Values[i]["bollinger_bottom"] = average - factor * stdev;

                total_average -= data.Values[i - period + 1]["close"];
            }
        }
    }

Answer 1

The answer is yes, you can. In the mid-80's I developed just such an algorithm (probably not original) in FORTRAN for a process monitoring and control application. Unfortunately, that was over 25 years ago and I do not remember the exact formulas, but the technique was an extension of the one for moving averages, with second order calculations instead of just linear ones.

---

After looking at your code some, I am think that I can suss out how I did it back then. Notice how your inner loop is making a Sum of Squares?:

            for (int x = i; x > (i - period); x--)
            {
                total_bollinger += Math.Pow(data.Values[x]["close"] - average, 2);
            }

in much the same way that your average must have originally had a Sum of Values? The only two differences are the order (its power 2 instead of 1) and that you are subtracting the average each value before you square it. Now that might look inseparable, but in fact they can be separated:

SUM(i=1; n){ (v[i] - k)^2 }

is

SUM(i=1..n){v[i]^2 -2*v[i]*k + k^2}

which becomes

SUM(i=1..n){v[i]^2 -2*v[i]*k} + k^2*n

which is

SUM(i=1..n){v[i]^2} + SUM(i=1..n){-2*v[i]*k} + k^2*n

which is also

SUM(i=1..n){v[i]^2} + SUM(i=1..n){-2*v[i]}*k + k^2*n

Now the first term is just a Sum of Squares, you handle that in the same way that you do the sum of Values for the average. The last term (k^2*n) is just the average squared times the period. Since you divide the result by the period anyway, you can just add the new average squared without the extra loop.

Finally, in the second term (SUM(-2*v[i]) * k), since SUM(v[i]) = total = k*n you can then change it into this:

-2 * k * k * n

or just -2*k^2*n, which is -2 times the average squared, once the period (n) is divided out again. So the final combined formula is:

SUM(i=1..n){v[i]^2} - n*k^2

or

SUM(i=1..n){values[i]^2} - period*(average^2)

(be sure to check the validity of this, since I am deriving it off the top of my head)

And incorporating into your code should look something like this:

public static void AddBollingerBands(ref SortedList<DateTime, Dictionary<string, double>> data, int period, int factor)
{
    double total_average = 0;
    double total_squares = 0;

    for (int i = 0; i < data.Count(); i++)
    {
        total_average += data.Values[i]["close"];
        total_squares += Math.Pow(data.Values[i]["close"], 2);

        if (i >= period - 1)
        {
            double total_bollinger = 0;
            double average = total_average / period;

            double stdev = Math.Sqrt((total_squares - Math.Pow(total_average,2)/period) / period);
            data.Values[i]["bollinger_average"] = average;
            data.Values[i]["bollinger_top"] = average + factor * stdev;
            data.Values[i]["bollinger_bottom"] = average - factor * stdev;

            total_average -= data.Values[i - period + 1]["close"];
            total_squares -= Math.Pow(data.Values[i - period + 1]["close"], 2);
        }
    }
}