1. Proceedings
  2. I3M
  3. 2019
  4. EMSS
  5. 10.46354/i3m.2019.emss.005

Quickest change-point detection in time series with unknown distributions

  • a S. M. Pergamenshchikov  ,
  • b A. G. Tartakovsky  
  • a LMRS, UMR 6085 CNRS, Université de Rouen Normandie, Saint-Etienne du Rouvray Cedex, France International Laboratory SSP & QF, Tomsk State University
  • b Space Informatics Laboratory, Moscow Institute of Physics and Technology, Moscow, Russia and AGT StatConsult, Los Angeles, California, USA
Cite as
Pergamenshchikov S.M. , Tartakovsky A.G.  (2019). Quickest change-point detection in time series with unknown distributions. Proceedings of the 31st European Modeling & Simulation Symposium (EMSS 2019), pp. 29-33. DOI: https://doi.org/10.46354/i3m.2019.emss.005.

Abstract

We consider a problem of sequential detection of changes in general time series, in which case the observations are dependent and non-identically distributed, e.g., follow Markov, hidden Markov or even more general stochastic models. It is assumed that the pre-change model is completely known, but the post-change model contains an unknown (possibly vector) parameter. Imposing a distribution on the unknown post-change parameter, we design a mixture Shiryaev-Roberts change detection procedure in such a way that the maximal local probability of a false alarm (MLPFA) in a prespecified time window does not exceed a given level and show that this procedure is nearly optimal as the MLPFA goes to zero in the sense of minimizing the expected delay to detection uniformly over all points of change under very general conditions. These conditions are formulated in terms of the rate of convergence in the strong law of large numbers for the log-likelihood ratios between the “change” and “nochange” hypotheses. An example related to a multivariate Markov model where these conditions hold is given.

References

  1. Basseville, M. and Nikiforov, I.V, 1993. Detection of Abrupt Changes: Theory and Applications. Englewood Cliffs: Prentice Hall.
  2. Girardin, V., Konev, V. and Pergamenshchikov, S. M., 2018. Kullback-Leibler Approach to CUSUM Quickest Detection Rule for Markovian Time Series. Sequential Analysis, 37 (3), 322-341.
  3. Fellouris, G., Tartakovsky, A. G., 2013. Almost optimal sequential tests of discrete composite hypotheses. Statistica Sinica, 23, 1717-1741.
  4. Kent, S., 2000. On the trial of intrusions into information systems. IEEE Spectrum, 37, Issue 12, 52-56.
  5. Lai, T.L., 1998. Information bounds and quick detection of parameters changes in stochastic systems. IEEE Transactions on Information Theory, 44(7), 2917-2929.
  6. Page, E.S., 1954. Continuous inspection schemes. Biometrika, 41, 100-115.
  7. Pollak, M., Tartakovsky, A., 2009. Optimality properties of the Shiryaev-Roberts procedure. Statistica Sinica, 19, 1729-1739.
  8. Pergamenshchikov, S. M., Tartakovsky, A.G., 2018. Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data. Statistical inference for stochastic processes, 21 (1), 217-259.
  9. Tartakovsky, A.G., Rozovskii, B.L., Blažek, R.B., and Kim, H., 2006. Detection of intrusions in information systems by sequential change-point methods. Statistical Methodology, 3, 252-293.
  10. Tartakovsky, A., Nikiforov, I. and Basseville, M. Sequential Analysis: Hypothesis Testing and Changepoint Detection. Chapman & Hall book, Taylor & Francis Group, 2015.
  11. Yakir, B., 1994. Optimal detection of a change in distribution when observations form a Markov chain with a finite state space. In: Change-Point problems (E. Carlstein, H. Muller and D. Siegmund, Eds), Hayward, CA: Inst. Math. Statist., 346-358.
  12. Yakir, B., 1995. A note on the run length to false alarm of a change-point detection policy. Annals of Statistics, 23, 272-281.