Data-efficient quickest change detection in minimax settings

Taposh Banerjee, Venugopal V. Veeravalli

Research output: Contribution to journalArticlepeer-review


The classical problem of quickest change detection is studied with an additional constraint on the cost of observations used in the detection process. The change point is modeled as an unknown constant, and minimax formulations are proposed for the problem. The objective in these formulations is to find a stopping time and an ON-OFF observation control policy for the observation sequence, to minimize a version of the worst possible average delay, subject to constraints on the false alarm rate and the fraction of time observations are taken before change. An algorithm called DE-CuSum is proposed and is shown to be asymptotically optimal for the proposed formulations, as the false alarm rate goes to zero. Numerical results are used to show that the DE-CuSum algorithm has good tradeoff curves and performs significantly better than the approach of fractional sampling, in which the observations are skipped using the outcome of a sequence of coin tosses, independent of the observation process. This study is guided by the insights gained from an earlier study of a Bayesian version of this problem.

Original languageEnglish (US)
Article number6553150
Pages (from-to)6917-6931
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - 2013


  • Asymptotic optimality
  • CuSum
  • minimax
  • observation control
  • quickest change detection

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Data-efficient quickest change detection in minimax settings'. Together they form a unique fingerprint.

Cite this