# 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].

• One simple approach might be to break the $n$ symbols into clusters and then only search within the clusters. – John Oct 10 '12 at 21:05
• While computing a covariance matrix indeed takes $O(n^2t)$, the real slowness comes from cache misses in naive algorithms. There is a ton of work in numerical linear algebra for fast matrix calculations, so see if there is an existing software package you can use. – chrisaycock Oct 10 '12 at 21:30
• As @John points out, you can break your data into clusters. If you are working with stocks, you can make those clusters industries. – Akavall Oct 11 '12 at 12:55
• I created an app to find co-integrated pairs. It's the computer doing the work so what do you care? kizbit.com – Chloe Oct 23 '12 at 3:58

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: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1434876&isnumber=30915

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".

• to add to Justin's point, our largest super computers today may not be able to take advantage of such algorithms – pyCthon Aug 18 '13 at 21:51

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?