Traditional quickest change detection, which detects distribution changes in random processes, requires full or partial knowledge of pre-change or post-change distributions of samples. In practice, it is possible that the prior information is unavailable, which prohibits the direct application of existing algorithms such as the cumulative sum (CUSUM) algorithm. In this paper, data driven quickest detection is studied, with only the assumption of stationary ergodic (not necessary i.i.d. or Markovian) processes. To fully exploit existing algorithms within the probabilistic framework, the theory of algorithmic complexity (a.k.a. Kolmogorov complexity) is applied to bridge the observed samples and unknown probability distributions. In particular, data compression algorithms such as Lempel-Ziv algorithm are used to measure the unconditional and conditional algorithm complexities. Numerical simulations are carried out to demonstrate the validity of the proposed algorithms.
['Husheng Li']
Data driven quickest change detection: An algorithmic complexity approach