Efficient Numerical Methods for Optimization and Performance Evaluation of Changepoint Detection Procedures

We consider the simple changepoint problem setting, where observations are iid pre-change and iid post-change, with known pre- and post-change distributions. The randomized Shiryaev-Roberts detection procedure (with the initial condition sampled from the quasi-stationary distribution) proposed by Pollak in 1985 is known to be asymptotically order-3 minimax in the sense of minimizing maximal expected detection delay subject to a bound on the average run length to false alarm, as the latter goes to infinity. Since the quasi-stationary distribution is usually impossible to find, Pollak's test was not popular so far. We offer, for the first time, tools for numerical computing the quasi-stationary distribution, thus making Pollak's test applicable in practice. We also propose an alternative version of the Shiryaev-Roberts procedure with a deterministic initializing strategy and evaluate its performance metrics by developing integral equations and a concise numerical method for solving these equations. Significant side-product of our computational technique is the observation that deterministic initializations of the Shiryaev-Roberts procedure can also enjoy the same order-3 optimality property as Pollak's randomized procedure and, if carefully selected, even uniformly outperform it. We also show that a similar numerical technique can be used to optimize and evaluate performance of other popular changepoint detection procedures such as CUSUM and EWMA.