a larger alpha provides a smoother signal, it also lags further behind the underlying trend as it gives a lot of weight
to older data. As discussed later, choosing a value for alpha translates into a
trade-off between a smooth signal and
a reduced lagging of the trend.
To illustrate the online regression
algorithm, we look at the time series
of mid prices for SPY and SSO, two
highly related ETFs (SSO is the double-leveraged version of SPY). As shown in
Figure 3, the relationship between the
two assets seems very close to linear
over the course of a day. Figure 4 plots
the online mean and intercept for two
values of alpha.
As indicated by its name, a one-pass
algorithm reads every input variable
exactly once and then discards it.
This type of algorithm is very efficient in terms of memory handling,
as it requires only a minimal amount
of data to be stored in memory. Here,
we present three important examples
of online one-pass algorithms: the exponential moving average, the exponentially weighted variance, and the
exponentially weighted regression.
Each of these algorithms has been
used in a HFT application in the previous section.
First, let’s look briefly at the simple
moving average of a time series. This
is an estimate of the mean of a time
series over a moving window of a fixed
size. In finance, it is often used to detect trends in price, in particular by
comparing two simple moving averages: one over a long window and one
over a short window. In another application, the average traded volume
over the past five minutes can serve as
a prediction of the volume traded in
the next minute. In contrast to the exponential moving average, the simple
moving average cannot be solved with
a one-pass algorithm.
Let (Xt)t = X0, X1, X2 … be the observed
sequence of input variables. At any given time t we want to predict the next
outcome Xt+ 1. For M > 0 and t ≥ M, the
simple moving average with window
size M is defined as the average of the
last M observations in the time series
(Xt)t —that is, Xt, M =
1 M SM– 1 j= 0 Xt–j . The moving average can also be computed via
the following recursion:
Xt, M = Xt – 1,M – Xt– M M + Xt M. ( 1)
While this is an online algorithm, it
is not a one-pass algorithm, as it needs
to access every input data point exactly
twice: once to add it to the moving aver-
age and then again to drop it out of the
moving average estimate. Such an algo-
rithm is also referred to as a two-pass
algorithm and requires keeping an en-
tire array of size M in memory.
Example 1: One-Pass Exponential
Weighted Average. In contrast to the
regular average X t,M =
t + 1 St j=0 Xj , the ex-
ponential weighted average assigns an
figure 3. online regression algorithm.
156.3 156.4 156.5 156.6 156.7 156.8 156.9 157 157.1 157.2 157.3
figure 4. online mean and intercept for two values of alpha.
0 0.5 1 1. 5 2 2. 5
alpha = 0.99 alpha = 0.999