Sequential Change-Point Detection Procedures That are Nearly Optimal and Computationally Simple

Abstract

Sequential schemes for detecting a change in distribution often require that all of the observations be stored in memory. Lai (1995, Journal of Royal Statistical Society, Series B 57: 613–658) proposed a class of detection schemes that enable one to retain a finite window of the most recent observations, yet promise first-order optimality. The asymptotics are such that the window size is asymptotically unbounded. We argue that what's of computational importance isn't having a finite window of observations, but rather making do with a finite number of registers. We illustrate in the context of detecting a change in the parameter of an exponential family that one can achieve eventually even second-order asymptotic optimality through using only three registers for storing information of the past. We propose a very simple procedure, and show by simulation that it is highly efficient for typical applications.

Keywords:

• Asymptotic optimality
• Average run length
• Change-point detection

Subject Classifications:

• 62L10
• 62L15

ACKNOWLEDGMENTS

Moshe Pollak's research was supported by a grant from the Israel Science Foundation.

Notes

∗Using s = 1, t = 4, δ = .25.

Recommended by Adam Martinsek