betaFeedback

WorksMathematics

Probability-Maximizing Change Detection: Finite-Window Optimality

Abstract

This paper investigates probability-maximizing sequential change detection, a formulation in which performance is measured by the probability of stopping within an admissible interval of duration ξξ after a change rather than by the expected detection delay. Earlier work introduced this viewpoint in a Bayesian setting and subsequently formalized it under Lorden- and Pollak-type minimax criteria for the case in which successful detection must occur on the first post-change observation, i.e., ξ=1ξ=1. This paper generalizes this framework in two directions. First, the decision maker is allowed to stop within a prescribed window of ξ∈Nξ\in\mathbb{N} post-change observations. Second, the monitored process is allowed to experience multiple, non-overlapping transient change episodes with unknown onset times and durations, so that success consists of stopping within the admissible window associated with any one of these episodes. False alarms are controlled through an average run-length constraint. For exact finite-sample analysis, the paper introduces a survival-weighted average success criterion, which represents the probability of successfully detecting a randomly encountered change opportunity conditional on the detector being active at its onset. It is established that this criterion admits an exact representation as the expected truncated Shiryaev–Roberts (TSR) statistic at the stopping time normalized by the average run length, and it characterizes its exactly optimal stopping rule. The optimal procedure has finite memory and aggregates the likelihood-ratio evidence corresponding to all possible change onsets within the most recent window and compares the resulting TSR statistic with a state-dependent continuation boundary obtained from an optimal-stopping formulation.

Introduction

*Electrical, Computer, and Systems Engineering Department, Rensselaer Polytechnic Institute, Troy, NY. †Cruise LLC, Seattle, WA.

The results in this paper were partly presented in the 2019 IEEE International Symposium on Information Theory.

Classical quickest change detection is principally concerned with a single change that occurs at an unknown time and persists thereafter. Its standard formulations fall into two broad categories: Bayesian and minimax [1, 2, 3]. In the Bayesian framework, the change-point is modeled as a random variable with a specified prior distribution, and the stopping rule is designed by averaging performance over both the change-point prior and the observation process [1]. In the minimax framework, the change-point is treated as an unknown but nonrandom time, and performance is assessed under its least favorable occurrence. Lorden’s criterion considers the worst conditional expected delay over all change times and all possible pre-change observation histories [2], whereas Pollak’s criterion considers the worst conditional expected delay over all change times, conditioned on no alarm having occurred before the change [3]. Although these formulations differ in how uncertainty about the change-point is represented and how worst-case performance is quantified, they share the objective of favoring an earlier post-change alarm over a later one, subject to false-alarm control. They do not, however, directly encode the requirement that detection occur within a prescribed admissible window.

When detections outside that window are operationally equivalent to misses, it is natural instead to maximize the probability that the stopping time falls within the admissible post-change interval. The probability-maximizing framework for change-point detection was first introduced by Bojdecki [4]. In a Bayesian setting, Bojdecki formulated an optimal-stopping problem in which success is defined by the stopping time lying in a prescribed neighborhood of a random change time. In the zero-tolerance case, success requires stopping at the first observation generated under the post-change distribution. This formulation treated premature or late stopping through the success event itself, rather than through a separate average-run-length constraint. Subsequent Bayesian and semi-Bayesian developments extended the probability-maximizing perspective to dependent observations and to composite post-change models [5, 6].

Moustakides subsequently placed this probability-maximizing viewpoint in the standard false-alarm-constrained framework of sequential change detection [7]. Specifically, probability-maximizing counterparts of the Shiryaev, Lorden, and Pollak criteria were formulated by crediting a decision when it occurs within a prescribed interval after the change. For the non-Bayesian Lorden- and Pollak-type formulations, the exact solution developed in [7] concerns the one-sample case: conditioned on no earlier alarm, the procedure is rewarded only when it stops on the first post-change observation. The optimal rule is then the classical Shewhart test with a constant threshold selected to meet the average-run-length constraint. The same framework was further studied for independent non-identically distributed observations, multiple possible post-change distributions, and Markovian data [7, 8]. This paper studies the probability-maximizing framework through two complementary performance perspectives: a survival-weighted average success criterion and Pollak- and Lorden-type worst-case criteria, and advances the underlying model in two directions.

  1. A multi-sample admissible detection window. We credit a detection whenever it occurs within the first ξ\xi observations after a change onset, rather than only on the first post-change observation. Thus, ξ=1\xi= 1 is exactly the one-sample problem solved by Moustakides, whereas ξ≥2\xi\ge2 is the nontrivial multi-sample extension addressed in this paper. All instants in this window are regarded as successful; stopping outside it is counted as a miss for that change onset.

2. Multiple transient change opportunities. We allow an unknown finite number of non-overlapping change episodes, with unknown onset times and durations. The detector operates once over the entire observation stream and seeks to stop in the admissible window associated with one of these episodes. The Pollak- and Lorden-type criteria aggregate the conditional success probabilities associated with the possible onsets and take the worst case over all admissible change configurations. Under the persistent-change convention specified in Section 2, the single persistent-change model is recovered by taking one episode of infinite duration. More generally, the behavior after the first ξ\xi post-change observations is immaterial to the success event as long as every episode lasts at least ξ\xi samples. The survival-weighted average criterion introduced in this paper evaluates one randomly encountered change opportunity, whereas the multiple-episode model is retained for the Pollak- and Lorden-type worst-case analysis.

The extension from one admissible post-change observation to a window containing two or more observations fundamentally changes the structure of the exact average-optimal procedure. In the one-sample setting, the optimal rule is the classical Shewhart test, which bases each decision only on the current observation. With a longer admissible window, the exact average-optimal rule acquires finite memory and combines the evidence associated with all possible change onsets within the most recent observations. It can therefore be viewed as a finite-memory generalization of the Shewhart test. Furthermore, its underlying detection statistic is a truncated version of the classical Shiryaev–Roberts statistic [1, 9]. Unlike the conventional Shiryaev–Roberts procedure, however, the proposed rule does not generally compare this statistic with a fixed threshold. Instead, its stopping boundary depends on the recent likelihood-ratio history, reflecting the value of retaining the accumulated evidence for future decisions. We refer to this state-dependent generalization as the truncated Shiryaev–Roberts (TSR) test. When the admissible window contains only the first post-change observation, the memory and state dependence disappear, and the TSR test reduces to the classical Shewhart rule established in the one-sample probability-maximizing setting.

Our analysis establishes exact finite-sample optimality for a survival-weighted average success criterion and develops complementary guarantees under the Pollak- and Lorden-type worst-case criteria. The average criterion measures the probability of successful detection for a randomly encountered change opportunity, conditional on the detector still being active at its onset. It admits an exact representation as the ratio between the expected TSR evidence available at the stopping time and the expected time to stopping. We solve the resulting ratio optimization through an optimal-stopping formulation and obtain the state-dependent TSR rule as its exact optimizer. For a single change opportunity, the Pollak- and Lorden-type success probabilities are upper-bounded by this survival-weighted average criterion; for ξ≥2\xi\ge2, we do not claim that these worst-case bounds are attained at finite ARL.

For ξ=2\xi= 2, the stopping region admits a scalar state-dependent threshold representation; for general ξ\xi, the sufficient state consists of the most recent ξ−1\xi- 1 likelihood ratios. We also characterize monotonicity and convexity properties of the continuation value and describe an offline–online implementation of the average-optimal rule. For ξ=1\xi= 1, the TSR rule reduces to Shewhart and remains exactly optimal under both the average and the Pollak- and Lorden-type minimax criteria. Additionally, we identify a complementary regime in which the simpler constant-boundary TSR procedure is asymptotically minimax optimal. Specifically, when the admissible window grows beyond a specific rate, the state-dependent continuation boundary is not needed for first-order optimality.

The present manuscript revises and substantially extends our preliminary work in [10], which introduced the multiple-opportunity model, developed the state-dependent stopping structure in detail for ξ=2\xi= 2, and stated its general-window extension under the Pollak- and Lorden-type criteria. It also assumed a known common episode duration and stated finite-sample minimax attainment for ξ≥2\xi\ge2. The present manuscript makes a necessary distinction that was not developed in the conference version: the state-dependent TSR rule is exactly finite-sample optimal for the newly explicit survival-weighted average criterion Aξ\mathcal{A}_{\xi}, whose exact TSR identity is proved here, whereas for the Pollak- and Lorden-type criteria the finite-sample result at ξ≥2\xi\ge2 is an upper bound rather than an attainment claim. Furthermore, this work allows unknown, episode-specific durations subject only to δi≥ξ\delta_i \ge\xi, establishes structural and computational properties of the continuation boundary, provides complete proofs, and proves growing-window asymptotic minimax optimality for the simpler constant-boundary TSR rule.

The present formulation is related to, but distinct from, several other strands of change-detection research. Work on persistent changes with transient dynamics studies processes that pass through intermediate post-change regimes before settling permanently into a new state [11, 12, 13, 14]; in our model, each episode instead returns to the nominal distribution. A separate literature studies finite-duration or temporary changes under a variety of formulations, including Bayesian quickest detection of transient changes, detection in multiple on–off processes, sampling-constrained transient detection, and likelihood-ratio, cumulative-sum, finite-moving-average, and window-limited procedures [10, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]. Related models include temporary changes in multivariate time series, intermittent changes of unknown duration, unknown appearance and disappearance times, and detection or estimation of multiple transient periods [25, 26, 27, 28]. Our focus differs in the combination of an explicit probability-maximizing success window, an exactly optimized survival-weighted average criterion, Lorden- and Pollak-type minimax protection, an average-run-length false-alarm constraint, and asymptotic minimax guarantees for multiple transient opportunities.

The remainder of the paper is organized as follows. Section 2 introduces the observation model and the average and worst-case probability-maximizing formulations. Section 3 develops the two-sample case ξ=2\xi= 2 and establishes exact average optimality, and Section 4 extends the analysis to arbitrary ξ≥2\xi\ge2. Section 5 treats the one-sample case and recovers the classical Shewhart rule under both the average and minimax criteria. Section 6 discusses structural properties and computational implementation. Section 7 develops worst-case minimax guarantees and establishes asymptotic minimax optimality of a constant-boundary TSR procedure in a joint ARL–window regime. Numerical results are presented in Section 8, and concluding remarks are provided in Section 9.

Observation Model and Probability-Maximizing Formulation

Observation and Change-Episode Model

Throughout, let N≜{1,2,…}\mathbb{N} \triangleq\{1,2,\ldots\} and N0≜N∪{0}\mathbb{N}_0 \triangleq\mathbb{N} \cup\{0\}. Consider the discrete-time observation sequence X≜{Xt:t∈N}\mathcal{X} \triangleq\{X_t:t \in\mathbb{N}\}. Define its natural filtration {Ft:t∈N0}\{\mathcal{F}_t:t \in\mathbb{N}_0\} by

F0={∅,Ω},Ft=σ(X1,…,Xt),t∈N.(1)\mathcal{F}_0 = \{\varnothing,\Omega\}, \qquad\mathcal{F}_t = \sigma(X_1,\ldots,X_t), \quad t \in\mathbb{N}. \tag*{(1)}

For a fixed finite integer s≥1s \ge1, let

S≜{γi:i∈{1,…,s}}⊂N,1≤γ1<⋯<γs,(2)\mathcal{S} \triangleq\{\gamma_i:i \in\{1,\ldots,s\}\} \subset\mathbb{N}, \qquad1 \le\gamma_1 < \cdots< \gamma_s, \tag*{(2)}

denote the set of change-episode onset times. At each γi\gamma_i, the observation distribution changes from the nominal cumulative distribution function (cdf) F0F_0 to a distinct cdf F1F_1. Let δi∈N\delta_i \in\mathbb{N} denote the duration of the episode beginning at γi\gamma_i. The onset times and durations are unknown to the detector. For a prescribed admissible-window length ξ≥1\xi\ge1, we require only

δi≥ξ,i∈{1,…,s},(3)\delta_i \ge\xi, \qquad i \in\{1,\ldots,s\}, \tag*{(3)}

so that the entire ξ\xi-sample detection window following each onset is generated under F1F_1. The durations themselves need not be known; beyond the requirement δi≥ξ\delta_i \ge\xi, no common episode-duration parameter enters the formulation. The change episodes do not overlap and are separated by at least one nominal observation; equivalently, γi+1≥γi+δi+1\gamma_{i+1} \ge\gamma_i+\delta_i+1 for all i∈{1,…,s−1}i \in\{1,\ldots,s-1\}. Otherwise, two adjacent episodes can be merged and viewed as a single episode. Define the set of affected time indices as

U≜⋃i=1s{γi,γi+1,…,γi+δi−1}⊂N.(4)\mathcal{U} \triangleq\bigcup_{i=1}^{s}\{\gamma_i,\gamma_i+1,\ldots,\gamma_i+\delta_i-1\} \subset\mathbb{N}. \tag*{(4)}

We also admit the single persistent-change convention s=1s=1 and δ1=∞\delta_1=\infty, in which case U≜{t∈N:t≥γ1}\mathcal{U} \triangleq\{t \in\mathbb{N}:t \ge\gamma_1\}. Since the success event depends only on the first ξ\xi observations following the onset, all subsequent results apply under this convention without modification. The observations follow the dichotomous model

Xt∼F0,t∈N∖UXt∼F1,t∈U.(5)\begin{aligned} X_t &\sim F_0, && t \in\mathbb{N}\setminus\mathcal{U}\\ X_t &\sim F_1, && t \in\mathcal{U}. \tag*{(5)} \end{aligned}

Figure 1 illustrates a configuration with s=3s=3 episodes beginning at γ1=50\gamma_1=50, γ2=115\gamma_2=115, and γ3=190\gamma_3=190, with durations δ1=40\delta_1=40, δ2=35\delta_2=35, and δ3=60\delta_3=60, respectively. Conditioned on the change configuration (S,{δi:i∈{1,…,s}})(\mathcal{S},\{\delta_i:i \in\{1,\ldots,s\}\}), the observations are assumed independent and satisfy (5). Let μ\mu be a common dominating measure for F0F_0 and F1F_1, with densities f0f_0 and f1f_1, and assume F1≪F0F_1 \ll F_0 so that the likelihood ratio f1/f0f_1/f_0 is well defined. For each fixed ss, let Θs(ξ)\Theta_s(\xi) denote the class of configurations θ=(S,{δi}i=1s)\theta=(\mathcal{S},\{\delta_i\}_{i=1}^{s}) satisfying δi≥ξ\delta_i \ge\xi and γi+1≥γi+δi+1\gamma_{i+1} \ge\gamma_i+\delta_i+1. When s=1s=1, we augment Θ1(ξ)\Theta_1(\xi) with the persistent configuration δ1=∞\delta_1=\infty under the convention specified above. We denote the probability measure and expectation induced by θ\theta by Pθ\mathbb{P}_\theta and Eθ\mathbb{E}_\theta. The no-change measure and expectation are denoted by P∞\mathbb{P}_\infty and E∞\mathbb{E}_\infty. Although $s indexes the performance class Θs(ξ)\Theta_s(\xi), the onset times and durations are unknown, and the stopping rule derived below does not use them.

Figure 1. Illustration of multiple non-overlapping change episodes.

The assumptions above delimit the scope of the results. Knowledge of F0F_0 and F1F_1 permits exact evaluation of the one-step likelihood ratio f1(Xt)/f0(Xt)f_1(X_t)/f_0(X_t). In applications in which these distributions are estimated, a plug-in implementation does not generally retain the exact finite-sample guarantees unless model uncertainty is incorporated explicitly. Conditional independence permits the likelihood ratio for each candidate window to be factored into one-step likelihood ratios and yields a finite-dimensional, time-homogeneous Markov state under the no-change measure. For dependent observations, the probability-maximizing formulation remains applicable, but both the likelihood ratios and the sufficient state must account for the dependence structure, and the present analysis does not apply without modification. Finally, the condition δi≥ξ\delta_i \ge\xi ensures that every observation in an admissible window follows the post-change distribution; the duration δi\delta_i remains unknown and is not used by the stopping rule.

Admissible Detection Windows

A sequential decision rule is an {Ft}t∈N0\{\mathcal{F}_t\}_{t\in\mathbb{N}_0}-stopping time τ\tau taking values in N0\mathbb{N}_0. When a result explicitly permits randomization, an auxiliary random variable BB, independent of the observations, is made available at time zero, and the stopping time is understood with respect to the enlarged filtration {Ft∨σ(B)}t∈N0\{\mathcal{F}_t \vee\sigma(B)\}_{t\in\mathbb{N}_0}. For an episode beginning at γi\gamma_i, a decision is credited as successful when

γi≤τ<γi+ξ.(6)\gamma_i \le\tau< \gamma_i + \xi. \tag*{(6)}

Thus, the admissible window consists of the first ξ\xi observations generated under F1F_1 after that onset. All stopping instants within this window are treated equally. The stopping time itself is not truncated or forced to stop by γi+ξ\gamma_i + \xi; a decision outside the window is permitted but is not counted as a successful detection of that onset. This distinction separates the finite-window success criterion from a finite-horizon stopping problem. Hence, the formulation replaces the conventional ranking of post-change delays with a probability-maximizing objective: conditional on the procedure having survived until a change onset, it seeks to maximize the probability that the eventual stopping time lies in the associated admissible window. The behavior of an episode after its first ξ\xi post-change observations is immaterial to this success event. Consequently, the same formulation covers both finite-duration episodes with δi≥ξ\delta_i \ge\xi and persistent changes. In the next two subsections, we formalize minimax and average decision criteria.

References

  1. [1]A. N. Shiryaev, “On optimum methods in quickest detection problems,” Theory of Probability and Its Applications, vol. 8, no. 1, pp. 22–46, 1963.DOI
  2. [2]G. Lorden, “Procedures for reacting to a change in distribution,” The Annals of Mathematical Statistics, vol. 42, no. 6, pp. 1897–1908, Dec. 1971.DOI
  3. [3]M. Pollak, “Optimal detection of a change in distribution,” The Annals of Statistics, vol. 13, no. 1, pp. 206–227, Mar. 1985.DOI
  4. [4]T. Bojdecki, “Probability maximizing approach to optimal stopping and its application to a disorder problem,” Stochastics, vol. 3, no. 1, pp. 61–71, 1979.DOI
  5. [5]W. Sarnowski and K. Szajowski, “Optimal detection of transition probability change in random sequence,” Stochastics, vol. 83, no. 4-6, pp. 569–581, 2011.DOI
  6. [6]M. Pollak and A. M. Krieger, “Shewhart revisited,” Sequential Analysis, vol. 32, no. 2, pp. 230–242, 2013.DOI
  7. [7]G. V. Moustakides, “Multiple optimality properties of the shewhart test,” Sequential Analysis, vol. 33, no. 3, pp. 318–344, 2014.
  8. [8]——, “Optimum Shewhart tests for Markovian data,” in Proc. Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Sep. 2015, pp. 822–826.DOI
  9. [9]S. W. Roberts, “A comparison of some control chart procedures,” Technometrics, vol. 8, no. 3, pp. 411–430, 1966.
  10. [10]J. Heydari and A. Tajer, “Quickest search for a change point,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT), Paris, France, Jul. 2019, pp. 2194–2198.arxiv.org/abs/1804.09657
  11. [11]G. V. Moustakides and V. V. Veeravalli, “Sequentially detecting transitory changes,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, Jul. 2016, pp. 26–30.DOI
  12. [12]S. Zou, G. Fellouris, and V. V. Veeravalli, “Quickest change detection under transient dynamics: Theory and asymptotic analysis,” IEEE Transactions on Information Theory, vol. 65, no. 3, pp. 1397–1412, Mar. 2019.
  13. [13]V. Krishnamurthy, “Bayesian sequential detection with phase-distributed change time and nonlinear penalty—A POMDP lattice programming approach,” IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 7096–7124, Oct. 2011.DOI
  14. [14]——, “Quickest detection POMDPs with social learning: Interaction of local and global decision makers,” IEEE Transactions on Information Theory, vol. 58, no. 8, pp. 5563–5587, Aug. 2012.
  15. [15]K. Premkumar, A. Kumar, and V. V. Veeravalli, “Bayesian quickest transient change detection,” in Proceedings of the Fifth International Workshop on Applied Probability (IWAP), Madrid, Spain, Jul. 2010, pp. 1–3.
  16. [16]Q. Zhao and J. Ye, “Quickest detection in multiple on–off processes,” IEEE Transactions on Signal Processing, vol. 58, no. 12, pp. 5994–6006, Dec. 2010.DOI
  17. [17]B. K. Guépié, L. Fillatre, and I. Nikiforov, “Sequential detection of transient changes,” Sequential Analysis, vol. 31, no. 4, pp. 528–547, 2012.DOI
  18. [18]B. K. Guépié, L. Fillatre, and I. V. Nikiforov, “Detecting a suddenly arriving dynamic profile of finite duration,” IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 3039–3052, May 2017.DOI
  19. [19]E. Ebrahimzadeh and A. Tchamkerten, “Sequential detection of transient changes in stochastic systems under a sampling constraint,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, China, Jun. 2015, pp. 156–160.DOI
  20. [20]D. Egea-Roca, J. A. López-Salcedo, G. Seco-Granados, and H. V. Poor, “Performance bounds for finite moving average tests in transient change detection,” IEEE Transactions on Signal Processing, vol. 66, no. 6, pp. 1594–1606, Mar. 2018.
  21. [21]D. Egea-Roca, B. K. Guépié, J. A. López-Salcedo, G. Seco-Granados, and I. V. Nikiforov, “Two strategies in transient change detection,” IEEE Transactions on Signal Processing, vol. 70, pp. 1418–1433, 2022.
  22. [22]F. E. Mana, B. K. Guépié, and I. V. Nikiforov, “Centralized and decentralized strategies for sequential detection of transient changes,” IFAC-PapersOnLine, vol. 55, no. 6, pp. 360–365, 2022.DOI
  23. [23]——, “Sequential detection of an arbitrary transient change profile by the FMA test,” Sequential Analysis, vol. 42, no. 2, pp. 91–111, 2023.DOI
  24. [24]I. V. Nikiforov, “Sequential detection of an unknown transient change profile by the finite moving average test,” Sequential Analysis, vol. 44, no. 3, pp. 293–325, 2025.DOI
  25. [25]V. Watson, F. Septier, P. Armand, and C. Duchenne, “Sequential detection of a temporary change in multivariate time series,” Digital Signal Processing, vol. 127, p. 103545, 2022.arxiv.org/abs/2110.15935
  26. [26]G. Sokolov, V. S. Spivak, and A. G. Tartakovsky, “Detecting an intermittent change of unknown duration,” Sequential Analysis, vol. 42, no. 3, pp. 269–302, 2023.
  27. [27]A. G. Tartakovsky, N. R. Berenkov, A. E. Kolessa, and I. V. Nikiforov, “Optimal sequential detection of signals with unknown appearance and disappearance points in time,” IEEE Transactions on Signal Processing, vol. 69, pp. 2653–2662, 2021.DOI
  28. [28]M. Baron and S. V. Malov, “Detection and estimation of multiple transient changes,” Journal of Applied Statistics, vol. 50, no. 14, pp. 2862–2888, 2023.
  29. [29]V. Raghavan and V. V. Veeravalli, “Quickest change detection of a Markov process across a sensor array,” IEEE Transactions on Information Theory, vol. 56, no. 4, pp. 1961–1981, Apr. 2010.DOI
  30. [30]A. N. Shiryaev, Optimal Stopping Rules. Springer, Nov. 2007.

Paper details

vlnc:W_m33bwvya
Version
v1 · latest
Published
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents