Faster Pair Searches Through Matrix Methods and Economic Grouping

# Searching for pairs-trading in sub O(n^2 t) time


# Searching for pairs-trading in sub O(n^2 t) time












Let there be $n$ stock symbols.

Let each stock symbol have exactly $t$ ticks (with all ticks miraculously aligned.)

We are now searching for potential pairs for pair trading.

A brute-force solution involves looking at all $\frac{n(n-1)}{2}$ pairs and for each pair, doing an $O(t)$ operation.

Can we get an approximate solution in sub $O(n^2 t)$ time? [I.e. something like fourier transforms for pair trading].

## Answer by justin-- (score 8, accepted)

https://quant.stackexchange.com/a/4334

Theoretically, the answer to the question is yes, a correlation matrix for potential pairs trades can be computed in $O\left((n^2t)^{(\omega+\epsilon)/3}\right)$ time, for any $\epsilon > 0$, where $\omega < 2.38$ is the so-called exponent of matrix multiplication.

However, these algorithms have a reputation for having a very large constant factor hidden in the big-O notation, and moreover being extraordinarily difficult to implement and apply in practice. No comment on state-of-the-art, but apparently people have researched this.

Whether or not it is advisable to trade on a supposed regression to the mean of an ex-post least-squares linear pairwise correlation of tick data is a whole other matter, but I'd assume if your trading algorithm is known and profitable, it's already been pretty well arbitraged away by the "big boys".

## Answer by pteetor (score 9)

https://quant.stackexchange.com/a/4323

For years, I performed this brute-force search daily on my universe of tradable stocks and futures. It is a waste of time. If your computer discovers that hog futures and MSFT are cointegrated, for example, do you really care? I would never trade that pair. There is no economic connection between hogs and Microsoft, so I must assume that the reported, small p-value merely identifies a spurious cointegration (yes, there is such a thing) and the trade is a loser.

John, above, gave the right answer: Partition your universe into groups of related stocks that could be sensibly traded in pairs. Check for cointegrated pairs within each group, and don't bother checking between groups. After all, if the trade does not make sense, why bother?

And, to address your problem, that will take much less time.

## Answer by Dominic Connor Quant Headhunt (score 3)

https://quant.stackexchange.com/a/8790

How about an O(N log(n)) solution ?

To be a viable trading strategy, you often expect them variances to be similar, so just calculate ordinary volatility and put it in an ordered array.

Of course that's going to be period dependent, so pick a few arbitrary periods and see which instruments end up being together.

Then you get clusters of vastly smaller size or even simple pairs if you want.