# How to detect inversions in the behavior of two time series through an online algorithm?

I would like to know if there is any technique which is capable to detect online (i.e. considering a sliding window) if there is a correlation between two time series. In particular, I'm trying to detect when there is an inversion between the tendency of the two time series, i.e. when the two time series are negatively correlated according to the Spearman Correlation coefficient.

To be more precise, considering the figure I've reported, I would like to detect as soon as possible (i.e. through an online detection algorithm) when the situations represented by the two yellow ovals.

In normal condition, this two time series as more or less the same trend (they differ only in term of amplitude as you can see in the figure), but there are particular situations (that I injected during the experiments) which cause these possible situations:

1. The green time series grows with the blu one, but after few seconds the green time series decreases and instead the blue one maintains its normal behaviour (situation represented by the big oval). This happens a few second after I've injected the particular condition, i.e. at time 600.

2. The green time series decreases with the blu one when I've returned to the situation of normal operation, i.e. at time 1400, and after few seconds the green time series goes below the blue one which instead maintains its normal behaviour (situation represented by the small oval).

So, I know what cause this inversion in the behavior of the two time series because I injected such a situation, but I'm interested in how I can detect as quickly as possible (so with few samples) when such a inversion occurs.

Have you any idea on what could be the right technique to adopt?

• Welcome to our site! Just so you know, there's no need to include thank you at the end of your questions here. – Silverfish Nov 10 '15 at 10:58
• Ok, but It is just a matter of politeness :D – Ugo Giordano Nov 10 '15 at 11:11
• We prefer to keep questions quite direct, because we hope thousands of other people will find your question useful and read it in future - we don't want them to have to read through salutations and thanks. But the best way of showing your appreciation, after you leave some time for several answers to come in (on this site, usually best to wait a couple of days) is to thank the author of the answer that helped you most by "accepting" (green tick) their answer. – Silverfish Nov 10 '15 at 11:30
• I know how to say tank you to the author of an answer, but anyway thanks for the clarification. – Ugo Giordano Nov 10 '15 at 11:35

You can keep two variables in memory:

• The running average $\mu$ of the difference between the two series at every time-step so far.
• A running average based on the last $w_{s}$ values.

Now at each time-step you update $\mu$ and $w_{s}$ until you detect that the difference between $\mu$ and $w_{s}$ becomes to large (use a threshold to determine sensitivity) which indicates a deviation.

As soon as you detect this you stop updating $\mu$ and for the next time-steps keep on updating $w_{s}$, as soon as the $w_{s}$ becomes in range of the $\mu$ again you can start updating the $\mu$ again.

This approach is easily implementable, requires few parameters to tune and should thus be used when you rapidly want to get some results.

• What do you mean with running average based on the last ws values? – Ugo Giordano Nov 10 '15 at 11:56
• if you take $w_{s}$ (window size) as 3 then you keep an average over the last 3 values, which is a running average in that you keep it updated at every step (you undo the oldest value and use the newest value to recompute) – Sjoerd Nov 10 '15 at 13:17
• Unfortunately this works well when the two time series shown significant changes. However, I would not detect when a time series becomes greater than the other, but I would detect when turnaround between the two occurs. – Ugo Giordano Nov 17 '15 at 9:20
• Did you freeze updating the mean whenever you detect that your running mean becomes higher/lower then the mean? Because if you keep updating the mean during that time the performance will get worse. All you can set the significance yourself by specifying the threshold between the mean and mean over the window. The smaller you set that threshold, the smaller deviations you can detect – Sjoerd Nov 17 '15 at 10:20
• I'm trying, but let me know if I understood the algorithm you've proposed. I compute the mean of the difference (X - Y) from time 1 to time t, and the mean of the moving window over a single time series (X for example). When at time t I detect that the mean of the difference is higher that the mean of the window, I stop the computation of the mean of the difference until I detect that the mean of the window become similar to the mean of the difference again. Do I understand right? – Ugo Giordano Nov 18 '15 at 10:16

This question is concerned with the minimum information required for detecting changepoints in a time series-based sequence of events. For example, in classic approaches to estimating sample sizes, the assumption is that the full course and information from a study will be used to evaluate the tests. Sequential sampling is concerned specifically with finding the minimum information necessary to make a determination as to the significance of the result. Changepoint detection is a natural outcome of this approach.

There is a rich literature on this beginning with Abraham Wald's 1947 book Sequential Analysis. The best, most recent and authoritative work is probably Alexander Tartakovsky's 2014 book Sequential Analysis: Hypothesis Testing and Changepoint Detection although his treatment is pretty advanced. Last June (2015), Columbia sponsored a 3-day workshop on this class of models and Tartakovsky was a co-chair:

Check the Program tab for details on specific topics and presentations. I'm sure there will be something that addresses your specific question.

Interestingly, between Wald's and Tartakovsky's books, sequential analysis was relegated largely to Op Research departments, i.e., it was pretty much an academic concern that didn't see wider use. That was until Google's adoption and use of the sequential probability ratio test (SPRT) some years back. Since then, sequential analysis has really come into its own.

Perhaps even more to the point of your concerns is a recent, less formally and theoretically statistical paper by Figueiredo, Ribeiro, Almeida and Faloutsos titled TribeFlow: Mining & Predicting User Trajectories. Here is their abstract:

Which song will Smith listen to next? Which restaurant will Alice go to tomorrow? Which product will John click next? These applications have in common the prediction of user trajectories that are in a constant state of flux over a hidden network (e.g. website links, geographic location). What users are doing now may be unrelated to what they will be doing in an hour from now. Mindful of these challenges we propose TribeFlow, a method designed to cope with the complex challenges of learning personalized predictive models of non-stationary, transient, and time-heterogeneous user trajectories. TribeFlow is a general method that can perform next product recommendation, next song recommendation, next location prediction, and general arbitrary-length user trajectory prediction without domain-specific knowledge.

Assuming you are using MATLAB, one approach is to calculate the cross-correlation between the two time series. Review the MATLAB help of function xcorr for extensive examples on computing lag or cross-correlation. Another approach is to compute the coherence between the two time series. As for the online detection, here is an idea. Do an offline investigation of the windowed values for the respective measure. Define a threshold by taking the average of all the events (hand labeled) of the respective measure.