Búsqueda de pares en tiempo sub O(n^2 t)

Question

Que haya $n$ símbolos de las acciones.

Que cada símbolo bursátil tenga exactamente $t$ ticks (con todos los ticks milagrosamente alineados.)

Ahora estamos buscando pares potenciales para el comercio de pares.

Una solución de fuerza bruta implica buscar en todos los $\frac{n(n-1)}{2}$ pares y para cada par, hacer un $O(t)$ operación.

¿Podemos obtener una solución aproximada en sub $O(n^2 t)$ tiempo? [Es decir, algo así como las transformadas de Fourier para el comercio de pares].

Answer 1

Durante años, realicé esta búsqueda de fuerza bruta diariamente en mi universo de acciones y futuros negociables. Es una pérdida de tiempo. Si tu ordenador descubre que los futuros del cerdo y MSFT están cointegrados, por ejemplo, ¿te importa realmente? Yo nunca negociaría ese par. No hay ninguna conexión económica entre los cerdos y Microsoft, por lo que debo suponer que el pequeño valor p notificado simplemente identifica una cointegración espuria (sí, existe una cosa ) y el comercio es un perdedor.

John, arriba, dio la respuesta correcta: Divida su universo en grupos de valores relacionados que puedan ser negociados de forma sensata en pares. Comprueba si hay pares cointegrados en cada grupo, y no se molestan en comprobar entre grupos. Al fin y al cabo, si el comercio no tiene sentido, ¿para qué molestarse?

Y, para abordar su problema, eso le llevará mucho menos tiempo.

Answer 2

Teóricamente, la respuesta a la pregunta es sí, se puede calcular una matriz de correlación para posibles operaciones de pares en $O\left((n^2t)^{(\omega+\epsilon)/3}\right)$ tiempo, para cualquier $\epsilon > 0$ , donde $\omega < 2.38$ es el llamado exponente de la multiplicación de matrices .

Sin embargo, estos algoritmos tienen fama de tener un factor constante muy grande oculto en la notación big-O, y además son extraordinariamente difíciles de implementar y aplicar en la práctica. No hay comentarios sobre el estado de la técnica, pero al parecer hay gente que ha investigado al respecto: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1434876&isnumber=30915

Si es aconsejable o no operar sobre una supuesta regresión a la media de una correlación lineal ex-post por mínimos cuadrados de los datos de los ticks es otro asunto, pero yo asumiría que si su algoritmo de trading es conocido y rentable, ya ha sido bastante bien arbitrado por los "grandes".

Answer 3

¿Qué tal una solución O(N log(n))?

Para que sea una estrategia de negociación viable, se suele esperar que las varianzas sean similares, por lo que basta con calcular la volatilidad ordinaria y ponerla en una matriz ordenada.

Por supuesto, eso va a depender del periodo, así que escoge unos cuantos periodos arbitrarios y mira qué instrumentos acaban estando juntos.

Entonces se obtienen grupos de tamaño mucho menor o incluso simples parejas si se quiere.