Quickest Change Detection

I. INTRODUCTION

• Quickest change detection aims to detect a distributional change as soon as possible while satisfying a false-alarm constraint.Applications include biomedical signal and image processing, quality control, financial markets, and machine-failure detection.Source: §I · pp. 1–2
• Shewhart control charts use current measurements, while Page’s moving-average and CuSum proposals incorporate past statistics to detect changes more efficiently.The early schemes emphasized implementability and performance rather than provable optimality.Source: §I · pp. 2–3
• The classical i.i.d. model assumes observations are independent and identically distributed before and after the change, with known distributions.The chapter contrasts Bayesian methods, which can model the change point as random, with minimax methods for a non-random unknown change point.Source: §I · p. 3
• The chapter covers Bayesian and minimax detection for a single sequence, then extensions for unknown distributions, observation costs, and geographically distributed sensors.It also surveys applications and future research directions.Source: §I · p. 4

A. Martingales

• Martingale inequalities help design thresholds that satisfy false-alarm constraints in procedures that compare a stochastic sequence with a threshold.Martingale convergence is also presented as a mathematical background result.Source: A. Martingales · p. 6

B. Stopping Times

• Stopping times formalize when sequential decisions can be made from observations so far; optional stopping and Wald’s identity support false-alarm and delay analyses.A stopping time’s decision at time n depends only on observations through n.Source: B. Stopping Times · pp. 6–7

C. Renewal and Nonlinear Renewal Theory

• For threshold-crossing sequences with slowly changing perturbations, the asymptotic overshoot distribution matches that of the underlying random walk.Overshoot estimates help approximate crossing times and detection-procedure performance under suitable assumptions.Source: C. Renewal and Nonlinear Renewal Theory · pp. 7, 9

III. BAYESIAN QUICKEST CHANGE DETECTION

• For non-i.i.d. models, exact optimal algorithms are difficult to find, but asymptotically optimal solutions are available as the false-alarm probability tends to zero.The chapter describes such solutions for a general non-i.i.d. setting.Source: §III · p. 10
• The Shiryaev procedure uses the posterior probability that a change has occurred, updated recursively using Bayes’ rule and the likelihood ratio.The setup assumes a geometric prior with parameter ρ and pre- and post-change densities f0 and f1.Source: A. The Bayesian I.I.D. Setting · p. 11
• Under i.i.d. observations and a geometric change-point prior, the Shiryaev rule exactly minimizes average detection delay subject to the probability-of-false-alarm constraint.The Bayesian problem is to choose a stopping time that minimizes ADD while meeting a PFA bound.Source: §III · p. 10, A. The Bayesian I.I.D. Setting · p. 11
• The optimal policy has a threshold structure in the posterior probability, with the decision to stop determined by its relation to a threshold.The chapter illustrates the policy with cost curves and a typical evolution of the Shiryaev algorithm.Source: A. The Bayesian I.I.D. Setting · pp. 12–13, Figure 2 · p. 13
• The posterior probability, averaged likelihood ratio, and Shiryaev statistic are linked by one-to-one mappings, and equivalent stopping-time descriptions are provided.The likelihood-ratio and statistic formulations are noted as useful in later non-i.i.d. and minimax discussions.Source: A. The Bayesian I.I.D. Setting · p. 14

• For non-i.i.d. observations, an exact solution is difficult, so the section develops Bayesian asymptotic theory for general pre- and post-change distributions.Source: B. General Asymptotic Bayesian Theory · p. 14
• Under a likelihood-ratio convergence condition, the Shiryaev algorithm is asymptotically optimal for Bayesian optimization as α → 0, minimizing all moments of detection delay.The proof establishes a lower bound for procedures meeting the false-alarm constraint and shows that the Shiryaev stopping time achieves it asymptotically.Source: B. General Asymptotic Bayesian Theory · p. 15
• Existence of the likelihood-ratio limit q alone guarantees almost-sure finiteness of T_ε(n), but not finiteness of its moments, which is needed to establish delay moments.Source: B. General Asymptotic Bayesian Theory · pp. 15–16
• With the stated convergence conditions, a lower bound on delay is given by (1−ε)|log α|/(q+d), where d captures the change-point prior’s tail.The prior tail parameter d is zero for a heavy-tailed prior and positive for an exponential-tail prior.Source: B. General Asymptotic Bayesian Theory · pp. 16–17

• The first-order ADD expression may estimate delay poorly unless PFA is very small, while the PFA bound can also be loose.A second-order estimate based on nonlinear renewal theory is useful in that regime.Source: C. Performance analysis for i.i.d.… · p. 18
• PFA is asymptotically determined by the overshoot when the Shiryaev statistic crosses its threshold from below.The expression relates PFA to the expected exponential of the negative overshoot.Source: C. Performance analysis for i.i.d.… · p. 19
• E₁[τS] = (b + κ − E₁[η])/(|log(1 − ρ)| + D(f1∥f0)) + o(1) as b → ∞, under the stated nonarithmetic condition.Source: C. Performance analysis for i.i.d.… · p. 20
• The ADD-versus-log(PFA) trade-off has slope 1/(|log(1−ρ)|+D(f1∥f0)); the prior or observations dominate according to which information term is larger.Source: C. Performance analysis for i.i.d.… · p. 21

• CuSum accumulates log-likelihood evidence: it has negative drift before the change and positive drift afterward, and signals when its statistic crosses a positive threshold.Source: §IV · p. 22
• A uniformly powerful test minimizing delay over every possible change point under a false-alarm-rate constraint is generally unavailable, motivating minimax formulations.Source: §IV · p. 23
• In the i.i.d. setting, CuSum is exactly optimal for Lorden’s minimax criterion under a false-alarm-rate constraint.It is also asymptotically optimal as the constraint tends to zero.Source: §IV · p. 24
• Pollak’s criterion uses conditional average delay; in the i.i.d. setting, Shiryaev–Roberts-based algorithms are within a constant of the best possible performance as the false-alarm rate tends to zero.Source: §IV · p. 25
• For non-i.i.d. observations, an extended CuSum achieves asymptotically the lower bound on conditional average delay and therefore also on Lorden’s worst-case average delay.Source: §IV · p. 25

A. Minimax Algorithms Based on the Shiryaev Algorithm

• The SR algorithm is second-order asymptotically optimal for criterion (55) as α → 0, with delay within a constant of the best possible over Dα, and is exactly optimal for a number of other criteria,.Source: A. Minimax Algorithms Based on the… · p. 26
• SRP initializes the Shiryaev–Roberts statistic from its quasi-stationary distribution, yielding third-order asymptotic optimality for Pollak’s formulation.Source: A. Minimax Algorithms Based on the… · p. 26
• SR-r and SRP are third-order asymptotically optimal for Pollak’s formulation, whereas SR is second-order asymptotically optimal.SR-r is reported to outperform SRP uniformly over possible change points.Source: A. Minimax Algorithms Based on the… · pp. 26–27
• Computing the quasi-stationary distribution is difficult in practice, making simulation evaluation of CADD and WADD challenging for SRP.The text notes that a numerical framework for computing the distribution is available in.Source: A. Minimax Algorithms Based on the… · pp. 26–28

B. Optimality Properties of the Minimax Algorithms

• The SR algorithm is the limit of a sequence of Bayes tests and is asymptotically Bayes efficient in that limit.Source: B. Optimality Properties of the… · pp. 28–29
• For Pollak’s criterion, the lower bound on CADD is |log α|/D(f1||f0) + κ̂ + o(1) as α → 0, under Theorem 4.2’s stated nonarithmetic condition.Source: B. Optimality Properties of the… · p. 29
• For the SR algorithm, threshold B = 1/α ensures FAR(τSR) ≤ α.Source: B. Optimality Properties of the… · p. 29
• CADD(τSR) ∼ CADD(τSRP) ∼ CADD(τSR−r) ∼ |log α| D(f1||f0), with SR-r and SRP third-order optimal and SR second-order optimal for Pollak’s formulation.Source: B. Optimality Properties of the… · p. 31
• CuSum with threshold b = |log α| is first-order asymptotically optimal for both Lorden’s and Pollak’s formulations, with CADD(τC) = WADD(τC) ∼ |log α| D(f1||f0).Source: B. Optimality Properties of the… · pp. 31–32
• CuSum’s ADD versus −log FAR trade-off curve has slope 1/D(f1||f0).Source: B. Optimality Properties of the… · p. 32, Figure 5 · p. 32

C. General Asymptotic Minimax Theory

• In the non-i.i.d. setting, an extension of CuSum asymptotically achieves lower bounds on WADD and CADD for stopping times in Dα.The lower bounds are established under general conditions.Source: C. General Asymptotic Minimax Theory · p. 32
• τG is first-order asymptotically optimal within Dα under the FAR constraint α.Its delay is asymptotically equal to the lower bound up to first order.Source: C. General Asymptotic Minimax Theory · pp. 32–33
• Chebyshev’s inequality is used to derive a CADD lower bound that applies to the entire family Dα.The proof sketch first obtains a lower bound independent of the particular stopping time.Source: C. General Asymptotic Minimax Theory · p. 33

V. RELATIONSHIP BETWEEN THE MODELS

• An adversary with access to observations yields Lorden’s delay expression for a given stopping time.The change-point distribution is chosen using the observation sequence.Source: §V · p. 35
• If the adversary sees only test performance, the resulting delay is Pollak’s formulation.The adversary does not have access to the observations.Source: §V · p. 35
• Shiryaev’s delay formulation corresponds to restricting the change-point distribution to one possibility.That possibility is the distribution of Γ.Source: §V · p. 35

VI. VARIANTS AND GENERALIZATIONS OF THE QUICKEST CHANGE DETECTION PROBLEM

• The section reviews three important variants and extensions of the classical quickest change detection problem.The chapter identifies these as areas where significant progress has been made.Source: §VI · p. 36

A. Quickest Change Detection with unknown pre- or post-change distributions

• WADDθ[τG] ∼ | log α| D(fθ, f0) for the GLR test when the post-change distribution is unknown and the pre-change distribution is known.Under the stated threshold choices, this is uniformly asymptotically optimal with respect to Lorden’s criterion.Source: A. Quickest Change Detection with… · pp. 36–37
• WADDθ[τM] ∼ | log α| D(fθ, f0) for the mixture-based test under the stated conditions.The mixture-based test is also uniformly asymptotically optimal with respect to Lorden’s criterion.Source: A. Quickest Change Detection with… · p. 37
• GLR and mixture tests lack the equivalent recursive implementation available to CuSum or Shiryaev-Roberts tests when the post-change distribution is known.The general implementations use the entire past; sliding-window variants use finitely many past observations, with window size chosen as a function of FAR.Source: A. Quickest Change Detection with… · p. 37
• WADDθ[ˆτG] ∼ WADDθ[ˆτM] ∼ | log α| D(fθ, f0) for the window-limited GLR and mixture tests under some conditions.The chapter states that these tests are asymptotically optimal for a suitable choice of their window parameters.Source: A. Quickest Change Detection with… · p. 38
• Window-limited tests remain asymptotically optimal under stated conditions, but non-i.i.d. implementations may require the full observation history.The stated exception is when dependence is finite-order Markov.Source: A. Quickest Change Detection with… · pp. 37–38
• For uncertainty classes, a least-favorable distribution pair can yield a classical robust test that is recursive and can outperform the GLR test in some parameter ranges and at moderate FAR.The robust test is not uniformly asymptotically optimal; the GLR may require solving a complex nonconvex optimization problem at each time.Source: A. Quickest Change Detection with… · p. 39

B. Data-efficient quickest change detection

• The DE-Shiryaev formulation adds an observation-cost constraint, measured by the average number of pre-change observations, alongside delay and false-alarm constraints.A policy decides whether to take each next observation using the information available so far.Source: B. Data-efficient quickest change… · pp. 39–40
• As α →0, the DE-Shiryaev algorithm’s PFA and ADD approach those of the Shiryaev algorithm, making it asymptotically optimal.The asymptotic ADD expression is given in [32].Source: B. Data-efficient quickest change… · p. 41
• With Gaussian observations and moderate false-alarm probabilities, delay stays within 10% of Shiryaev delay even when observation cost falls by more than 50%.The algorithm also substantially outperforms fractional sampling, which preselects observations to skip (Fig. 6b).Source: B. Data-efficient quickest change… · p. 41, Figure 6 · p. 41
• Without a change-point prior, the Bayesian data-efficient approach has no obvious substitute for its prior-based skipped-observation update, motivating a minimax formulation.The formulation uses a duty-cycle metric for pre-change observation cost and yields the DE-CuSum algorithm, which is asymptotically optimal and performs significantly better than fractional sampling.Source: B. Data-efficient quickest change… · p. 42

C. Distributed sensor systems

• Without certain conditional-independence assumptions across sensors, finding optimal solutions is computationally intractable even for static binary hypothesis testing.Dynamic decentralized decisions are harder because decision makers have different information.Source: C. Distributed sensor systems · p. 43
• In the simplest model, sensors are affected simultaneously and observations are i.i.d. over time and independent across sensors; even then, decentralized optimization is intractable.Asymptotically, stationary monotone likelihood-ratio quantizers are optimal, with thresholds chosen to maximize the sensors’ K-L divergence.Source: C. Distributed sensor systems · p. 44
• With fixed stationary quantizers, the fusion center faces a centralized quickest-change problem, and delay–false-alarm tradeoff is governed by the K-L divergence of quantized observations.First-order asymptotic performance with quantization is at best equal to that without quantization.Source: C. Distributed sensor systems · p. 44
• Under Lorden’s and Pollak’s minimax criteria, τall is globally first-order asymptotically optimal with appropriate thresholds, while τmax and τmin are not.For the Bayesian case with local Shiryaev statistics, both τmax and τall are globally first-order asymptotically optimal, unlike τmin.Source: C. Distributed sensor systems · p. 45
• Local-decision schemes can match centralized first-order performance asymptotically, but simulations show those asymptotics may require unreasonably low false-alarm levels.At moderate false-alarm levels, even binary sensor quantization can outperform globally asymptotically optimal local-decision tests.Source: C. Distributed sensor systems · p. 45

D. Variants of quickest change detection problem for distributed sensor systems

• A summed-CuSum fusion test for changes affecting only a subset of sensors has lower computational complexity than a GLRT and is asymptotically as good as centralized CuSum as FAR vanishes.At moderate FAR, unaffected-sensor noise can degrade performance; transmitting only above a local threshold suppresses that noise and improves performance.Source: D. Variants of quickest change… · pp. 45–46

VII. APPLICATIONS OF QUICKEST CHANGE DETECTION

• Sensor-network monitoring of infrastructure or habitats may require data-efficient detection because sensors remain deployed for long periods while changes occur rarely.Other listed applications include process control, computer-network security, cognitive radio, and monitoring drug sales for disease outbreaks or bioterrorism effects.Source: §VII · pp. 46–47

VIII. CONCLUSIONS AND FUTURE DIRECTIONS

• The review finds exact or nearly optimal algorithms mainly for i.i.d. single-sequence detection, while asymptotically optimal methods extend to broader settings including unknown post-change distributions, data-efficient detection, decentralized detection, and non-i.i.d. models.The authors state that the reviewed topics are far from exhaustive.Source: §VIII · p. 47
• Future directions include transient changes, propagation across sensors, multiple change points in networks, social learning, simultaneous classification, and asynchronous sensor communications.Transient-change settings may require metrics for detecting the change while the system remains in that state.Source: §VIII · pp. 47–48
• In network settings, further open problems include relating multiple change points to affected sensors, detecting changes from processed information passed between agents, and handling asynchronous sensor messages.The review also notes interest in detecting and identifying which of several possible post-change hypotheses is true.Source: §VIII · p. 48