Let's say I'm a stock exchange, and I have an order flow for Apple shares. Let's say those numbers look like:
- 10,000 (buy)
- -3,100 (sell)
- 24,243 (buy)
These orders come in very quickly. What I want to know, in realtime, is the balance of the orders, with respect to overall volume. Do buys outweigh sells?
In the end, I want a number that is between -1 and 1, representing sell or buy.
I created a moving average of the form:
$$V_{i+1} = S\alpha + V_i(1-\alpha)$$
where:
- $S$ is the side for the individual share, so -1 (sell) or 1 (buy).
- $V$ is my variable estimating the balance of the flow (what we want).
- $\alpha$ is the decay rate
- $i$ is the $i$'th share
The problem:
If I get an order of a million shares, I have to evaluate this formula recursively one million times.
What shortcut or reasonable approximation can I make, so I can apply each order in one step, rather than having to loop over every individual share?
I'd do something along those lines:
First of all you can solve your recurrence in closed form. $$ V_{i+1} = \alpha S + (1 - \alpha)V_i = \alpha \left(1 + (1 - \alpha) \right)S + (1-\alpha)^2V_{i-1} = \alpha \left(1 + (1 - \alpha) + (1 - \alpha)^2 \right)S + (1-\alpha)^3V_{i-2} = ... = \alpha \left(\sum_{j=0}^{k} (1 - \alpha)^j \right)S + (1-\alpha)^{k+1}V_{i-k} = \alpha \left( \frac{1 - (1-\alpha)^{k+1}}{\alpha}\right)S + (1-\alpha)^{k+1}V_{i-k} = S + (1-\alpha)^{k+1}(V_{i-k}-S) $$ for $k=i$ we have
$$ V_{i+1} = S + (1-\alpha)^{i+1}(V_0 -S) $$
Rewriting this in terms of $i$ instead $i+1$ we have
$$ V_i = S + (1-\alpha)^i (V_0 - S) $$
therefore your problem is characterized by $(1-\alpha)^i$, if you can compute this efficiently with a further multiplication and a couple of sums you're done. Observe that (assuming $i$ even)
$$ (1-\alpha)^i = (1-\alpha)^{i/2}(1-\alpha)^{i/2} $$
The time complexity of that recurrence is $$ T(i) = 1 + T(i/2) $$
which has solution $T(i) = O(\log i)$, if you then have $i = 10^6$ you should get the computation done with $T(10^6) \approx 6 log 10$ iterations.