9
$\begingroup$

Is there a standard (or best) method for testing when a given time-series has stabilized?


Some motivation

I have a stochastic dynamic system that outputs a value $x_t$ at each time step $t \in \mathbb{N}$. This system has some transient behavior until time step $t^*$ and then stabilizes around some mean value $x^*$ with some error. None of $t^*$, $x^*$, or the error are known to me. I am willing to make some assumptions (like Gaussian error around $x^*$ for instance) but the less a priori assumptions I need, the better. The only thing I know for sure, is that there is only one stable point that the system converges towards, and the fluctuations around the stable point are much smaller that the fluctuations during the transient period. The process is also monotonic-ish, I can assume that $x_0$ starts near $0$ and climbs towards $x^*$ (maybe overshooting by a bit before stabilizing around $x^*$).

The $x_t$ data will be coming from a simulation, and I need the stability test as a stopping condition for my simulation (since I am only interested in the transient period).

Precise question

Given only access to the time value $x_0 ... x_T$ for some finite $T$, is there a method to say with reasonable accuracy that the stochastic dynamic system has stabilized around some point $x^*$? Bonus points if the test also returns $x^*$, $t^*$, and the error around $x^*$. However, this is not essential since there are simple ways to figure this out after the simulation has finished.


Naive approach

The naive approach that first pops into my mind (which I have seen used as win conditions for some neural networks, for instance) is to pick to parameters $T$ and $E$, then if for the last $T$ timesteps there are not two points $x$ and $x'$ such that $x' - x > E$ then we conclude we have stabilized. This approach is easy, but not very rigorous. It also forces me to guess at what good values of $T$ and $E$ should be.

It seems like there should be a better approach that looks back at some number of steps in the past (or maybe somehow discounts old data), calculates the standard error from this data, and then tests if for some other numbers of steps (or another discounting scheme) the time-series has not been outside this error range. I included such a slightly less naive but still simple strategy as an answer.


Any help, or references to standard techniques are appreciated.

Notes

I also cross posted this question as-is to MetaOptimize and in a more simulation-flavored description to Computational Science.

$\endgroup$
  • $\begingroup$ Have you found a clear solution? I am interested in the same question but all the answers are not convincing. $\endgroup$ – Herman Toothrot Nov 20 '17 at 18:43
  • 1
    $\begingroup$ @user4050 unfortunately, I have not. I think it is actually a very broad question and there are many techniques that are better in some domain and worse in others. $\endgroup$ – Artem Kaznatcheev Dec 2 '17 at 19:07
5
$\begingroup$

This short remark is far from complete answer, just some suggestions:

  • if you have two periods of time where the behaviour is different, by different I mean either differences in model parameters (not relevant in this particular situation), mean or variance or any other expected characteristic of time-series object ($x_t$ in your case), you can try any methods that do estimate the time (interval) of structural (or epidemic) change.
  • In R there is a strucchange library for structural changes in linear regression models. Though it is primarily used for testing and monitoring changes in linear regression's parameters, some statistics could be used for general structural changes in time series.
$\endgroup$
  • $\begingroup$ The absence of any outlier/level shift/trend changes AND the non-accounting for serial correlation of any lag in model residuals are ingredients that often cause the standard F tests to be misapplied thus care should be taken ( as you suggested !) . $\endgroup$ – IrishStat Jun 9 '11 at 14:15
  • $\begingroup$ @IrishStat, as you may see from my post, I am not suggesting to use the linear regression model, I just noted that it may have similar form of statistics (CUMSUM or whatever, since the latter are applied to residuals of the model, that clearly are time series objects) with (probably) different limiting distributions that accounts for the autocorrelation (testable) and that if you want you may make outlier (also testable) adjustments prior to further testing. It is just the only R library I know that works with structural changes. $\endgroup$ – Dmitrij Celov Jun 9 '11 at 16:36
  • $\begingroup$ I am starting to like this answer more and more. Do you have a suggestion for a good reference (preferably a recent-ish survey paper) for some common methods of estimating the time of structural change? $\endgroup$ – Artem Kaznatcheev Jan 12 '12 at 18:22
4
$\begingroup$

As I read your question "and the fluctuations around the stable point are much smaller that the fluctuations during the transient period " what I get out of it is a request to detect when and if the variance of the errors has changed and if so when ! If that is your objective then you might consider reviewing the work or R. Tsay "outliers, Level Shifts and Variance Changes in Time Series" , Journal of Forecasting Vol 7 , 1-20 (1988). I have done considerable work in this area and find it very productive in yielding good analysis. Other approaches (ols/linear regression analysis for example ) which assume independent observations and no Pulse Outliers and/or no level shifts or local time trends and time-invariant parameters are insufficient in my opinion.

$\endgroup$
1
$\begingroup$

I was thinking more about the question and thought I would give a slight enhancement of the naive approach as an answer in hopes that people know further ideas in the direction. It also allows us to eliminate the need to know the size of the fluctuations.


The easiest way to implement it is with two parameters $(T,\alpha)$. Let $y_t = x_{t + 1} - x_{t}$ be the change in the time series between timestep $t$ and $t + 1$. When the series is stable around $x^*$, $y$ will fluctuate around zero with some standard error. Here we will assume that this error is normal.

Take the last $T$, $y_t$'s and fit a Gaussian with confidence $\alpha$ using a function like Matlab's normfit. The fit will give us a mean $\mu$ with $\alpha$ confidence error on the mean $E_\mu$ and a standard deviation $\sigma$ with corresponding error $E_\sigma$. If $0 \in (\mu - E_\mu, \mu + E_\mu)$, then you can accept. If you want to be extra sure, then you can also renormalize the $y_t$s by the $\sigma$ you found (so that you now have standard deviation $1$) and test with the Kolmogorov-Smirnov test at the $\alpha$ confidence level.


The advantage of this method is that unlike the naive approach, you no longer need to know anything about the magnitude of the thermal fluctuations around the mean. The limitation is that you still have an arbitrary $T$ parameter, and we had to assume a normal distribution on the noise (which is not unreasonable). I am not sure if this can be modified by some weighted mean with discounting. If a different distribution is expected to model the noise, then normfit and the Kolmogorov-Smirnov test should be replaced by their equivalents for that distribution.

$\endgroup$
0
$\begingroup$

You might consider testing backward (with a rolling window) for co-integration between x and the long term mean.

When x is flopping around the mean, hopefully the windowed Augmented Dickey Fuller test, or whatever co-integration test you choose, will tell you that the two series are co-integrated. Once you get into the transition period, where the two series stray away from each other, hopefully your test will tell you that the windowed series are not co-integrated.

The problem with this scheme is that it is harder to detect co-integration in a smaller window. And, a window that is too big, if it includes only a small segment of the transition period, will tell you that the windowed series is co-integrated when it shouldn't. And, as you might guess, there's no way to know ahead of time what the "right" window size might be.

All I can say is that you'll have to play around with it to see if you get reasonable results.

$\endgroup$
0
$\begingroup$

As the simulation runs, divide take the last 2N points segmenting it into the first and second half. Compute the series of changes (the value of $m_{t+1} - m_{t}$) for the metric of interest for each half. Test the distribution of these two sets of deltas for stationarity. The easiest way to do this is compute the cdf of each distribution, labeling the recent one as "observed" and the prior one as "expected". Then conduct Pearson's chi-squared test for the value of your metric at each decile.

$\endgroup$
0
$\begingroup$

Aside from the obvious Kalman Filter solution, you can use wavelet decompositions and get a time and frequency localised power spectrum. This satisfies your no assumptions desire, but unfortunately does not give you a formal test of when the system settles. But, for a practical application, it's fine; just look at the time when the energy in the high frequencies dies, and when the father wavelet coefficients stabilise.

$\endgroup$
  • $\begingroup$ doesn't that just pass the buck around, since I have to not test when the father wavelet coefficient time-series stabilizes? Or is there a standard method for this particular time series? What is the obvious Kalman filter solution? $\endgroup$ – Artem Kaznatcheev Oct 3 '13 at 16:00
  • $\begingroup$ @ArtemKaznatcheev Why can't you just look at a plot of the coefficient series? I was trying to offer a solution that didn't adhere to your desire to test, but as a trade-off was without many assumptions. $\endgroup$ – user2763361 Oct 4 '13 at 1:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.