PaperlayerView exact revision on arXiv

Source-linked AI summary

State-of-the-Art in Sequential Change-Point Detection

Aleksey S. Polunchenko, Alexander G. Tartakovsky

arXiv:1109.2938v1math.STstat.TH

TL;DR

Sequential change-point detection must balance rapid detection against the risk of false alarms. This paper surveys four formulations and recent optimality advances, connecting generalized Bayesian detection with multi-cyclic detection in a stationary regime. In the iid setting, the multi-cyclic SR procedure solves the stationary-regime problem, which is equivalent to the generalized Bayesian problem.

  • Problem

    Sequential change-point detection seeks timely online detection while keeping the risk of false alarms tolerable, despite the unknown time of change.

    Source: §1 · p. 2

  • Method

    The paper surveys four connected formulations of quickest change detection and assesses recent exact and asymptotic optimality results.

    Source: §1 · p. 2, §3 · p. 5

  • Results

    For iid observations, the multi-cyclic SR procedure solves stationary-regime detection, whose criterion is equivalent to generalized Bayesian RIADD.

    Source: §3.4 · p. 13

  • Takeaways & Limitations

    The generalized Bayesian formulation also represents repeated detection in a stationary regime when the change is distant and alarms recur before it.

    Source: §3.2 · p. 9, §3.4 · p. 13

    Pollak’s JP(T) optimality remains open in general, and finding the potentially optimal time-varying initialization sequences is extremely difficult.

    Source: §7 · pp. 25–26

Abstract

from arXiv · show

We provide an overview of the state-of-the-art in the area of sequential change-point detection assuming discrete time and known pre- and post-change distributions. The overview spans over all major formulations of the underlying optimization problem, namely, Bayesian, generalized Bayesian, and minimax. We pay particular attention to the latest advances in each. Also, we link together the generalized Bayesian problem with multi-cyclic disorder detection in a stationary regime when the change occurs at a distant time horizon. We conclude with two case studies to illustrate the cutting edge of the field at work.

1 Introduction

Sequential change-point detection seeks to detect a change quickly while keeping false alarms tolerable, balancing the competing costs of delay and false detection. This overview surveys four connected formulations and emphasizes recent exact and asymptotic optimality results.

1 Introduction

  • Fast detection risks false alarms, while avoiding false alarms too aggressively increases delay, so sequential policies trade off both losses.The change-point is unknown in advance, and decisions must be made in real time from successive observations.Source: §1 · p. 2
  • The paper surveys Bayesian, generalized Bayesian, minimax, and multi-cyclic formulations as connected approaches to quickest change detection.The four approaches formalize detection delay and false-alarm risk in different ways.Source: §1 · p. 2
  • The overview assesses progress across these formulations, emphasizing novel exact and asymptotic optimality results.Source: §1 · p. 2

2 Change-point models

The change-point model specifies both the observations’ probabilistic structure and the change-point’s status, which may be deterministic or random. The section reviews general models and common special cases.

2 Change-point models

  • Change-point models can vary in observation dependence and homogeneity, and in whether the change-point is deterministic, random, or related to the observed data.The general model permits arbitrary dependent and non-identically distributed observations.Source: §2 · pp. 3–4
  • The paper uses ν for the last normal observation; the change-point’s prior may depend on observations, although the discussion assumes an observation-independent prior.The authors note that an observation-dependent probability series could instead be viewed as a posterior distribution.Source: §2 · pp. 3–5
  • In the iid special case, observations before and after the change follow distinct common distributions.The pre-change observations follow f(x), and post-change observations follow g(x) ≠ f(x).Source: §2 · p. 4

3 Overview of optimality criteria

The section compares Bayesian, generalized Bayesian, minimax, and multi-cyclic formulations, including how their false-alarm constraints and delay criteria differ. It highlights optimal procedures and connects generalized Bayesian detection with repeated detection in a stationary regime.

3 Overview of optimality criteria

  • Bayesian, generalized Bayesian, and minimax procedures use a single-run paradigm, whereas repeated applications with restarts form a multi-cyclic procedure.The multi-cyclic setting treats the ARL to false alarm as the mean time between consecutive false alarms.Source: §3 · p. 5, §3.4 · p. 11

3.1 Bayesian formulation

  • Under a geometric change-point prior, thresholding the posterior probability yields the Shiryaev procedure, which is optimal when its threshold achieves the specified false-alarm probability exactly.The paper notes that selecting a threshold to attain the exact false-alarm level is rarely possible.Source: §3.1 · pp. 7–8

3.2 Generalized Bayesian formulation

  • As the geometric-prior parameter tends to zero, the Bayesian Shiryaev statistic converges to the SR statistic, which minimizes RIADD in the iid generalized Bayesian setting.The section also identifies generalized Bayesian detection as the limiting case of the Bayesian formulation.Source: §3.1 · p. 8, §3.2 · pp. 8–9

3.3 Minimax formulation

  • For the iid scenario, CUSUM is exactly optimal for Lorden’s problem for every γ > 1; no procedure can minimize average conditional detection delay Eν[T − ν | T > ν] for all ν ≥ 0 simultaneously.Source: §3.3 · p. 10
  • The section presents a sliding-window conditional false-alarm probability as an alternative to ARL, since ARL may not adequately measure false-alarm risk in general non-iid models.For iid models, stopping times in a class of common procedures are asymptotically exponential with parameter 1/E∞[T].Source: §3.3 · pp. 10–11

3.4 Multi-cyclic detection of a disorder in a stationary regime

  • For iid observations, the multi-cyclic SR procedure solves stationary-regime detection, and its criterion is equivalent to generalized Bayesian RIADD.The setting models repeated alarms before a change occurring at a distant time horizon.Source: §3.4 · pp. 11, 13

4 Optimality properties of the Shiryaev–Roberts detection procedure

Under the iid known-density model, the section defines the Shiryaev–Roberts (SR) procedure and states its optimality for generalized Bayesian RIADD and stationary multi-cyclic detection.

4 Optimality properties of the Shiryaev–Roberts detection procedure

  • The results concern iid observations with known pre-change density f and distinct known post-change density g; likelihood ratios feed the selected sequential procedure.In this setting, the SR procedure solves both the generalized Bayesian and stationary multi-cyclic problems.Source: §4 · p. 13

4.1 The Shiryaev–Roberts procedure

  • The SR procedure stops when its recursively updated statistic Rn = (1 + Rn−1)Λn, initialized at zero, crosses threshold A.Shiryaev and Roberts developed the procedure independently in different change-detection settings.Source: §4.1 · p. 14

4.2 Optimality properties

  • For γ > 1 and the stated threshold selection, the SR procedure minimizes RIADD over stopping times with E∞[T] ≥ γ.The theorem selects Aγ so that E∞[SAγ] = γ.Source: §4.2 · p. 14
  • Because RIADD(T) equals JST(T) for any stopping time, the SR procedure also minimizes stationary average detection delay among multi-cyclic procedures in ∆(γ).This optimality holds for every γ > 1.Source: §4.2 · p. 14
  • For large γ, setting Aγ = γζ yields E∞[SAγ] ≈ γ, while E∞[SA] ≥ A for all A > 0.Here 0 < ζ < 1.Source: §4.2 · p. 14

5 Optimal and nearly optimal minimax detection procedures

The minimax problem remains unsolved in general, so the section develops asymptotically optimal procedures as the false-alarm ARL γ grows. It presents the SRP and SR–r procedures, their design rationale, and their asymptotic guarantees.

5 Optimal and nearly optimal minimax detection procedures

  • The minimax problem is not solved in general, motivating asymptotic optimality as γ →∞, with first-, second-, and third-order notions distinguished.The section measures how closely a procedure approaches the minimax optimum in this limit.Source: §5 · p. 15

5.1 The Shiryaev–Roberts–Pollak procedure

  • Starting the SR statistic from its quasi-stationary distribution makes SRP an equalizer, giving the same conditional average detection delay for every change point.The motivation is that the SR statistic’s conditional distribution stabilizes in its quasi-stationary mode.Source: §5.1 · pp. 15–16
  • The SRP procedure is third-order asymptotically optimal for Pollak’s delay measure under the stated moment condition and threshold calibration.Its threshold is selected to give an average run length to false alarm of γ.Source: §5.1 · p. 16

5.2 The Shiryaev–Roberts–r procedure

  • Because SRP requires the quasi-stationary distribution, which is rarely available in closed form, it has not been used in practice.The section notes that closed-form examples are rare.Source: §5.2 · p. 17
  • The SR–r procedure uses a specially designed deterministic head start r; numerical evidence indicates some such procedures are uniformly better than SRP.This fixed initialization was proposed as an implementable alternative to SRP’s quasi-stationary initialization.Source: §5.2 · p. 17
  • If an SR–r procedure is an equalizer, the section states it is strictly minimax in the class Δ(γ).The section also identifies two specific models for which a specially designed SR–r is strictly optimal.Source: §5.2 · p. 18
  • With a specially selected initialization, SR–r is third-order asymptotically minimax, whereas the conventional zero-start SR procedure is only second-order asymptotically optimal.For sufficiently large γ, the optimized SR–r advantage in supremum delay is (C(0) − C∞)/I, which can be large when the Kullback–Leibler information number I is small.Source: §5.2 · pp. 19–20
  • Choosing r so the delay at the beginning and at infinity approximately match motivates a γ-independent asymptotic initialization and supports approximate optimality.The proposed asymptotic choice satisfies C(r*) = C∞.Source: §5.2 · pp. 17, 19, 20

6 Numerical performance evaluation

This section gives integral-equation methods for computing operating characteristics across detection procedures and problem settings. It also describes numerical solution methods and a randomized procedure with change-point-independent delay.

6 Numerical performance evaluation

  • The section presents integral equations for operating characteristics across Bayesian, minimax, and other settings, since procedure efficiency must be assessed using the relevant performance measures.The equations can usually not be solved analytically, so numerical techniques are often needed.Source: §6 · p. 20
  • For a generic detection statistic, the equations yield conditional average delays for each change point, enabling evaluation of their supremum.The procedure’s starting point and threshold are inputs to these calculations.Source: §6 · pp. 20–21
  • The quasi-stationary randomized variant is designed as an equalizer, and its false-alarm time is geometrically distributed under P∞.Its starting point is sampled from the quasi-stationary distribution.Source: §6 · p. 22
  • Because the Fredholm integral equations usually lack exact analytical solutions, the section describes a piecewise collocation interpolation-projection scheme with at-worst linear convergence.The equations support evaluating operating characteristics for particular scenarios.Source: §6 · p. 23

7 Exact optimality of the Shiryaev–Roberts–r procedure

The section overturns the conjecture that SRP is Pollak-minimax by showing SR–r optimal in two counterexamples, while stressing that this optimality is not general.

7 Exact optimality of the Shiryaev–Roberts–r procedure

  • The integral equation with given v and kernel K is an umbrella for equations used to determine the operating characteristics of SR-type procedures.Source: §7 · pp. 23–24
  • When the kernel is separable, the integral equation can be solved analytically, enabling analytical computation of SR-type operating characteristics.Source: §7 · p. 24
  • Choosing the SR–r starting point to equalize performance at ν = 0 and ν ≥ 1 makes it an equalizer for all ν ≥ 0 and minimax in the separable-kernel case.The quasi-stationary distribution takes effect from the first observation in this case.Source: §7 · p. 24
  • A seemingly different exponential pre- and post-change model has exactly the same P_Λ distributions as the uniform(0, 1)-to-beta(2, 1) model (Polunchenko and Tartakovsky 2010).Source: §7 · p. 24
  • For 1 < γ < γ̄ ≈ 2.2, SR–r is strictly minimax, while the SRP procedure with the same ARL to false alarm has strictly greater JP.The theorem sets each procedure's ARL to false alarm to γ.Source: §7 · p. 25
  • Pollak's optimizer remains open in general; the authors conjecture time-dependent initializations and thresholds, whose sequences are extremely difficult to find.For moderate, low false-alarm rates, the lower bound and supremum ADD are usually close.Source: §7 · pp. 25–26
  • For the class Δ_m_α, SR–r is minimax; the paper describes this as the first exact optimality result in that class.Source: §7 · p. 26

8 Case studies

The case studies compare SR–r and SRP under beta-shift and exponential-mean models, examining detection delays and asymptotic approximations. Their results show that practical preference and best performance depend on the model and delay criterion.

8 Case studies

  • The case studies use two iid models to illustrate the performance margin between SR–r and SRP.For the beta model, the needed asymptotic quantities are analytically computable for any δ > 0, enabling comparison of measured performance with asymptotic predictions.Source: §8 · p. 26, §8.1 · p. 27

8.1 Example 1: A beta-to-beta model

  • The beta(δ, δ + 1)-to-beta(δ + 1, δ) model and its swapped counterpart are statistically indistinguishable for any δ > 0.The model’s mirrored Beta-prime likelihood-ratio distributions establish this symmetry.Source: §8.1 · p. 27
  • At ARL 100, the actual worst delays are 3.54 for SRP and 3.52 for SR–r, versus an approximation of about 2.9; at higher ARL, the approximations are accurate.The authors attribute the low-ARL inaccuracy to the ARL being only 100 and the higher-ARL accuracy to the relatively high false-alarm ARL.Source: §8.1 · pp. 29–30
  • In the beta model, SR–r is almost an equalizer and nearly indistinguishable from SRP, but is easier to implement and recommended for practical use.At δ = 1, SR–r is uniformly better across change times, though the gain is practically negligible.Source: §8.1 · pp. 29–31, Figure 6 · p. 30, Figure 7 · p. 31

8.2 Example 2: An exponential scenario

  • For the exponential scenario, SR–r performs best under Pollak’s delay criterion and is close to its lower bound, while SR is optimal for stationary delay with relatively small differences.The authors suggest the unknown optimal procedure could improve only insignificantly over SR–r under Pollak’s criterion.Source: §8.2 · p. 32
Loading 1109.2938v1…