Café Math : Moving Averages

# 1. Foreword

Hi today I want to talk about moving averages and their practical computation. The questions treated here were asked to me as part of quant job interview one year ago. Here is a transcription of my responses. If you are curious... I got the job.

# 2. Convolution of Signals

Let $(a_k)_{k\ge 0}$ be a regular temporal series (which means a sequence of numerical values regularly spaced in time). We want to apply various filters to it: moving averages, exponential moving averages, triangular moving averages etc... in an efficient manner. Those problems enter the domain of signal theory where well known tools permit a proper treatment. The considered filters all are causal linear filters and they are characterized as such by there impulse response.

To apply a linear filter $H$ to a signal $a$ amounts to compute the convolution of the signal $a$ with the impulse response $b$ of the filter. In other words, \begin{align*} c_k = \sum_{\ell \ge 0} b_{\ell}\, a _{k-\ell} \end{align*}

Everything gets clearer by introducing the $z$-transform of a signal $a$. It's the formal series $F_a(z) = \sum_{k\ge 0} a_k z^k$. The above relation is rewritten in, \begin{align*} F_c(z) &= \sum_{k\ge 0} c_k \,z^k = \sum_{k\ge 0} \sum_{\ell \ge 0} b_{\ell}\, a _{k-\ell} \,z^k = F_b(z) F_a (z) \end{align*} A simple product of power series.

# 3. Rectangular Moving Averages

Suppose we want to compute the moving average of a signal $a$ over $n$ periods. In order to see how the method works we translate the problem in terms of formal power series. The impulse response of the filter is,

\begin{align*} b^1_{k} = \begin{cases} 1/n& \text{if $k < n$,} \\ 0 & \text{else.} \end{cases} \end{align*} The $z$-transform of the signal is, \begin{align*} F_{1} ( z ) = \frac{1}{n} (1+z+z^2 + ... + z^{n-1}) = \frac{1}{n}\: \frac{z^n - 1}{z- 1} \end{align*} The relation between those two signals $a$ and $c = H_1(a)$ is then, \begin{align*} F_c(z) = \frac{1}{n}\: \frac{z^n - 1}{z- 1} \, F_a(z) \end{align*} Or else, \begin{align*} F_c(z) = \frac{1}{n} ( 1-z^n) F_a(z) + z\,F_c(z) \end{align*} We can readily read the following computation schema, \begin{align*} c_k = \frac{1}{n} ( a_k - a_{k-n} ) + c_{k-1} \end{align*} It can be implemented without difficulty with a small loop. One just has to handle its initialization carefully. Here, we assumed that $a_k = 0$ as soon as $k < 0$. We very well could have assumed instead that $a_k = a_0$ for negative $k$. It's a matter of taste.

# 4. Exponential Moving Averages

We denote the filter by $H_2$ and its impulse response by $b^2$, etc... We have, \begin{align*} b^2_k &= \alpha_0\,\alpha^k \end{align*} the $z$-transform is the a geometric series, \begin{align*} F_2(z) &= \alpha_0 ( 1+\alpha z + (\alpha z)^2+...) = \frac{\alpha_0}{1-\alpha z} \end{align*} We see that if we want to normalize by setting $F_2(1) = 1$ we get $\alpha_0 = 1-\alpha$. The relation $c = H_2(a)$ is then, \begin{align*} F_c(z) = \frac{1-\alpha}{1-\alpha z} F_a(z) \end{align*} Or else, \begin{align*} F_c(z) = (1-\alpha)\,F_a(z) + \alpha z \,F_c(z) \end{align*} Here is the recurrence relation that can be used to compute an exponential moving average, \begin{align*} c_k = (1-\alpha) \,a_k + \alpha\, c_{k-1} \end{align*}

# 5. Triangular Moving Averages

This one is a bit trickier that the two others but with a little of technic it goes. We unroll the same plan of study as before. Impulse response, \begin{align*} b^3_k = \begin{cases} \alpha k + \beta & \text{if $k < n$,} \\ 0 & \text{else.} \end{cases} \end{align*} (the parameters $\alpha$ and $\beta$ are considered below). The $z$-transform is, \begin{align*} F_3 (z) &= \sum_{k = 0}^{n-1} (\alpha k + \beta)z^k \\ &= \alpha \left( n\frac{z ^{n-1}}{z-1} - \frac{z^n-1}{(z-1)^2} \right) + \beta \left( \frac{z ^n-1}{z-1} \right) \end{align*} We just have to apply the operator $\alpha\, z\frac{d}{dz} + \beta$ to the impulse response of the simple moving average (without the $1/n$ which is irelevent). We then write the relation $c = H_3(a)$ as, \begin{align*} F_c(z) = \left[ \alpha \left( n\frac{z ^{n-1}}{z-1} - \frac{z^n-1}{(z-1)^2} \right) + \beta \left( \frac{z ^n-1}{z-1} \right) \right] F_a(z) \end{align*} Or else... \begin{align*} F_c(z) = \left[ ((n-1)\,\alpha + \beta)\,z^{n+1} - (n\,\alpha + \beta)\,z^{n}+(\alpha-\beta)\,z + \beta\right] F_a(z) +(2\,z-z^2) \, F_c(z) \end{align*} Reducing to the same denominator, expanding etc... we get the following recurrence equation, \begin{align*} c_k = u_1 \, a_{k-n-1} + u_2\,a_{k-n} + u_3\, a_{k-1} + u_4\,a_k + v_1\,c_{k-1} + v_2\, c_{k-2} \end{align*} with, \begin{align*} u_1 &= (n-1)\,\alpha + \beta & v_1 &= 2 \\ u_2 &= - n\,\alpha - \beta & v_2 &= -1 \\ u_3 &= \alpha-\beta \\ u_4 &= \beta \end{align*}

The obvious normalization, with $F_3(1) = 1$ and $\alpha n + \beta = 0$, gives us, \begin{align*} \alpha &= -\frac{2}{n^2+n} & \beta &= \frac{2}{n+1} \end{align*} The details of the computations is a bit long to get efficiently presented on a black board at a job interview but the problem itself isn't that hard.

# 1 Comment

Samuel VIDAL  posted 2013-03-22 17:54:28

Some cool code:

/// <summary>
/// Computes the Exponential Moving Average of the input
/// </summary>
public static IEnumerable<float> GetEMA(this IEnumerable<float> input, float alpha)
{
var alpha0 = 1 - alpha;
var c1 = 0f;
var c0 = 0f;

foreach (var a0 in input)
{
c0 = (1 - alpha) * a0 + alpha * c1;
yield return c0;
c1 = c0;
}
}

/// <summary>
/// Computes the Ordinary Moving Average of the input
/// </summary>
public static IEnumerable<float> GetMA(this IEnumerable<float> input, int n)
{
var c1 = 0f;
var c0 = 0f;
var a = new float[n];
int jn = 0;
var b = 1f / n;

foreach (var a0 in input)
{
var an = a[jn];
c0 = b * (a0 - an) + c1;
yield return c0;
c1 = c0;
a[jn] = a0;
jn = (jn + 1) % n;
}
}

/// <summary>
/// Computes the Triangular Moving Average of the input
/// </summary>
public static IEnumerable<float> GetTMA(this IEnumerable<float> input, int n)
{
var c0 = 0f;
var c1 = 0f;
var c2 = 0f;

var a1 = 0f;
var an1 = 0f;
var a = new float[n];
var jn = 0;

var alpha = -2f / (n * n + n);
var beta = 2f / (n + 1);

var u1 = (n - 1) * alpha + beta;
var u2 = -n * alpha - beta;
var u3 = alpha - beta;
var u4 = beta;

var v1 = 2f;
var v2 = -1f;

foreach (var a0 in input)
{
var an = a[jn];
c0 = u1 * an1 + u2 * an + u3 * a1 + u4 * a0 + v1 * c1 + v2 * c2;
yield return c0;
a1 = a0;
an1 = an;
c2 = c1;
c1 = c0;
a[jn] = a0;
jn = (jn + 1) % n;
}
}
Comment:

Name:

Email:

Website: