Café Math : Moving Averages
1, 1, 2, 2, 1, 8, 6, 7, 14, 27, 26, 80, 133, 170, 348, 765, 1002, 2176, 4682, ...   (A121350)
Math Blog
Articles
Talks
Teaching
Phd Thesis
Financial Maths
About me
PrevNext

Moving Averages

Wen, 14 Mar 2012 00:06:52 GMT


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: