Simple Moving Average

Sliding Window

In statistics a simple moving average is an algorithm that calculates the unweighted mean of the last n samples. The parameter n is often called the window size, because the algorithm can be thought of as an window that slides over the data points.

By using a recursive formulation of the algorithm, the number of operations required per sample is reduced to one addition, one subtraction and one division. Since the formulation is independent of the window size n, the runtime complexity is O(1), i.e. constant.

The recursive formula of the unweighted moving average is avg_k = avg_{k-1} + \frac{x_k - x_{k-n}}{n}, where avg is the rolling average and x represents a data point. So, whenever the window slides to the right, one data point, the tail, drops out and one data point, the head, moves in.

Implementation

An implementation of the simple moving average has to take the following into account

  • Algorithm initialization As long as the window is not fully populated with values, the recursive formula fails.
  • Storage Access to the tail element is required, which depending on the implementation requires a storage of n elements.

My implementation uses the presented formula when the window is totally populated with values, and otherwise switches to the formula avg_k = \frac{avg_{k-1} * (k-1) + x_k}{k}, which updates the mean by recalculating the sum of the previous elements. Note that this can lead to numerical instabilities because of floating point arithmetic.

As far as memory consumption is concerned, the implementation uses iterators to keep track of head and tail elements. This leads to an implementation with constant memory requirements independent of the window size. Here is the update procedure that slides the window to the right.

// _head and _next are enumerators of the data points collection
// _count is the number of elements in the window (at max _n)
// _running is the moving average initialized with zero.

public void Shift() {
  if (!_head.MoveNext())
    throw new InvalidOperationException("Cannot move to next element");
  double next = _head.Current;
  
  if (_count < _n) {
    // Window not filled
    _count++;
    _running = (_running * (_count - 1) + next) / _count;
  } else {
    _tail.MoveNext();
    double drop= (double)_tail.Current;
    _running = _running + (next - drop) / _n;
  }
}

In .NET most of the collections invalidate their enumerators when the underlying collection is modified. The implementation, however, relies on valid enumerators. Especially in streaming based applications the underlying collection needs modified when a new element arrives. One way to deal with that is to create a simple circular fixed size collection of size n+1 that never invalidates its iterators and alternately add an element and call Shift.

About these ads

3 thoughts on “Simple Moving Average

  1. I wish I could figure out how to actually implement this, as the Test function is very confusing to me… Do I need to convert data to Array, then run
    SMA sma = new SMA(20, [array]); for a 20 period SMA? How do I handle shift() function? Is it necessary to implement constructors ?? (sorry for confusion).

    • Craig,

      No you don’t need to convert your data into an array as long as your data implements IEnumerable[1] and the enumerated type is double. As far as your private messaging is concerned you need to convert the DataRow to something that is enumerable of double values. Your approach works.

      Shift, slides the window one position to the left. For a dataset of say 40 values and a 20 period SMA you have 21 positions the window fits in (40 – 20 + 1). Each time you call Shift() the window is moved to the left by one position and Average() returns the SMA for the current window position. That is, the unweighted average of all values inside the window.

      Additionally my implementation allows to calculate the SMA even if the window is not fully filled at the beginning. So in essence

      SMA sma = new SMA(2, values); // assume values is [2,4,6]
      sma.Shift(); // move window to left
      sma.Average; // returns average of [2] => 2
      sma.Shift();
      sma.Average; // returns average of [2,4] => 3
      sma.Shift();
      sma.Average; // returns average of [4,6] => 5
      

      Hope this helps. Any further questions?

      [1] http://msdn.microsoft.com/en-us/library/9eekhta0.aspx

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s