5
$\begingroup$

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

|improve this question
$\endgroup$
  • $\begingroup$ One simple approach might be to break the $n$ symbols into clusters and then only search within the clusters. $\endgroup$ – John Oct 10 '12 at 21:05
  • 1
    $\begingroup$ 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. $\endgroup$ – chrisaycock Oct 10 '12 at 21:30
  • $\begingroup$ As @John points out, you can break your data into clusters. If you are working with stocks, you can make those clusters industries. $\endgroup$ – Akavall Oct 11 '12 at 12:55
  • $\begingroup$ I created an app to find co-integrated pairs. It's the computer doing the work so what do you care? kizbit.com $\endgroup$ – Chloe Oct 23 '12 at 3:58
8
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ to add to Justin's point, our largest super computers today may not be able to take advantage of such algorithms $\endgroup$ – pyCthon Aug 18 '13 at 21:51
9
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ How do you know there is no connection between hogs and MS? A butterfly flaps its wings... and all. The link about spurious co-integration talked about detrended data and auto-correlation, but didn't give any actual examples. I'd be interested to see an example. If you pre-process your data before, then of course it could have a spurious co-integration. Even flat data, which acts like a constant, could be co-integrated with everything, since you are technically supposed to test for a unit-root on the individual pairs first. Pairs do tend to be found in sectors. Ex: BHP & BBL. $\endgroup$ – Chloe Oct 23 '12 at 4:07
  • 5
    $\begingroup$ Common sense tells me there is no connection between hogs and Microsoft stock. I tried trading several of those pure quant pairs. After losing enough money, I decided that common sense does have a role in quantitative finance after all. $\endgroup$ – pteetor Oct 24 '12 at 0:01
  • 1
    $\begingroup$ I can think of a connection. Programmers seem to like bacon. Hogs produce bacon. If the price of hogs goes down, then the price of bacon goes down. Cheap bacon makes happy programmers, which translates to productive software development. QED. $\endgroup$ – Chloe Oct 25 '12 at 20:06
3
$\begingroup$

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.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy