Programmatic trader leverage: incremental update algorithm to calculate the mean and variance

Other information

In programmatic trading, it is often necessary to calculate averages and spreads, such as in the calculation of averages and volatility. When we need high-frequency and long-cycle calculations, it is necessary to keep historical data for a long time, which is unnecessary and time-consuming. This article introduces an online update algorithm for calculating weighted averages and spreads, which is especially important for dealing with real-time data streams and dynamically adjusted trading strategies, especially high-frequency strategies.

Simple Mean and Differential

If we represent the mean of the $\mu_n$ data point, assuming we have calculated the mean of $\mu_{n-1}$ data points, we now receive a new data point $x_{n}$. We want to calculate the new mean of $\mu_{n}$ that contains this new data point.

$\mu_n = \frac{1}{n} \sum_{i=1}^{n} x_i$ $\mu_n = \frac{1}{n} \left( x_n + \sum_{i=1}^{n-1} x_i \right)$ $\mu_{n-1} = \frac{1}{n-1} \sum_{i=1}^{n-1} x_i$ $(n-1)\mu_{n-1} = \sum_{i=1}^{n-1} x_i$ $\mu_n = \frac{1}{n} \left( x_n + (n-1)\mu_{n-1} \right)$ $\mu_n = \mu_{n-1} + \frac{1}{n} (x_n - \mu_{n-1})$

The differential update process can be broken down into the following steps:

$S_n = \sum_{i=1}^{n} (x_i - \mu_n)^2$ $S_n = \sum_{i=1}^{n} x_i^2 - n\mu_n^2$ $S_n - S_{n-1} = x_n^2 - n\mu_n^2 + (n - 1)\mu_{n-1}^2$ $S_n - S_{n-1} = (x_n - \mu_{n-1})(x_n - \mu_n)$ $S_n = S_{n-1} + (x_n - \mu_{n-1})(x_n - \mu_n)$ $\sigma_n^2 = \frac{S_n}{n}$

As can be seen from the above two formulas, this process allows us to keep the mean and difference of only one data point for each new data point $x_n$ that we receive, to update the new mean and difference without storing historical data, and to calculate faster. But the problem is that this calculation is the mean and difference of the whole sample, and in the practical strategy, we need to consider a certain fixed period.

Exponentially-weighted mean

The index-weighted average can be defined by the following recurrence relation:

$\mu_t = \alpha x_t + (1 - \alpha) \mu_{t-1}$

Here, $\mu_t$ is the index-weighted average at time point $t$, $x_t$ is the observed value at time point $t$, $\alpha$ is the weighting factor, and $\mu_{t-1}$ is the index-weighted average at the previous time point.

Exponentially-weighted variance

For the differential, we need to compute the index-weighted average of the square deviation of each time point. This can be done by the following recurrence relation:

$S_n = \alpha S_{n-1} + (1 - \alpha)(x_n - \mu_n)(x_n - \mu_{n-1})$

In this case, $\sigma_t^2$ is the exponential decomposition of $t$ at the time point $t$, and $\sigma_{t-1}^2$ is the exponential decomposition of $t$ at the previous time point.

Observational indices with weighted averages and differentials, in their incremental updated form, are intuitive and retain some of the past values, plus new changes. The specific inference process can be referenced in this paper:https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf

Simple moving averages (SMA) and index moving averages (EMA)

Simple averages (also known as arithmetic averages) and weighted averages are two common statistical measures, each with different characteristics and uses. Simple averages assign the same weight to each observation value, which reflects the central position of the data set. Indexed weighted averages are a recursive calculation that assigns a higher weight to the most recent observation value. Weights decrease exponentially as the observation value increases in distance from the current time.

• Weight distributionSimple averages give each data point the same weight, while index-weighted averages give the most recent data point a higher weight.
• Sensitivity to new informationSimple averages are not sensitive to newly added data because they involve recalculation of all data points. Index-weighted averages reflect changes in recent data more quickly.
• Computational complexityThe calculation of simple averages is relatively simple, but the cost of computing increases with the number of data points. The calculation of exponential weighted averages is more complex, but due to its recursive nature, it can handle continuous data streams more efficiently.

EMA and SMA approximate conversion methods

Although simple averages and index-weighted averages are conceptually different, we can approximate an index-weighted average to a simple average that contains observations of a specific quantity by choosing the appropriate $\alpha$ value. This approximation can be described by the effective sample size, which is a function of the weighting factor $\alpha$ in the index-weighted average.

A simple moving average (SMA) is the arithmetic mean of all prices in a given time window. For a time window $N$, the center of mass (SMA) of the average can be thought of as:

$\text{SMA} is equal to \frac{1 + N}{2}$

An index moving average (EMA) is a weighted average in which the most recent data point has a greater weight. The weight of the EMA decreases with the time index scale. The mass center of the EMA can be obtained by summing the following scale:

$\text{EMA} = \alpha \times \left[1 + 2(1 - \alpha) + 3(1 - \alpha) ^2 + \cdots \right] = \frac{1}{\alpha}$

When we assume that SMA and EMA have the same center of mass, we get:

$\frac{1 + N}{2} = \frac{1}{\alpha}$

So if we solve this equation, we get the relationship between $\alpha$ and $N$:

$\alpha = \frac{2}{N + 1}$

This means that for a given $N$day SMA, the corresponding $\alpha$ value can be used to calculate an equation-equivalent EMA, so that the two have the same mass and the results are very close.

EMAs are updated at different frequencies

Suppose we have an EMA that is updated once per second with a weighting factor of $\alpha_1$. This means that every second, new data points are added to the EMA with a weight of $\alpha_1$, while the effects of old data points are multiplied by $1 - \alpha_1$.

If we change the frequency of updates, say once every $f$ second, we want to find a new weighting factor $\alpha_2$ so that the total impact of data points in $f$ seconds is the same as when they are updated per second.

In $f$ seconds, if no update is made, the effect of the old data point will decay $f$ consecutively, each time by $1 - \alpha_1$. Thus, the total decay factor after $f$ seconds is $(1 - \alpha_1) ^f$.

In order for an EMA that is updated once in $f$ seconds to have the same attenuation effect as an EMA that is updated once per second in an update cycle, we set the total attenuation factor after $f$ seconds to be equal to the attenuation factor in an update cycle:

$(1 - \alpha_1)^f = 1 - \alpha_2$

So if we solve this equation, we get the new weighting factor $\alpha_2$:

$\alpha_2 = 1 - (1 - \alpha_1)^f$

This formula gives the approximate value of the new weighting factor $\alpha_2$, which keeps the EMA smooth when the frequency changes. For example, if we calculate the average price $\alpha_1$ is 0.001, the latest price is updated every 10s, and the equivalent $\alpha_2$ is about 0.01 if we change to 1s.

Python code implementation

class ExponentialWeightedStats:
    def __init__(self, alpha):
        self.alpha = alpha
        self.mu = 0
        self.S = 0
        self.initialized = False

    def update(self, x):
        if not self.initialized:
            self.mu = x
            self.S = 0
            self.initialized = True
        else:
            temp = x - self.mu
            new_mu = self.mu + self.alpha * temp
            self.S = self.alpha * self.S + (1 - self.alpha) * temp * (x - self.mu)
            self.mu = new_mu

    @property
    def mean(self):
        return self.mu

    @property
    def variance(self):
        return self.S

# 使用示例
alpha = 0.05  # 权重因子
stats = ExponentialWeightedStats(alpha)
data_stream = [] # 数据流
for data_point in data_stream:
    stats.update(data_point)

Summary

In high-frequency programmatic trading, fast processing of real-time data is essential. To improve computational efficiency and reduce resource consumption, this article introduces an online update algorithm for continuous computation of the weighted averages and differentials of data streams. Real-time incremental updates can also be used to calculate a variety of statistics and indicators, such as the correlation between two asset prices, linear fit, etc.