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.
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 ξ = 1 is exactly the one-sample problem solved by Moustakides, whereas ξ ≥ 2 \xi\ge2 ξ ≥ 2 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 ξ ≥ 2 , we do not claim that these worst-case bounds are attained at finite ARL.
For ξ = 2 \xi= 2 ξ = 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 ξ − 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 ξ = 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 ξ = 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 ξ ≥ 2 . 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} A ξ , whose exact TSR identity is proved here, whereas for the Pollak- and Lorden-type criteria the finite-sample result at ξ ≥ 2 \xi\ge2 ξ ≥ 2 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 δ i ≥ ξ , 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 ξ = 2 and establishes exact average optimality, and Section 4 extends the analysis to arbitrary ξ ≥ 2 \xi\ge2 ξ ≥ 2 . 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 and Change-Episode Model
Throughout, let N ≜ { 1 , 2 , … } \mathbb{N} \triangleq\{1,2,\ldots\} N ≜ { 1 , 2 , … } and N 0 ≜ N ∪ { 0 } \mathbb{N}_0 \triangleq\mathbb{N} \cup\{0\} N 0 ≜ N ∪ { 0 } . Consider the discrete-time observation sequence X ≜ { X t : t ∈ N } \mathcal{X} \triangleq\{X_t:t \in\mathbb{N}\} X ≜ { X t : t ∈ N } . Define its natural filtration { F t : t ∈ N 0 } \{\mathcal{F}_t:t \in\mathbb{N}_0\} { F t : t ∈ N 0 } by
F 0 = { ∅ , Ω } , F t = σ ( X 1 , … , X t ) , 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)} F 0 = { ∅ , Ω } , F t = σ ( X 1 , … , X t ) , t ∈ N . (1)
For a fixed finite integer s ≥ 1 s \ge1 s ≥ 1 , 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)} S ≜ { γ i : i ∈ { 1 , … , s }} ⊂ N , 1 ≤ γ 1 < ⋯ < γ s , (2)
denote the set of change-episode onset times. At each γ i \gamma_i γ i , the observation distribution changes from the nominal cumulative distribution function (cdf) F 0 F_0 F 0 to a distinct cdf F 1 F_1 F 1 . Let δ i ∈ N \delta_i \in\mathbb{N} δ i ∈ N denote the duration of the episode beginning at γ i \gamma_i γ i . The onset times and durations are unknown to the detector. For a prescribed admissible-window length ξ ≥ 1 \xi\ge1 ξ ≥ 1 , we require only
δ i ≥ ξ , i ∈ { 1 , … , s } , (3) \delta_i \ge\xi, \qquad i \in\{1,\ldots,s\}, \tag*{(3)} δ i ≥ ξ , i ∈ { 1 , … , s } , (3)
so that the entire ξ \xi ξ -sample detection window following each onset is generated under F 1 F_1 F 1 . The durations themselves need not be known; beyond the requirement δ i ≥ ξ \delta_i \ge\xi δ i ≥ ξ , 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 γ i + 1 ≥ γ i + δ i + 1 for all i ∈ { 1 , … , s − 1 } i \in\{1,\ldots,s-1\} i ∈ { 1 , … , 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 = 1 s { γ 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)} U ≜ i = 1 ⋃ s { γ i , γ i + 1 , … , γ i + δ i − 1 } ⊂ N . (4)
We also admit the single persistent-change convention s = 1 s=1 s = 1 and δ 1 = ∞ \delta_1=\infty δ 1 = ∞ , in which case U ≜ { t ∈ N : t ≥ γ 1 } \mathcal{U} \triangleq\{t \in\mathbb{N}:t \ge\gamma_1\} U ≜ { t ∈ N : t ≥ γ 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
X t ∼ F 0 , t ∈ N ∖ U X t ∼ F 1 , 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} X t X t ∼ F 0 , ∼ F 1 , t ∈ N ∖ U t ∈ U . (5)
Figure 1 illustrates a configuration with s = 3 s=3 s = 3 episodes beginning at γ 1 = 50 \gamma_1=50 γ 1 = 50 , γ 2 = 115 \gamma_2=115 γ 2 = 115 , and γ 3 = 190 \gamma_3=190 γ 3 = 190 , with durations δ 1 = 40 \delta_1=40 δ 1 = 40 , δ 2 = 35 \delta_2=35 δ 2 = 35 , and δ 3 = 60 \delta_3=60 δ 3 = 60 , respectively. Conditioned on the change configuration ( S , { δ i : i ∈ { 1 , … , s } } ) (\mathcal{S},\{\delta_i:i \in\{1,\ldots,s\}\}) ( S , { δ i : i ∈ { 1 , … , s }}) , the observations are assumed independent and satisfy (5). Let μ \mu μ be a common dominating measure for F 0 F_0 F 0 and F 1 F_1 F 1 , with densities f 0 f_0 f 0 and f 1 f_1 f 1 , and assume F 1 ≪ F 0 F_1 \ll F_0 F 1 ≪ F 0 so that the likelihood ratio f 1 / f 0 f_1/f_0 f 1 / f 0 is well defined. For each fixed s s s , let Θ s ( ξ ) \Theta_s(\xi) Θ s ( ξ ) denote the class of configurations θ = ( S , { δ i } i = 1 s ) \theta=(\mathcal{S},\{\delta_i\}_{i=1}^{s}) θ = ( S , { δ i } i = 1 s ) satisfying δ i ≥ ξ \delta_i \ge\xi δ i ≥ ξ and γ i + 1 ≥ γ i + δ i + 1 \gamma_{i+1} \ge\gamma_i+\delta_i+1 γ i + 1 ≥ γ i + δ i + 1 . When s = 1 s=1 s = 1 , we augment Θ 1 ( ξ ) \Theta_1(\xi) Θ 1 ( ξ ) with the persistent configuration δ 1 = ∞ \delta_1=\infty δ 1 = ∞ under the convention specified above. We denote the probability measure and expectation induced by θ \theta θ by P θ \mathbb{P}_\theta P θ and E θ \mathbb{E}_\theta E θ . The no-change measure and expectation are denoted by P ∞ \mathbb{P}_\infty P ∞ and E ∞ \mathbb{E}_\infty E ∞ . Although $s indexes the performance class Θ s ( ξ ) \Theta_s(\xi) Θ s ( ξ ) , 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 F 0 F_0 F 0 and F 1 F_1 F 1 permits exact evaluation of the one-step likelihood ratio f 1 ( X t ) / f 0 ( X t ) f_1(X_t)/f_0(X_t) 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 δ i ≥ ξ ensures that every observation in an admissible window follows the post-change distribution; the duration δ i \delta_i δ i remains unknown and is not used by the stopping rule.
Admissible Detection Windows
A sequential decision rule is an { F t } t ∈ N 0 \{\mathcal{F}_t\}_{t\in\mathbb{N}_0} { F t } t ∈ N 0 -stopping time τ \tau τ taking values in N 0 \mathbb{N}_0 N 0 . When a result explicitly permits randomization, an auxiliary random variable B B B , independent of the observations, is made available at time zero, and the stopping time is understood with respect to the enlarged filtration { F t ∨ σ ( B ) } t ∈ N 0 \{\mathcal{F}_t \vee\sigma(B)\}_{t\in\mathbb{N}_0} { F t ∨ σ ( B ) } t ∈ N 0 . For an episode beginning at γ i \gamma_i γ i , a decision is credited as successful when
γ i ≤ τ < γ i + ξ . (6) \gamma_i \le\tau< \gamma_i + \xi. \tag*{(6)} γ i ≤ τ < γ i + ξ . (6)
Thus, the admissible window consists of the first ξ \xi ξ observations generated under F 1 F_1 F 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 γ i + ξ ; 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 δ i ≥ ξ and persistent changes. In the next two subsections, we formalize minimax and average decision criteria.
Note that the global stopping time remains an infinite-horizon random variable and may be arbitrarily large. The admissible window does not impose a deterministic deadline on τ \tau τ ; it defines the 0 0 0 –1 1 1 event that is credited as a successful response to a particular onset. This objective is distinct from expected-delay optimization in which a delay criterion ranks earlier post-change stops above later ones and continues to assign value to sufficiently late stops, whereas the present criterion treats all stops within the admissible window equally and assigns no credit outside it for that onset. In the multiple-episode model, missing one admissible window does not terminate monitoring, and the procedure may still stop successfully in the window of a later episode.
Pollak- and Lorden-Type Minimax Criteria
By adopting the approach in [7 ] , for each fixed s s s , we assess performance uniformly over the unknown configurations in Θ s ( ξ ) \Theta_s(\xi) Θ s ( ξ ) . The Pollak-type criterion is
L P ( τ ) ≜ inf θ ∈ Θ s ( ξ ) ∑ i = 1 s P θ ( γ i ≤ τ < γ i + ξ ∣ τ ≥ γ i ) . (7) \mathcal{L}_{\mathrm{P}}(\tau) \triangleq\inf_{\theta\in\Theta_s(\xi)} \sum_{i=1}^{s} \mathbb{P}_{\theta}\left(\gamma_i \le\tau< \gamma_i + \xi\mid\tau\ge\gamma_i\right). \tag*{(7)} L P ( τ ) ≜ θ ∈ Θ s ( ξ ) inf i = 1 ∑ s P θ ( γ i ≤ τ < γ i + ξ ∣ τ ≥ γ i ) . (7)
Each summand is the probability of stopping in the admissible window of episode i i i , conditioned on no alarm having occurred before its onset. Accordingly, the Pollak-type criterion averages over the pre-change histories compatible with survival to γ i \gamma_i γ i and then takes the least favorable admissible configuration.
The Lorden-type criterion strengthens this protection by also taking the essential infimum over the information available immediately before each onset:
L L ( τ ) ≜ inf θ ∈ Θ s ( ξ ) ∑ i = 1 s ess inf F γ i − 1 P θ ( γ i ≤ τ < γ i + ξ ∣ F γ i − 1 , τ ≥ γ i ) . (8) \mathcal{L}_{\mathrm{L}}(\tau) \triangleq\inf_{\theta\in\Theta_s(\xi)} \sum_{i=1}^{s} \operatorname*{ess\,inf}_{\mathcal{F}_{\gamma_i-1}} \mathbb{P}_{\theta}\left(\gamma_i \le\tau< \gamma_i + \xi\mid\mathcal{F}_{\gamma_i-1}, \tau\ge\gamma_i\right). \tag*{(8)} L L ( τ ) ≜ θ ∈ Θ s ( ξ ) inf i = 1 ∑ s F γ i − 1 ess inf P θ ( γ i ≤ τ < γ i + ξ ∣ F γ i − 1 , τ ≥ γ i ) . (8)
Thus, both criteria treat the onset locations as unknown and nonrandom, while the Lorden-type criterion additionally protects against the least favorable pre-change observation history. Directly from the definitions,
L L ( τ ) ≤ L P ( τ ) . (9) \mathcal{L}_{\mathrm{L}}(\tau) \le\mathcal{L}_{\mathrm{P}}(\tau). \tag*{(9)} L L ( τ ) ≤ L P ( τ ) . (9)
The quantities in (7) and (8) are aggregate episode-wise success scores: each term is a conditional probability, and the sum evaluates the detector across the s s s available opportunities. For fixed s s s , dividing either criterion by s s s gives the corresponding average conditional success probability and does not change the optimizing stopping rule. We retain the unnormalized sum because it leads to cleaner expressions in the optimality analysis that follows.
False alarms are controlled through the average run length (ARL) under the no-change measure, E ∞ [ τ ] \mathbb{E}_{\infty}[\tau] E ∞ [ τ ] . Let T \mathcal{T} T denote the resulting class of stopping times taking values in N 0 \mathbb{N}_0 N 0 , including the independently randomized extension described above when randomization is invoked. The Pollak-type optimization problem is
P P ( ε ) ≜ sup τ ∈ T L P ( τ ) s.t. E ∞ [ τ ] ≥ ε , (10) \mathcal{P}_{\mathrm{P}}(\varepsilon) \triangleq\sup_{\tau\in\mathcal{T}} \mathcal{L}_{\mathrm{P}}(\tau) \quad\text{s.t.} \quad\mathbb{E}_{\infty}[\tau] \ge\varepsilon, \tag*{(10)} P P ( ε ) ≜ τ ∈ T sup L P ( τ ) s.t. E ∞ [ τ ] ≥ ε , (10)
and the Lorden-type problem is
P L ( ε ) ≜ sup τ ∈ T L L ( τ ) s.t. E ∞ [ τ ] ≥ ε , (11) \mathcal{P}_{\mathrm{L}}(\varepsilon) \triangleq\sup_{\tau\in\mathcal{T}} \mathcal{L}_{\mathrm{L}}(\tau) \quad\text{s.t.} \quad\mathbb{E}_{\infty}[\tau] \ge\varepsilon, \tag*{(11)} P L ( ε ) ≜ τ ∈ T sup L L ( τ ) s.t. E ∞ [ τ ] ≥ ε , (11)
where ε ≥ 1 \varepsilon\ge1 ε ≥ 1 specifies the required ARL to false alarm.
Survival-weighted Average Success Criterion
Recall that T \mathcal{T} T denotes the class of stopping times, possibly randomized at time zero, taking values in N 0 \mathbb{N}_0 N 0 . For each γ ∈ N \gamma\in\mathbb{N} γ ∈ N , define P γ ξ \mathbb{P}^{\xi}_{\gamma} P γ ξ as an auxiliary local-change measure on F γ + ξ − 1 \mathcal{F}_{\gamma+\xi-1} F γ + ξ − 1 that coincides with P ∞ \mathbb{P}_{\infty} P ∞ on F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 and under which X γ , … , X γ + ξ − 1 X_{\gamma}, \ldots, X_{\gamma+\xi-1} X γ , … , X γ + ξ − 1 are independent with density f 1 f_1 f 1 . Equivalently, for each k ∈ { 1 , … , ξ } k \in\{1, \ldots, \xi\} k ∈ { 1 , … , ξ } ,
d P γ ξ d P ∞ ∣ F γ + k − 1 = ∏ j = 0 k − 1 ℓ γ + j . (12) \left.\frac{\mathrm{d}\mathbb{P}^{\xi}_{\gamma}}{\mathrm{d}\mathbb{P}_{\infty}}\right|_{\mathcal{F}_{\gamma+k-1}} = \prod_{j=0}^{k-1} \ell_{\gamma+j}. \tag*{(12)} d P ∞ d P γ ξ F γ + k − 1 = j = 0 ∏ k − 1 ℓ γ + j . (12)
No distributional specification beyond time γ + ξ − 1 \gamma+\xi-1 γ + ξ − 1 is needed, since the success event associated with onset γ \gamma γ is measurable with respect to F γ + ξ − 1 \mathcal{F}_{\gamma+\xi-1} F γ + ξ − 1 . For a stopping time τ \tau τ that has survived until γ \gamma γ , define the γ \gamma γ -specific conditional success probability
p γ ξ ( τ ) ≜ P γ ξ ( γ ≤ τ < γ + ξ ∣ τ ≥ γ ) , (13) p^{\xi}_{\gamma}(\tau) \triangleq\mathbb{P}^{\xi}_{\gamma}(\gamma\le\tau< \gamma+\xi\mid\tau\ge\gamma), \tag*{(13)} p γ ξ ( τ ) ≜ P γ ξ ( γ ≤ τ < γ + ξ ∣ τ ≥ γ ) , (13)
with the convention p γ ξ ( τ ) = 0 p^{\xi}_{\gamma}(\tau)=0 p γ ξ ( τ ) = 0 whenever P ∞ ( τ ≥ γ ) = 0 \mathbb{P}_{\infty}(\tau\ge\gamma)=0 P ∞ ( τ ≥ γ ) = 0 . For 0 < E ∞ [ τ ] < ∞ 0 < \mathbb{E}_{\infty}[\tau] < \infty 0 < E ∞ [ τ ] < ∞ , define the survival weights
w γ ( τ ) ≜ P ∞ ( τ ≥ γ ) E ∞ [ τ ] , γ ≥ 1. (14) w_{\gamma}(\tau) \triangleq\frac{\mathbb{P}_{\infty}(\tau\ge\gamma)}{\mathbb{E}_{\infty}[\tau]}, \qquad\gamma\ge1 . \tag*{(14)} w γ ( τ ) ≜ E ∞ [ τ ] P ∞ ( τ ≥ γ ) , γ ≥ 1. (14)
The weight w γ ( τ ) w_{\gamma}(\tau) w γ ( τ ) has a natural operational interpretation. Its numerator is the probability, under the no-change law, that the detector remains active through time γ \gamma γ , and hence that a change opportunity occurring at γ \gamma γ can still be acted upon. The normalization by E ∞ [ τ ] \mathbb{E}_{\infty}[\tau] E ∞ [ τ ] makes these survival probabilities sum to one. Equivalently, consider repeated independent monitoring cycles, with the detector restarted after each alarm, and select an active monitoring instant at random from the resulting long-run operation. Then w γ ( τ ) w_{\gamma}(\tau) w γ ( τ ) is the probability that the selected instant occupies position γ \gamma γ within its monitoring cycle. Thus, change opportunities at times that the detector reaches more frequently receive proportionally greater weight. The tail-sum identity implies w γ ( τ ) ≥ 0 w_{\gamma}(\tau) \ge0 w γ ( τ ) ≥ 0 and ∑ γ ≥ 1 w γ ( τ ) = 1 \sum_{\gamma\ge1} w_{\gamma}(\tau)=1 ∑ γ ≥ 1 w γ ( τ ) = 1 . Based on these, we define the survival-weighted average success probability
A ξ ( τ ) ≜ ∑ γ = 1 ∞ w γ ( τ ) p γ ξ ( τ ) . (15) \mathcal{A}_{\xi}(\tau) \triangleq\sum_{\gamma=1}^{\infty} w_{\gamma}(\tau) p^{\xi}_{\gamma}(\tau) . \tag*{(15)} A ξ ( τ ) ≜ γ = 1 ∑ ∞ w γ ( τ ) p γ ξ ( τ ) . (15)
Because it is a convex combination of conditional success probabilities, 0 ≤ A ξ ( τ ) ≤ 1 0 \le A_{\xi}(\tau) \le1 0 ≤ A ξ ( τ ) ≤ 1 . Note that under repeated operation with restart after each alarm, w γ ( τ ) w_{\gamma}(\tau) w γ ( τ ) is the long-run fraction of active monitoring instants that occupy position γ \gamma γ within a renewal cycle. Thus, A ξ ( τ ) A_{\xi}(\tau) A ξ ( τ ) is the average probability of successful detection per encountered change opportunity. The criterion A ξ A_{\xi} A ξ evaluates one randomly encountered opportunity. The general multiple-episode model is retained for the worst-case criteria below; without an explicit reset between episodes, we do not identify its finite-sample aggregate score with a simple multiple of A ξ A_{\xi} A ξ . The exact finite-sample problem studied in this paper is
P A ( ε , ξ ) ≜ sup τ ∈ T A ξ ( τ ) s.t. E ∞ [ τ ] ≥ ε . (16) \mathcal{P}_{A}(\varepsilon,\xi) \triangleq\sup_{\tau\in\mathcal{T}} A_{\xi}(\tau) \quad\text{s.t.} \quad\mathbb{E}_{\infty}[\tau] \ge\varepsilon. \tag*{(16)} P A ( ε , ξ ) ≜ τ ∈ T sup A ξ ( τ ) s.t. E ∞ [ τ ] ≥ ε . (16)
Truncated Shiryaev–Roberts Statistic
In this subsection, we formally define the truncated Shiryaev–Roberts statistic. We show that stopping rules induced by the TSR statistic enjoy two complementary optimality guarantees. Under the survival-weighted average success criterion, comparison with a state-dependent boundary yields exact finite-sample optimality. Under the Pollak- and Lorden-type probability-maximizing criteria, comparison with a constant boundary yields first-order asymptotic minimax optimality in the joint growing-ARL and growing-window regime specified in Section 7.
Definition 1 (TSR Statistic) Given the sequence of likelihood-ratio statistics { ℓ t : t ∈ N } \{\ell_t : t \in\mathbb{N}\} { ℓ t : t ∈ N } , for a given window length ξ ∈ N \xi\in\mathbb{N} ξ ∈ N , define the TSR statistic at time t t t as
W t ( ξ ) ≜ ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ t − j = ℓ t + ℓ t ℓ t − 1 + ℓ t ℓ t − 1 ℓ t − 2 + ⋯ + ∏ j = 0 ξ − 1 ℓ t − j . (17) W_t^{(\xi)} \triangleq\sum_{k=1}^{\xi} \prod_{j=0}^{k-1} \ell_{t-j} = \ell_t + \ell_t\ell_{t-1} + \ell_t\ell_{t-1}\ell_{t-2} + \cdots+ \prod_{j=0}^{\xi-1}\ell_{t-j}. \tag*{(17)} W t ( ξ ) ≜ k = 1 ∑ ξ j = 0 ∏ k − 1 ℓ t − j = ℓ t + ℓ t ℓ t − 1 + ℓ t ℓ t − 1 ℓ t − 2 + ⋯ + j = 0 ∏ ξ − 1 ℓ t − j . (17)
This statistic is the window-limited, or truncated, version of the classical Shiryaev–Roberts statistic. The corresponding TSR test is the stopping rule
T ( b t ) ≜ inf { t ≥ 1 : W t ( ξ ) ≥ b t } , (18) \mathcal{T}(b_t) \triangleq\inf\{t \ge1 : W_t^{(\xi)} \ge b_t\}, \tag*{(18)} T ( b t ) ≜ inf { t ≥ 1 : W t ( ξ ) ≥ b t } , (18)
where b t b_t b t is an F t \mathcal{F}_t F t -measurable boundary. In the optimal rule derived below, this boundary is state dependent rather than a fixed or deterministic time-varying threshold.
To show the connection to the Shiryaev–Roberts statistics, re-indexing the statistic gives
W t ( ξ ) = ∑ j = t − ξ + 1 t ∏ k = j t ℓ k , (19) W_t^{(\xi)} = \sum_{j=t-\xi+1}^{t} \prod_{k=j}^{t} \ell_k, \tag*{(19)} W t ( ξ ) = j = t − ξ + 1 ∑ t k = j ∏ t ℓ k , (19)
with the usual initialization convention near the beginning of the sequence. Hence, the statistic is exactly a window-limited, or truncated, version of the classical Shiryaev–Roberts statistic [1 , 9 ] . The distinction lies in the complete stopping rule: the classical Shiryaev–Roberts procedure uses a constant boundary, whereas exact optimality for the survival-weighted average probability-maximizing problem yields a state-dependent continuation boundary determined by the most recent ξ − 1 \xi- 1 ξ − 1 likelihood ratios. This statistic is also distinct from a windowed CuSum statistic, which takes the maximum over the likelihood ratios associated with the candidate onset locations; the TSR statistic sums those likelihood ratios because a stop at time t t t is successful under any one of the compatible onset locations.
When s = 1 s = 1 s = 1 and the episode persists indefinitely, the model reduces to a single persistent change with an admissible post-change window. When ξ = 1 \xi= 1 ξ = 1 , success requires stopping on the first post-change observation, and the average-optimal rule reduces to Shewhart. In this one-sample case, the established Pollak- and Lorden-type probability-maximizing formulations also admit Shewhart as an exact minimax solution. For ξ ≥ 2 \xi\ge2 ξ ≥ 2 , recent samples can jointly contribute to a successful stop, leading to the finite-memory TSR structure characterized. A formulation that assigns a decreasing reward to later stopping times inside the admissible window is also possible, but it defines a different objective from the equal-credit probability-maximizing criterion studied here.
Probability-maximizing Detection: Admissible Window ξ = 2 \xi= 2 ξ = 2
In this section, we characterize the stopping rule that is exactly optimal for the survival-weighted average success criterion A 2 A_2 A 2 . To simplify the exposition and highlight the main ideas, we begin with the special case ξ = 2 \xi= 2 ξ = 2 . In this setting, a decision is credited as successful for onset γ i \gamma_i γ i when the stopping time τ \tau τ satisfies γ i ≤ τ < γ i + 2 \gamma_i \le\tau< \gamma_i + 2 γ i ≤ τ < γ i + 2 , i.e., when it stops on either the first or the second post-change observation. The stopping rule itself is not truncated and may continue if it does not stop within that window. If this two-sample window is missed, monitoring continues; in the multiple-episode setting, the same rule may still stop successfully in the admissible window of a later episode. The multiple-episode model remains relevant to the Pollak- and Lorden-type worst-case criteria studied later; the exact finite-sample criterion optimized in this section concerns one randomly encountered change opportunity, as formalized by A 2 A_2 A 2 . We first establish the core results for this case and then extend the analysis to arbitrary values of ξ \xi ξ in Section 4. Finally, we treat the case ξ = 1 \xi= 1 ξ = 1 separately, as it leads to a qualitatively different structure of the optimal rule.
Throughout this section, the finite-sample optimization concerns the survival-weighted average criterion in (15). For the choice of ξ = 2 \xi= 2 ξ = 2 , we characterize the optimal decision rule, i.e., the solution to (16), in three steps:
we first derive an upper bound for the single-opportunity worst-case objective functions L P ( τ ) \mathcal{L}_{\mathrm{P}}(\tau) L P ( τ ) and L L ( τ ) \mathcal{L}_{\mathrm{L}}(\tau) L L ( τ ) and identify the ratio appearing in that bound with the exact average criterion A 2 ( τ ) A_2(\tau) A 2 ( τ ) ;
subsequently, we characterize a decision rule that maximizes the exact average criterion; and
we show that the stopping rule of step 2 is exactly optimal for A 2 A_2 A 2 under the ARL constraint.
Throughout the analysis, we denote the likelihood ratio of the sample collected at time t ∈ N t \in\mathbb{N} t ∈ N by ℓ t \ell_t ℓ t , i.e.,
ℓ t ≜ f 1 ( X t ) f 0 ( X t ) (20) \ell_t \triangleq\frac{f_1(X_t)}{f_0(X_t)} \tag*{(20)} ℓ t ≜ f 0 ( X t ) f 1 ( X t ) (20)
and adopt the convention ℓ 0 = 0 \ell_0 = 0 ℓ 0 = 0 . Before deriving the worst-case bounds, we establish a fundamental identity that connects the survival-weighted average success criterion to the TSR statistic. Although we state the identity for an arbitrary window length ξ \xi ξ , in this section we use its specialization to ξ = 2 \xi= 2 ξ = 2 .
Lemma 1 (Average-success identity) For every stopping time τ \tau τ satisfying 0 < E ∞ [ τ ] < ∞ 0 < \mathbb{E}_{\infty}[\tau] < \infty 0 < E ∞ [ τ ] < ∞ ,
A ξ ( τ ) = E ∞ [ W τ ( ξ ) ] E ∞ [ τ ] . (21) \mathcal{A}_{\xi}(\tau) = \frac{\mathbb{E}_{\infty}[W_{\tau}^{(\xi)}]}{\mathbb{E}_{\infty}[\tau]} . \tag*{(21)} A ξ ( τ ) = E ∞ [ τ ] E ∞ [ W τ ( ξ ) ] . (21)
Proof: See Appendix A.
For ξ = 2 \xi= 2 ξ = 2 , Lemma 1 specializes to
A 2 ( τ ) = E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] E ∞ [ τ ] . (22) \mathcal{A}_{2}(\tau) = \frac{\mathbb{E}_{\infty}[\ell_{\tau} + \ell_{\tau-1}\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]} . \tag*{(22)} A 2 ( τ ) = E ∞ [ τ ] E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] . (22)
We now derive an upper bound on the single-opportunity performance criteria L P ( τ ) \mathcal{L}_{P}(\tau) L P ( τ ) and L L ( τ ) \mathcal{L}_{L}(\tau) L L ( τ ) for ξ = 2 \xi= 2 ξ = 2 .
Theorem 1 (Upper Bound for ξ = 2 \xi= 2 ξ = 2 ) For any stopping time τ ∈ T \tau\in\mathcal{T} τ ∈ T satisfying 0 < E ∞ [ τ ] < ∞ 0 < \mathbb{E}_{\infty}[\tau] < \infty 0 < E ∞ [ τ ] < ∞ , and for any change set S S S with ∣ S ∣ = s |S| = s ∣ S ∣ = s , the performance criteria L P ( τ ) \mathcal{L}_{P}(\tau) L P ( τ ) and L L ( τ ) \mathcal{L}_{L}(\tau) L L ( τ ) , defined in (7) and (8), respectively, for ξ = 2 \xi= 2 ξ = 2 satisfy
L L ( τ ) ≤ L P ( τ ) ≤ s ⋅ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] E ∞ [ τ ] = s ⋅ A 2 ( τ ) . (23) \mathcal{L}_{L}(\tau) \le\mathcal{L}_{P}(\tau) \le s \cdot\frac{\mathbb{E}_{\infty}[\ell_{\tau} + \ell_{\tau-1}\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]} = s \cdot\mathcal{A}_{2}(\tau) . \tag*{(23)} L L ( τ ) ≤ L P ( τ ) ≤ s ⋅ E ∞ [ τ ] E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] = s ⋅ A 2 ( τ ) . (23)
Proof: See Appendix B for the worst-case inequalities. The final identity follows from Lemma 1.
The bound in Theorem 1 also has an information-theoretic converse interpretation. It applies to every admissible stopping rule and is independent of any particular detector construction; after imposing the ARL constraint, it therefore specifies a universal upper performance limit for the probability of successful finite-window detection. Furthermore, by Lemma 1, the upper bound is exactly the survival-weighted average success probability A 2 ( τ ) \mathcal{A}_{2}(\tau) A 2 ( τ ) . The remainder of the analysis constructs the TSR stopping rule and proves that it exactly maximizes this average criterion. We do not assert that the single-opportunity Pollak- or Lorden-type upper bound in (23) is attained at finite ϵ \epsilon ϵ for ξ = 2 \xi= 2 ξ = 2 . First, note that according to Lemma 1 we have
A 2 ( τ ) = E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] E ∞ [ τ ] . (24) \mathcal{A}_{2}(\tau) = \frac{\mathbb{E}_{\infty}[\ell_{\tau} + \ell_{\tau-1}\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]} . \tag*{(24)} A 2 ( τ ) = E ∞ [ τ ] E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] . (24)
In the next step, we seek the stopping time τ \tau τ that maximizes the exact average criterion in (24) subject to the false alarm constraint specified in (16). This leads to the optimization problem
Q ( ϵ ) ≜ sup τ ∈ T E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] E ∞ [ τ ] s.t. E ∞ [ τ ] ≥ ϵ . (25) Q(\epsilon) \triangleq\sup_{\tau\in\mathcal{T}} \frac{\mathbb{E}_{\infty}[\ell_{\tau} + \ell_{\tau-1}\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]}
\quad\text{s.t.} \quad\mathbb{E}_{\infty}[\tau] \ge\epsilon. \tag*{(25)} Q ( ϵ ) ≜ τ ∈ T sup E ∞ [ τ ] E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] s.t. E ∞ [ τ ] ≥ ϵ . (25)
By (24), Q ( ϵ ) Q(\epsilon) Q ( ϵ ) is precisely the optimal value of the survival-weighted average problem P A ( ϵ , 2 ) \mathcal{P}_{A}(\epsilon, 2) P A ( ϵ , 2 ) in (16). To solve Q ( ϵ ) Q(\epsilon) Q ( ϵ ) , we next show that the supremum over the inequality constraint can equivalently be achieved over stopping times satisfying the equality constraint. Specifically, for any feasible1 stopping time ν \nu ν with associated ratio
E ∞ [ ℓ ν + ℓ ν − 1 ℓ ν ] E ∞ [ ν ] , (26) \frac{\mathbb{E}_{\infty}[\ell_{\nu} + \ell_{\nu-1}\ell_{\nu}]}{\mathbb{E}_{\infty}[\nu]} , \tag*{(26)} E ∞ [ ν ] E ∞ [ ℓ ν + ℓ ν − 1 ℓ ν ] , (26)
there exists a (possibly randomized) stopping time ν ′ \nu' ν ′ satisfying
E ∞ [ ν ′ ] = ε , (27) \mathbb{E}_{\infty}[\nu'] = \varepsilon, \tag*{(27)} E ∞ [ ν ′ ] = ε , (27)
and
E ∞ [ ℓ ν ′ + ℓ ν ′ − 1 ℓ ν ′ ] E ∞ [ ν ′ ] = E ∞ [ ℓ ν + ℓ ν − 1 ℓ ν ] E ∞ [ ν ] . (28) \frac{\mathbb{E}_{\infty}[\ell_{\nu'}+\ell_{\nu'-1}\ell_{\nu'}]}{\mathbb{E}_{\infty}[\nu']} = \frac{\mathbb{E}_{\infty}[\ell_{\nu}+\ell_{\nu-1}\ell_{\nu}]}{\mathbb{E}_{\infty}[\nu]} . \tag*{(28)} E ∞ [ ν ′ ] E ∞ [ ℓ ν ′ + ℓ ν ′ − 1 ℓ ν ′ ] = E ∞ [ ν ] E ∞ [ ℓ ν + ℓ ν − 1 ℓ ν ] . (28)
This reduction is formalized in the following lemma, which incorporates the ARL to false alarm as an equality constraint.
Lemma 2 (Reducing the ARL constraint to equality) Fix ε ≥ 1 \varepsilon\ge1 ε ≥ 1 . For any feasible stopping time ν \nu ν satisfying E ∞ [ ν ] ≥ ε \mathbb{E}_{\infty}[\nu] \ge\varepsilon E ∞ [ ν ] ≥ ε , there exists a (possibly randomized) stopping time ν ′ \nu' ν ′ such that
E ∞ [ ν ′ ] = ε \mathbb{E}_{\infty}[\nu'] = \varepsilon E ∞ [ ν ′ ] = ε , i.e., the false alarm constraint is satisfied with equality; and
the performance ratio is preserved, namely
E ∞ [ ℓ ν ′ + ℓ ν ′ − 1 ℓ ν ′ ] E ∞ [ ν ′ ] = E ∞ [ ℓ ν + ℓ ν − 1 ℓ ν ] E ∞ [ ν ] . (29) \frac{\mathbb{E}_{\infty}[\ell_{\nu'}+\ell_{\nu'-1}\ell_{\nu'}]}{\mathbb{E}_{\infty}[\nu']} = \frac{\mathbb{E}_{\infty}[\ell_{\nu}+\ell_{\nu-1}\ell_{\nu}]}{\mathbb{E}_{\infty}[\nu]} . \tag*{(29)} E ∞ [ ν ′ ] E ∞ [ ℓ ν ′ + ℓ ν ′ − 1 ℓ ν ′ ] = E ∞ [ ν ] E ∞ [ ℓ ν + ℓ ν − 1 ℓ ν ] . (29)
Proof: See Appendix C.
Therefore, in solving Q ( ε ) \mathcal{Q}(\varepsilon) Q ( ε ) , the inequality constraint can be replaced by an equality constraint without loss of optimality. Consequently, it suffices to consider the equivalent problem
Q ~ ( ε ) ≜ sup τ ∈ T E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] E ∞ [ τ ] s.t. E ∞ [ τ ] = ε . (30) \widetilde{\mathcal{Q}}(\varepsilon) \triangleq\sup_{\tau\in\mathcal{T}} \frac{\mathbb{E}_{\infty}[\ell_{\tau}+\ell_{\tau-1}\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]}
\quad\text{s.t.} \quad\mathbb{E}_{\infty}[\tau] = \varepsilon. \tag*{(30)} Q ( ε ) ≜ τ ∈ T sup E ∞ [ τ ] E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] s.t. E ∞ [ τ ] = ε . (30)
The equality-constrained problem in (30) can, in turn, be reformulated as the following unconstrained Lagrangian problem:
V ( λ ) ≜ sup τ ∈ T E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ − λ τ ] , (31) \mathcal{V}(\lambda) \triangleq\sup_{\tau\in\mathcal{T}} \mathbb{E}_{\infty}[\ell_{\tau}+\ell_{\tau-1}\ell_{\tau}-\lambda\tau] , \tag*{(31)} V ( λ ) ≜ τ ∈ T sup E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ − λ τ ] , (31)
where λ > 0 \lambda> 0 λ > 0 is a Lagrange multiplier chosen so that the resulting optimizer satisfies E ∞ [ τ ] = ε \mathbb{E}_{\infty}[\tau] = \varepsilon E ∞ [ τ ] = ε . This equivalence is established formally in the following lemma.
Lemma 3 (Lagrangian equivalence of the ARL-equality problem) Fix ε ≥ 1 \varepsilon\ge1 ε ≥ 1 . For V ( λ ) \mathcal{V}(\lambda) V ( λ ) defined in (31), there exists λ ε > 0 \lambda_{\varepsilon} > 0 λ ε > 0 and a (possibly randomized) stopping time τ ⋆ ∈ T \tau^{\star} \in\mathcal{T} τ ⋆ ∈ T that attains V ( λ ε ) \mathcal{V}(\lambda_{\varepsilon}) V ( λ ε ) and satisfies
E ∞ [ τ ⋆ ] = ε , (32) \mathbb{E}_{\infty}[\tau^{\star}] = \varepsilon, \tag*{(32)} E ∞ [ τ ⋆ ] = ε , (32)
and consequently τ ⋆ \tau^{\star} τ ⋆ solves Q ~ ( ε ) \widetilde{\mathcal{Q}}(\varepsilon) Q ( ε ) .
Proof: See Appendix D.
We proceed by analyzing the Lagrangian problem V ( λ ) \mathcal{V}(\lambda) V ( λ ) . For t ∈ N t \in\mathbb{N} t ∈ N , define
W t ≜ ℓ t + ℓ t − 1 ℓ t , (33) W_t \triangleq\ell_t+\ell_{t-1}\ell_t, \tag*{(33)} W t ≜ ℓ t + ℓ t − 1 ℓ t , (33)
with the convention that W 0 = 0 W_0=0 W 0 = 0 . Further, define
T t ≜ { τ ∈ T : τ ≥ t a.s. } , (34) \mathcal{T}_t \triangleq\{\tau\in\mathcal{T}: \tau\ge t\ \text{a.s.}\}, \tag*{(34)} T t ≜ { τ ∈ T : τ ≥ t a.s. } , (34)
where T \mathcal{T} T denotes the class of stopping times, possibly randomized at time zero, that take values in N 0 \mathbb{N}_0 N 0 and satisfy P ∞ ( τ < ∞ ) = 1 \mathbb{P}_{\infty}(\tau< \infty)=1 P ∞ ( τ < ∞ ) = 1 . Given F t \mathcal{F}_t F t , define the infinite-horizon value function
J t ( F t ) ≜ ess sup τ ∈ T t E ∞ [ W τ − λ ( τ − t ) ∣ F t ] , (35) J_t(\mathcal{F}_t) \triangleq\operatorname{ess\,sup}_{\tau\in\mathcal{T}_t}\mathbb{E}_{\infty}\left[W_\tau-\lambda(\tau-t)\mid\mathcal{F}_t\right], \tag*{(35)} J t ( F t ) ≜ ess sup τ ∈ T t E ∞ [ W τ − λ ( τ − t ) ∣ F t ] , (35)
and the continuation value function;
R t ( F t ) ≜ E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] . (36) R_t(\mathcal{F}_t) \triangleq\mathbb{E}_{\infty}\left[J_{t+1}(\mathcal{F}_{t+1})\mid\mathcal{F}_t\right]. \tag*{(36)} R t ( F t ) ≜ E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] . (36)
The essential supremum in (35) is taken with respect to the almost-sure order over F t \mathcal{F}_t F t -measurable random variables and therefore is well defined. Furthermore, by definition of the essential supremum, for any τ ∈ T t \tau\in\mathcal{T}_t τ ∈ T t ,
J t ( F t ) ≥ E ∞ [ W τ − λ ( τ − t ) ∣ F t ] a.s. (37) J_t(\mathcal{F}_t) \ge\mathbb{E}_{\infty}\left[W_\tau-\lambda(\tau-t)\mid\mathcal{F}_t\right]\quad\text{a.s.} \tag*{(37)} J t ( F t ) ≥ E ∞ [ W τ − λ ( τ − t ) ∣ F t ] a.s. (37)
Using this property, we next establish the Bellman identity that relates J t ( F t ) J_t(\mathcal{F}_t) J t ( F t ) to the immediate reward W t W_t W t and the continuation value R t ( F t ) R_t(\mathcal{F}_t) R t ( F t ) . For notational simplicity, we henceforth write J t J_t J t and R t R_t R t in place of J t ( F t ) J_t(\mathcal{F}_t) J t ( F t ) and R t ( F t ) R_t(\mathcal{F}_t) R t ( F t ) , respectively.
Lemma 4 (Bellman identity for the infinite horizon) Fix λ > 0 \lambda> 0 λ > 0 . For every t ≥ 1 t \ge1 t ≥ 1 we almost surely have
J t ( F t ) = max { W t , − λ + R t } . (38) J_t(\mathcal{F}_t)=\max\{W_t,-\lambda+R_t\}. \tag*{(38)} J t ( F t ) = max { W t , − λ + R t } . (38)
Proof: See Appendix E.
The following lemma determines a stopping time that optimizes V ( λ ) \mathcal{V}(\lambda) V ( λ ) defined in (31), which we subsequently show solves the exact average-success problem in (25).
Lemma 5 The following stopping rule is an optimal solution to the optimization problem in (31).
τ λ ∗ ≜ inf { t ≥ 1 : ℓ t + ℓ t − 1 ℓ t ≥ − λ + R t } = T ( − λ + R t ) . (39) \tau_\lambda^* \triangleq\inf\{t \ge1:\ell_t+\ell_{t-1}\ell_t \ge-\lambda+R_t\}=\mathcal{T}(-\lambda+R_t). \tag*{(39)} τ λ ∗ ≜ inf { t ≥ 1 : ℓ t + ℓ t − 1 ℓ t ≥ − λ + R t } = T ( − λ + R t ) . (39)
Proof: See Appendix F.
Finally, we show that ℓ t − 1 \ell_{t-1} ℓ t − 1 and ℓ t \ell_t ℓ t are sufficient statistics for describing the terms J t J_t J t and R t R_t R t . This is formalized in the next lemma.
Lemma 6 (Sufficient statistics) There exist Borel functions J : [ 0 , ∞ ) 2 → R J:[0,\infty)^2\to\mathbb{R} J : [ 0 , ∞ ) 2 → R and R : [ 0 , ∞ ) → R R:[0,\infty)\to\mathbb{R} R : [ 0 , ∞ ) → R such that, almost surely,
J t ( F t ) = J ( ℓ t − 1 , ℓ t ) , and R t ( F t ) = R ( ℓ t ) . (40) J_t(\mathcal{F}_t)=J(\ell_{t-1},\ell_t),\qquad\text{and}\qquad R_t(\mathcal{F}_t)=R(\ell_t). \tag*{(40)} J t ( F t ) = J ( ℓ t − 1 , ℓ t ) , and R t ( F t ) = R ( ℓ t ) . (40)
In particular, ( ℓ t − 1 , ℓ t ) (\ell_{t-1},\ell_t) ( ℓ t − 1 , ℓ t ) is a sufficient statistic for J t J_t J t and ℓ t \ell_t ℓ t is a sufficient statistic for R t R_t R t .
Proof: See Appendix G.
Based on these properties, we have the following expressions for R R R and J J J , which are instrumental in specifying the optimal stopping time.
R ( ℓ t ) = E ∞ [ J ( ℓ t , ℓ t + 1 ) ∣ ℓ t ] , (41) R(\ell_t)=\mathbb{E}_{\infty}\left[J(\ell_t,\ell_{t+1})\mid\ell_t\right], \tag*{(41)} R ( ℓ t ) = E ∞ [ J ( ℓ t , ℓ t + 1 ) ∣ ℓ t ] , (41)
J ( ℓ t − 1 , ℓ t ) = max { ℓ t + ℓ t − 1 ℓ t , − λ + R ( ℓ t ) } . (42) J(\ell_{t-1},\ell_t)=\max\left\{\ell_t+\ell_{t-1}\ell_t,-\lambda+R(\ell_t)\right\}. \tag*{(42)} J ( ℓ t − 1 , ℓ t ) = max { ℓ t + ℓ t − 1 ℓ t , − λ + R ( ℓ t ) } . (42)
With these notations, the stopping time τ λ ⋆ \tau_{\lambda}^{\star} τ λ ⋆ defined in (39) can be restated as2
τ λ ⋆ = inf { t ≥ 1 : ℓ t + ℓ t − 1 ℓ t ≥ − λ + R ( ℓ t ) } . (43) \tau_{\lambda}^{\star}=\inf\left\{t\ge1:\ell_t+\ell_{t-1}\ell_t\ge-\lambda+R(\ell_t)\right\}. \tag*{(43)} τ λ ⋆ = inf { t ≥ 1 : ℓ t + ℓ t − 1 ℓ t ≥ − λ + R ( ℓ t ) } . (43)
Lemmas 1, 2, 3, and 5, collectively, establish that the stopping rule specified in (43) maximizes the exact survival-weighted average criterion A 2 \mathcal{A}_2 A 2 subject to the ARL constraint. After selecting λ = λ ε \lambda=\lambda_{\varepsilon} λ = λ ε so that E ∞ [ τ λ ε ⋆ ] = ε \mathbb{E}_{\infty}[\tau_{\lambda_{\varepsilon}}^{\star}]=\varepsilon E ∞ [ τ λ ε ⋆ ] = ε , define τ ⋆ ≜ τ λ ε ⋆ \tau^{\star}\triangleq\tau_{\lambda_{\varepsilon}}^{\star} τ ⋆ ≜ τ λ ε ⋆ . The following theorem formalizes the resulting exact average optimality.
Theorem 2 (TSR Average Optimality for ξ = 2 \xi=2 ξ = 2 ) For the stopping time τ ⋆ \tau^{\star} τ ⋆ defined in (43) with λ = λ ε \lambda=\lambda_{\varepsilon} λ = λ ε selected so that E ∞ [ τ ⋆ ] = ε \mathbb{E}_{\infty}[\tau^{\star}]=\varepsilon E ∞ [ τ ⋆ ] = ε , we have
A 2 ( τ ⋆ ) = E ∞ [ ℓ τ ⋆ + ℓ τ ⋆ − 1 ℓ τ ⋆ ] E ∞ [ τ ⋆ ] = sup τ : E ∞ [ τ ] ≥ ε A 2 ( τ ) . (44) \mathcal{A}_2(\tau^{\star})=\frac{\mathbb{E}_{\infty}[\ell_{\tau^{\star}}+\ell_{\tau^{\star}-1}\ell_{\tau^{\star}}]}{\mathbb{E}_{\infty}[\tau^{\star}]}=\sup_{\tau:\mathbb{E}_{\infty}[\tau]\ge\varepsilon}\mathcal{A}_2(\tau). \tag*{(44)} A 2 ( τ ⋆ ) = E ∞ [ τ ⋆ ] E ∞ [ ℓ τ ⋆ + ℓ τ ⋆ − 1 ℓ τ ⋆ ] = τ : E ∞ [ τ ] ≥ ε sup A 2 ( τ ) . (44)
Proof: Lemma 1 identifies A 2 ( τ ) \mathcal{A}_2(\tau) A 2 ( τ ) with the ratio in (25). Lemma 2 reduces the ARL inequality to equality without changing that ratio. Lemma 3 identifies a multiplier λ ε \lambda_{\varepsilon} λ ε whose Lagrangian optimizer has ARL ε \varepsilon ε , and Lemma 5 identifies that optimizer as the stopping rule in (43). These statements together prove (44). ■
Theorem 1 additionally implies
L L ( τ ⋆ ) ≤ L P ( τ ⋆ ) ≤ s ⋅ A 2 ( τ ⋆ ) . (45) \mathcal{L}_{L}(\tau^{\star})\le\mathcal{L}_{P}(\tau^{\star})\le s\cdot\mathcal{A}_2(\tau^{\star}). \tag*{(45)} L L ( τ ⋆ ) ≤ L P ( τ ⋆ ) ≤ s ⋅ A 2 ( τ ⋆ ) . (45)
This relation records the worst-case performance bound associated with the average-optimal rule, but no finite-sample equality or Pollak-/Lorden-optimality claim is made for $\xi=2.
Hence, the exact average-optimal test involves comparing ( ℓ t + ℓ t − 1 ℓ t ) (\ell_t+\ell_{t-1}\ell_t) ( ℓ t + ℓ t − 1 ℓ t ) with the state-dependent continuation boundary − λ + R ( ℓ t ) -\lambda+R(\ell_t) − λ + R ( ℓ t ) . Here λ = λ ε \lambda=\lambda_{\varepsilon} λ = λ ε is selected so that the ARL constraint E ∞ [ τ ⋆ ] = ε \mathbb{E}_{\infty}[\tau^{\star}]=\varepsilon E ∞ [ τ ⋆ ] = ε holds. The value of this boundary depends on the last likelihood ratio ℓ t \ell_t ℓ t . We discuss the computational aspect of finding R ( ℓ ) R(\ell) R ( ℓ ) in Section 6.
Probability-maximizing Detection: General Admissible Window ξ ≥ 2 \xi\ge2 ξ ≥ 2
In this section, we generalize the results of Section 3 to an arbitrary admissible detection-window length ξ ≥ 2 \xi\ge2 ξ ≥ 2 . The arguments follow the same line of reasoning as for ξ = 2 \xi=2 ξ = 2 . Therefore, we state the key definitions and results and omit the proofs for brevity. As in the two-sample case, the window determines whether a stop is credited as successful; it does not truncate the stopping rule. The exact finite-sample result generalized in this section is optimality with respect to the survival-weighted average success criterion A ξ A_\xi A ξ ; the Pollak-and Lorden-type criteria remain complementary worst-case measures and are related to A ξ A_\xi A ξ through the single-opportunity upper bound. For this purpose, at any time t t t we define
ℓ t ξ ≜ ( ℓ t − ξ + 1 , … , ℓ t ) ∈ [ 0 , ∞ ) ξ (46) \ell_t^\xi\triangleq(\ell_{t-\xi+1},\ldots,\ell_t) \in[0,\infty)^\xi \tag*{(46)} ℓ t ξ ≜ ( ℓ t − ξ + 1 , … , ℓ t ) ∈ [ 0 , ∞ ) ξ (46)
as the collection of the last ξ \xi ξ likelihood ratio terms up to time t t t . For notational convenience (and consistent with Section 3), we set ℓ 0 = 0 \ell_0=0 ℓ 0 = 0 and extend this convention by letting ℓ t = 0 \ell_t=0 ℓ t = 0 for all t ≤ 0 t\leq0 t ≤ 0 . We also define the ( ξ − 1 ) (\xi-1) ( ξ − 1 ) -lag vector
ℓ t − 1 ξ ≜ ( ℓ t − ξ + 2 , … , ℓ t ) ∈ [ 0 , ∞ ) ξ − 1 . (47) \ell_{t-1}^\xi\triangleq(\ell_{t-\xi+2},\ldots,\ell_t) \in[0,\infty)^{\xi-1}. \tag*{(47)} ℓ t − 1 ξ ≜ ( ℓ t − ξ + 2 , … , ℓ t ) ∈ [ 0 , ∞ ) ξ − 1 . (47)
Recall the TSR statistic at time t t t :
W t ( ξ ) = ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ t − j . (48) W_t^{(\xi)}=\sum_{k=1}^{\xi}\prod_{j=0}^{k-1}\ell_{t-j}. \tag*{(48)} W t ( ξ ) = k = 1 ∑ ξ j = 0 ∏ k − 1 ℓ t − j . (48)
By Lemma 1, for every stopping time satisfying 0 < E ∞ [ τ ] < ∞ 0<E_\infty[\tau]<\infty 0 < E ∞ [ τ ] < ∞ ,
A ξ ( τ ) = E ∞ [ W τ ( ξ ) ] E ∞ [ τ ] . (49) A_\xi(\tau)=\frac{E_\infty[W_\tau^{(\xi)}]}{E_\infty[\tau]}. \tag*{(49)} A ξ ( τ ) = E ∞ [ τ ] E ∞ [ W τ ( ξ ) ] . (49)
Furthermore, the reduction of the ARL inequality to equality and the Lagrangian equivalence arguments in Lemmas 2 and 3 extend directly after replacing W t ( 2 ) W_t^{(2)} W t ( 2 ) by W t ( ξ ) W_t^{(\xi)} W t ( ξ ) . In the first step, we define the following unconstrained Lagrangian problem that generalizes (31) from the two-sample case to an arbitrary window length ξ ≥ 2 \xi\geq2 ξ ≥ 2 :
V ξ ( λ ) ≜ sup τ ∈ T E ∞ [ W τ ( ξ ) − λ τ ] . (50) \mathcal{V}_\xi(\lambda)\triangleq\sup_{\tau\in\mathcal{T}}E_\infty\left[W_\tau^{(\xi)}-\lambda\tau\right]. \tag*{(50)} V ξ ( λ ) ≜ τ ∈ T sup E ∞ [ W τ ( ξ ) − λ τ ] . (50)
Here, T \mathcal{T} T denotes the class of stopping times, possibly randomized at time zero, with values in N 0 \mathbb{N}_0 N 0 . Similarly to Section 3, define for t ∈ N t\in\mathbb{N} t ∈ N the truncated class
T t ≜ { τ ∈ T : τ ≥ t a.s. } , (51) \mathcal{T}_t\triangleq\{\tau\in\mathcal{T}:\tau\geq t\ \text{a.s.}\}, \tag*{(51)} T t ≜ { τ ∈ T : τ ≥ t a.s. } , (51)
and the value and continuation functions
J t ξ ( F t ) ≜ ess sup τ ∈ T t E ∞ [ W τ ( ξ ) − λ ( τ − t ) ∣ F t ] , (52) J_t^\xi(\mathcal{F}_t)\triangleq\operatorname*{ess\,sup}_{\tau\in\mathcal{T}_t}E_\infty\left[W_\tau^{(\xi)}-\lambda(\tau-t)\mid\mathcal{F}_t\right], \tag*{(52)} J t ξ ( F t ) ≜ τ ∈ T t ess sup E ∞ [ W τ ( ξ ) − λ ( τ − t ) ∣ F t ] , (52)
and
R t ξ ( F t ) ≜ E ∞ [ J t + 1 ξ ( F t + 1 ) ∣ F t ] . (53) R_t^\xi(\mathcal{F}_t)\triangleq E_\infty\left[J_{t+1}^\xi(\mathcal{F}_{t+1})\mid\mathcal{F}_t\right]. \tag*{(53)} R t ξ ( F t ) ≜ E ∞ [ J t + 1 ξ ( F t + 1 ) ∣ F t ] . (53)
In particular, the Bellman identity takes the form
J t ξ ( F t ) = max { W t ( ξ ) , − λ + R t ξ ( F t ) } . (54) J_t^\xi(\mathcal{F}_t)=\max\left\{W_t^{(\xi)},-\lambda+R_t^\xi(\mathcal{F}_t)\right\}. \tag*{(54)} J t ξ ( F t ) = max { W t ( ξ ) , − λ + R t ξ ( F t ) } . (54)
Similar to the case of ξ = 2 \xi=2 ξ = 2 , we first show that the problem at hand is a Markov optimal stopping problem.
Lemma 7 (Sufficient Statistic) Fix ξ ≥ 2 \xi\ge2 ξ ≥ 2 and λ > 0 \lambda> 0 λ > 0 . There exist Borel functions
J ξ : [ 0 , ∞ ) ξ → R and R ξ : [ 0 , ∞ ) ξ − 1 → R , (55) J_{\xi} : [0,\infty)^{\xi} \to\mathbb{R} \qquad\text{and} \qquad R_{\xi} : [0,\infty)^{\xi-1} \to\mathbb{R}, \tag*{(55)} J ξ : [ 0 , ∞ ) ξ → R and R ξ : [ 0 , ∞ ) ξ − 1 → R , (55)
such that, almost surely, for all t ∈ N t \in\mathbb{N} t ∈ N
J t ξ ( F t ) = J ξ ( ℓ t ξ ) , R t ξ ( F t ) = R ξ ( ℓ t − 1 ξ ) . (56) J_{t}^{\xi}(\mathcal{F}_{t}) = J_{\xi}(\ell_{t}^{\xi}), \qquad R_{t}^{\xi}(\mathcal{F}_{t}) = R_{\xi}(\ell_{t-1}^{\xi}). \tag*{(56)} J t ξ ( F t ) = J ξ ( ℓ t ξ ) , R t ξ ( F t ) = R ξ ( ℓ t − 1 ξ ) . (56)
In particular, ℓ t ξ \ell_{t}^{\xi} ℓ t ξ is a sufficient statistic for J t ξ J_{t}^{\xi} J t ξ and ℓ t − 1 ξ \ell_{t-1}^{\xi} ℓ t − 1 ξ is a sufficient statistic for R t ξ R_{t}^{\xi} R t ξ .
Proof. The proof arguments parallel those of the proof of Lemma 6.
Based on Lemma 7, we therefore write
J t ξ = J ξ ( ℓ t ξ ) and R t ξ = R ξ ( ℓ t − 1 ξ ) . (57) J_{t}^{\xi} = J_{\xi}(\ell_{t}^{\xi}) \qquad\text{and} \qquad R_{t}^{\xi} = R_{\xi}(\ell_{t-1}^{\xi}). \tag*{(57)} J t ξ = J ξ ( ℓ t ξ ) and R t ξ = R ξ ( ℓ t − 1 ξ ) . (57)
With these definitions, the extension of the ξ = 2 \xi= 2 ξ = 2 results to general ξ \xi ξ is summarized next.
Theorem 3 (TSR Test for general ξ \xi ξ ) For any integer ξ ≥ 2 \xi\ge2 ξ ≥ 2 , the following statements are true.
Worst-case upper bound and exact average identity: For any stopping time τ ∈ T \tau\in\mathcal{T} τ ∈ T satisfying 0 < E ∞ [ τ ] < ∞ 0 < \mathbb{E}_{\infty}[\tau] < \infty 0 < E ∞ [ τ ] < ∞ , the Pollak- and Lorden-type criteria satisfy
L L ( τ ) ≤ L P ( τ ) ≤ s ⋅ A ξ ( τ ) = s ⋅ E ∞ [ W τ ( ξ ) ] E ∞ [ τ ] = s ⋅ E ∞ [ ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ τ − j ] E ∞ [ τ ] . (58) \mathcal{L}_{\mathrm{L}}(\tau) \le\mathcal{L}_{\mathrm{P}}(\tau) \le s \cdot\mathcal{A}_{\xi}(\tau) = s \cdot\frac{\mathbb{E}_{\infty}\left[W_{\tau}^{(\xi)}\right]}{\mathbb{E}_{\infty}[\tau]} = s \cdot\frac{\mathbb{E}_{\infty}\left[\sum_{k=1}^{\xi}\prod_{j=0}^{k-1}\ell_{\tau-j}\right]}{\mathbb{E}_{\infty}[\tau]}. \tag*{(58)} L L ( τ ) ≤ L P ( τ ) ≤ s ⋅ A ξ ( τ ) = s ⋅ E ∞ [ τ ] E ∞ [ W τ ( ξ ) ] = s ⋅ E ∞ [ τ ] E ∞ [ ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ τ − j ] . (58)
Stopping rule maximizing the exact average criterion: Let λ > 0 \lambda> 0 λ > 0 and let R ξ R_{\xi} R ξ be as in Lemma 7. The stopping time
τ λ , ξ ⋆ ≜ inf { t ≥ 1 : W t ( ξ ) ≥ − λ + R ξ ( ℓ t − 1 ξ ) } = T ( − λ + R ξ ( ℓ t − 1 ξ ) ) (59) \tau_{\lambda,\xi}^{\star} \triangleq\inf\left\{t \ge1 : W_{t}^{(\xi)} \ge-\lambda+ R_{\xi}(\ell_{t-1}^{\xi})\right\} = \mathcal{T}\left(-\lambda+ R_{\xi}(\ell_{t-1}^{\xi})\right) \tag*{(59)} τ λ , ξ ⋆ ≜ inf { t ≥ 1 : W t ( ξ ) ≥ − λ + R ξ ( ℓ t − 1 ξ ) } = T ( − λ + R ξ ( ℓ t − 1 ξ ) ) (59)
maximizes the Lagrangian in (50). After choosing λ = λ ε \lambda= \lambda_{\varepsilon} λ = λ ε so that
E ∞ [ τ λ ε , ξ ⋆ ] = ε , (60) \mathbb{E}_{\infty}\left[\tau_{\lambda_{\varepsilon},\xi}^{\star}\right] = \varepsilon, \tag*{(60)} E ∞ [ τ λ ε , ξ ⋆ ] = ε , (60)
the resulting stopping rule solves the exact average-success problem P A ( ε , ξ ) \mathrm{P}_{\mathrm{A}}(\varepsilon,\xi) P A ( ε , ξ ) in (16).
Exact average optimality: For τ ξ ⋆ ≜ τ λ ε , ξ ⋆ \tau_{\xi}^{\star} \triangleq\tau_{\lambda_{\varepsilon},\xi}^{\star} τ ξ ⋆ ≜ τ λ ε , ξ ⋆ we have
A ξ ( τ ξ ⋆ ) = E ∞ [ W τ ξ ⋆ ( ξ ) ] E ∞ [ τ ξ ⋆ ] = E ∞ [ ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ τ ξ ⋆ − j ] E ∞ [ τ ξ ⋆ ] = sup τ ∈ T : ε ≤ E ∞ [ τ ] < ∞ A ξ ( τ ) . (61) \mathcal{A}_{\xi}(\tau_{\xi}^{\star}) = \frac{\mathbb{E}_{\infty}\left[W_{\tau_{\xi}^{\star}}^{(\xi)}\right]}{\mathbb{E}_{\infty}[\tau_{\xi}^{\star}]} = \frac{\mathbb{E}_{\infty}\left[\sum_{k=1}^{\xi}\prod_{j=0}^{k-1}\ell_{\tau_{\xi}^{\star}-j}\right]}{\mathbb{E}_{\infty}[\tau_{\xi}^{\star}]} = \sup_{\substack{\tau\in\mathcal{T}:\\ \varepsilon\le\mathbb{E}_{\infty}[\tau] < \infty}} \mathcal{A}_{\xi}(\tau). \tag*{(61)} A ξ ( τ ξ ⋆ ) = E ∞ [ τ ξ ⋆ ] E ∞ [ W τ ξ ⋆ ( ξ ) ] = E ∞ [ τ ξ ⋆ ] E ∞ [ ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ τ ξ ⋆ − j ] = τ ∈ T : ε ≤ E ∞ [ τ ] < ∞ sup A ξ ( τ ) . (61)
Hence, following the same line of arguments as in Section 3, the statements of Theorem 3 collectively establish that the stopping rule specified in (59) is an exactly optimal solution to (16) for every $\xi \ge 2. For the single-opportunity worst-case criteria, the same theorem yields
L L ( τ ξ ⋆ ) ≤ L P ( τ ξ ⋆ ) ≤ s ⋅ A ξ ( τ ξ ⋆ ) . (62) \mathcal{L}_{\mathrm{L}}(\tau_{\xi}^{\star}) \le\mathcal{L}_{\mathrm{P}}(\tau_{\xi}^{\star}) \le s \cdot\mathcal{A}_{\xi}(\tau_{\xi}^{\star}). \tag*{(62)} L L ( τ ξ ⋆ ) ≤ L P ( τ ξ ⋆ ) ≤ s ⋅ A ξ ( τ ξ ⋆ ) . (62)
In particular, the exact average-optimal test compares the statistic W t ( ξ ) W_t^{(\xi)} W t ( ξ ) , which is a function of the most recent ξ \xi ξ likelihood ratios ℓ ξ t \ell_\xi^t ℓ ξ t , with the state-dependent continuation boundary
− λ + R ξ ( ℓ ξ − 1 t ) . (63) -\lambda+ R_\xi(\ell_{\xi-1}^t). \tag*{(63)} − λ + R ξ ( ℓ ξ − 1 t ) . (63)
The boundary depends on the most recent ξ − 1 \xi-1 ξ − 1 likelihood ratios through ℓ ξ − 1 t \ell_{\xi-1}^t ℓ ξ − 1 t . We discuss the computational aspect of finding R ξ ( ⋅ ) R_\xi(\cdot) R ξ ( ⋅ ) in Section 6.
Probability-maximizing Detection: Admissible Window ξ = 1 \xi= 1 ξ = 1
In this section, we treat the case of ξ = 1 \xi= 1 ξ = 1 , i.e., the one-sample admissible-window setting. Since
{ γ i ≤ τ < γ i + 1 } = { τ = γ i } , (64) \{\gamma_i \le\tau< \gamma_i + 1\} = \{\tau= \gamma_i\}, \tag*{(64)} { γ i ≤ τ < γ i + 1 } = { τ = γ i } , (64)
a decision is credited as successful for onset γ i \gamma_i γ i only when τ = γ i \tau= \gamma_i τ = γ i . This setting is treated independently since the analysis has important differences, and it provides the one-sample benchmark from which the general TSR rule is extended. The optimal test simplifies to the well-known Shewhart test, recovering the exact solution established for the one-sample probability-maximizing minimax problem in [7 ] .
We note that although the resulting Shewhart rule uses only the current observation, this is a conclusion of a sequential optimization problem rather than a reduction to an isolated hypothesis test. The onset time is unknown, observations arrive successively, and at every time the detector chooses between stopping and preserving the opportunity to act later. These decisions are coupled through the ARL constraint, and the optimization ranges over all admissible stopping times, including rules that use the complete observation history. Shewhart optimality therefore establishes that past samples have no value for the one-sample probability-maximizing objective; when ξ > 1 \xi> 1 ξ > 1 , the optimal rule instead acquires the finite memory characterized in Sections 3 and 4.
In this one-sample case, the survival-weighted average criterion and the established Pollak- and Lorden-type minimax criteria are optimized by the same rule. Thus, unlike the setting ξ ≥ 2 \xi\ge2 ξ ≥ 2 , the distinction between exact finite-sample average optimality and worst-case minimax optimality disappears when ξ = 1 \xi= 1 ξ = 1 . Specifically, in this setting, the optimal test involves a one-sample likelihood-ratio test. Formally, at each time t t t and based on the observation X t X_t X t , we form the likelihood-ratio value ℓ t \ell_t ℓ t defined in (20) . The Shewhart test compares ℓ t \ell_t ℓ t with a fixed threshold α \alpha α and declares a change when ℓ t \ell_t ℓ t exceeds α \alpha α . The main difference between the optimal test in the settings ξ = 1 \xi= 1 ξ = 1 and ξ ≥ 2 \xi\ge2 ξ ≥ 2 is that, when ξ = 1 \xi= 1 ξ = 1 , the optimal test compares the most recent likelihood ratio with a time-invariant threshold, i.e., it is the Shewhart test. When ξ ≥ 2 \xi\ge2 ξ ≥ 2 , the optimal test instead compares a function of the most recent ξ \xi ξ likelihood ratios with a state-dependent continuation boundary that depends on the most recent ( ξ − 1 ) (\xi- 1) ( ξ − 1 ) likelihood ratios. The stopping time of the Shewhart test is
τ S ≜ inf { t ≥ 1 : ℓ t ≥ α } = T ( α ) . (65) \tau_{\mathrm{S}} \triangleq\inf\{t \ge1 : \ell_t \ge\alpha\} = \mathcal{T}(\alpha). \tag*{(65)} τ S ≜ inf { t ≥ 1 : ℓ t ≥ α } = T ( α ) . (65)
The value of the threshold α \alpha α is chosen such that the average run length to a false alarm is guaranteed not to be smaller than ε \varepsilon ε , i.e., E ∞ [ τ s ] ≥ ε \mathbb{E}_{\infty}[\tau_s] \ge\varepsilon E ∞ [ τ s ] ≥ ε . Under P ∞ \mathbb{P}_{\infty} P ∞ , { ℓ t } t ∈ N \{\ell_t\}_{t\in\mathbb{N}} { ℓ t } t ∈ N are i.i.d., so τ s \tau_s τ s is geometric with parameter P ∞ ( ℓ 1 ≥ α ) \mathbb{P}_{\infty}(\ell_1 \ge\alpha) P ∞ ( ℓ 1 ≥ α ) , and hence
E ∞ [ τ s ] = 1 P ∞ ( ℓ 1 ≥ α ) . (66) \mathbb{E}_{\infty}[\tau_s] = \frac{1}{\mathbb{P}_{\infty}(\ell_1 \ge\alpha)}. \tag*{(66)} E ∞ [ τ s ] = P ∞ ( ℓ 1 ≥ α ) 1 . (66)
Accordingly, a convenient choice is to enforce the ARL constraint with equality, and α \alpha α can be computed by solving
P ∞ ( ℓ 1 ≥ α ) = ε − 1 . (67) \mathbb{P}_{\infty}(\ell_1 \ge\alpha) = \varepsilon^{-1}. \tag*{(67)} P ∞ ( ℓ 1 ≥ α ) = ε − 1 . (67)
Relationship in (67) assumes that the desired probability can be attained by a deterministic threshold. If the distribution of ℓ 1 \ell_1 ℓ 1 under P ∞ \mathbb{P}_{\infty} P ∞ has an atom at the threshold, the Shewhart rule may instead randomize on the event { ℓ 1 = α } \{\ell_1 = \alpha\} { ℓ 1 = α } so that its one-step stopping probability is exactly ε − 1 \varepsilon^{-1} ε − 1 . For notational simplicity, we use the deterministic form below. Since W t ( 1 ) = ℓ t W_t^{(1)} = \ell_t W t ( 1 ) = ℓ t , Lemma 1 yields
A 1 ( τ ) = E ∞ [ ℓ τ ] E ∞ [ τ ] . (68) \mathcal{A}_1(\tau) = \frac{\mathbb{E}_{\infty}[\ell_\tau]}{\mathbb{E}_{\infty}[\tau]}. \tag*{(68)} A 1 ( τ ) = E ∞ [ τ ] E ∞ [ ℓ τ ] . (68)
An argument analogous to the one used to obtain Theorem 1 yields the following ξ = 1 \xi= 1 ξ = 1 upper bound: for any fixed s ≥ 1 s \ge1 s ≥ 1 and any τ ∈ T \tau\in\mathcal{T} τ ∈ T with 0 < E ∞ [ τ ] < ∞ 0 < \mathbb{E}_{\infty}[\tau] < \infty 0 < E ∞ [ τ ] < ∞ ,
L L ( τ ) ≤ L P ( τ ) ≤ s ⋅ E ∞ [ ℓ τ ] E ∞ [ τ ] = s A 1 ( τ ) . (69) \mathcal{L}_{L}(\tau) \le\mathcal{L}_{P}(\tau) \le s \cdot\frac{\mathbb{E}_{\infty}[\ell_\tau]}{\mathbb{E}_{\infty}[\tau]} = s\mathcal{A}_1(\tau). \tag*{(69)} L L ( τ ) ≤ L P ( τ ) ≤ s ⋅ E ∞ [ τ ] E ∞ [ ℓ τ ] = s A 1 ( τ ) . (69)
In this section, we establish the optimality of the Shewhart test formalized in (65) and (67) for the average-success problem in (16), as well as for the problems in (10) and (11). We leverage Lemma 2 and prove the following properties:
The Shewhart test is feasible.
It maximizes A 1 ( τ ) \mathcal{A}_1(\tau) A 1 ( τ ) and, equivalently, the upper bound on L P ( τ ) \mathcal{L}_{P}(\tau) L P ( τ ) and L L ( τ ) \mathcal{L}_{L}(\tau) L L ( τ ) in (69), subject to the false-alarm constraint.
For the Shewhart test, the performance criteria L P ( τ ) \mathcal{L}_{P}(\tau) L P ( τ ) and L L ( τ ) \mathcal{L}_{L}(\tau) L L ( τ ) attain the maximized upper bound, so the rule is simultaneously exact average-optimal and exact minimax-optimal.
These properties are formalized in the following lemma and two theorems.
Lemma 8 (Feasibility of Shewhart) The Shewhart stopping time τ s \tau_s τ s with threshold α \alpha α chosen according to (67) satisfies E ∞ [ τ s ] = ε \mathbb{E}_{\infty}[\tau_s] = \varepsilon E ∞ [ τ s ] = ε , and hence is feasible for (16) and for (10)–(11).
Proof: See Appendix H.
In the next theorem, we establish that the Shewhart test maximizes the upper bound in (69), which is exactly the average criterion up to the factor s s s .
Theorem 4 The Shewhart test is a solution to
sup τ ∈ T E ∞ [ ℓ τ ] E ∞ [ τ ] s.t. E ∞ [ τ ] = ε . (70) \sup_{\tau\in\mathcal{T}} \frac{\mathbb{E}_{\infty}[\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]} \quad\text{s.t.} \quad\mathbb{E}_{\infty}[\tau] = \varepsilon. \tag*{(70)} τ ∈ T sup E ∞ [ τ ] E ∞ [ ℓ τ ] s.t. E ∞ [ τ ] = ε . (70)
Equivalently, it solves
sup τ ∈ T A 1 ( τ ) s.t. E ∞ [ τ ] = ε . (71) \sup_{\tau\in\mathcal{T}} \mathcal{A}_1(\tau) \quad\text{s.t.} \quad\mathbb{E}_{\infty}[\tau] = \varepsilon. \tag*{(71)} τ ∈ T sup A 1 ( τ ) s.t. E ∞ [ τ ] = ε . (71)
Proof. See Appendix K.
The following theorem proves that, for the Shewhart test, the performance criteria attain their common upper bound and, consequently, that the Shewhart test is an optimal solution to the average-success problem (16) and to (10) and (11) for ξ = 1 \xi= 1 ξ = 1 .
Theorem 5 (Optimality of Shewhart for ξ = 1 \xi= 1 ξ = 1 ) Fix s ≥ 1 s \ge1 s ≥ 1 and take the infima defining L P \mathcal{L}_{P} L P and L L \mathcal{L}_{L} L L over Θ s ( 1 ) \Theta_s(1) Θ s ( 1 ) . The Shewhart test with the stopping time and threshold given in (65) and (67) , respectively, is an optimal solution to the survival-weighted average problem and to both problems in (10) and (11) , i.e.,
A 1 ( τ s ) = sup τ ∈ T : E ∞ [ τ ] ≥ ε A 1 ( τ ) (72) \mathcal{A}_1(\tau_s) = \sup_{\tau\in\mathcal{T}: \mathbb{E}_{\infty}[\tau] \ge\varepsilon} \mathcal{A}_1(\tau) \tag*{(72)} A 1 ( τ s ) = τ ∈ T : E ∞ [ τ ] ≥ ε sup A 1 ( τ ) (72)
L L ( τ s ) = L P ( τ s ) = s A 1 ( τ s ) = sup τ ∈ T : E ∞ [ τ ] ≥ ε L L ( τ ) = sup τ ∈ T : E ∞ [ τ ] ≥ ε L P ( τ ) . (73) \mathcal{L}_L(\tau_s) = \mathcal{L}_P(\tau_s) = s\mathcal{A}_1(\tau_s) = \sup_{\tau\in\mathcal{T}: \mathbb{E}_{\infty}[\tau] \ge\varepsilon} \mathcal{L}_L(\tau) = \sup_{\tau\in\mathcal{T}: \mathbb{E}_{\infty}[\tau] \ge\varepsilon} \mathcal{L}_P(\tau). \tag*{(73)} L L ( τ s ) = L P ( τ s ) = s A 1 ( τ s ) = τ ∈ T : E ∞ [ τ ] ≥ ε sup L L ( τ ) = τ ∈ T : E ∞ [ τ ] ≥ ε sup L P ( τ ) . (73)
Proof. The average-optimality statement follows from Lemma 2, Theorem 4, and the identity (68) . The minimax equalities and optimality statements are proved in Appendix L.
Finally, the Shewhart test is not only optimal but also simple to implement: at each time t t t , it computes the likelihood ratio ℓ t \ell_t ℓ t and compares it with the fixed threshold α \alpha α , stopping and declaring a change at the first time ℓ t ≥ α \ell_t \ge\alpha ℓ t ≥ α . Thus, the one-sample member of the TSR family is precisely the classical Shewhart rule: the finite-memory statistic reduces to the current likelihood ratio, and the state-dependent continuation boundary reduces to a constant threshold. The one-sample setting is therefore the boundary case in which the exact average-optimal rule also attains the Pollak- and Lorden-type worst-case optima at finite ε \varepsilon ε .
Structure, Computation, and Complexity
For ξ ≥ 2 \xi\ge2 ξ ≥ 2 , the exact average-optimal TSR stopping rule in Theorem 3 can be written as
τ λ , ξ ⋆ ≜ inf { t ≥ 1 : W t ( ξ ) ≥ − λ + R ξ ( ℓ ξ − 1 t ) } . (74) \tau_{\lambda,\xi}^{\star} \triangleq\inf\left\{t \ge1 : W_t^{(\xi)} \ge-\lambda+ R_{\xi}\left(\ell_{\xi-1}^{t}\right)\right\}. \tag*{(74)} τ λ , ξ ⋆ ≜ inf { t ≥ 1 : W t ( ξ ) ≥ − λ + R ξ ( ℓ ξ − 1 t ) } . (74)
Here λ = λ ε \lambda= \lambda_{\varepsilon} λ = λ ε is chosen so that E ∞ [ τ λ ε , ξ ⋆ ] = ε \mathbb{E}_{\infty}[\tau_{\lambda_{\varepsilon},\xi}^{\star}] = \varepsilon E ∞ [ τ λ ε , ξ ⋆ ] = ε , and we write τ ξ ⋆ ≜ τ λ ε , ξ ⋆ \tau_{\xi}^{\star} \triangleq\tau_{\lambda_{\varepsilon},\xi}^{\star} τ ξ ⋆ ≜ τ λ ε , ξ ⋆ . Note that, for ξ = 2 \xi= 2 ξ = 2 , R ξ R_{\xi} R ξ reduces to the scalar continuation function R : [ 0 , ∞ ) → R R : [0,\infty) \to\mathbb{R} R : [ 0 , ∞ ) → R used below. Here
ℓ ξ − 1 t = ( ℓ t − ξ + 2 , … , ℓ t ) (75) \ell_{\xi-1}^{t} = (\ell_{t-\xi+2}, \ldots, \ell_t) \tag*{(75)} ℓ ξ − 1 t = ( ℓ t − ξ + 2 , … , ℓ t ) (75)
and
W t ( ξ ) ≜ ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ t − j = ℓ t ( 1 + ∑ k = 1 ξ − 1 ∏ j = 1 k ℓ t − j ) . (76) W_t^{(\xi)} \triangleq\sum_{k=1}^{\xi} \prod_{j=0}^{k-1} \ell_{t-j} = \ell_t \left(1+\sum_{k=1}^{\xi-1}\prod_{j=1}^{k}\ell_{t-j}\right). \tag*{(76)} W t ( ξ ) ≜ k = 1 ∑ ξ j = 0 ∏ k − 1 ℓ t − j = ℓ t ( 1 + k = 1 ∑ ξ − 1 j = 1 ∏ k ℓ t − j ) . (76)
The online implementation consists of two distinct operations: updating the TSR statistic W t ( ξ ) W_t^{(\xi)} W t ( ξ ) and evaluating the state-dependent continuation boundary. Implementation of (74) also requires evaluating the continuation value R ξ ( ℓ t − ξ + 1 t ) R_{\xi}(\ell_{t-\xi+1}^{t}) R ξ ( ℓ t − ξ + 1 t ) , which can be computed offline by dynamic programming and stored for real-time use.
This separation makes the scalability of the method explicit. Online implementation requires O ( ξ ) O(\xi) O ( ξ ) arithmetic operations and O ( ξ ) O(\xi) O ( ξ ) memory, while for ξ = 2 \xi=2 ξ = 2 it reduces to one scalar state-dependent threshold evaluation using only the current and previous likelihood ratios. The principal limitation is offline: a direct tensor-grid representation with M M M points per state coordinate has order M ξ − 1 M^{\xi-1} M ξ − 1 states, before quadrature and interpolation. Thus, exact boundary computation is practical for small windows, especially ξ = 2 \xi=2 ξ = 2 and potentially ξ = 3 \xi=3 ξ = 3 ; substantially larger windows require sparse grids, function approximation, or approximate dynamic programming.
Structural Properties of the Value Functions. The following property is the key enabler for an efficient offline–online implementation. For fixed past likelihood ratios ℓ t − ξ + 1 t − 1 \ell_{t-\xi+1}^{t-1} ℓ t − ξ + 1 t − 1 , the immediate stopping reward W t ( ξ ) W_t^{(\xi)} W t ( ξ ) in (76) is affine in the current likelihood ratio ℓ t \ell_t ℓ t . Moreover, for fixed ℓ t − ξ + 2 t − 1 \ell_{t-\xi+2}^{t-1} ℓ t − ξ + 2 t − 1 , the continuation value R ξ ( ℓ t − ξ + 1 t − 1 ) R_{\xi}(\ell_{t-\xi+1}^{t-1}) R ξ ( ℓ t − ξ + 1 t − 1 ) is nondecreasing and convex in ℓ t \ell_t ℓ t .
Lemma 9 (Monotonicity and convexity) Fix λ > 0 \lambda>0 λ > 0 and ξ ≥ 2 \xi\geq2 ξ ≥ 2 . For any fixed values of the past likelihood ratios ℓ t − ξ + 1 t − 1 \ell_{t-\xi+1}^{t-1} ℓ t − ξ + 1 t − 1 , the reward-to-go J t ξ J_t^{\xi} J t ξ and the continuation value R t ξ R_t^{\xi} R t ξ are nondecreasing and convex functions of the current likelihood ratio ℓ t \ell_t ℓ t , when holding ℓ t − ξ + 1 t − 1 \ell_{t-\xi+1}^{t-1} ℓ t − ξ + 1 t − 1 fixed .
Proof: See Appendix I.
The monotonicity has a direct continuation-value interpretation. For ξ = 2 \xi=2 ξ = 2 , if the procedure continues from time t t t to time t + 1 t+1 t + 1 , the current likelihood ratio becomes the lagged component of the next stopping reward,
W t + 1 ( 2 ) = ℓ t + 1 ( 1 + ℓ t ) . (77) W_{t+1}^{(2)}=\ell_{t+1}(1+\ell_t). \tag*{(77)} W t + 1 ( 2 ) = ℓ t + 1 ( 1 + ℓ t ) . (77)
Increasing ℓ t \ell_t ℓ t therefore increases the next-step stopping reward for every realization of ℓ t + 1 \ell_{t+1} ℓ t + 1 ; taking the maximum of stopping and continuing and then averaging preserves this pointwise monotonicity. For a general window, the same principle applies because strong current evidence remains in the finite-memory state and contributes to future TSR products until it exits the window. This does not mean that stronger evidence necessarily discourages immediate stopping, since the immediate stopping reward also increases with ℓ t \ell_t ℓ t . The decision is governed by the difference between the immediate reward and the continuation value; the Lipschitz result below controls how rapidly the latter can grow in the two-sample case.
Lemma 9 implies that, for each fixed history ℓ t − ξ + 1 t − 1 \ell_{t-\xi+1}^{t-1} ℓ t − ξ + 1 t − 1 , the difference between the affine stopping reward and the convex continuation value is concave in ℓ t \ell_t ℓ t . Hence the stopping set is an interval in the current likelihood ratio (possibly empty, unbounded, or degenerate), and its boundary has at most two points. In the important special case ξ = 2 \xi= 2 ξ = 2 , this boundary can be sharpened to a single state-dependent threshold in the current likelihood ratio via the Lipschitz property below, which substantially simplifies computation.
Single-threshold reduction for ξ = 2 \xi= 2 ξ = 2 . When ξ = 2 \xi= 2 ξ = 2 , the stopping rule depends on ( ℓ t − 1 , ℓ t ) (\ell_{t-1}, \ell_t) ( ℓ t − 1 , ℓ t ) and has the form
τ λ ⋆ ≜ inf { t ≥ 1 : ℓ t + ℓ t − 1 ℓ t ≥ − λ + R ( ℓ t ) } . (78) \tau_\lambda^\star\triangleq\inf\left\{t \ge1 : \ell_t + \ell_{t-1}\ell_t \ge-\lambda+ R(\ell_t)\right\}. \tag*{(78)} τ λ ⋆ ≜ inf { t ≥ 1 : ℓ t + ℓ t − 1 ℓ t ≥ − λ + R ( ℓ t ) } . (78)
For each fixed ℓ t − 1 \ell_{t-1} ℓ t − 1 , define the scalar equation
( 1 + ℓ t − 1 ) ℓ = − λ + R ( ℓ ) . (79) (1+\ell_{t-1})\ell= -\lambda+ R(\ell). \tag*{(79)} ( 1 + ℓ t − 1 ) ℓ = − λ + R ( ℓ ) . (79)
Lemma 10 (Lipschitz property of R R R for ξ = 2 \xi= 2 ξ = 2 ). Assume ξ = 2 \xi= 2 ξ = 2 . Under P ∞ \mathbb{P}_{\infty} P ∞ , the function R R R is nondecreasing and 1-Lipschitz: for all ℓ 2 ≥ ℓ 1 ≥ 0 \ell_2 \ge\ell_1 \ge0 ℓ 2 ≥ ℓ 1 ≥ 0 ,
0 ≤ R ( ℓ 2 ) − R ( ℓ 1 ) ≤ ℓ 2 − ℓ 1 . (80) 0 \le R(\ell_2)-R(\ell_1) \le\ell_2-\ell_1. \tag*{(80)} 0 ≤ R ( ℓ 2 ) − R ( ℓ 1 ) ≤ ℓ 2 − ℓ 1 . (80)
Proof: See Appendix J. ■
Corollary 1 (Unique state-dependent threshold for ξ = 2 \xi= 2 ξ = 2 ). Assume ξ = 2 \xi= 2 ξ = 2 . For any fixed ℓ t − 1 > 0 \ell_{t-1} > 0 ℓ t − 1 > 0 , the function
g ℓ t − 1 ( ℓ ) ≜ ( 1 + ℓ t − 1 ) ℓ + λ − R ( ℓ ) (81) g_{\ell_{t-1}}(\ell) \triangleq(1+\ell_{t-1})\ell+ \lambda- R(\ell) \tag*{(81)} g ℓ t − 1 ( ℓ ) ≜ ( 1 + ℓ t − 1 ) ℓ + λ − R ( ℓ ) (81)
is strictly increasing in ℓ \ell ℓ , and therefore (79) admits at most one solution. When a solution exists, denote it by Γ ( ℓ t − 1 ) \Gamma(\ell_{t-1}) Γ ( ℓ t − 1 ) . Then the average-optimal stopping rule (78) reduces to the single-threshold form
τ λ ⋆ = inf { t ≥ 1 : ℓ t ≥ Γ ( ℓ t − 1 ) } . (82) \tau_\lambda^\star= \inf\{t \ge1 : \ell_t \ge\Gamma(\ell_{t-1})\}. \tag*{(82)} τ λ ⋆ = inf { t ≥ 1 : ℓ t ≥ Γ ( ℓ t − 1 )} . (82)
Computational implication. Corollary 1 turns the online decision into a single comparison in (82). Moreover, since g ℓ t − 1 ( ⋅ ) g_{\ell_{t-1}}(\cdot) g ℓ t − 1 ( ⋅ ) is increasing, Γ ( ℓ t − 1 ) \Gamma(\ell_{t-1}) Γ ( ℓ t − 1 ) can be computed robustly by bisection. Once the function Γ ( ⋅ ) \Gamma(\cdot) Γ ( ⋅ ) has been computed offline, the real-time decision for ξ = 2 \xi= 2 ξ = 2 requires only the current and previous likelihood ratios and a one-dimensional boundary evaluation.
Offline computation of R R R . The continuation value R ( ⋅ ) R(\cdot) R ( ⋅ ) can be computed offline via value iteration or, equivalently, by truncating to a large finite horizon and iterating backward, using the stationary Bellman equation specialized to ξ = 2 \xi= 2 ξ = 2 :
R ( ℓ ) = E ∞ [ max { L ( 1 + ℓ ) , − λ + R ( L ) } ] , (83) R(\ell) = \mathbb{E}_{\infty}\left[\max\{L(1+\ell), -\lambda+ R(L)\}\right], \tag*{(83)} R ( ℓ ) = E ∞ [ max { L ( 1 + ℓ ) , − λ + R ( L )} ] , (83)
where L = d ℓ 1 L \stackrel{d}{=} \ell_1 L = d ℓ 1 under P ∞ \mathbb{P}_{\infty} P ∞ . A practical implementation discretizes ℓ \ell ℓ on a grid { ℓ ( m ) } m = 1 M \{\ell^{(m)}\}_{m=1}^{M} { ℓ ( m ) } m = 1 M and approximates the expectation in (83) via numerical quadrature, or Monte Carlo when needed. Each iteration then costs O ( M ) O(M) O ( M ) evaluations of the right-hand side, multiplied by the number of quadrature nodes, and convergence is typically achieved in a moderate number of iterations. For general ξ > 2 \xi> 2 ξ > 2 , the sufficient statistic is
ℓ ξ − 1 t = ( ℓ t − ξ + 2 , … , ℓ t ) ∈ [ 0 , ∞ ) ξ − 1 (84) \ell_{\xi-1}^{t} = (\ell_{t-\xi+2},\ldots,\ell_t) \in[0,\infty)^{\xi-1} \tag*{(84)} ℓ ξ − 1 t = ( ℓ t − ξ + 2 , … , ℓ t ) ∈ [ 0 , ∞ ) ξ − 1 (84)
(cf. Section 4), and the same approach applies on an ( ξ − 1 ) (\xi-1) ( ξ − 1 ) -dimensional grid. In this case, the cost grows as O ( M ξ − 1 ) O(M^{\xi-1}) O ( M ξ − 1 ) . In this regime, Lemma 9 is especially useful because it implies that, for each fixed history ℓ t − ξ + 1 t − 1 \ell_{t-\xi+1}^{t-1} ℓ t − ξ + 1 t − 1 , the stopping region is described by a low-complexity boundary in the scalar variable ℓ t \ell_t ℓ t . Thus, for online implementation, it suffices to store the boundary rather than the full value function on the entire grid, although computing that boundary offline still requires approximating the multidimensional continuation value. Accordingly, the principal scalability limitation for large ξ \xi ξ is the ( ξ − 1 ) (\xi-1) ( ξ − 1 ) -dimensional offline state space, not the update of the truncated Shiryaev–Roberts statistic itself.
Calibrating λ \lambda λ to meet E ∞ [ τ ] = ε \mathbb{E}_{\infty}[\tau] = \varepsilon E ∞ [ τ ] = ε . The multiplier λ \lambda λ is chosen so that the resulting average-optimal rule satisfies the ARL constraint with equality. For ξ = 2 \xi= 2 ξ = 2 under the threshold representation (82) , the ARL can be computed without Monte Carlo as the solution to a fixed-point equation. Let m ( x ) m(x) m ( x ) denote the expected remaining time to stop given ℓ t − 1 = x \ell_{t-1} = x ℓ t − 1 = x under P ∞ \mathbb{P}_{\infty} P ∞ . Then
m ( x ) = 1 + E ∞ [ m ( L ) 1 { L < Γ ( x ) } ] , L = d ℓ 1 , (85) m(x) = 1 + \mathbb{E}_{\infty}\left[m(L)\mathbf{1}\{L < \Gamma(x)\}\right], \qquad L \mathrel{\stackrel{d}{=}} \ell_1, \tag*{(85)} m ( x ) = 1 + E ∞ [ m ( L ) 1 { L < Γ ( x )} ] , L = d ℓ 1 , (85)
and
E ∞ [ τ λ ⋆ ] = m ( 0 ) , (86) \mathbb{E}_{\infty}[\tau_{\lambda}^{\star}] = m(0), \tag*{(86)} E ∞ [ τ λ ⋆ ] = m ( 0 ) , (86)
where we recall that ℓ 0 = 0 \ell_0 = 0 ℓ 0 = 0 . Equation (85) can be solved numerically on the same grid used for R R R , yielding a fast and stable calibration of λ \lambda λ , for example through bisection in λ \lambda λ , since a larger λ \lambda λ assigns greater cost to continued sampling in the auxiliary optimal-stopping problem and typically decreases the ARL.
Minimax Guarantees and Constant-Boundary Asymptotics
Sections 3–5 established exact finite-sample optimality under the survival-weighted average criterion. We now return to the Pollak- and Lorden-type worst-case criteria in (10)–(11) and for ξ ≥ 2 \xi\ge2 ξ ≥ 2 , we identify a joint growing ARL and ξ \xi ξ regime in which a simpler constant-boundary TSR procedure is asymptotically minimax optimal. Intuitively, an ARL requirement of order ε \varepsilon ε imposes a logarithmic evidence scale of order log ε \log\varepsilon log ε , while a window of length ξ \xi ξ provides approximately ξ D K L ( F 1 ∥ F 0 ) \xi D_{\mathrm{KL}}(F_1\Vert F_0) ξ D KL ( F 1 ∥ F 0 ) units of post-change log-likelihood information. When the latter dominates, the constant-boundary rule succeeds uniformly with probability approaching one and attains the largest possible minimax score. To formalize these, we start with specifying a constant-boundary TSR test.
A related distinction between a structurally complex optimal rule and a simpler asymptotically optimal threshold rule appears in quickest detection of a Markov process across a sensor array [29 ] .
Constant-boundary TSR procedure. For a boundary A > 0 A > 0 A > 0 and an admissible-window length ξ ≥ 1 \xi\ge1 ξ ≥ 1 , define
τ A , ξ c ≜ inf { t ≥ 1 : W t ( ξ ) ≥ A } , (87) \tau^{\mathrm{c}}_{A,\xi} \triangleq\inf\left\{t \ge1 : W_t^{(\xi)} \ge A\right\}, \tag*{(87)} τ A , ξ c ≜ inf { t ≥ 1 : W t ( ξ ) ≥ A } , (87)
with the convention inf ∅ = ∞ \inf\varnothing= \infty inf ∅ = ∞ . The rule uses the same finite-memory TSR statistic as the average-optimal procedure, but replaces its state-dependent continuation boundary by the scalar A A A .
Lemma 11 (ARL guarantee for a constant boundary). For every ξ ≥ 1 \xi\ge1 ξ ≥ 1 and A > 0 A > 0 A > 0 ,
E ∞ [ τ A , ξ c ] ≥ A . (88) \mathbb{E}_{\infty}\left[\tau^{\mathrm{c}}_{A,\xi}\right] \ge A. \tag*{(88)} E ∞ [ τ A , ξ c ] ≥ A . (88)
Proof. See Appendix M.
Therefore, the choice A = ε A = \varepsilon A = ε guarantees the ARL constraint. In the asymptotic regime considered below, Theorem 6 additionally establishes that the resulting stopping time is proper and has finite mean.
Uniform finite-window success guarantee. Let { Z r : r ≥ 1 } \{Z_r : r \ge1\} { Z r : r ≥ 1 } be i.i.d. according to F 1 F_1 F 1 , and define the post-change log-likelihood random walk by
Y r ≜ log ℓ ( Z r ) , S k ≜ ∑ r = 1 k Y r . (89) Y_r \triangleq\log\ell(Z_r), \qquad S_k \triangleq\sum_{r=1}^{k} Y_r. \tag*{(89)} Y r ≜ log ℓ ( Z r ) , S k ≜ r = 1 ∑ k Y r . (89)
For A > 0 A > 0 A > 0 and ξ ≥ 1 \xi\ge1 ξ ≥ 1 , define the finite-window crossing probability
p ˉ ξ ( A ) ≜ P 1 ( max 1 ≤ k ≤ ξ S k ≥ log A ) . (90) \bar{p}_{\xi}(A) \triangleq\mathbb{P}_1\left(\max_{1 \le k \le\xi} S_k \ge\log A\right). \tag*{(90)} p ˉ ξ ( A ) ≜ P 1 ( 1 ≤ k ≤ ξ max S k ≥ log A ) . (90)
This is the probability that the likelihood-ratio product associated with the true onset crosses A A A at some point in the admissible window. To aggregate this guarantee over all s s s episodes, we note that it can be readily shown that there exists b ∈ ( 0 , 1 ) b \in(0,1) b ∈ ( 0 , 1 ) such that
P 1 ( ℓ 1 ≤ b ) > 0. (91) \mathbb{P}_1(\ell_1 \le b) > 0. \tag*{(91)} P 1 ( ℓ 1 ≤ b ) > 0. (91)
Since F 1 ≪ F 0 F_1 \ll F_0 F 1 ≪ F 0 , condition (91) also implies P ∞ ( ℓ 1 ≤ b ) > 0 \mathbb{P}_{\infty}(\ell_1 \le b) > 0 P ∞ ( ℓ 1 ≤ b ) > 0 . It ensures that every finite episode onset remains reachable with positive probability for the constant-boundary rules considered below.
Lemma 12 (Uniform window-success lower bound). Fix s ≥ 1 s \ge1 s ≥ 1 , ξ ≥ 1 \xi\ge1 ξ ≥ 1 , and A > 0 A > 0 A > 0 , and let τ = τ A , ξ c \tau= \tau^{\mathrm{c}}_{A,\xi} τ = τ A , ξ c . For every θ ∈ Θ s ( ξ ) \theta\in\Theta_s(\xi) θ ∈ Θ s ( ξ ) and every episode onset γ i \gamma_i γ i ,
E θ [ 1 { γ i ≤ τ < γ i + ξ } ∣ F γ i − 1 ] ≥ p ˉ ξ ( A ) 1 { τ ≥ γ i } . (92) \mathbb{E}_{\theta}\left[\mathbf{1}_{\{\gamma_i \le\tau< \gamma_i+\xi\}} \mid\mathcal{F}_{\gamma_i-1}\right] \ge\bar{p}_{\xi}(A)\mathbf{1}_{\{\tau\ge\gamma_i\}}. \tag*{(92)} E θ [ 1 { γ i ≤ τ < γ i + ξ } ∣ F γ i − 1 ] ≥ p ˉ ξ ( A ) 1 { τ ≥ γ i } . (92)
Whenever P θ ( τ ≥ γ i ) > 0 \mathbb{P}_{\theta}(\tau\ge\gamma_i) > 0 P θ ( τ ≥ γ i ) > 0 , the corresponding episode-wise Pollak and Lorden success terms are therefore at least p ˉ ξ ( A ) \bar{p}_{\xi}(A) p ˉ ξ ( A ) . If condition (91) holds and
A > b 1 − b , (93) A > \frac{b}{1-b}, \tag*{(93)} A > 1 − b b , (93)
then P θ ( τ ≥ γ i ) > 0 \mathbb{P}_{\theta}(\tau\ge\gamma_i) > 0 P θ ( τ ≥ γ i ) > 0 for every θ ∈ Θ s ( ξ ) \theta\in\Theta_s(\xi) θ ∈ Θ s ( ξ ) and every i ∈ { 1 , … , s } i \in\{1,\ldots,s\} i ∈ { 1 , … , s } , and
L Q ( τ A , ξ c ) ≥ s p ˉ ξ ( A ) , Q ∈ { L , P } . (94) \mathcal{L}_{Q}\left(\tau^{\mathrm{c}}_{A,\xi}\right) \ge s\bar{p}_{\xi}(A), \qquad Q \in\{\mathrm{L},\mathrm{P}\}. \tag*{(94)} L Q ( τ A , ξ c ) ≥ s p ˉ ξ ( A ) , Q ∈ { L , P } . (94)
Proof: See Appendix N.
For Q ∈ { L , P } Q \in\{\mathrm{L},\mathrm{P}\} Q ∈ { L , P } , define the optimal minimax value
V Q ⋆ ( ε , ξ ; s ) ≜ sup τ ∈ T : E ∞ [ τ ] ≥ ε L Q ( τ ) . (95) V_Q^\star(\varepsilon,\xi;s) \triangleq\sup_{\tau\in\mathcal{T}:\mathbb{E}_{\infty}[\tau]\ge\varepsilon} \mathcal{L}_Q(\tau). \tag*{(95)} V Q ⋆ ( ε , ξ ; s ) ≜ τ ∈ T : E ∞ [ τ ] ≥ ε sup L Q ( τ ) . (95)
Because L Q \mathcal{L}_Q L Q is the sum of s s s episode-wise success probabilities,
V Q ⋆ ( ε , ξ ; s ) ≤ s . (96) V_Q^\star(\varepsilon,\xi;s) \le s. \tag*{(96)} V Q ⋆ ( ε , ξ ; s ) ≤ s . (96)
Consequently, whenever τ A , ξ c \tau^c_{A,\xi} τ A , ξ c is feasible and (93) holds, Lemma 12 gives
s p ‾ ξ ( A ) ≤ L Q ( τ A , ξ c ) ≤ V Q ⋆ ( ε , ξ ; s ) ≤ s , Q ∈ { L , P } . (97) s\overline{p}_{\xi}(A) \le\mathcal{L}_Q(\tau^c_{A,\xi}) \le V_Q^\star(\varepsilon,\xi;s) \le s,\qquad Q \in\{\mathrm{L},\mathrm{P}\}. \tag*{(97)} s p ξ ( A ) ≤ L Q ( τ A , ξ c ) ≤ V Q ⋆ ( ε , ξ ; s ) ≤ s , Q ∈ { L , P } . (97)
Joint ARL–window asymptotics. Assume
P 1 ( ℓ 1 > 0 ) = 1 , E 1 [ ∣ log ℓ 1 ∣ ] < ∞ , (98) \mathbb{P}_1(\ell_1 > 0)=1,\qquad\mathbb{E}_1[|\log\ell_1|] < \infty, \tag*{(98)} P 1 ( ℓ 1 > 0 ) = 1 , E 1 [ ∣ log ℓ 1 ∣ ] < ∞ , (98)
and define the post-change information number
I ≜ E 1 [ log ℓ 1 ] = D K L ( F 1 ∥ F 0 ) ∈ ( 0 , ∞ ) . (99) I \triangleq\mathbb{E}_1[\log\ell_1] = D_{\mathrm{KL}}(F_1\|F_0) \in(0,\infty). \tag*{(99)} I ≜ E 1 [ log ℓ 1 ] = D KL ( F 1 ∥ F 0 ) ∈ ( 0 , ∞ ) . (99)
Theorem 6 (Asymptotic minimax optimality of a constant-boundary TSR test) Let ε → ∞ \varepsilon\to\infty ε → ∞ , and let ξ ε → ∞ \xi_\varepsilon\to\infty ξ ε → ∞ be an integer-valued sequence satisfying
lim sup ε → ∞ log ε ξ ε < I . (100) \limsup_{\varepsilon\to\infty}\frac{\log\varepsilon}{\xi_\varepsilon} < I. \tag*{(100)} ε → ∞ lim sup ξ ε log ε < I . (100)
Define
τ ε c ≜ τ ε , ξ ε c . (101) \tau^c_\varepsilon\triangleq\tau^c_{\varepsilon,\xi_\varepsilon}. \tag*{(101)} τ ε c ≜ τ ε , ξ ε c . (101)
Then, for every fixed s ≥ 1 s \ge1 s ≥ 1 , the following statements hold.
For all sufficiently large ε \varepsilon ε , the procedure is proper and feasible:
ε ≤ E ∞ [ τ ε c ] < ∞ . (102) \varepsilon\le\mathbb{E}_{\infty}[\tau^c_\varepsilon] < \infty. \tag*{(102)} ε ≤ E ∞ [ τ ε c ] < ∞. (102)
Under both minimax criteria,
L Q ( τ ε c ) ⟶ s , Q ∈ { L , P } . (103) \mathcal{L}_Q(\tau^c_\varepsilon) \longrightarrow s,\qquad Q \in\{\mathrm{L},\mathrm{P}\}. \tag*{(103)} L Q ( τ ε c ) ⟶ s , Q ∈ { L , P } . (103)
The procedure is asymptotically optimal in the additive sense:
V Q ⋆ ( ε , ξ ε ; s ) − L Q ( τ ε c ) ⟶ 0 , Q ∈ { L , P } . (104) V_Q^\star(\varepsilon,\xi_\varepsilon;s)-\mathcal{L}_Q(\tau^c_\varepsilon) \longrightarrow0,\qquad Q \in\{\mathrm{L},\mathrm{P}\}. \tag*{(104)} V Q ⋆ ( ε , ξ ε ; s ) − L Q ( τ ε c ) ⟶ 0 , Q ∈ { L , P } . (104)
The procedure is asymptotically optimal in the relative sense:
L Q ( τ ε , ξ ε c ) V Q ∗ ( ξ , ξ ε ; s ) ⟶ 1 , Q ∈ { L , P } . (105) \frac{\mathcal{L}_{Q}\left(\tau_{\varepsilon,\xi_{\varepsilon}}^{c}\right)}{\mathcal{V}_{Q}^{*}\left(\xi,\xi_{\varepsilon};s\right)} \longrightarrow1,\qquad Q \in\{\mathrm{L},\mathrm{P}\}. \tag*{(105)} V Q ∗ ( ξ , ξ ε ; s ) L Q ( τ ε , ξ ε c ) ⟶ 1 , Q ∈ { L , P } . (105)
Proof: See Appendix O.
Condition (100) places the admissible window strictly above the information scale. In fact, it implies
ξ ε I − log ε ⟶ ∞ . (106) \xi_{\varepsilon} I-\log\varepsilon\longrightarrow\infty. \tag*{(106)} ξ ε I − log ε ⟶ ∞. (106)
Thus, the typical post-change information accumulated within the admissible window eventually exceeds the logarithmic evidence required by an ARL of order ε \varepsilon ε by a diverging margin.
Corollary 2 (Window length above the information scale) For any fixed δ > 0 \delta> 0 δ > 0 , let
ξ ε ≜ ⌈ ( 1 + δ ) log ε I ⌉ . (107) \xi_{\varepsilon} \triangleq\left\lceil\frac{(1+\delta)\log\varepsilon}{I} \right\rceil. \tag*{(107)} ξ ε ≜ ⌈ I ( 1 + δ ) log ε ⌉ . (107)
Then τ ε , ξ ε c \tau_{\varepsilon,\xi_{\varepsilon}}^{c} τ ε , ξ ε c satisfies all conclusions of Theorem 6. The same conclusions hold, whenever such finite thresholds exist, for exactly ARL-calibrated boundaries A ^ ε \widehat{A}_{\varepsilon} A ε satisfying
E ∞ [ τ A ^ ε , ξ ε c ] = ε . (108) \mathbb{E}_{\infty}\left[\tau_{\widehat{A}_{\varepsilon},\xi_{\varepsilon}}^{c}\right]=\varepsilon. \tag*{(108)} E ∞ [ τ A ε , ξ ε c ] = ε . (108)
Proof: See Appendix P.
The corollary shows that, above the scale log ε / D K L ( F 1 ∥ F 0 ) \log\varepsilon/D_{\mathrm{KL}}(F_{1}\|F_{0}) log ε / D KL ( F 1 ∥ F 0 ) , the state-dependent continuation boundary is unnecessary for first-order minimax optimality. This conclusion does not extend to a fixed short window: if ξ \xi ξ remains fixed while ε → ∞ \varepsilon\to\infty ε → ∞ , condition (100) fails and the finite-window success probability may vanish. For the criteria normalized by s s s , the limiting value in Theorem 6 is one.
Numerical Evaluations
In this section, we numerically illustrate the finite-window behavior of the TSR procedures and compare them with classical sequential detectors. Because the criteria in (7) –(8) sum the episode-wise success probabilities, the reported detection probabilities are shown on a per-episode scale (equivalently, the criteria are normalized by s s s when multiple episodes are simulated). For Monte Carlo comparisons labeled “worst-case detection probability,” the infimum over the onset time is approximated by the minimum over the onset locations included in the simulation. Detection thresholds are calibrated under P ∞ \mathbb{P}_{\infty} P ∞ , and when a horizontal axis reports ARL we use the empirically attained value of E ∞ [ τ ] \mathbb{E}_{\infty}[\tau] E ∞ [ τ ] so that residual calibration differences remain visible. The exact finite-sample optimality results for ξ ≥ 2 \xi\ge2 ξ ≥ 2 established in Sections 3–4 concern the survival-weighted average criterion A ξ \mathcal{A}_{\xi} A ξ ; the Pollak-type and grid-worst quantities retained below therefore provide complementary onset-robustness diagnostics rather than the criterion for which exact finite-sample optimality is claimed.
We begin with a unit-variance Gaussian mean-shift model, F 0 = N ( 0 , 1 ) F_0 = \mathcal{N}(0,1) F 0 = N ( 0 , 1 ) and F 1 = N ( μ 1 , 1 ) F_1 = \mathcal{N}(\mu_1,1) F 1 = N ( μ 1 , 1 ) . Figure 2 illustrates the decay of the per-episode Pollak-type success probability as the false-alarm requirement E ∞ [ τ ] ≥ ε \mathbb{E}_{\infty}[\tau] \ge\varepsilon E ∞ [ τ ] ≥ ε becomes more stringent, for μ 1 = 1 \mu_1=1 μ 1 = 1 and 2 2 2 and for admissible-window lengths ξ = 1 , 2 , 3 \xi=1,2,3 ξ = 1 , 2 , 3 . In the weaker-signal regime (μ 1 = 1 \mu_1=1 μ 1 = 1 ), the success probability decreases markedly with ε \varepsilon ε ; ξ = 1 \xi=1 ξ = 1 exhibits the steepest decline, while ξ = 3 \xi=3 ξ = 3 consistently benefits from the longer admissible window. For the stronger signal (μ 1 = 2 \mu_1=2 μ 1 = 2 ), the decay is substantially milder and the probabilities remain close to one over the displayed range, so the incremental benefit of enlarging ξ \xi ξ is less pronounced.
Figure 2. Per-episode Pollak-type success probability versus the ARL false-alarm constraint ε \varepsilon ε for two Gaussian mean shifts and admissible-window lengths ξ = 1 , 2 , 3 \xi=1,2,3 ξ = 1 , 2 , 3 .
Figure 3 shows the convergence behavior of the numerical procedure used to compute R ( ℓ ) R(\ell) R ( ℓ ) , plotting the error versus the iteration index n n n on a logarithmic scale. The vertical axis represents the error in computing R ( ℓ ) R(\ell) R ( ℓ ) (log scale), while the horizontal axis shows the iteration number up to n = 500 n=500 n = 500 . The curve exhibits a sharp initial decrease in error during the first few iterations, followed by a steady and nearly linear decay on the logarithmic scale, indicating approximately exponential convergence. After roughly 400 iterations, the error is reduced by several orders of magnitude (from about 10 2 10^2 1 0 2 down to below 10 − 2 10^{-2} 1 0 − 2 ), demonstrating both numerical stability and strong contraction properties of the underlying recursion. The smooth monotonic decline without visible oscillations further suggests that the update rule for R ( ℓ ) R(\ell) R ( ℓ ) is well-conditioned and does not suffer from instability or divergence, thereby confirming the effectiveness of the computational scheme.
Figure 3. Convergence of iteratively computing the state-dependent R ( ℓ ) R(\ell) R ( ℓ ) .
Figure 4 illustrates the single-threshold representation of the ξ = 2 \xi=2 ξ = 2 rule by plotting Γ ( ℓ t − 1 ) \Gamma(\ell_{t-1}) Γ ( ℓ t − 1 ) against the previous likelihood ratio for ε = 50 \varepsilon=50 ε = 50 , 100 100 100 , and 200 200 200 . Recall that
Figure 4. State-dependent current-likelihood-ratio threshold Γ ( ℓ t − 1 ) \Gamma(\ell_{t-1}) Γ ( ℓ t − 1 ) for ξ = 2 \xi=2 ξ = 2 under different ARL constraints.
τ λ ⋆ = inf { t : ℓ t ( 1 + ℓ t − 1 ) ≥ − λ + R ( ℓ t ) } , (109) \tau_{\lambda}^{\star} = \inf\{t:\ell_t(1+\ell_{t-1}) \ge-\lambda+ R(\ell_t)\}, \tag*{(109)} τ λ ⋆ = inf { t : ℓ t ( 1 + ℓ t − 1 ) ≥ − λ + R ( ℓ t )} , (109)
and, for fixed ℓ t − 1 = ℓ \ell_{t-1}=\ell ℓ t − 1 = ℓ , Γ ( ℓ ) \Gamma(\ell) Γ ( ℓ ) is the solution of x ( 1 + ℓ ) = − λ + R ( x ) x(1+\ell)=-\lambda+R(x) x ( 1 + ℓ ) = − λ + R ( x ) whenever that solution exists. Thus, Γ ( ℓ ) \Gamma(\ell) Γ ( ℓ ) is the minimum current likelihood ratio required for stopping given the retained evidence ℓ t − 1 \ell_{t-1} ℓ t − 1 . The curves decrease with ℓ t − 1 \ell_{t-1} ℓ t − 1 , illustrating that stronger recent evidence lowers the amount of new evidence required to stop. Increasing the ARL requirement shifts the threshold upward, reflecting the more conservative decision rule required for stronger false-alarm protection. Importantly, this is a state-dependent infinite-horizon boundary; the horizontal axis is ℓ t − 1 \ell_{t-1} ℓ t − 1 , not time.
To assess the onset sensitivity of the average-optimal TSR rule, we evaluate the detection probability as a function of the change-point location. Specifically, for each candidate transient onset time γ \gamma γ , we estimate
π ^ γ = P γ ( γ ≤ τ < γ + ξ ∣ τ ≥ γ ) , (110) \hat{\pi}_\gamma= \mathbb{P}_\gamma\left(\gamma\le\tau< \gamma+\xi\mid\tau\ge\gamma\right), \tag*{(110)} π ^ γ = P γ ( γ ≤ τ < γ + ξ ∣ τ ≥ γ ) , (110)
that is, the probability of detecting within the admissible window conditioned on not having stopped before the change. The exact average-optimality theory does not require this conditional probability to be constant across γ \gamma γ . Figure 5 shows a nearly flat profile around 0.21–0.23. Thus, in this numerical regime, optimizing the survival-weighted average does not appear to sacrifice performance at particular onset locations. The remaining fluctuations are consistent with the finite Monte Carlo uncertainty indicated by the confidence intervals; no finite-horizon or terminal-time effect is involved, since the stopping problem itself is infinite-horizon.
Figure 5. Estimated conditional detection probability π ^ γ \hat{\pi}_\gamma π ^ γ as a function of the change-point location γ \gamma γ , illustrating the onset sensitivity of the average-optimal TSR rule.
Figure 6 shows the value function J ( ℓ t − 1 , ℓ t ) J(\ell_{t-1},\ell_t) J ( ℓ t − 1 , ℓ t ) for ξ = 2 \xi=2 ξ = 2 . This is not a second detection statistic: the TSR detection statistic is W t ( 2 ) W_t^{(2)} W t ( 2 ) , whereas J J J is the reward-to-go appearing in the optimal-stopping formulation. The surface makes explicit the two-dimensional state ( ℓ t − 1 , ℓ t ) (\ell_{t-1},\ell_t) ( ℓ t − 1 , ℓ t ) and increases with both retained and current evidence, consistent with the monotonicity established in Section 6. Its geometry also reflects the multiplicative term ℓ t ( 1 + ℓ t − 1 ) \ell_t(1+\ell_{t-1}) ℓ t ( 1 + ℓ t − 1 ) : stronger retained evidence increases the value associated with a given current likelihood ratio and underlies the state dependence of the stopping decision.
Figure 6. Surface plot of the two-state value function J ( ℓ t − 1 , ℓ t ) J(\ell_{t-1},\ell_t) J ( ℓ t − 1 , ℓ t ) , illustrating its dependence on the retained and current likelihood ratios.
We next assess whether tailoring the stopping rule to the finite-window probability-maximizing objective provides a material advantage over standard sequential detectors. Figure 7 compares the average-optimal TSR test with the classical Shiryaev–Roberts, CuSum, and Shewhart tests for ξ = 2 \xi= 2 ξ = 2 in two Gaussian models. Because exact finite-sample optimality is established for A 2 \mathcal{A}_2 A 2 , the grid-worst quantity in Figure 7 is a complementary robustness comparison rather than the optimized criterion. The left panel uses the variance-contraction model F 0 = N ( 0 , 1 ) F_0 = \mathcal{N}(0,1) F 0 = N ( 0 , 1 ) and F 1 = N ( 0 , 0.2 2 ) F_1 = \mathcal{N}(0,0.2^2) F 1 = N ( 0 , 0. 2 2 ) . This setting is particularly informative because the single-sample likelihood ratio is bounded, ℓ ( x ) = 5 exp ( − 12 x 2 ) ≤ 5 \ell(x) = 5\exp(-12x^2) \le5 ℓ ( x ) = 5 exp ( − 12 x 2 ) ≤ 5 . Thus, no individual observation can provide arbitrarily large evidence for the change, making effective use of the two observations available within the admissible detection window important. The left panel shows a clear separation between the average-optimal TSR rule and the classical alternatives. When the ARL requirement is small, all procedures operate aggressively, and their detection probabilities are high. As the false-alarm constraint becomes more stringent, however, the TSR curve decays substantially more slowly and remains uniformly above the classical procedures over the displayed range. At moderate and large ARLs, the gain becomes pronounced: TSR retains a substantial probability of detection within the two-sample window, whereas classical Shiryaev–Roberts and CuSum eventually have essentially zero grid-worst detection probability.
Figure 7. Grid-worst conditional probability of detection within the admissible window versus empirically attained ARL for the TSR, Shiryaev–Roberts, CuSum, and Shewhart procedures, with ξ = 2 \xi= 2 ξ = 2 .
The right panel provides a complementary comparison for the standard unbounded mean-shift model F 0 = N ( 0 , 1 ) F_0 = \mathcal{N}(0,1) F 0 = N ( 0 , 1 ) and F 1 = N ( 1 , 1 ) F_1 = \mathcal{N}(1,1) F 1 = N ( 1 , 1 ) . At an attained ARL near 20, CuSum and Shewhart have grid-worst success probabilities of approximately 0.432 and 0.452, respectively, compared with 0.455 for TSR. Thus, the pronounced separation in the bounded-likelihood-ratio example does not persist in this aggressive operating regime. The advantage of TSR becomes clearer as the false-alarm requirement increases. Near ARL 100, the corresponding probabilities are approximately 0.192 for TSR, 0.176 for Shewhart, 0.099 for CuSum, and 0.023 for Shiryaev–Roberts. Taken together, the two panels show that the benefit of finite-window tailoring is regime dependent: classical procedures can remain competitive when thresholds are low and individual observations can provide unbounded evidence, whereas the TSR rule retains a larger onset-robust success probability as the false-alarm constraint becomes more stringent.
For the right panel, all accumulation statistics are initialized at zero, and the grid-worst value is the minimum over onset locations γ ∈ { 1 , 5 , 10 , 20 , 40 } \gamma\in\{1,5,10,20,40\} γ ∈ { 1 , 5 , 10 , 20 , 40 } . The continuation function for TSR is computed from (83) using 96-point Gauss–Hermite quadrature and a value-iteration tolerance of 2 × 10 − 10 2 \times10^{-10} 2 × 1 0 − 10 . For TSR, Shiryaev–Roberts, and CuSum, threshold calibration uses 30,000 no-change sample paths. The attained ARLs are estimated from an independent set of 100,000 paths, and the onset-specific success probabilities use 150,000 paths per onset. The Shewhart threshold and success probability are evaluated analytically. The displayed error bars for the other procedures are pointwise 95% Monte Carlo intervals. The accompanying simulation script and tabulated output record the thresholds, attained ARLs, standard errors, and fixed random seeds.
The latter behavior has a simple interpretation in this example. Since ℓ t ≤ 5 \ell_t \le5 ℓ t ≤ 5 , a CuSum statistic initialized at zero can accumulate at most 2 log 5 2 \log5 2 log 5 during the first two post-change observations. Likewise, a classical Shiryaev–Roberts statistic initialized at zero satisfies
S 1 S R ≤ 5 , S 2 S R = ( 1 + S 1 S R ) ℓ 2 ≤ 30. (111) S_1^{\mathrm{SR}} \le5,\qquad S_2^{\mathrm{SR}} = \left(1+S_1^{\mathrm{SR}}\right)\ell_2 \le30. \tag*{(111)} S 1 SR ≤ 5 , S 2 SR = ( 1 + S 1 SR ) ℓ 2 ≤ 30. (111)
Consequently, once the thresholds required to meet a stringent ARL constraint exceed these levels, the corresponding procedures cannot stop within the two-sample admissible window for an early change onset. This explains the sharp deterioration of their worst-case finite-window performance; it is a consequence of the mismatch between procedures designed to accumulate evidence over an unrestricted horizon and an objective that credits detection only within a short window. The comparison with Shewhart highlights the complementary effect. Shewhart does not suffer from accumulation of irrelevant old evidence, but it uses only the current observation and therefore cannot exploit the second sample available when ξ = 2 \xi= 2 ξ = 2 . TSR occupies the appropriate middle ground: its statistic retains precisely the likelihood-ratio terms associated with change onsets that can still lead to a successful decision,
W t ( 2 ) = ℓ t ( 1 + ℓ t − 1 ) , (112) W_t^{(2)} = \ell_t\left(1+\ell_{t-1}\right), \tag*{(112)} W t ( 2 ) = ℓ t ( 1 + ℓ t − 1 ) , (112)
while its state-dependent continuation boundary accounts for the value of the retained evidence. Hence, although W t ( ξ ) W_t^{(\xi)} W t ( ξ ) is a truncated Shiryaev–Roberts statistic, the finite-memory truncation and the associated stopping rule can lead to substantially different behavior from classical Shiryaev–Roberts and CuSum when the admissible detection window is short.
Structure of the state-dependent boundary. We next examine the role of the state-dependent continuation boundary itself for the variance-contraction setting used in the left panel of Figure 7 . For ξ = 2 \xi= 2 ξ = 2 , the state-dependent TSR rule compares the statistic
W t ( 2 ) = ℓ t ( 1 + ℓ t − 1 ) (113) W_t^{(2)} = \ell_t(1+\ell_{t-1}) \tag*{(113)} W t ( 2 ) = ℓ t ( 1 + ℓ t − 1 ) (113)
with the continuation boundary
h λ ( ℓ t ) ≜ − λ + R ( ℓ t ) , (114) h_{\lambda}(\ell_t) \triangleq-\lambda+ R(\ell_t), \tag*{(114)} h λ ( ℓ t ) ≜ − λ + R ( ℓ t ) , (114)
whereas the constant-boundary TSR rule replaces h λ ( ℓ t ) h_{\lambda}(\ell_t) h λ ( ℓ t ) by a scalar threshold A A A . To isolate the effect of this state dependence, the constant threshold is calibrated to essentially the same ARL as the average-optimal rule. Figure 8 shows the resulting boundaries for three false-alarm constraints. The empirically attained ARLs, 20.2, 101.2, and 206.1, are close to the corresponding target values ε = 20 \varepsilon= 20 ε = 20 , 100, and 200. The figure shows that the average-optimal boundary is genuinely state dependent, but that the extent of this dependence changes with the operating regime. For ε = 20 \varepsilon= 20 ε = 20 , the variation is substantial over a broad range of ℓ t \ell_t ℓ t : the average-optimal boundary initially lies well below the matched constant threshold, crosses it at an intermediate likelihood-ratio value, and then rises appreciably above it. Thus, at this relatively aggressive operating point, replacing the continuation value by a single threshold removes a significant amount of state adaptation.
Figure 8. State-dependent continuation boundary − λ + R ( ℓ t ) -\lambda+ R(\ell_t) − λ + R ( ℓ t ) and a matched-ARL constant boundary.
As the ARL constraint becomes more stringent, the state dependence becomes more localized. For ε = 100 \varepsilon= 100 ε = 100 and 200, the average-optimal boundary is nearly flat over most of the likelihood-ratio range and lies moderately below the corresponding constant threshold. It then increases sharply when ℓ t \ell_t ℓ t approaches the upper end of its attainable range. Hence, a constant threshold can approximate the average-optimal boundary reasonably well over much of the state space in these regimes, but it does not reproduce the behavior of the average-optimal rule when the current likelihood ratio is large. In precisely those states, strong current evidence also has substantial continuation value because it becomes part of the next finite-memory TSR statistic. This observation provides a more nuanced answer to whether the state-dependent boundary is practically necessary. State dependence is not equally important at every state or every ARL: for stringent false-alarm constraints, much of the boundary is close to constant, while the principal adaptation is concentrated in high-evidence states. For less stringent constraints, the departure from a constant boundary is considerably more pronounced. Thus, the constant-boundary approximation can be useful in some operating regimes, while the exact average-optimal TSR construction retains a qualitatively different decision structure that becomes relevant in particular regions of the likelihood-ratio state space.
Finite-sample comparison with a constant boundary. We next isolate the practical value of state dependence by comparing the state-dependent TSR procedure with a constant-boundary TSR procedure using the same statistic and approximately matched false-alarm levels. Figure 9 uses an exponential model with nominal rate 1, post-change rate 8, and admissible-window length ξ = 3 \xi= 3 ξ = 3 . For each operating point, the scalar boundary of the constant-boundary TSR procedure is calibrated separately to approximately match the ARL attained by the state-dependent procedure; the horizontal coordinate reports the empirically attained ARL. As in Figure 7 , the grid-worst probability reported here is a robustness diagnostic; the finite-sample exact optimality of the state-dependent rule is with respect to A ξ A_{\xi} A ξ .
Figure 9. State-dependent and constant-boundary TSR procedures under approximately matched false-alarm levels for the exponential model with nominal rate 1, post-change rate 8, and admissible-window length ξ = 3 \xi= 3 ξ = 3 .
Both procedures exhibit the expected decrease in finite-window detection probability as the ARL requirement becomes more stringent. The state-dependent procedure has the higher point estimate throughout the displayed range, with the clearest separation at moderate ARLs. Near ARL 50, the worst-case detection probability increases from approximately 0.826 for the constant-boundary rule to 0.888 for the state-dependent rule, an absolute gain of about 0.062 and a relative gain of approximately 7.5%. Near ARL 100, the corresponding probabilities are approximately 0.687 and 0.734, yielding a relative improvement of about 6.8%. The advantage decreases as the false-alarm requirement becomes more stringent and is small at the displayed resolution near ARL 200. Thus, the experiment shows that state dependence can provide a measurable finite-sample benefit without obtaining that gain through a higher false-alarm rate, while also illustrating that the benefit becomes small in more stringent operating regimes.
Information-Scale Transition. We next numerically illustrate the asymptotic mechanism underlying Theorem 6. We consider the Gaussian mean-shift model F 0 = N ( 0 , 1 ) F_0 = \mathcal{N}(0,1) F 0 = N ( 0 , 1 ) and F 1 = N ( 1 , 1 ) F_1 = \mathcal{N}(1,1) F 1 = N ( 1 , 1 ) for which
I ≜ D K L ( F 1 ∥ F 0 ) = 1 2 . (115) I \triangleq D_{\mathrm{KL}}(F_1 \mathbin{\|} F_0) = \frac{1}{2}. \tag*{(115)} I ≜ D KL ( F 1 ∥ F 0 ) = 2 1 . (115)
Recall the finite-window crossing probability introduced in Section 7,
p ˉ ξ ( A ) ≜ P 1 ( max 1 ≤ k ≤ ξ S k ≥ log A ) . (116) \bar{p}_{\xi}(A) \triangleq\mathbb{P}_1\left(\max_{1 \leq k \leq\xi} S_k \geq\log A\right). \tag*{(116)} p ˉ ξ ( A ) ≜ P 1 ( 1 ≤ k ≤ ξ max S k ≥ log A ) . (116)
For the constant-boundary TSR rule with A = ε A = \varepsilon A = ε , Lemma 12 shows that p ˉ ξ ( ε ) \bar{p}_{\xi}(\varepsilon) p ˉ ξ ( ε ) provides a uniform lower bound on the per-opportunity Pollak- and Lorden-type success probabilities. Hence, the convergence
p ˉ ξ ε ( ε ) → 1 (117) \bar{p}_{\xi_{\varepsilon}}(\varepsilon) \to1 \tag*{(117)} p ˉ ξ ε ( ε ) → 1 (117)
is precisely the mechanism used in Theorem 6 to establish asymptotic minimax optimality. Figure 10 illustrates this behavior. In the left panel, we select the admissible-window length according to
Figure 10. Information-scale transition. Left: finite-window crossing probability p ˉ ξ ε ( ε ) \bar{p}_{\xi_\varepsilon}(\varepsilon) p ˉ ξ ε ( ε ) for ξ ε = ⌈ c log ( ε ) / I ⌉ \xi_\varepsilon= \lceil c\log(\varepsilon)/I\rceil ξ ε = ⌈ c log ( ε ) / I ⌉ . Curves with c > 1 c > 1 c > 1 correspond to the regime covered by Theorem 6; c ≤ 1 c \le1 c ≤ 1 is included as an empirical comparison. Right: crossing probability versus the normalized information ratio r = ξ I / log ε r = \xi I/\log\varepsilon r = ξ I / log ε for increasing values of ε \varepsilon ε . The dashed line marks the critical information scale r = 1 r = 1 r = 1 .
ξ ε = ⌈ c log ε I ⌉ (118) \xi_{\varepsilon} = \left\lceil c \frac{\log\varepsilon}{I} \right\rceil \tag*{(118)} ξ ε = ⌈ c I log ε ⌉ (118)
for several values of c c c . The resulting behavior changes sharply depending on whether c c c lies below or above one. When c < 1 c < 1 c < 1 , the typical amount of post-change log-likelihood information available within the admissible window satisfies ξ ε I ≈ c log ε < log ε \xi_{\varepsilon} I \approx c \log\varepsilon< \log\varepsilon ξ ε I ≈ c log ε < log ε and the crossing probability decreases as the false-alarm requirement becomes more stringent. At the critical scaling c = 1 c = 1 c = 1 , the available mean information and the required evidence are of the same order, and the crossing probability remains at an intermediate level over the range considered. In contrast, when c > 1 c > 1 c > 1 , the admissible window provides an excess amount of mean post-change information of approximately ξ ε I − log ε ≈ ( c − 1 ) log ε \xi_{\varepsilon} I - \log\varepsilon\approx(c - 1) \log\varepsilon ξ ε I − log ε ≈ ( c − 1 ) log ε . Accordingly, p ˉ ξ ε ( ε ) \bar{p}_{\xi_{\varepsilon}}(\varepsilon) p ˉ ξ ε ( ε ) increases with ε \varepsilon ε . The increase is more pronounced for larger values of c c c , since the admissible window extends farther beyond the information scale. This behavior is consistent with the sufficient condition of Theorem 6: any fixed c > 1 c > 1 c > 1 satisfies
lim sup ε → ∞ log ε ξ ε < I . (119) \limsup_{\varepsilon\to\infty} \frac{\log\varepsilon}{\xi_{\varepsilon}} < I . \tag*{(119)} ε → ∞ lim sup ξ ε log ε < I . (119)
The convergence in the left panel is relatively gradual, especially when c c c is only moderately larger than one. This is expected in the Gaussian model. Under F 1 F_1 F 1 , the log-likelihood increments satisfy
log f 1 ( Z r ) f 0 ( Z r ) ∼ N ( I , 1 ) , (120) \log\frac{f_1(Z_r)}{f_0(Z_r)} \sim\mathcal{N}(I,1), \tag*{(120)} log f 0 ( Z r ) f 1 ( Z r ) ∼ N ( I , 1 ) , (120)
for the present choice of unit mean shift. With ξ ε ≈ c log ε / I \xi_{\varepsilon} \approx c \log\varepsilon/ I ξ ε ≈ c log ε / I , the excess mean evidence above the crossing level, normalized by the standard deviation of S ξ ε S_{\xi_{\varepsilon}} S ξ ε , grows only on the order of
( c − 1 ) log ε 2 c . (121) (c - 1)\sqrt{\frac{\log\varepsilon}{2c}} . \tag*{(121)} ( c − 1 ) 2 c log ε . (121)
Thus, even for large but finite ε \varepsilon ε , the crossing probability need not yet be close to one when c c c is near the critical value. The right figure displays the same phenomenon using the normalized information ratio
r ≜ ξ I log ε . (122) r \triangleq\frac{\xi I}{\log\varepsilon}. \tag*{(122)} r ≜ log ε ξ I . (122)
The vertical dashed line at r = 1 r = 1 r = 1 corresponds to the information scale
ξ = log ε I . (123) \xi= \frac{\log\varepsilon}{I}. \tag*{(123)} ξ = I log ε . (123)
As ε \varepsilon ε increases, the curves separate increasingly on the two sides of this value. For r < 1 r < 1 r < 1 , the crossing probability becomes smaller with increasing ε \varepsilon ε , whereas for r > 1 r > 1 r > 1 it becomes larger. Hence, the transition becomes progressively sharper around r = 1 r = 1 r = 1 , numerically illustrating the information scale identified by the asymptotic analysis. The curves with r ≤ 1 r \le1 r ≤ 1 are included only as empirical contrasts, since Theorem 6 establishes the sufficient supercritical regime r > 1 r > 1 r > 1 rather than a converse for r ≤ 1 r \le1 r ≤ 1 .
We have studied the problem of probability-maximizing sequential detection in a stochastic process that may experience multiple, non-overlapping departures from a nominal distribution, each of finite duration, and followed by a return to the nominal regime. The formulation also includes a single persistent change as a special case. The objective has been to identify a change-point in real time, within a prescribed admissible detection window after its occurrence, while satisfying a false-alarm constraint. The stopping time itself remains infinite-horizon; the detection window determines whether a stop is credited as successful for a given change onset. To address this problem, we have adopted a probability-maximizing formulation, considering both a survival-weighted average success criterion and Pollak- and Lorden-type minimax criteria, under which performance is measured by the probability of stopping within the allowable detection window following a transient onset. This formulation differs fundamentally from classical quickest-change detection criteria based on expected delay and is particularly well suited to transient phenomena that may disappear before a detector has time to react. Our analysis has led to an exact characterization of the optimal stopping rule under the survival-weighted average success criterion. In particular, we have shown that the optimal decision rule is governed by a finite-memory statistic that aggregates likelihood-ratio evidence over the most recent observations within the admissible detection window. This yields a state-dependent optimal stopping structure and establishes the proposed truncated Shiryaev–Roberts (TSR) test as the exactly optimal rule for the survival-weighted average problem. The results have further revealed a natural and interpretable connection to classical sequential detection procedures: when the admissible window is ξ = 1 \xi= 1 ξ = 1 , the optimal rule reduces to the classical Shewhart test, corresponding to the requirement of detecting the change immediately upon its onset. In this case, the Shewhart test is also exactly optimal under the Pollak- and Lorden-type minimax criteria. The case ξ = 2 \xi= 2 ξ = 2 provides the first nontrivial extension and illustrates explicitly how the optimal rule departs from a purely myopic likelihood-ratio threshold. More generally, the analysis has shown that enlarging the admissible detection window transforms the decision rule from an instantaneous test into a structured, finite-memory, infinite-horizon stopping rule that combines evidence from several recent samples. For ξ ≥ 2 \xi\ge2 ξ ≥ 2 , we do not claim finite-sample exact minimax optimality of the state-dependent TSR rule; instead, the Pollak- and Lorden-type criteria provide complementary worst-case guarantees. We further showed that a simpler constant-boundary TSR procedure is asymptotically minimax optimal under both criteria when the admissible window grows beyond the information-accumulation scale log ϵ / D K L ( F 1 ∥ F 0 ) \log\epsilon/D_{\mathrm{KL}}(F_1\Vert F_0) log ϵ / D KL ( F 1 ∥ F 0 ) .
These findings suggest several directions for future work, including extensions to settings with unknown pre- and post-change distributions, overlapping or dependent transient periods, composite and nonparametric models, and decentralized or high-dimensional observation structures, as well as scalable approximations for computing the state-dependent boundary for large admissible windows.
Proof of Lemma 1
For each γ ≥ 1 \gamma\ge1 γ ≥ 1 , the event { τ ≥ γ } \{\tau\ge\gamma\} { τ ≥ γ } is F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 -measurable, and P γ ξ \mathbb{P}_{\gamma}^{\xi} P γ ξ and P ∞ \mathbb{P}_{\infty} P ∞ coincide on F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 . Hence,
P ∞ ( τ ≥ γ ) p γ ξ ( τ ) = P γ ξ ( γ ≤ τ < γ + ξ ) . (124) \mathbb{P}_{\infty}(\tau\ge\gamma)p_{\gamma}^{\xi}(\tau) = \mathbb{P}_{\gamma}^{\xi}(\gamma\le\tau< \gamma+\xi). \tag*{(124)} P ∞ ( τ ≥ γ ) p γ ξ ( τ ) = P γ ξ ( γ ≤ τ < γ + ξ ) . (124)
Decomposing according to the stopping time gives
P γ ξ ( γ ≤ τ < γ + ξ ) = ∑ k = 1 ξ P γ ξ ( τ = γ + k − 1 ) (125) \mathbb{P}_{\gamma}^{\xi}(\gamma\le\tau< \gamma+\xi) = \sum_{k=1}^{\xi}\mathbb{P}_{\gamma}^{\xi}(\tau=\gamma+k-1) \tag*{(125)} P γ ξ ( γ ≤ τ < γ + ξ ) = k = 1 ∑ ξ P γ ξ ( τ = γ + k − 1 ) (125)
= ∑ k = 1 ξ E ∞ [ ( ∏ j = 0 k − 1 ℓ γ + j ) 1 { τ = γ + k − 1 } ] . (126) = \sum_{k=1}^{\xi}\mathbb{E}_{\infty}\left[\left(\prod_{j=0}^{k-1}\ell_{\gamma+j}\right)\mathbf{1}_{\{\tau=\gamma+k-1\}}\right]. \tag*{(126)} = k = 1 ∑ ξ E ∞ [ ( j = 0 ∏ k − 1 ℓ γ + j ) 1 { τ = γ + k − 1 } ] . (126)
Summing over γ ≥ 1 \gamma\ge1 γ ≥ 1 and applying Tonelli’s theorem,
∑ γ = 1 ∞ P ∞ ( τ ≥ γ ) p γ ξ ( τ ) = E ∞ [ ∑ k = 1 ξ ∑ γ = 1 ∞ ( ∏ j = 0 k − 1 ℓ γ + j ) 1 { τ = γ + k − 1 } ] . (127) \sum_{\gamma=1}^{\infty}\mathbb{P}_{\infty}(\tau\ge\gamma)p_{\gamma}^{\xi}(\tau) = \mathbb{E}_{\infty}\left[\sum_{k=1}^{\xi}\sum_{\gamma=1}^{\infty}\left(\prod_{j=0}^{k-1}\ell_{\gamma+j}\right)\mathbf{1}_{\{\tau=\gamma+k-1\}}\right]. \tag*{(127)} γ = 1 ∑ ∞ P ∞ ( τ ≥ γ ) p γ ξ ( τ ) = E ∞ [ k = 1 ∑ ξ γ = 1 ∑ ∞ ( j = 0 ∏ k − 1 ℓ γ + j ) 1 { τ = γ + k − 1 } ] . (127)
For each fixed k k k , setting t = γ + k − 1 t=\gamma+k-1 t = γ + k − 1 and noting that γ ≥ 1 \gamma\ge1 γ ≥ 1 is equivalent to t ≥ k t \ge k t ≥ k , we obtain
∑ γ = 1 ∞ ( ∏ j = 0 k − 1 ℓ γ + j ) 1 { τ = γ + k − 1 } = 1 { τ ≥ k } ∏ j = 0 k − 1 ℓ τ − j . (128) \sum_{\gamma=1}^{\infty}\left(\prod_{j=0}^{k-1}\ell_{\gamma+j}\right)\mathbf{1}_{\{\tau=\gamma+k-1\}} = \mathbf{1}_{\{\tau\ge k\}}\prod_{j=0}^{k-1}\ell_{\tau-j}. \tag*{(128)} γ = 1 ∑ ∞ ( j = 0 ∏ k − 1 ℓ γ + j ) 1 { τ = γ + k − 1 } = 1 { τ ≥ k } j = 0 ∏ k − 1 ℓ τ − j . (128)
Therefore,
∑ γ = 1 ∞ P ∞ ( τ ≥ γ ) p γ ξ ( τ ) = E ∞ [ ∑ k = 1 ξ 1 { τ ≥ k } ∏ j = 0 k − 1 ℓ τ − j ] (129) \sum_{\gamma=1}^{\infty}\mathbb{P}_{\infty}(\tau\ge\gamma)p_{\gamma}^{\xi}(\tau) = \mathbb{E}_{\infty}\left[\sum_{k=1}^{\xi}\mathbf{1}_{\{\tau\ge k\}}\prod_{j=0}^{k-1}\ell_{\tau-j}\right] \tag*{(129)} γ = 1 ∑ ∞ P ∞ ( τ ≥ γ ) p γ ξ ( τ ) = E ∞ [ k = 1 ∑ ξ 1 { τ ≥ k } j = 0 ∏ k − 1 ℓ τ − j ] (129)
= E ∞ [ W τ ( ξ ) ] . (130) = \mathbb{E}_{\infty}\left[W_{\tau}^{(\xi)}\right]. \tag*{(130)} = E ∞ [ W τ ( ξ ) ] . (130)
Finally, the tail-sum identity gives
∑ γ = 1 ∞ P ∞ ( τ ≥ γ ) = E ∞ [ τ ] . (131) \sum_{\gamma=1}^{\infty}\mathbb{P}_{\infty}(\tau\ge\gamma)=\mathbb{E}_{\infty}[\tau]. \tag*{(131)} γ = 1 ∑ ∞ P ∞ ( τ ≥ γ ) = E ∞ [ τ ] . (131)
Dividing the preceding identity by E ∞ [ τ ] \mathbb{E}_{\infty}[\tau] E ∞ [ τ ] and using the definitions of w γ ( τ ) w_{\gamma}(\tau) w γ ( τ ) and A ξ ( τ ) A_{\xi}(\tau) A ξ ( τ ) proves the result.
Proof of Theorem 1
For each γ ∈ N \gamma\in\mathbb{N} γ ∈ N , let P γ \mathbb{P}_{\gamma} P γ denote the local (window-2) post-change law under which X γ X_{\gamma} X γ and X γ + 1 X_{\gamma+1} X γ + 1 have density f 1 f_{1} f 1 and all other X t X_{t} X t have density f 0 f_{0} f 0 , and all X t X_{t} X t are independent. Then for any γ ∈ N \gamma\in\mathbb{N} γ ∈ N the measures P γ \mathbb{P}_{\gamma} P γ and P ∞ \mathbb{P}_{\infty} P ∞ coincide on F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 . Furthermore, due to independence of samples over time, for any F γ − \mathcal{F}_{\gamma-} F γ − and F γ + 1 − \mathcal{F}_{\gamma+1-} F γ + 1 − -measurable events A A A and B B B we have
P γ ( A ) = E ∞ [ ℓ γ 1 A ] , P γ ( B ) = E ∞ [ ℓ γ ℓ γ + 1 1 B ] . (132) \mathbb{P}_{\gamma}(A)=\mathbb{E}_{\infty}\left[\ell_{\gamma}1_{A}\right], \qquad\mathbb{P}_{\gamma}(B)=\mathbb{E}_{\infty}\left[\ell_{\gamma}\ell_{\gamma+1}1_{B}\right]. \tag*{(132)} P γ ( A ) = E ∞ [ ℓ γ 1 A ] , P γ ( B ) = E ∞ [ ℓ γ ℓ γ + 1 1 B ] . (132)
Step 1: Bound the Pollak-like criterion for s = 1 s=1 s = 1 . We first treat the setting s = 1 s=1 s = 1 . For ξ = 2 \xi=2 ξ = 2 , the Pollak-like criterion (7) reduces to
L P ( τ ) = inf γ ≥ 1 P γ ( τ ∈ { γ , γ + 1 } ∣ τ ≥ γ ) . (133) \mathcal{L}_{\mathrm{P}}(\tau)=\inf_{\gamma\ge1}\mathbb{P}_{\gamma}(\tau\in\{\gamma,\gamma+1\}\mid\tau\ge\gamma). \tag*{(133)} L P ( τ ) = γ ≥ 1 inf P γ ( τ ∈ { γ , γ + 1 } ∣ τ ≥ γ ) . (133)
Fix γ ≥ 1 \gamma\ge1 γ ≥ 1 . Dropping the infimum in (133) yields
L P ( τ ) ≤ P γ ( τ ∈ { γ , γ + 1 } ∣ τ ≥ γ ) . (134) \mathcal{L}_{\mathrm{P}}(\tau)\le\mathbb{P}_{\gamma}(\tau\in\{\gamma,\gamma+1\}\mid\tau\ge\gamma). \tag*{(134)} L P ( τ ) ≤ P γ ( τ ∈ { γ , γ + 1 } ∣ τ ≥ γ ) . (134)
Multiplying both sides by P γ ( τ ≥ γ ) \mathbb{P}_{\gamma}(\tau\ge\gamma) P γ ( τ ≥ γ ) and using the definition of conditional probability, we obtain
P γ ( τ ≥ γ ) L P ( τ ) ≤ P γ ( τ = γ ) + P γ ( τ = γ + 1 ) . (135) \mathbb{P}_{\gamma}(\tau\ge\gamma)\mathcal{L}_{\mathrm{P}}(\tau)\le\mathbb{P}_{\gamma}(\tau=\gamma)+\mathbb{P}_{\gamma}(\tau=\gamma+1). \tag*{(135)} P γ ( τ ≥ γ ) L P ( τ ) ≤ P γ ( τ = γ ) + P γ ( τ = γ + 1 ) . (135)
Since { τ ≥ γ } ∈ F γ − 1 \{\tau\ge\gamma\}\in\mathcal{F}_{\gamma-1} { τ ≥ γ } ∈ F γ − 1 (because τ \tau τ is a stopping time) and P γ \mathbb{P}_{\gamma} P γ and P ∞ \mathbb{P}_{\infty} P ∞ coincide on F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 ,
P γ ( τ ≥ γ ) = P ∞ ( τ ≥ γ ) . (136) \mathbb{P}_{\gamma}(\tau\ge\gamma)=\mathbb{P}_{\infty}(\tau\ge\gamma). \tag*{(136)} P γ ( τ ≥ γ ) = P ∞ ( τ ≥ γ ) . (136)
Furthermore, { τ = γ } ∈ F γ \{\tau=\gamma\}\in\mathcal{F}_{\gamma} { τ = γ } ∈ F γ and { τ = γ + 1 } ∈ F γ + 1 \{\tau=\gamma+1\}\in\mathcal{F}_{\gamma+1} { τ = γ + 1 } ∈ F γ + 1 , so (132) gives
P γ ( τ = γ ) = E ∞ [ ℓ γ 1 { τ = γ } ] , P γ ( τ = γ + 1 ) = E ∞ [ ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (137) \mathbb{P}_{\gamma}(\tau=\gamma)=\mathbb{E}_{\infty}\left[\ell_{\gamma}1_{\{\tau=\gamma\}}\right], \qquad\mathbb{P}_{\gamma}(\tau=\gamma+1)=\mathbb{E}_{\infty}\left[\ell_{\gamma}\ell_{\gamma+1}1_{\{\tau=\gamma+1\}}\right]. \tag*{(137)} P γ ( τ = γ ) = E ∞ [ ℓ γ 1 { τ = γ } ] , P γ ( τ = γ + 1 ) = E ∞ [ ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (137)
Substituting these identities into (135) yields, for every γ ≥ 1 \gamma\ge1 γ ≥ 1 ,
P ∞ ( τ ≥ γ ) L P ( τ ) ≤ E ∞ [ ℓ γ 1 { τ = γ } + ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (138) \mathbb{P}_{\infty}(\tau\ge\gamma)\mathcal{L}_{\mathrm{P}}(\tau)\le\mathbb{E}_{\infty}\left[\ell_{\gamma}1_{\{\tau=\gamma\}}+\ell_{\gamma}\ell_{\gamma+1}1_{\{\tau=\gamma+1\}}\right]. \tag*{(138)} P ∞ ( τ ≥ γ ) L P ( τ ) ≤ E ∞ [ ℓ γ 1 { τ = γ } + ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (138)
Summing (138) over γ ≥ 1 \gamma\ge1 γ ≥ 1 and using the identity τ = ∑ γ ≥ 1 1 { τ ≥ γ } \tau=\sum_{\gamma\ge1}1_{\{\tau\ge\gamma\}} τ = ∑ γ ≥ 1 1 { τ ≥ γ } (hence E ∞ [ τ ] = ∑ γ ≥ 1 P ∞ ( τ ≥ γ ) \mathbb{E}_{\infty}[\tau]=\sum_{\gamma\ge1}\mathbb{P}_{\infty}(\tau\ge\gamma) E ∞ [ τ ] = ∑ γ ≥ 1 P ∞ ( τ ≥ γ ) ), we obtain
E ∞ [ τ ] L P ( τ ) ≤ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] . (139) \mathbb{E}_{\infty}[\tau]\mathcal{L}_{\mathrm{P}}(\tau)\le\mathbb{E}_{\infty}\left[\ell_{\tau}+\ell_{\tau-1}\ell_{\tau}\right]. \tag*{(139)} E ∞ [ τ ] L P ( τ ) ≤ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] . (139)
Therefore, for s = 1 s=1 s = 1 ,
L P ( τ ) ≤ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] E ∞ [ τ ] , (140) \mathcal{L}_{\mathrm{P}}(\tau)\le\frac{\mathbb{E}_{\infty}\left[\ell_{\tau}+\ell_{\tau-1}\ell_{\tau}\right]}{\mathbb{E}_{\infty}[\tau]}, \tag*{(140)} L P ( τ ) ≤ E ∞ [ τ ] E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] , (140)
where we use the convention ℓ 0 = 0 \ell_{0}=0 ℓ 0 = 0 so that ℓ τ − 1 ℓ τ = 0 \ell_{\tau-1}\ell_{\tau}=0 ℓ τ − 1 ℓ τ = 0 when τ = 1 \tau=1 τ = 1 .
Step 2: Bound the Lorden-like criterion for s = 1 s = 1 s = 1 . For ξ = 2 \xi= 2 ξ = 2 and s = 1 s = 1 s = 1 , the Lorden-like criterion (8) reduces to
L L ( τ ) = inf γ ≥ 1 ess inf F γ − 1 P γ ( τ ∈ { γ , γ + 1 } ∣ F γ − 1 , τ ≥ γ ) . (141) \mathcal{L}_{\mathrm{L}}(\tau) = \inf_{\gamma\ge1} \operatorname*{ess\,inf}_{\mathcal{F}_{\gamma-1}} \mathbb{P}_{\gamma}\left(\tau\in\{\gamma,\gamma+1\} \mid\mathcal{F}_{\gamma-1},\tau\ge\gamma\right). \tag*{(141)} L L ( τ ) = γ ≥ 1 inf F γ − 1 ess inf P γ ( τ ∈ { γ , γ + 1 } ∣ F γ − 1 , τ ≥ γ ) . (141)
Fix γ ≥ 1 \gamma\ge1 γ ≥ 1 and define the F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 –measurable random variable
π γ ≜ P γ ( τ ∈ { γ , γ + 1 } ∣ F γ − 1 , τ ≥ γ ) . (142) \pi_{\gamma} \triangleq\mathbb{P}_{\gamma}\left(\tau\in\{\gamma,\gamma+1\} \mid\mathcal{F}_{\gamma-1},\tau\ge\gamma\right). \tag*{(142)} π γ ≜ P γ ( τ ∈ { γ , γ + 1 } ∣ F γ − 1 , τ ≥ γ ) . (142)
We adopt the convention that π γ = 0 \pi_{\gamma} = 0 π γ = 0 on { τ < γ } \{\tau< \gamma\} { τ < γ } . Let
a γ ≜ ess inf F γ − 1 π γ . (143) a_{\gamma} \triangleq\operatorname*{ess\,inf}_{\mathcal{F}_{\gamma-1}} \pi_{\gamma}. \tag*{(143)} a γ ≜ F γ − 1 ess inf π γ . (143)
By definition of the essential infimum, a γ ≤ π γ a_{\gamma} \le\pi_{\gamma} a γ ≤ π γ P γ \mathbb{P}_{\gamma} P γ –a.s., and hence P ∞ \mathbb{P}_{\infty} P ∞ –a.s. (because P γ \mathbb{P}_{\gamma} P γ and P ∞ \mathbb{P}_{\infty} P ∞ coincide on F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 ). Furthermore, by definition of L L ( τ ) \mathcal{L}_{\mathrm{L}}(\tau) L L ( τ ) as an infimum over γ \gamma γ , we have L L ( τ ) ≤ a γ \mathcal{L}_{\mathrm{L}}(\tau) \le a_{\gamma} L L ( τ ) ≤ a γ for every γ \gamma γ , hence
1 { τ ≥ γ } L L ( τ ) ≤ 1 { τ ≥ γ } π γ P ∞ -a.s. (144) \mathbb{1}\{\tau\ge\gamma\}\mathcal{L}_{\mathrm{L}}(\tau) \le\mathbb{1}\{\tau\ge\gamma\}\pi_{\gamma}\qquad\mathbb{P}_{\infty}\text{-a.s.} \tag*{(144)} 1 { τ ≥ γ } L L ( τ ) ≤ 1 { τ ≥ γ } π γ P ∞ -a.s. (144)
Next, take the expectation of (144) . Since 1 { τ ≥ γ } \mathbb{1}\{\tau\ge\gamma\} 1 { τ ≥ γ } is F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 –measurable and P γ \mathbb{P}_{\gamma} P γ and P ∞ \mathbb{P}_{\infty} P ∞ coincide on F γ − 1 \mathcal{F}_{\gamma-1} F γ − 1 ,
E ∞ [ 1 { τ ≥ γ } π γ ] = E γ [ 1 { τ ≥ γ } π γ ] = P γ ( τ ∈ { γ , γ + 1 } ) , (145) \mathbb{E}_{\infty}\left[\mathbb{1}\{\tau\ge\gamma\}\pi_{\gamma}\right] = \mathbb{E}_{\gamma}\left[\mathbb{1}\{\tau\ge\gamma\}\pi_{\gamma}\right] = \mathbb{P}_{\gamma}\left(\tau\in\{\gamma,\gamma+1\}\right), \tag*{(145)} E ∞ [ 1 { τ ≥ γ } π γ ] = E γ [ 1 { τ ≥ γ } π γ ] = P γ ( τ ∈ { γ , γ + 1 } ) , (145)
where the last equality is the defining property of conditional probability. Using (132) we obtain
E ∞ [ 1 { τ ≥ γ } π γ ] = E ∞ [ ℓ γ 1 { τ = γ } + ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (146) \mathbb{E}_{\infty}\left[\mathbb{1}\{\tau\ge\gamma\}\pi_{\gamma}\right] = \mathbb{E}_{\infty}\left[\ell_{\gamma}\mathbb{1}\{\tau= \gamma\} + \ell_{\gamma}\ell_{\gamma+1}\mathbb{1}\{\tau= \gamma+1\}\right]. \tag*{(146)} E ∞ [ 1 { τ ≥ γ } π γ ] = E ∞ [ ℓ γ 1 { τ = γ } + ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (146)
Therefore (144) –(146) imply that for every γ ≥ 1 \gamma\ge1 γ ≥ 1 ,
P ∞ ( τ ≥ γ ) L L ( τ ) ≤ E ∞ [ ℓ γ 1 { τ = γ } + ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (147) \mathbb{P}_{\infty}(\tau\ge\gamma)\mathcal{L}_{\mathrm{L}}(\tau) \le\mathbb{E}_{\infty}\left[\ell_{\gamma}\mathbb{1}\{\tau= \gamma\} + \ell_{\gamma}\ell_{\gamma+1}\mathbb{1}\{\tau= \gamma+1\}\right]. \tag*{(147)} P ∞ ( τ ≥ γ ) L L ( τ ) ≤ E ∞ [ ℓ γ 1 { τ = γ } + ℓ γ ℓ γ + 1 1 { τ = γ + 1 } ] . (147)
Summing over γ ≥ 1 \gamma\ge1 γ ≥ 1 yields
E ∞ [ τ ] L L ( τ ) ≤ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] , (148) \mathbb{E}_{\infty}[\tau]\mathcal{L}_{\mathrm{L}}(\tau) \le\mathbb{E}_{\infty}\left[\ell_{\tau}+\ell_{\tau-1}\ell_{\tau}\right], \tag*{(148)} E ∞ [ τ ] L L ( τ ) ≤ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] , (148)
and hence L L ( τ ) ≤ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] / E ∞ [ τ ] \mathcal{L}_{\mathrm{L}}(\tau) \le\mathbb{E}_{\infty}[\ell_{\tau}+\ell_{\tau-1}\ell_{\tau}]/\mathbb{E}_{\infty}[\tau] L L ( τ ) ≤ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] / E ∞ [ τ ] .
Step 3: Extension to s ≥ 1 s \ge1 s ≥ 1 . For ξ = 2 \xi= 2 ξ = 2 , the criteria (7) and (8) are sums over i ∈ { 1 , … , s } i \in\{1,\ldots,s\} i ∈ { 1 , … , s } of window-2 success terms. Applying the preceding s = 1 s = 1 s = 1 bounds to each summand (corresponding to each onset time γ i \gamma_i γ i ) and noting that the right-hand side depends only on τ \tau τ , we obtain
L P ( τ ) ≤ s ⋅ E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] E ∞ [ τ ] . (149) \mathcal{L}_{\mathrm{P}}(\tau) \le s \cdot\frac{\mathbb{E}_{\infty}\left[\ell_{\tau}+\ell_{\tau-1}\ell_{\tau}\right]}{\mathbb{E}_{\infty}[\tau]}. \tag*{(149)} L P ( τ ) ≤ s ⋅ E ∞ [ τ ] E ∞ [ ℓ τ + ℓ τ − 1 ℓ τ ] . (149)
Moreover, since L L ( τ ) ≤ L P ( τ ) \mathcal{L}_{\mathrm{L}}(\tau) \le\mathcal{L}_{\mathrm{P}}(\tau) L L ( τ ) ≤ L P ( τ ) by definition (cf. the discussion following (8)), the same bound applies to L L ( τ ) \mathcal{L}_{\mathrm{L}}(\tau) L L ( τ ) . This completes the proof.
Proof of Lemma 2
Throughout Appendices C–G, we use the shorthand W t = W t ( 2 ) W_t = W_t^{(2)} W t = W t ( 2 ) . Let ν ∈ T \nu\in\mathcal{T} ν ∈ T be a feasible stopping time, i.e., E ∞ [ ν ] ≥ ε \mathbb{E}_{\infty}[\nu] \ge\varepsilon E ∞ [ ν ] ≥ ε and E ∞ [ ν ] < ∞ \mathbb{E}_{\infty}[\nu] < \infty E ∞ [ ν ] < ∞ . Recall the likelihood ratio ℓ t = f 1 ( X t ) / f 0 ( X t ) \ell_t = f_1(X_t)/f_0(X_t) ℓ t = f 1 ( X t ) / f 0 ( X t ) and the convention ℓ 0 = 0 \ell_0 = 0 ℓ 0 = 0 . For convenience, define
W t ≜ ℓ t + ℓ t − 1 ℓ t , t ∈ N , W 0 ≜ 0. (150) W_t \triangleq\ell_t + \ell_{t-1}\ell_t,\qquad t \in\mathbb{N},\qquad W_0 \triangleq0. \tag*{(150)} W t ≜ ℓ t + ℓ t − 1 ℓ t , t ∈ N , W 0 ≜ 0. (150)
Let π 0 ≜ P ∞ ( ν = 0 ) \pi_0 \triangleq\mathbb{P}_{\infty}(\nu= 0) π 0 ≜ P ∞ ( ν = 0 ) . Then
E ∞ [ W ν ] = ( 1 − π 0 ) E ∞ [ W ν ∣ ν > 0 ] , E ∞ [ ν ] = ( 1 − π 0 ) E ∞ [ ν ∣ ν > 0 ] , (151) \mathbb{E}_{\infty}[W_\nu] = (1-\pi_0)\mathbb{E}_{\infty}[W_\nu\mid\nu> 0],\qquad\mathbb{E}_{\infty}[\nu] = (1-\pi_0)\mathbb{E}_{\infty}[\nu\mid\nu> 0], \tag*{(151)} E ∞ [ W ν ] = ( 1 − π 0 ) E ∞ [ W ν ∣ ν > 0 ] , E ∞ [ ν ] = ( 1 − π 0 ) E ∞ [ ν ∣ ν > 0 ] , (151)
and hence
E ∞ [ W ν ] E ∞ [ ν ] = E ∞ [ W ν ∣ ν > 0 ] E ∞ [ ν ∣ ν > 0 ] . (152) \frac{\mathbb{E}_{\infty}[W_\nu]}{\mathbb{E}_{\infty}[\nu]} = \frac{\mathbb{E}_{\infty}[W_\nu\mid\nu> 0]}{\mathbb{E}_{\infty}[\nu\mid\nu> 0]}. \tag*{(152)} E ∞ [ ν ] E ∞ [ W ν ] = E ∞ [ ν ∣ ν > 0 ] E ∞ [ W ν ∣ ν > 0 ] . (152)
If E ∞ [ ν ] = ε \mathbb{E}_{\infty}[\nu] = \varepsilon E ∞ [ ν ] = ε , we simply set ν ′ = ν \nu' = \nu ν ′ = ν and we are done. Otherwise, since ν \nu ν is feasible and E ∞ [ ν ] < ∞ \mathbb{E}_{\infty}[\nu] < \infty E ∞ [ ν ] < ∞ , we have E ∞ [ ν ] > ε \mathbb{E}_{\infty}[\nu] > \varepsilon E ∞ [ ν ] > ε . Define
p ≜ 1 − ε E ∞ [ ν ] ∈ ( 0 , 1 ) . (153) p \triangleq1 - \frac{\varepsilon}{\mathbb{E}_{\infty}[\nu]} \in(0,1). \tag*{(153)} p ≜ 1 − E ∞ [ ν ] ε ∈ ( 0 , 1 ) . (153)
Let B ∼ Bernoulli ( p ) B \sim\operatorname{Bernoulli}(p) B ∼ Bernoulli ( p ) be independent of { X t } t ∈ N \{X_t\}_{t \in\mathbb{N}} { X t } t ∈ N (equivalently, measurable at time 0 under an external randomization). Construct the randomized stopping time
ν ′ ≜ { 0 , B = 1 , ν , B = 0. (154) \nu' \triangleq
\begin{cases}
0, & B = 1,\\
\nu, & B = 0.
\end{cases} \tag*{(154)} ν ′ ≜ { 0 , ν , B = 1 , B = 0. (154)
Then ν ′ \nu' ν ′ is a (randomized) stopping time with respect to the filtration augmented by σ ( B ) \sigma(B) σ ( B ) , and it satisfies the following two properties.
ARL constraint with equality: Since B B B is independent of ν \nu ν and ν ′ ≡ ν \nu' \equiv\nu ν ′ ≡ ν on { B = 0 } \{B = 0\} { B = 0 } ,
E ∞ [ ν ′ ] = ( 1 − p ) E ∞ [ ν ] = ε . (155) \mathbb{E}_{\infty}[\nu'] = (1-p)\mathbb{E}_{\infty}[\nu] = \varepsilon. \tag*{(155)} E ∞ [ ν ′ ] = ( 1 − p ) E ∞ [ ν ] = ε . (155)
Ratio preservation: Using W 0 = 0 W_0 = 0 W 0 = 0 and independence of B B B ,
E ∞ [ W ν ′ ] = ( 1 − p ) E ∞ [ W ν ] , (156) \mathbb{E}_{\infty}[W_{\nu'}] = (1-p)\mathbb{E}_{\infty}[W_\nu], \tag*{(156)} E ∞ [ W ν ′ ] = ( 1 − p ) E ∞ [ W ν ] , (156)
and therefore
E ∞ [ W ν ′ ] E ∞ [ ν ′ ] = ( 1 − p ) E ∞ [ W ν ] ( 1 − p ) E ∞ [ ν ] = E ∞ [ W ν ] E ∞ [ ν ] . (157) \frac{\mathbb{E}_{\infty}[W_{\nu'}]}{\mathbb{E}_{\infty}[\nu']} = \frac{(1-p)\mathbb{E}_{\infty}[W_\nu]}{(1-p)\mathbb{E}_{\infty}[\nu]} = \frac{\mathbb{E}_{\infty}[W_\nu]}{\mathbb{E}_{\infty}[\nu]}. \tag*{(157)} E ∞ [ ν ′ ] E ∞ [ W ν ′ ] = ( 1 − p ) E ∞ [ ν ] ( 1 − p ) E ∞ [ W ν ] = E ∞ [ ν ] E ∞ [ W ν ] . (157)
Recalling W τ = ℓ τ + ℓ τ − 1 ℓ τ W_\tau= \ell_\tau+ \ell_{\tau-1}\ell_\tau W τ = ℓ τ + ℓ τ − 1 ℓ τ , (157) is exactly (29).
The properties (155)–(157) establish that ν ′ \nu' ν ′ is feasible with E ∞ [ ν ′ ] = ε \mathbb{E}_{\infty}[\nu'] = \varepsilon E ∞ [ ν ′ ] = ε and achieves the same performance ratio as ν \nu ν , completing the proof. Note that augmented filtration σ ( B ) \sigma(B) σ ( B ) does not violate the sequential nature of the test, since B B B is determined at time zero before any observations are processed.
Proof of Lemma 3
For notational brevity, write Q ~ = Q ~ 2 \widetilde{\mathcal{Q}} = \widetilde{\mathcal{Q}}_2 Q = Q 2 and V = V 2 \mathcal{V} = \mathcal{V}_2 V = V 2 . Recall the ARL-equality problem (cf. (30) )
Q ~ ( ε ) = sup τ : E ∞ [ τ ] = ε E ∞ [ W τ ] E ∞ [ τ ] = 1 ε sup τ : E ∞ [ τ ] = ε E ∞ [ W τ ] , (158) \widetilde{\mathcal{Q}}(\varepsilon) = \sup_{\tau: \mathbb{E}_{\infty}[\tau]=\varepsilon} \frac{\mathbb{E}_{\infty}[W_{\tau}]}{\mathbb{E}_{\infty}[\tau]} = \frac{1}{\varepsilon}\sup_{\tau: \mathbb{E}_{\infty}[\tau]=\varepsilon}\mathbb{E}_{\infty}[W_{\tau}], \tag*{(158)} Q ( ε ) = τ : E ∞ [ τ ] = ε sup E ∞ [ τ ] E ∞ [ W τ ] = ε 1 τ : E ∞ [ τ ] = ε sup E ∞ [ W τ ] , (158)
where W t ≜ ℓ t + ℓ t − 1 ℓ t W_t \triangleq\ell_t+\ell_{t-1}\ell_t W t ≜ ℓ t + ℓ t − 1 ℓ t for t ∈ N t\in\mathbb{N} t ∈ N and W 0 ≜ 0 W_0\triangleq0 W 0 ≜ 0 (under the convention ℓ 0 = 0 \ell_0=0 ℓ 0 = 0 ). Also recall the unconstrained Lagrangian value (cf. (31) )
V ( λ ) ≜ sup τ ∈ T E ∞ [ W τ − λ τ ] , λ > 0 , (159) \mathcal{V}(\lambda) \triangleq\sup_{\tau\in\mathcal{T}}\mathbb{E}_{\infty}[W_{\tau}-\lambda\tau],\qquad\lambda>0, \tag*{(159)} V ( λ ) ≜ τ ∈ T sup E ∞ [ W τ − λ τ ] , λ > 0 , (159)
where the supremum is over all τ ∈ T \tau\in\mathcal{T} τ ∈ T with P ∞ ( τ < ∞ ) = 1 \mathbb{P}_{\infty}(\tau<\infty)=1 P ∞ ( τ < ∞ ) = 1 . For given λ \lambda λ and ε \varepsilon ε define the dual function
ϕ ε ( λ ) ≜ λ + V ( λ ) ε . (160) \phi_{\varepsilon}(\lambda)\triangleq\lambda+\frac{\mathcal{V}(\lambda)}{\varepsilon}. \tag*{(160)} ϕ ε ( λ ) ≜ λ + ε V ( λ ) . (160)
To prove this lemma, we show two properties.
First, we show that for a fixed ε ≥ 1 \varepsilon\ge1 ε ≥ 1 , the function ϕ ε \phi_{\varepsilon} ϕ ε is convex, lower semicontinuous, and admits at least one minimizer λ ε > 0 \lambda_{\varepsilon}>0 λ ε > 0 .
Secondly, by defining ρ ≜ ϕ ε ( λ ε ) \rho\triangleq\phi_{\varepsilon}(\lambda_{\varepsilon}) ρ ≜ ϕ ε ( λ ε ) , we show that there exists a (possibly randomized) stopping time τ ∗ \tau^* τ ∗ such that
E ∞ [ τ ∗ ] = ε , E ∞ [ W τ ∗ ] E ∞ [ τ ∗ ] = ρ . (161) \mathbb{E}_{\infty}[\tau^*]=\varepsilon,\qquad\frac{\mathbb{E}_{\infty}[W_{\tau^*}]}{\mathbb{E}_{\infty}[\tau^*]}=\rho. \tag*{(161)} E ∞ [ τ ∗ ] = ε , E ∞ [ τ ∗ ] E ∞ [ W τ ∗ ] = ρ . (161)
Step 1: Existence of a minimizer. For each stopping time τ \tau τ , the map λ ↦ E ∞ [ W τ − λ τ ] \lambda\mapsto\mathbb{E}_{\infty}[W_{\tau}-\lambda\tau] λ ↦ E ∞ [ W τ − λ τ ] is affine. Hence V ( λ ) \mathcal{V}(\lambda) V ( λ ) is the pointwise supremum of affine functions, so V \mathcal{V} V is convex and nonincreasing in λ \lambda λ . Therefore, ϕ ε \phi_{\varepsilon} ϕ ε is convex and lower semicontinuous. Furthermore, since the trivial stopping time τ ≡ 0 \tau\equiv0 τ ≡ 0 belongs to T \mathcal{T} T and yields W 0 = 0 W_0=0 W 0 = 0 , we have V ( λ ) ≥ 0 \mathcal{V}(\lambda)\ge0 V ( λ ) ≥ 0 for all λ > 0 \lambda>0 λ > 0 . Hence,
ϕ ε ( λ ) ≥ λ → λ → ∞ + ∞ . (162) \phi_{\varepsilon}(\lambda)\ge\lambda\xrightarrow{\lambda\to\infty}+\infty. \tag*{(162)} ϕ ε ( λ ) ≥ λ λ → ∞ + ∞. (162)
Thus ϕ ε \phi_{\varepsilon} ϕ ε attains a finite minimum at some λ ε > 0 \lambda_{\varepsilon}>0 λ ε > 0 .
Step 2: Weak duality and attainment by (randomized) selection. Let τ \tau τ satisfy E ∞ [ τ ] = ε \mathbb{E}_{\infty}[\tau]=\varepsilon E ∞ [ τ ] = ε . Then for any λ > 0 \lambda>0 λ > 0 ,
E ∞ [ W τ ] ε = λ + E ∞ [ W τ − λ τ ] ε ≤ λ + V ( λ ) ε = ϕ ε ( λ ) . (163) \frac{\mathbb{E}_{\infty}[W_{\tau}]}{\varepsilon}=\lambda+\frac{\mathbb{E}_{\infty}[W_{\tau}-\lambda\tau]}{\varepsilon}\le\lambda+\frac{\mathcal{V}(\lambda)}{\varepsilon}=\phi_{\varepsilon}(\lambda). \tag*{(163)} ε E ∞ [ W τ ] = λ + ε E ∞ [ W τ − λ τ ] ≤ λ + ε V ( λ ) = ϕ ε ( λ ) . (163)
Taking the supremum over such τ \tau τ and then the infimum over λ > 0 \lambda>0 λ > 0 gives
sup τ : E ∞ [ τ ] = ε E ∞ [ W τ ] ε ≤ inf λ > 0 ϕ ε ( λ ) = ρ . (164) \sup_{\tau:\mathbb{E}_{\infty}[\tau]=\varepsilon}\frac{\mathbb{E}_{\infty}[W_{\tau}]}{\varepsilon}\le\inf_{\lambda>0}\phi_{\varepsilon}(\lambda)=\rho. \tag*{(164)} τ : E ∞ [ τ ] = ε sup ε E ∞ [ W τ ] ≤ λ > 0 inf ϕ ε ( λ ) = ρ . (164)
Now fix a minimizer λ ε \lambda_{\varepsilon} λ ε . Let A ( λ ε ) \mathcal{A}(\lambda_{\varepsilon}) A ( λ ε ) denote the set of optimizers of V ( λ ε ) \mathcal{V}(\lambda_{\varepsilon}) V ( λ ε ) , i.e.,
A ( λ ε ) ≜ { τ ∈ T : E ∞ [ W τ − λ ε τ ] = V ( λ ε ) } . (165) \mathcal{A}(\lambda_{\varepsilon}) \triangleq\left\{ \tau\in\mathcal{T}: \mathbb{E}_{\infty}[W_{\tau}-\lambda_{\varepsilon}\tau]=\mathcal{V}(\lambda_{\varepsilon}) \right\}. \tag*{(165)} A ( λ ε ) ≜ { τ ∈ T : E ∞ [ W τ − λ ε τ ] = V ( λ ε ) } . (165)
Standard optimal stopping arguments imply A ( λ ε ) ≠ ∅ \mathcal{A}(\lambda_{\varepsilon})\ne\varnothing A ( λ ε ) = ∅ . In particular, V ( λ ε ) \mathcal{V}(\lambda_{\varepsilon}) V ( λ ε ) is attained by an optimal stopping time. For any τ ∈ A ( λ ε ) \tau\in\mathcal{A}(\lambda_{\varepsilon}) τ ∈ A ( λ ε ) , define D τ ≜ E ∞ [ τ ] D_{\tau}\triangleq\mathbb{E}_{\infty}[\tau] D τ ≜ E ∞ [ τ ] and N τ ≜ E ∞ [ W τ ] N_{\tau}\triangleq\mathbb{E}_{\infty}[W_{\tau}] N τ ≜ E ∞ [ W τ ] . Then N τ − λ ε D τ = V ( λ ε ) N_{\tau}-\lambda_{\varepsilon}D_{\tau}=\mathcal{V}(\lambda_{\varepsilon}) N τ − λ ε D τ = V ( λ ε ) for all τ ∈ A ( λ ε ) \tau\in\mathcal{A}(\lambda_{\varepsilon}) τ ∈ A ( λ ε ) . Accordingly, consider the affine functions
f τ ( λ ) ≜ λ + N τ − λ D τ ε = ( 1 − D τ ε ) λ + N τ ε . (166) f_{\tau}(\lambda)\triangleq\lambda+\frac{N_{\tau}-\lambda D_{\tau}}{\varepsilon}=\left(1-\frac{D_{\tau}}{\varepsilon}\right)\lambda+\frac{N_{\tau}}{\varepsilon}. \tag*{(166)} f τ ( λ ) ≜ λ + ε N τ − λ D τ = ( 1 − ε D τ ) λ + ε N τ . (166)
Then ϕ ε ( λ ) = sup τ ∈ T f τ ( λ ) \phi_{\varepsilon}(\lambda)=\sup_{\tau\in\mathcal{T}}f_{\tau}(\lambda) ϕ ε ( λ ) = sup τ ∈ T f τ ( λ ) , and the active set at λ ε \lambda_{\varepsilon} λ ε coincides with A ( λ ε ) \mathcal{A}(\lambda_{\varepsilon}) A ( λ ε ) (since f τ ( λ ε ) = ϕ ε ( λ ε ) f_{\tau}(\lambda_{\varepsilon})=\phi_{\varepsilon}(\lambda_{\varepsilon}) f τ ( λ ε ) = ϕ ε ( λ ε ) if and only if N τ − λ ε D τ = V ( λ ε ) N_{\tau}-\lambda_{\varepsilon}D_{\tau}=\mathcal{V}(\lambda_{\varepsilon}) N τ − λ ε D τ = V ( λ ε ) ). Because ϕ ε \phi_{\varepsilon} ϕ ε is convex and minimized at λ ε \lambda_{\varepsilon} λ ε , 0 0 0 belongs to the subdifferential ∂ ϕ ε ( λ ε ) \partial\phi_{\varepsilon}(\lambda_{\varepsilon}) ∂ ϕ ε ( λ ε ) , which is the convex hull of the active slopes. Equivalently, letting
m τ ≜ 1 − D τ ε , τ ∈ A ( λ ε ) , (167) m_{\tau}\triangleq1-\frac{D_{\tau}}{\varepsilon},\qquad\tau\in\mathcal{A}(\lambda_{\varepsilon}), \tag*{(167)} m τ ≜ 1 − ε D τ , τ ∈ A ( λ ε ) , (167)
we must have that the active slopes straddle 0 0 0 ; i.e., letting m min ≜ inf τ ∈ A ( λ ε ) m τ m_{\min}\triangleq\inf_{\tau\in\mathcal{A}(\lambda_{\varepsilon})}m_{\tau} m m i n ≜ inf τ ∈ A ( λ ε ) m τ and m max ≜ sup τ ∈ A ( λ ε ) m τ m_{\max}\triangleq\sup_{\tau\in\mathcal{A}(\lambda_{\varepsilon})}m_{\tau} m m a x ≜ sup τ ∈ A ( λ ε ) m τ , we have m min ≤ 0 ≤ m max m_{\min}\le0\le m_{\max} m m i n ≤ 0 ≤ m m a x . If there exists τ ˉ ∈ A ( λ ε ) \bar{\tau}\in\mathcal{A}(\lambda_{\varepsilon}) τ ˉ ∈ A ( λ ε ) with m τ ˉ = 0 m_{\bar{\tau}}=0 m τ ˉ = 0 , then D τ ˉ = ε D_{\bar{\tau}}=\varepsilon D τ ˉ = ε and we may take τ ⋆ = τ ˉ \tau^{\star}=\bar{\tau} τ ⋆ = τ ˉ . Otherwise choose τ 1 , τ 2 ∈ A ( λ ε ) \tau_{1},\tau_{2}\in\mathcal{A}(\lambda_{\varepsilon}) τ 1 , τ 2 ∈ A ( λ ε ) with m τ 1 > 0 m_{\tau_{1}}>0 m τ 1 > 0 and m τ 2 < 0 m_{\tau_{2}}<0 m τ 2 < 0 , and pick α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) such that
α m τ 1 + ( 1 − α ) m τ 2 = 0 ⟺ α D τ 1 + ( 1 − α ) D τ 2 = ε . (168) \alpha m_{\tau_{1}}+(1-\alpha)m_{\tau_{2}}=0\quad\Longleftrightarrow\quad\alpha D_{\tau_{1}}+(1-\alpha)D_{\tau_{2}}=\varepsilon. \tag*{(168)} α m τ 1 + ( 1 − α ) m τ 2 = 0 ⟺ α D τ 1 + ( 1 − α ) D τ 2 = ε . (168)
Define the time-0 randomized stopping time
τ ⋆ = { τ 1 , with probability α , τ 2 , with probability 1 − α , (169) \tau^{\star}=
\begin{cases}
\tau_{1}, & \text{with probability }\alpha,\\
\tau_{2}, & \text{with probability }1-\alpha,
\end{cases} \tag*{(169)} τ ⋆ = { τ 1 , τ 2 , with probability α , with probability 1 − α , (169)
Then E ∞ [ τ ⋆ ] = ε \mathbb{E}_{\infty}[\tau^{\star}]=\varepsilon E ∞ [ τ ⋆ ] = ε and
E ∞ [ W τ ⋆ − λ ε τ ⋆ ] = α ( N τ 1 − λ ε D τ 1 ) + ( 1 − α ) ( N τ 2 − λ ε D τ 2 ) = V ( λ ε ) . (170) \mathbb{E}_{\infty}[W_{\tau^{\star}}-\lambda_{\varepsilon}\tau^{\star}]
=\alpha(N_{\tau_{1}}-\lambda_{\varepsilon}D_{\tau_{1}})
+(1-\alpha)(N_{\tau_{2}}-\lambda_{\varepsilon}D_{\tau_{2}})
=\mathcal{V}(\lambda_{\varepsilon}). \tag*{(170)} E ∞ [ W τ ⋆ − λ ε τ ⋆ ] = α ( N τ 1 − λ ε D τ 1 ) + ( 1 − α ) ( N τ 2 − λ ε D τ 2 ) = V ( λ ε ) . (170)
Consequently,
E ∞ [ W τ ⋆ ] ε = λ ε + E ∞ [ W τ ⋆ − λ ε τ ⋆ ] ε = λ ε + V ( λ ε ) ε = ϕ ε ( λ ε ) = ρ . (171) \frac{\mathbb{E}_{\infty}[W_{\tau^{\star}}]}{\varepsilon}
=\lambda_{\varepsilon}
+\frac{\mathbb{E}_{\infty}[W_{\tau^{\star}}-\lambda_{\varepsilon}\tau^{\star}]}{\varepsilon}
=\lambda_{\varepsilon}+\frac{\mathcal{V}(\lambda_{\varepsilon})}{\varepsilon}
=\phi_{\varepsilon}(\lambda_{\varepsilon})=\rho. \tag*{(171)} ε E ∞ [ W τ ⋆ ] = λ ε + ε E ∞ [ W τ ⋆ − λ ε τ ⋆ ] = λ ε + ε V ( λ ε ) = ϕ ε ( λ ε ) = ρ . (171)
Combining with (164) shows that τ ⋆ \tau^{\star} τ ⋆ achieves the primal optimum value ρ \rho ρ , and therefore solves Q ~ ( ε ) \widetilde{Q}(\varepsilon) Q ( ε ) .
Proof of Lemma 4
All conditional expectations are under P ∞ \mathbb{P}_{\infty} P ∞ . Recall W t ≜ ℓ t + ℓ t − 1 ℓ t W_t\triangleq\ell_t+\ell_{t-1}\ell_t W t ≜ ℓ t + ℓ t − 1 ℓ t (with ℓ 0 = 0 \ell_0=0 ℓ 0 = 0 ). Note that W t W_t W t is integrable since E ∞ [ ℓ t ] = 1 \mathbb{E}_{\infty}[\ell_t]=1 E ∞ [ ℓ t ] = 1 and, by independence under P ∞ \mathbb{P}_{\infty} P ∞ , E ∞ [ ℓ t − 1 ℓ t ] = E ∞ [ ℓ t − 1 ] E ∞ [ ℓ t ] ∈ { 0 , 1 } \mathbb{E}_{\infty}[\ell_{t-1}\ell_t]=\mathbb{E}_{\infty}[\ell_{t-1}]\mathbb{E}_{\infty}[\ell_t]\in\{0,1\} E ∞ [ ℓ t − 1 ℓ t ] = E ∞ [ ℓ t − 1 ] E ∞ [ ℓ t ] ∈ { 0 , 1 } , resulting in E ∞ [ W t ] = E ∞ [ ℓ t ] + E ∞ [ ℓ t − 1 ℓ t ] ≤ 2 < ∞ \mathbb{E}_{\infty}[W_t]=\mathbb{E}_{\infty}[\ell_t]+\mathbb{E}_{\infty}[\ell_{t-1}\ell_t]\le2<\infty E ∞ [ W t ] = E ∞ [ ℓ t ] + E ∞ [ ℓ t − 1 ℓ t ] ≤ 2 < ∞ . (a) Lower bound. First, choosing τ ≡ t \tau\equiv t τ ≡ t in (35) indicates that J t ≥ W t J_t \ge W_t J t ≥ W t a.s. Next, fix η > 0 \eta> 0 η > 0 . By the definition of J t + 1 ( F t + 1 ) J_{t+1}(\mathcal{F}_{t+1}) J t + 1 ( F t + 1 ) there exists τ η ∈ T t + 1 \tau^\eta\in\mathcal{T}_{t+1} τ η ∈ T t + 1 such that
J t + 1 ( F t + 1 ) ≤ E ∞ [ W τ η − λ ( τ η − ( t + 1 ) ) ∣ F t + 1 ] + η a.s. (172) J_{t+1}(\mathcal{F}_{t+1}) \le\mathbb{E}_{\infty}\left[W_{\tau^\eta}-\lambda(\tau^\eta-(t+1)) \mid\mathcal{F}_{t+1}\right]+\eta\quad\text{a.s.} \tag*{(172)} J t + 1 ( F t + 1 ) ≤ E ∞ [ W τ η − λ ( τ η − ( t + 1 )) ∣ F t + 1 ] + η a.s. (172)
Using τ η \tau^\eta τ η as a feasible action at time t + 1 t+1 t + 1 and then invoking the tower property we obtain
J t ( F t ) ≥ E ∞ [ W τ η − λ ( τ η − t ) ∣ F t ] (173) J_t(\mathcal{F}_t) \ge\mathbb{E}_{\infty}\left[W_{\tau^\eta}-\lambda(\tau^\eta-t) \mid\mathcal{F}_t\right] \tag*{(173)} J t ( F t ) ≥ E ∞ [ W τ η − λ ( τ η − t ) ∣ F t ] (173)
= − λ + E ∞ [ E ∞ [ W τ η − λ ( τ η − ( t + 1 ) ) ∣ F t + 1 ] ∣ F t ] (174) = -\lambda+\mathbb{E}_{\infty}\left[\mathbb{E}_{\infty}\left[W_{\tau^\eta}-\lambda(\tau^\eta-(t+1)) \mid\mathcal{F}_{t+1}\right]\mid\mathcal{F}_t\right] \tag*{(174)} = − λ + E ∞ [ E ∞ [ W τ η − λ ( τ η − ( t + 1 )) ∣ F t + 1 ] ∣ F t ] (174)
≥ − λ + E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] − η (175) \ge-\lambda+\mathbb{E}_{\infty}\left[J_{t+1}(\mathcal{F}_{t+1})\mid\mathcal{F}_t\right]-\eta \tag*{(175)} ≥ − λ + E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] − η (175)
= − λ + R t − η . (176) = -\lambda+R_t-\eta. \tag*{(176)} = − λ + R t − η . (176)
Letting η → 0 \eta\to0 η → 0 yields J t ≥ − λ + R t J_t \ge-\lambda+R_t J t ≥ − λ + R t a.s. Combining with J t ≥ W t J_t \ge W_t J t ≥ W t we have
J t ≥ max { W t , − λ + R t } a.s. (177) J_t \ge\max\{W_t,-\lambda+R_t\}\quad\text{a.s.} \tag*{(177)} J t ≥ max { W t , − λ + R t } a.s. (177)
(b) Upper bound. Take an arbitrary τ ∈ T t \tau\in\mathcal{T}_t τ ∈ T t and consider the following decomposition according to the events { τ = t } \{\tau=t\} { τ = t } and { τ ≥ t + 1 } \{\tau\ge t+1\} { τ ≥ t + 1 } :
E ∞ [ W τ − λ ( τ − t ) ∣ F t ] = E ∞ [ 1 { τ = t } W t + 1 { τ ≥ t + 1 } [ W τ − λ − λ ( τ − ( t + 1 ) ) ] ∣ F t ] ≤ 1 { τ = t } W t + 1 { τ ≥ t + 1 } ( − λ + E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] ) (178) \begin{aligned}
\mathbb{E}_{\infty}\left[W_\tau-\lambda(\tau-t)\mid\mathcal{F}_t\right]
=\mathbb{E}_{\infty}\left[\mathbf{1}_{\{\tau=t\}}W_t+\mathbf{1}_{\{\tau\ge t+1\}}\left[W_\tau-\lambda-\lambda(\tau-(t+1))\right]\mid\mathcal{F}_t\right] \\
&\le\mathbf{1}_{\{\tau=t\}}W_t+\mathbf{1}_{\{\tau\ge t+1\}}\left(-\lambda+\mathbb{E}_{\infty}\left[J_{t+1}(\mathcal{F}_{t+1})\mid\mathcal{F}_t\right]\right) \tag*{(178)}
\end{aligned} E ∞ [ W τ − λ ( τ − t ) ∣ F t ] = E ∞ [ 1 { τ = t } W t + 1 { τ ≥ t + 1 } [ W τ − λ − λ ( τ − ( t + 1 )) ] ∣ F t ] ≤ 1 { τ = t } W t + 1 { τ ≥ t + 1 } ( − λ + E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] ) (178)
= 1 { τ = t } W t + 1 { τ ≥ t + 1 } ( − λ + R t ) (179) = \mathbf{1}_{\{\tau=t\}}W_t+\mathbf{1}_{\{\tau\ge t+1\}}(-\lambda+R_t) \tag*{(179)} = 1 { τ = t } W t + 1 { τ ≥ t + 1 } ( − λ + R t ) (179)
≤ max { W t , − λ + R t } a.s. (180) \le\max\{W_t,-\lambda+R_t\}\quad\text{a.s.} \tag*{(180)} ≤ max { W t , − λ + R t } a.s. (180)
where we used that { τ = t } , { τ ≥ t + 1 } ∈ F t \{\tau=t\},\{\tau\ge t+1\}\in\mathcal{F}_t { τ = t } , { τ ≥ t + 1 } ∈ F t , the tower property, the definition of J t + 1 J_{t+1} J t + 1 in (35), and the definition of R t R_t R t in (36). Taking the essential supremum over τ ∈ T t \tau\in\mathcal{T}_t τ ∈ T t on the left-hand side yields
J t ≤ max { W t , − λ + R t } a.s. (181) J_t\le\max\{W_t,-\lambda+R_t\}\quad\text{a.s.} \tag*{(181)} J t ≤ max { W t , − λ + R t } a.s. (181)
Combining (177) and (181) proves the Bellman identity
J t ( F t ) = max { W t , − λ + R t } a.s. for all t ≥ 1. (182) J_t(\mathcal{F}_t)=\max\{W_t,-\lambda+R_t\}\quad\text{a.s. for all }t\ge1. \tag*{(182)} J t ( F t ) = max { W t , − λ + R t } a.s. for all t ≥ 1. (182)
Proof of Lemma 5
For each t ≥ 1 t\ge1 t ≥ 1 , we had defined the admissible set in 34 as
T t ≜ { τ ∈ T : τ ≥ t a.s. } , (183) \mathcal{T}_t\triangleq\{\tau\in\mathcal{T}:\tau\ge t\quad\text{a.s.}\}, \tag*{(183)} T t ≜ { τ ∈ T : τ ≥ t a.s. } , (183)
Recall W t ≜ ℓ t + ℓ t − 1 ℓ t W_t\triangleq\ell_t+\ell_{t-1}\ell_t W t ≜ ℓ t + ℓ t − 1 ℓ t for t ∈ N t\in\mathbb{N} t ∈ N (with ℓ 0 = 0 \ell_0=0 ℓ 0 = 0 ). Define the infinite-horizon value function
J t ≜ ess sup τ ∈ T t E ∞ [ W τ − λ ( τ − t ) ∣ F t ] , R t ≜ E ∞ [ J t + 1 ∣ F t ] . (184) J_t\triangleq\operatorname*{ess\,sup}_{\tau\in\mathcal{T}_t}\mathbb{E}_{\infty}[W_\tau-\lambda(\tau-t)\mid\mathcal{F}_t],\qquad R_t\triangleq\mathbb{E}_{\infty}[J_{t+1}\mid\mathcal{F}_t]. \tag*{(184)} J t ≜ τ ∈ T t ess sup E ∞ [ W τ − λ ( τ − t ) ∣ F t ] , R t ≜ E ∞ [ J t + 1 ∣ F t ] . (184)
Lemma 4 then reads
J t = max { W t , − λ + R t } a.s. for all t ≥ 1. (185) J_t = \max\{W_t, -\lambda+ R_t\}\quad\text{a.s. for all } t \ge1. \tag*{(185)} J t = max { W t , − λ + R t } a.s. for all t ≥ 1. (185)
Define the candidate stopping time
τ λ ∗ ≜ inf { t ≥ 1 : W t ≥ − λ + R t } . (186) \tau_\lambda^* \triangleq\inf\{t \ge1 : W_t \ge-\lambda+ R_t\}. \tag*{(186)} τ λ ∗ ≜ inf { t ≥ 1 : W t ≥ − λ + R t } . (186)
Because { W t ≥ − λ + R t } ∈ F t \{W_t \ge-\lambda+ R_t\} \in\mathcal{F}_t { W t ≥ − λ + R t } ∈ F t and τ λ ∗ \tau_\lambda^* τ λ ∗ is the first entry time into an { F t } \{\mathcal{F}_t\} { F t } -measurable set, τ λ ∗ \tau_\lambda^* τ λ ∗ is an { F t } \{\mathcal{F}_t\} { F t } -stopping time.
Step 1: Reduce the problem to a standard optimal stopping form. Define the reward process
Y t ≜ W t − λ t , t ≥ 1. (187) Y_t \triangleq W_t - \lambda t,\qquad t \ge1. \tag*{(187)} Y t ≜ W t − λ t , t ≥ 1. (187)
For each t ≥ 1 t \ge1 t ≥ 1 define its Snell envelope
V t ≜ ess sup τ ∈ T t E ∞ [ Y τ ∣ F t ] . (188) V_t \triangleq\operatorname*{ess\,sup}_{\tau\in\mathcal{T}_t}\mathbb{E}_{\infty}[Y_\tau\mid\mathcal{F}_t]. \tag*{(188)} V t ≜ τ ∈ T t ess sup E ∞ [ Y τ ∣ F t ] . (188)
Note that
J t = ess sup τ ∈ T t E ∞ [ W τ − λ ( τ − t ) ∣ F t ] (189) J_t = \operatorname*{ess\,sup}_{\tau\in\mathcal{T}_t}\mathbb{E}_{\infty}[W_\tau-\lambda(\tau-t)\mid\mathcal{F}_t] \tag*{(189)} J t = τ ∈ T t ess sup E ∞ [ W τ − λ ( τ − t ) ∣ F t ] (189)
= λ t + ess sup τ ∈ T t E ∞ [ W τ − λ τ ∣ F t ] (190) = \lambda t+\operatorname*{ess\,sup}_{\tau\in\mathcal{T}_t}\mathbb{E}_{\infty}[W_\tau-\lambda\tau\mid\mathcal{F}_t] \tag*{(190)} = λ t + τ ∈ T t ess sup E ∞ [ W τ − λ τ ∣ F t ] (190)
= λ t + V t . (191) = \lambda t+V_t. \tag*{(191)} = λ t + V t . (191)
Hence, the stopping condition J t = W t J_t=W_t J t = W t is equivalent to V t = Y t V_t=Y_t V t = Y t . By (185),
{ J t = W t } = { W t ≥ − λ + R t } , (192) \{J_t=W_t\}=\{W_t\ge-\lambda+R_t\}, \tag*{(192)} { J t = W t } = { W t ≥ − λ + R t } , (192)
so the stopping time in (186) can equivalently be written as
τ λ ∗ = inf { t ≥ 1 : V t = Y t } . (193) \tau_\lambda^*=\inf\{t\ge1:V_t=Y_t\}. \tag*{(193)} τ λ ∗ = inf { t ≥ 1 : V t = Y t } . (193)
Step 2: Verify the hypotheses for the Snell-envelope optimality theorem. Since W t ≥ 0 W_t\ge0 W t ≥ 0 , and by using the notation ( X ) + = max ( 0 , X ) (X)^+=\max(0,X) ( X ) + = max ( 0 , X ) , we have Y t + = ( W t − λ t ) + ≤ W t Y_t^+=(W_t-\lambda t)^+\le W_t Y t + = ( W t − λ t ) + ≤ W t . Under P ∞ \mathbb{P}_{\infty} P ∞ , E ∞ [ W t ] = E ∞ [ ℓ t ] + E ∞ [ ℓ t − 1 ℓ t ] ≤ 2 \mathbb{E}_{\infty}[W_t]=\mathbb{E}_{\infty}[\ell_t]+\mathbb{E}_{\infty}[\ell_{t-1}\ell_t]\le2 E ∞ [ W t ] = E ∞ [ ℓ t ] + E ∞ [ ℓ t − 1 ℓ t ] ≤ 2 (by independence), hence
sup t ≥ 1 E ∞ [ Y t + ] ≤ sup t ≥ 1 E ∞ [ W t ] ≤ 2 < ∞ . (194) \sup_{t\ge1}\mathbb{E}_{\infty}[Y_t^+]\le\sup_{t\ge1}\mathbb{E}_{\infty}[W_t]\le2<\infty. \tag*{(194)} t ≥ 1 sup E ∞ [ Y t + ] ≤ t ≥ 1 sup E ∞ [ W t ] ≤ 2 < ∞. (194)
This standard integrability condition ensures that the Snell envelope is well defined (of class D \mathcal{D} D ), so optional sampling applies to the stopped envelope.
Step 3: Optimality. By the discrete-time Snell envelope theorem (optimal stopping in discrete time), { V t } \{V_t\} { V t } is the smallest { F t } \{\mathcal{F}_t\} { F t } –supermartingale that dominates { Y t } \{Y_t\} { Y t } , and the stopping time τ λ ∗ = inf { t ≥ 1 : V t = Y t } \tau_\lambda^* = \inf\{t \ge1 : V_t = Y_t\} τ λ ∗ = inf { t ≥ 1 : V t = Y t } is optimal:
E ∞ [ Y τ λ ∗ ] = sup τ ∈ T 1 E ∞ [ Y τ ] = E ∞ [ V 1 ] . (195) \mathbb{E}_{\infty}[Y_{\tau_\lambda^*}] = \sup_{\tau\in\mathcal{T}_1} \mathbb{E}_{\infty}[Y_\tau] = \mathbb{E}_{\infty}[V_1]. \tag*{(195)} E ∞ [ Y τ λ ∗ ] = τ ∈ T 1 sup E ∞ [ Y τ ] = E ∞ [ V 1 ] . (195)
Equivalently,
sup τ ∈ T 1 E ∞ [ W τ − λ τ ] = E ∞ [ W τ λ ∗ − λ τ λ ∗ ] . (196) \sup_{\tau\in\mathcal{T}_1} \mathbb{E}_{\infty}[W_\tau- \lambda\tau] = \mathbb{E}_{\infty}[W_{\tau_\lambda^*} - \lambda\tau_\lambda^*]. \tag*{(196)} τ ∈ T 1 sup E ∞ [ W τ − λ τ ] = E ∞ [ W τ λ ∗ − λ τ λ ∗ ] . (196)
This shows that τ λ ∗ \tau_\lambda^* τ λ ∗ attains the supremum in V ( λ ) \mathcal{V}(\lambda) V ( λ ) (cf. (31) ), completing the proof of Lemma 5.
Proof of Lemma 6
Step 1: Markov structure. Define the two-dimensional state process
Z t ≜ ( ℓ t − 1 , ℓ t ) , t ∈ N . (197) Z_t \triangleq(\ell_{t-1}, \ell_t), \qquad t \in\mathbb{N}. \tag*{(197)} Z t ≜ ( ℓ t − 1 , ℓ t ) , t ∈ N . (197)
Since { ℓ t } \{\ell_t\} { ℓ t } are i.i.d. under P ∞ \mathbb{P}_{\infty} P ∞ , the process { Z t : t ∈ N } \{Z_t : t \in\mathbb{N}\} { Z t : t ∈ N } is a time-homogeneous Markov chain on [ 0 , ∞ ) 2 [0,\infty)^2 [ 0 , ∞ ) 2 with transition Z t + 1 = ( ℓ t , ℓ t + 1 ) Z_{t+1} = (\ell_t,\ell_{t+1}) Z t + 1 = ( ℓ t , ℓ t + 1 ) , where ℓ t + 1 \ell_{t+1} ℓ t + 1 is independent of Z t Z_t Z t and distributed as ℓ 1 \ell_1 ℓ 1 . Moreover, for ξ = 2 \xi= 2 ξ = 2 the one-step reward is W t ≜ ℓ t + ℓ t − 1 ℓ t W_t \triangleq\ell_t + \ell_{t-1}\ell_t W t ≜ ℓ t + ℓ t − 1 ℓ t , which is a measurable function of Z t Z_t Z t .
Step 2: Markov optimal stopping formulation. Recall the value-to-go function
J t ( F t ) = ess sup τ ∈ T t E ∞ [ W τ − λ ( τ − t ) ∣ F t ] . (198) J_t(\mathcal{F}_t) = \mathop{\operatorname{ess\,sup}}_{\tau\in\mathcal{T}_t} \mathbb{E}_{\infty}\left[W_\tau- \lambda(\tau-t) \mid\mathcal{F}_t\right]. \tag*{(198)} J t ( F t ) = ess sup τ ∈ T t E ∞ [ W τ − λ ( τ − t ) ∣ F t ] . (198)
Because Z t Z_t Z t is Markov and the reward W t W_t W t depends only on Z t Z_t Z t , the infinite-horizon optimal stopping problem is a Markov optimal stopping problem (see, e.g., [30 ] , Ch. III). Hence, the value function depends on the past only through the current Markov state Z t Z_t Z t . Therefore, there exists a Borel function J : [ 0 , ∞ ) 2 → R J : [0,\infty)^2 \to\mathbb{R} J : [ 0 , ∞ ) 2 → R such that
J t ( F t ) = J ( ℓ t − 1 , ℓ t ) a.s. (199) J_t(\mathcal{F}_t) = J(\ell_{t-1},\ell_t) \quad\text{a.s.} \tag*{(199)} J t ( F t ) = J ( ℓ t − 1 , ℓ t ) a.s. (199)
Step 3: Structure of the continuation value. By definition,
R t ( F t ) = E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] . (200) R_t(\mathcal{F}_t) = \mathbb{E}_{\infty}\left[J_{t+1}(\mathcal{F}_{t+1}) \mid\mathcal{F}_t\right]. \tag*{(200)} R t ( F t ) = E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] . (200)
Using the representation above,
J t + 1 ( F t + 1 ) = J ( ℓ t , ℓ t + 1 ) . (201) J_{t+1}(\mathcal{F}_{t+1}) = J(\ell_t,\ell_{t+1}). \tag*{(201)} J t + 1 ( F t + 1 ) = J ( ℓ t , ℓ t + 1 ) . (201)
Since ℓ t + 1 \ell_{t+1} ℓ t + 1 is independent of F t \mathcal{F}_t F t and has the same law as ℓ 1 \ell_1 ℓ 1 , we obtain
R t ( F t ) = E ∞ [ J ( ℓ t , ℓ t + 1 ) ∣ ℓ t ] = R ( ℓ t ) , (202) R_t(\mathcal{F}_t) = \mathbb{E}_{\infty}\left[J(\ell_t,\ell_{t+1}) \mid\ell_t\right] = R(\ell_t), \tag*{(202)} R t ( F t ) = E ∞ [ J ( ℓ t , ℓ t + 1 ) ∣ ℓ t ] = R ( ℓ t ) , (202)
where
R ( y ) ≜ E ∞ [ J ( y , ℓ ~ ) ] , ℓ ~ = d ℓ 1 . (203) R(y) \triangleq\mathbb{E}_{\infty}\left[J(y,\widetilde{\ell})\right], \qquad\widetilde{\ell} \overset{d}{=} \ell_1. \tag*{(203)} R ( y ) ≜ E ∞ [ J ( y , ℓ ) ] , ℓ = d ℓ 1 . (203)
Thus R t R_t R t depends on F t \mathcal{F}_t F t only through ℓ t \ell_t ℓ t .
Step 4: Bellman representation. From the Bellman identity, we have
J t = max { W t , − λ + R t } . (204) J_t = \max\{W_t, -\lambda+ R_t\}. \tag*{(204)} J t = max { W t , − λ + R t } . (204)
Since W t W_t W t is a function of ( ℓ t − 1 , ℓ t ) (\ell_{t-1}, \ell_t) ( ℓ t − 1 , ℓ t ) and R t = R ( ℓ t ) R_t = R(\ell_t) R t = R ( ℓ t ) , it follows that
J t = J ( ℓ t − 1 , ℓ t ) , (205) J_t = J(\ell_{t-1}, \ell_t), \tag*{(205)} J t = J ( ℓ t − 1 , ℓ t ) , (205)
for a suitable Borel function J J J . Combining the above steps proves that ( ℓ t − 1 , ℓ t ) (\ell_{t-1}, \ell_t) ( ℓ t − 1 , ℓ t ) is a sufficient statistic for J t J_t J t and ℓ t \ell_t ℓ t is a sufficient statistic for R t R_t R t , establishing the desired result.
Proof of Lemma 8
For the Shewhart test with stopping time (65), define p ≜ P ∞ ( ℓ 1 ≥ α ) p \triangleq\mathbb{P}_{\infty}(\ell_1 \ge\alpha) p ≜ P ∞ ( ℓ 1 ≥ α ) . Under P ∞ \mathbb{P}_{\infty} P ∞ , the likelihood ratios { ℓ t } t ∈ N \{\ell_t\}_{t\in\mathbb{N}} { ℓ t } t ∈ N are i.i.d., hence τ s \tau_s τ s is geometric on { 1 , 2 , … } \{1,2,\ldots\} { 1 , 2 , … } with success probability p p p . Therefore,
E ∞ [ τ s ] = ∑ t = 1 ∞ P ∞ ( τ s ≥ t ) (206) \mathbb{E}_{\infty}[\tau_s] = \sum_{t=1}^{\infty} \mathbb{P}_{\infty}(\tau_s \ge t) \tag*{(206)} E ∞ [ τ s ] = t = 1 ∑ ∞ P ∞ ( τ s ≥ t ) (206)
= ∑ t = 1 ∞ ( 1 − p ) t − 1 (207) = \sum_{t=1}^{\infty}(1-p)^{t-1} \tag*{(207)} = t = 1 ∑ ∞ ( 1 − p ) t − 1 (207)
= 1 p (208) = \frac{1}{p} \tag*{(208)} = p 1 (208)
= ε , (209) = \varepsilon, \tag*{(209)} = ε , (209)
where (207) follows because P ∞ ( τ s ≥ t ) = ( 1 − p ) t − 1 \mathbb{P}_{\infty}(\tau_s \ge t) = (1-p)^{t-1} P ∞ ( τ s ≥ t ) = ( 1 − p ) t − 1 , (208) is the sum of a geometric series, and (209) holds by the threshold choice (67), i.e., p = ε − 1 p = \varepsilon^{-1} p = ε − 1 .
Proof of Lemma 9
Fix λ > 0 \lambda> 0 λ > 0 and ξ ≥ 2 \xi\ge2 ξ ≥ 2 . Work under P ∞ \mathbb{P}_{\infty} P ∞ , under which { ℓ t : t ∈ N } \{\ell_t:t\in\mathbb{N}\} { ℓ t : t ∈ N } are i.i.d. and ℓ t ≥ 0 \ell_t \ge0 ℓ t ≥ 0 . For each finite horizon H ≥ 1 H \ge1 H ≥ 1 , consider an auxiliary finite-horizon truncation of the infinite-horizon optimal-stopping problem, used only for the backward-induction argument, in which the decision-maker must stop no later than time H H H . Define the truncated reward-to-go J t H J_t^H J t H and continuation value R t H R_t^H R t H by backward recursion as follows. First, define the (time-t t t ) immediate stopping reward
W t ( ξ ) ≜ ∑ k = 1 ξ ∏ j = 0 k − 1 ℓ t − j = ℓ t ( 1 + ∑ k = 1 ξ − 1 ∏ j = 1 k ℓ t − j ) . (210) W_t^{(\xi)} \triangleq\sum_{k=1}^{\xi}\prod_{j=0}^{k-1}\ell_{t-j} = \ell_t\left(1+\sum_{k=1}^{\xi-1}\prod_{j=1}^{k}\ell_{t-j}\right). \tag*{(210)} W t ( ξ ) ≜ k = 1 ∑ ξ j = 0 ∏ k − 1 ℓ t − j = ℓ t ( 1 + k = 1 ∑ ξ − 1 j = 1 ∏ k ℓ t − j ) . (210)
where we use the convention ℓ u = 0 \ell_u = 0 ℓ u = 0 for u ≤ 0 u \le0 u ≤ 0 (equivalently, the above products vanish whenever an index is nonpositive). Then set the terminal condition
J H H ≜ W H ξ . (211) J_H^H \triangleq W_H^{\xi}. \tag*{(211)} J H H ≜ W H ξ . (211)
For t ∈ { 1 , … , H − 1 } t \in\{1,\ldots,H-1\} t ∈ { 1 , … , H − 1 } , define
R t H ≜ E ∞ [ J t + 1 H ∣ F t ] , and J t H ≜ max { W t ( ξ ) , − λ + R t H } . (212) R_t^H \triangleq\mathbb{E}_{\infty}\left[J_{t+1}^H \mid\mathcal{F}_t\right], \qquad\text{and} \qquad J_t^H \triangleq\max\left\{W_t^{(\xi)},-\lambda+R_t^H\right\}. \tag*{(212)} R t H ≜ E ∞ [ J t + 1 H ∣ F t ] , and J t H ≜ max { W t ( ξ ) , − λ + R t H } . (212)
Step 1: W t ( ξ ) W_t^{(\xi)} W t ( ξ ) is affine in ℓ t \ell_t ℓ t for fixed past. Fix a time t t t and fix the past likelihood ratios ( ℓ t − ξ + 1 , … , ℓ t − 1 ) (\ell_{t-\xi+1},\ldots,\ell_{t-1}) ( ℓ t − ξ + 1 , … , ℓ t − 1 ) . From (210), W t ( ξ ) W_t^{(\xi)} W t ( ξ ) can be written as
W t ( ξ ) = ℓ t c t , c t ≜ 1 + ∑ k = 1 ξ − 1 ∏ j = 1 k ℓ t − j ≥ 1 , (213) W_t^{(\xi)}=\ell_t c_t,\qquad c_t \triangleq1+\sum_{k=1}^{\xi-1}\prod_{j=1}^{k}\ell_{t-j}\ge1, \tag*{(213)} W t ( ξ ) = ℓ t c t , c t ≜ 1 + k = 1 ∑ ξ − 1 j = 1 ∏ k ℓ t − j ≥ 1 , (213)
which is affine in ℓ t \ell_t ℓ t (hence convex) and nondecreasing in ℓ t \ell_t ℓ t for fixed c t c_t c t .
Step 2: Backward induction for convexity and monotonicity. We prove by backward induction on t t t that, for each fixed ( ℓ t − ξ + 1 , … , ℓ t − 1 ) (\ell_{t-\xi+1},\ldots,\ell_{t-1}) ( ℓ t − ξ + 1 , … , ℓ t − 1 ) , both mappings
ℓ t ↦ J t H , and ℓ t ↦ R t H , (214) \ell_t\mapsto J_t^H,\qquad\text{and}\qquad\ell_t\mapsto R_t^H, \tag*{(214)} ℓ t ↦ J t H , and ℓ t ↦ R t H , (214)
are convex and nondecreasing.
R t H ( ℓ t ; ℓ t − ξ + 1 t ) = E ∞ [ J t + 1 H ( ℓ t + 1 ; ℓ t − ξ + 2 t ) ∣ ℓ t − ξ + 1 ] , (215) R_t^H(\ell_t;\ell_{t-\xi+1}^t)=\mathbb{E}_{\infty}\left[J_{t+1}^H(\ell_{t+1};\ell_{t-\xi+2}^t)\mid\ell_{t-\xi+1}\right], \tag*{(215)} R t H ( ℓ t ; ℓ t − ξ + 1 t ) = E ∞ [ J t + 1 H ( ℓ t + 1 ; ℓ t − ξ + 2 t ) ∣ ℓ t − ξ + 1 ] , (215)
where the dependence on ℓ t \ell_t ℓ t enters only through the shifted history ℓ t − ξ + 2 t = ( ℓ t − ξ + 2 , … , ℓ t ) \ell_{t-\xi+2}^t=(\ell_{t-\xi+2},\ldots,\ell_t) ℓ t − ξ + 2 t = ( ℓ t − ξ + 2 , … , ℓ t ) . By the induction hypothesis, for each fixed realization of ℓ t + 1 \ell_{t+1} ℓ t + 1 and the earlier ratios, the map ℓ t ↦ J t + 1 H ( ℓ t + 1 ; ℓ t − ξ + 2 t ) \ell_t\mapsto J_{t+1}^H(\ell_{t+1};\ell_{t-\xi+2}^t) ℓ t ↦ J t + 1 H ( ℓ t + 1 ; ℓ t − ξ + 2 t ) is convex and nondecreasing. Therefore, R t H R_t^H R t H , being an average of convex and nondecreasing functions of ℓ t \ell_t ℓ t , is itself convex and nondecreasing in ℓ t \ell_t ℓ t when the earlier likelihood ratios are held fixed. Finally,
J t H = max { W t ( ξ ) , − λ + R t H } (216) J_t^H=\max\{W_t^{(\xi)},-\lambda+R_t^H\} \tag*{(216)} J t H = max { W t ( ξ ) , − λ + R t H } (216)
is the pointwise maximum of two convex and nondecreasing functions of ℓ t \ell_t ℓ t , hence it is itself convex and nondecreasing.
Step 3: Infinite horizon. Let J t ξ J_t^\xi J t ξ and R t ξ R_t^\xi R t ξ denote the corresponding infinite-horizon reward-to-go and continuation value. As H H H increases, these auxiliary finite-horizon truncations admit larger classes of stopping times, so J t H J_t^H J t H increases pointwise to J t ξ J_t^\xi J t ξ (and consequently R t H R_t^H R t H increases pointwise to R t ξ R_t^\xi R t ξ ). A pointwise supremum of convex (respectively, nondecreasing) functions is convex (respectively, nondecreasing), so J t ξ J_t^\xi J t ξ and R t ξ R_t^\xi R t ξ inherit these properties in ℓ t \ell_t ℓ t when the past likelihood ratios are held fixed. This completes the proof.
Proof of Lemma 10
Recall the definition of R R R in (83)
R ( ℓ ) = E ∞ [ max { L ( 1 + ℓ ) , − λ + R ( L ) } ] , where L = d ℓ 1 under P ∞ . (217) R(\ell) = \mathbb{E}_{\infty}\left[\max\{L(1+\ell),-\lambda+R(L)\}\right], \qquad\text{where } L \overset{d}{=} \ell_{1}\text{ under }\mathbb{P}_{\infty}. \tag*{(217)} R ( ℓ ) = E ∞ [ max { L ( 1 + ℓ ) , − λ + R ( L )} ] , where L = d ℓ 1 under P ∞ . (217)
Fix ℓ 2 ≥ ℓ 1 ≥ 0 \ell_{2} \ge\ell_{1} \ge0 ℓ 2 ≥ ℓ 1 ≥ 0 and for each realization L ≥ 0 L \ge0 L ≥ 0 define
ϕ L ( ℓ ) ≜ max { L ( 1 + ℓ ) , − λ + R ( L ) } . (218) \phi_{L}(\ell) \triangleq\max\{L(1+\ell),-\lambda+R(L)\}. \tag*{(218)} ϕ L ( ℓ ) ≜ max { L ( 1 + ℓ ) , − λ + R ( L )} . (218)
Since L ( 1 + ℓ ) L(1+\ell) L ( 1 + ℓ ) is nondecreasing in ℓ \ell ℓ and the max of two functions preserves monotonicity, ϕ L ( ℓ ) \phi_{L}(\ell) ϕ L ( ℓ ) is nondecreasing in ℓ \ell ℓ , hence
R ( ℓ 2 ) − R ( ℓ 1 ) = E ∞ [ ϕ L ( ℓ 2 ) − ϕ L ( ℓ 1 ) ] ≥ 0 , (219) R(\ell_{2})-R(\ell_{1})=\mathbb{E}_{\infty}\left[\phi_{L}(\ell_{2})-\phi_{L}(\ell_{1})\right]\ge0, \tag*{(219)} R ( ℓ 2 ) − R ( ℓ 1 ) = E ∞ [ ϕ L ( ℓ 2 ) − ϕ L ( ℓ 1 ) ] ≥ 0 , (219)
so R ( ⋅ ) R(\cdot) R ( ⋅ ) is nondecreasing. For the Lipschitz bound, use the elementary inequality (valid for all real a ≥ a ′ a \ge a' a ≥ a ′ and any b b b ):
0 ≤ max { a , b } − max { a ′ , b } ≤ a − a ′ . (220) 0 \le\max\{a,b\}-\max\{a',b\}\le a-a'. \tag*{(220)} 0 ≤ max { a , b } − max { a ′ , b } ≤ a − a ′ . (220)
Applying this with a = L ( 1 + ℓ 2 ) a=L(1+\ell_{2}) a = L ( 1 + ℓ 2 ) , a ′ = L ( 1 + ℓ 1 ) a'=L(1+\ell_{1}) a ′ = L ( 1 + ℓ 1 ) and b = − λ + R ( L ) b=-\lambda+R(L) b = − λ + R ( L ) yields
0 ≤ ϕ L ( ℓ 2 ) − ϕ L ( ℓ 1 ) ≤ L ( ℓ 2 − ℓ 1 ) . (221) 0 \le\phi_{L}(\ell_{2})-\phi_{L}(\ell_{1})\le L(\ell_{2}-\ell_{1}). \tag*{(221)} 0 ≤ ϕ L ( ℓ 2 ) − ϕ L ( ℓ 1 ) ≤ L ( ℓ 2 − ℓ 1 ) . (221)
Taking the expectation, we obtain
0 ≤ R ( ℓ 2 ) − R ( ℓ 1 ) ≤ ( ℓ 2 − ℓ 1 ) E ∞ [ L ] . (222) 0 \le R(\ell_{2})-R(\ell_{1})\le(\ell_{2}-\ell_{1})\mathbb{E}_{\infty}[L]. \tag*{(222)} 0 ≤ R ( ℓ 2 ) − R ( ℓ 1 ) ≤ ( ℓ 2 − ℓ 1 ) E ∞ [ L ] . (222)
Finally, E ∞ [ L ] = E ∞ [ ℓ 1 ] = 1 \mathbb{E}_{\infty}[L]=\mathbb{E}_{\infty}[\ell_{1}]=1 E ∞ [ L ] = E ∞ [ ℓ 1 ] = 1 since ℓ 1 = f 1 ( X 1 ) / f 0 ( X 1 ) \ell_{1}=f_{1}(X_{1})/f_{0}(X_{1}) ℓ 1 = f 1 ( X 1 ) / f 0 ( X 1 ) is a likelihood ratio under P ∞ \mathbb{P}_{\infty} P ∞ . Therefore,
0 ≤ R ( ℓ 2 ) − R ( ℓ 1 ) ≤ ℓ 2 − ℓ 1 , (223) 0 \le R(\ell_{2})-R(\ell_{1})\le\ell_{2}-\ell_{1}, \tag*{(223)} 0 ≤ R ( ℓ 2 ) − R ( ℓ 1 ) ≤ ℓ 2 − ℓ 1 , (223)
i.e., R R R is nondecreasing and 1-Lipschitz on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) .
Proof of Theorem 4
Consider the equality-constrained problem
sup τ ∈ T E ∞ [ ℓ τ ] E ∞ [ τ ] , s.t. E ∞ [ τ ] = ε . (224) \sup_{\tau\in\mathcal{T}}\frac{\mathbb{E}_{\infty}[\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]}, \qquad\text{s.t. }\mathbb{E}_{\infty}[\tau]=\varepsilon. \tag*{(224)} τ ∈ T sup E ∞ [ τ ] E ∞ [ ℓ τ ] , s.t. E ∞ [ τ ] = ε . (224)
Since E ∞ [ τ ] = ε \mathbb{E}_{\infty}[\tau]=\varepsilon E ∞ [ τ ] = ε is fixed, this is equivalent to
sup τ ∈ T : E ∞ [ τ ] = ε E ∞ [ ℓ τ ] . (225) \sup_{\tau\in\mathcal{T}:\mathbb{E}_{\infty}[\tau]=\varepsilon}\mathbb{E}_{\infty}[\ell_{\tau}]. \tag*{(225)} τ ∈ T : E ∞ [ τ ] = ε sup E ∞ [ ℓ τ ] . (225)
For λ > 0 \lambda> 0 λ > 0 define the unconstrained Lagrangian value
V 1 ( λ ) ≜ sup τ ∈ T : P ∞ ( τ < ∞ ) = 1 E ∞ [ ℓ τ − λ τ ] . (226) \mathcal{V}_1(\lambda) \triangleq\sup_{\substack{\tau\in\mathcal{T}:\\ \mathbb{P}_{\infty}(\tau<\infty)=1}} \mathbb{E}_{\infty}[\ell_{\tau}-\lambda\tau]. \tag*{(226)} V 1 ( λ ) ≜ τ ∈ T : P ∞ ( τ < ∞ ) = 1 sup E ∞ [ ℓ τ − λ τ ] . (226)
It is noteworthy that we use V 1 \mathcal{V}_1 V 1 to avoid confusion with the continuation function R ( ⋅ ) R(\cdot) R ( ⋅ ) used elsewhere. For t ≥ 1 t \ge1 t ≥ 1 , define the value-to-go function
J t ( F t ) ≜ ess sup τ ∈ T t E ∞ [ ℓ τ − λ ( τ − t ) ∣ F t ] , (227) J_t(\mathcal{F}_t) \triangleq\operatorname{ess\,sup}_{\tau\in\mathcal{T}_t} \mathbb{E}_{\infty}[\ell_{\tau}-\lambda(\tau-t)\mid\mathcal{F}_t], \tag*{(227)} J t ( F t ) ≜ ess sup τ ∈ T t E ∞ [ ℓ τ − λ ( τ − t ) ∣ F t ] , (227)
where T t ≜ { τ ∈ T : τ ≥ t a.s. } \mathcal{T}_t \triangleq\{\tau\in\mathcal{T}:\tau\ge t\ \text{a.s.}\} T t ≜ { τ ∈ T : τ ≥ t a.s. } . Standard optimal stopping arguments imply the Bellman identity
J t ( F t ) = max { ℓ t , − λ + E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] } . (228) J_t(\mathcal{F}_t)=\max\{\ell_t,-\lambda+\mathbb{E}_{\infty}[J_{t+1}(\mathcal{F}_{t+1})\mid\mathcal{F}_t]\}. \tag*{(228)} J t ( F t ) = max { ℓ t , − λ + E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ]} . (228)
Under P ∞ \mathbb{P}_{\infty} P ∞ , { ℓ t : t ∈ N } \{\ell_t:t\in\mathbb{N}\} { ℓ t : t ∈ N } are i.i.d., and future samples are independent of F t \mathcal{F}_t F t . Hence, by stationarity,
E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] = E ∞ [ J t + 1 ( F t + 1 ) ] = E ∞ [ J 1 ( F 1 ) ] ≜ c λ . (229) \mathbb{E}_{\infty}[J_{t+1}(\mathcal{F}_{t+1})\mid\mathcal{F}_t]=\mathbb{E}_{\infty}[J_{t+1}(\mathcal{F}_{t+1})]=\mathbb{E}_{\infty}[J_1(\mathcal{F}_1)]\triangleq c_{\lambda}. \tag*{(229)} E ∞ [ J t + 1 ( F t + 1 ) ∣ F t ] = E ∞ [ J t + 1 ( F t + 1 )] = E ∞ [ J 1 ( F 1 )] ≜ c λ . (229)
Therefore,
J t ( F t ) = max { ℓ t , − λ + c λ } . (230) J_t(\mathcal{F}_t)=\max\{\ell_t,-\lambda+c_{\lambda}\}. \tag*{(230)} J t ( F t ) = max { ℓ t , − λ + c λ } . (230)
Consequently, an optimal stopping time for V 1 ( λ ) \mathcal{V}_1(\lambda) V 1 ( λ ) is
τ λ = inf { t ≥ 1 : ℓ t ≥ c λ − λ } , (231) \tau_{\lambda}=\inf\{t\ge1:\ell_t\ge c_{\lambda}-\lambda\}, \tag*{(231)} τ λ = inf { t ≥ 1 : ℓ t ≥ c λ − λ } , (231)
i.e., a Shewhart rule with threshold α λ ≜ c λ − λ \alpha_{\lambda}\triangleq c_{\lambda}-\lambda α λ ≜ c λ − λ . Taking expectations of the Bellman fixed-point equation yields
c λ = E ∞ [ max { ℓ 1 , c λ − λ } ] , (232) c_{\lambda}=\mathbb{E}_{\infty}[\max\{\ell_1,c_{\lambda}-\lambda\}], \tag*{(232)} c λ = E ∞ [ max { ℓ 1 , c λ − λ }] , (232)
equivalently,
λ = E ∞ [ ( ℓ 1 − α λ ) + ] . (233) \lambda=\mathbb{E}_{\infty}[(\ell_1-\alpha_{\lambda})^{+}]. \tag*{(233)} λ = E ∞ [( ℓ 1 − α λ ) + ] . (233)
Finally, we enforce the condition E ∞ [ τ ] = ε \mathbb{E}_{\infty}[\tau]=\varepsilon E ∞ [ τ ] = ε . Choose α \alpha α such that
P ∞ ( ℓ 1 ≥ α ) = ε − 1 . (234) \mathbb{P}_{\infty}(\ell_1\ge\alpha)=\varepsilon^{-1}. \tag*{(234)} P ∞ ( ℓ 1 ≥ α ) = ε − 1 . (234)
For the Shewhart stopping time τ s ≜ inf { t ≥ 1 : ℓ t ≥ α } \tau_s\triangleq\inf\{t\ge1:\ell_t\ge\alpha\} τ s ≜ inf { t ≥ 1 : ℓ t ≥ α } ,
E ∞ [ τ s ] = 1 P ∞ ( ℓ 1 ≥ α ) = ε . (235) \mathbb{E}_{\infty}[\tau_s]=\frac{1}{\mathbb{P}_{\infty}(\ell_1\ge\alpha)}=\varepsilon. \tag*{(235)} E ∞ [ τ s ] = P ∞ ( ℓ 1 ≥ α ) 1 = ε . (235)
Now set
λ ≜ E ∞ [ max { ℓ 1 , α } ] − α . (236) \lambda\triangleq\mathbb{E}_{\infty}[\max\{\ell_1,\alpha\}]-\alpha. \tag*{(236)} λ ≜ E ∞ [ max { ℓ 1 , α }] − α . (236)
Then c λ = E ∞ [ max { ℓ 1 , α } ] c_{\lambda}=\mathbb{E}_{\infty}[\max\{\ell_1,\alpha\}] c λ = E ∞ [ max { ℓ 1 , α }] and α λ = c λ − λ = α \alpha_{\lambda}=c_{\lambda}-\lambda=\alpha α λ = c λ − λ = α , so τ s \tau_s τ s attains the supremum in V 1 ( λ ) \mathcal{V}_1(\lambda) V 1 ( λ ) and satisfies the ARL constraint. Hence, for any τ \tau τ with E ∞ [ τ ] = ε \mathbb{E}_{\infty}[\tau]=\varepsilon E ∞ [ τ ] = ε ,
E ∞ [ ℓ τ ] = E ∞ [ ℓ τ − λ τ ] + λ ε (237) \mathbb{E}_{\infty}[\ell_{\tau}]=\mathbb{E}_{\infty}[\ell_{\tau}-\lambda\tau]+\lambda\varepsilon \tag*{(237)} E ∞ [ ℓ τ ] = E ∞ [ ℓ τ − λ τ ] + λ ε (237)
≤ E ∞ [ ℓ τ s − λ τ s ] + λ ε (238) \le\mathbb{E}_{\infty}[\ell_{\tau_s}-\lambda\tau_s]+\lambda\varepsilon \tag*{(238)} ≤ E ∞ [ ℓ τ s − λ τ s ] + λ ε (238)
= E ∞ [ ℓ τ s ] , (239) =\mathbb{E}_{\infty}[\ell_{\tau_s}], \tag*{(239)} = E ∞ [ ℓ τ s ] , (239)
which proves that the Shewhart test τ s \tau_s τ s solves (70).
Proof of Theorem 5
Let τ s ≜ inf { t ≥ 1 : ℓ t ≥ α } \tau_s \triangleq\inf\{t \ge1:\ell_t \ge\alpha\} τ s ≜ inf { t ≥ 1 : ℓ t ≥ α } , where α \alpha α satisfies
P ∞ ( ℓ 1 ≥ α ) = ε − 1 . (240) \mathbb{P}_{\infty}(\ell_1 \ge\alpha)=\varepsilon^{-1}. \tag*{(240)} P ∞ ( ℓ 1 ≥ α ) = ε − 1 . (240)
For ξ = 1 \xi=1 ξ = 1 , success at γ i \gamma_i γ i means τ = γ i \tau=\gamma_i τ = γ i . Under the Shewhart rule,
{ τ s = γ i } = { τ s ≥ γ i } ∩ { ℓ γ i ≥ α } . (241) \{\tau_s=\gamma_i\}=\{\tau_s\ge\gamma_i\}\cap\{\ell_{\gamma_i}\ge\alpha\}. \tag*{(241)} { τ s = γ i } = { τ s ≥ γ i } ∩ { ℓ γ i ≥ α } . (241)
Under any admissible configuration, conditional on F γ i − 1 \mathcal{F}_{\gamma_i-1} F γ i − 1 and { τ s ≥ γ i } \{\tau_s\ge\gamma_i\} { τ s ≥ γ i } , the random variable ℓ γ i \ell_{\gamma_i} ℓ γ i depends only on X γ i ∼ f 1 X_{\gamma_i}\sim f_1 X γ i ∼ f 1 and is independent of the past. Hence
P θ ( τ s = γ i ∣ F γ i − 1 , τ s ≥ γ i ) = P 1 ( ℓ 1 ≥ α ) , (242) \mathbb{P}_{\theta}(\tau_s=\gamma_i\mid\mathcal{F}_{\gamma_i-1},\tau_s\ge\gamma_i)=\mathbb{P}_1(\ell_1\ge\alpha), \tag*{(242)} P θ ( τ s = γ i ∣ F γ i − 1 , τ s ≥ γ i ) = P 1 ( ℓ 1 ≥ α ) , (242)
a constant (not depending on γ i \gamma_i γ i or F γ i − 1 \mathcal{F}_{\gamma_i-1} F γ i − 1 ). Therefore
L L ( τ s ) = L P ( τ s ) = s P 1 ( ℓ 1 ≥ α ) . (243) \mathcal{L}_{L}(\tau_s)=\mathcal{L}_{P}(\tau_s)=s\mathbb{P}_1(\ell_1\ge\alpha). \tag*{(243)} L L ( τ s ) = L P ( τ s ) = s P 1 ( ℓ 1 ≥ α ) . (243)
Using the same change-of-measure argument as in Appendix A (specialized to ξ = 1 \xi=1 ξ = 1 ), for any stopping time τ \tau τ with 0 < E ∞ [ τ ] < ∞ 0<\mathbb{E}_{\infty}[\tau]<\infty 0 < E ∞ [ τ ] < ∞ ,
L L ( τ ) ≤ L P ( τ ) ≤ s E ∞ [ ℓ τ ] E ∞ [ τ ] . (244) \mathcal{L}_{L}(\tau)\le\mathcal{L}_{P}(\tau)\le s\frac{\mathbb{E}_{\infty}[\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]}. \tag*{(244)} L L ( τ ) ≤ L P ( τ ) ≤ s E ∞ [ τ ] E ∞ [ ℓ τ ] . (244)
From Theorem 4, the Shewhart rule solves the ratio problem with ARL equality, and in particular,
sup τ : E ∞ [ τ ] = ε E ∞ [ ℓ τ ] E ∞ [ τ ] = E ∞ [ ℓ τ s ] ε . (245) \sup_{\tau:\mathbb{E}_{\infty}[\tau]=\varepsilon}\frac{\mathbb{E}_{\infty}[\ell_{\tau}]}{\mathbb{E}_{\infty}[\tau]}=\frac{\mathbb{E}_{\infty}[\ell_{\tau_s}]}{\varepsilon}. \tag*{(245)} τ : E ∞ [ τ ] = ε sup E ∞ [ τ ] E ∞ [ ℓ τ ] = ε E ∞ [ ℓ τ s ] . (245)
Next, note that under P ∞ \mathbb{P}_{\infty} P ∞ , τ s \tau_s τ s is geometric with success probability P ∞ ( ℓ 1 ≥ α ) = ε − 1 \mathbb{P}_{\infty}(\ell_1\ge\alpha)=\varepsilon^{-1} P ∞ ( ℓ 1 ≥ α ) = ε − 1 , hence the likelihood ratio at the stopping time has the stationary overshoot identity
E ∞ [ ℓ τ s ] = E ∞ [ ℓ 1 ∣ ℓ 1 ≥ α ] = E ∞ [ ℓ 1 1 { ℓ 1 ≥ α } ] P ∞ ( ℓ 1 ≥ α ) . (246) \mathbb{E}_{\infty}[\ell_{\tau_s}]=\mathbb{E}_{\infty}[\ell_1\mid\ell_1\ge\alpha]=\frac{\mathbb{E}_{\infty}[\ell_1\mathbf{1}\{\ell_1\ge\alpha\}]}{\mathbb{P}_{\infty}(\ell_1\ge\alpha)}. \tag*{(246)} E ∞ [ ℓ τ s ] = E ∞ [ ℓ 1 ∣ ℓ 1 ≥ α ] = P ∞ ( ℓ 1 ≥ α ) E ∞ [ ℓ 1 1 { ℓ 1 ≥ α }] . (246)
Using the likelihood-ratio change of measure,
E ∞ [ ℓ 1 1 { ℓ 1 ≥ α } ] = P 1 ( ℓ 1 ≥ α ) , (247) \mathbb{E}_{\infty}[\ell_1\mathbf{1}\{\ell_1\ge\alpha\}]=\mathbb{P}_1(\ell_1\ge\alpha), \tag*{(247)} E ∞ [ ℓ 1 1 { ℓ 1 ≥ α }] = P 1 ( ℓ 1 ≥ α ) , (247)
and therefore
E ∞ [ ℓ τ s ] = P 1 ( ℓ 1 ≥ α ) P ∞ ( ℓ 1 ≥ α ) = ε P 1 ( ℓ 1 ≥ α ) . (248) \mathbb{E}_{\infty}[\ell_{\tau_s}]=\frac{\mathbb{P}_1(\ell_1\ge\alpha)}{\mathbb{P}_{\infty}(\ell_1\ge\alpha)}=\varepsilon\mathbb{P}_1(\ell_1\ge\alpha). \tag*{(248)} E ∞ [ ℓ τ s ] = P ∞ ( ℓ 1 ≥ α ) P 1 ( ℓ 1 ≥ α ) = ε P 1 ( ℓ 1 ≥ α ) . (248)
Consequently,
sup τ : E ∞ [ τ ] ≥ ε L P ( τ ) = s P 1 ( ℓ 1 ≥ α ) = L P ( τ s ) , (249) \sup_{\tau:\mathbb{E}_{\infty}[\tau]\ge\varepsilon}\mathcal{L}_{P}(\tau)=s\mathbb{P}_1(\ell_1\ge\alpha)=\mathcal{L}_{P}(\tau_s), \tag*{(249)} τ : E ∞ [ τ ] ≥ ε sup L P ( τ ) = s P 1 ( ℓ 1 ≥ α ) = L P ( τ s ) , (249)
where the supremum over E ∞ [ τ ] ≥ ε \mathbb{E}_{\infty}[\tau]\ge\varepsilon E ∞ [ τ ] ≥ ε reduces to E ∞ [ τ ] = ε \mathbb{E}_{\infty}[\tau]=\varepsilon E ∞ [ τ ] = ε by Lemma 2. The same argument applies to L L \mathcal{L}_{L} L L , yielding
L L ( τ s ) = L P ( τ s ) = sup τ : E ∞ [ τ ] ≥ ε L L ( τ ) = sup τ : E ∞ [ τ ] ≥ ε L P ( τ ) . (250) \mathcal{L}_{L}(\tau_s)=\mathcal{L}_{P}(\tau_s)=\sup_{\tau:\mathbb{E}_{\infty}[\tau]\ge\varepsilon}\mathcal{L}_{L}(\tau)=\sup_{\tau:\mathbb{E}_{\infty}[\tau]\ge\varepsilon}\mathcal{L}_{P}(\tau). \tag*{(250)} L L ( τ s ) = L P ( τ s ) = τ : E ∞ [ τ ] ≥ ε sup L L ( τ ) = τ : E ∞ [ τ ] ≥ ε sup L P ( τ ) . (250)
Proof of Lemma 11
Write τ = τ A , ξ c \tau= \tau^c_{A,\xi} τ = τ A , ξ c . Define the classical Shiryaev–Roberts statistic by
S t S R ≜ ∑ j = 1 t ∏ k = j t ℓ k , S 0 S R ≜ 0. (251) S^{\mathrm{SR}}_t \triangleq\sum_{j=1}^{t}\prod_{k=j}^{t}\ell_k,\qquad S^{\mathrm{SR}}_0 \triangleq0. \tag*{(251)} S t SR ≜ j = 1 ∑ t k = j ∏ t ℓ k , S 0 SR ≜ 0. (251)
Since the TSR statistic retains only the terms associated with the most recent ξ \xi ξ candidate onsets,
0 ≤ W t ( ξ ) ≤ S t S R for every t . (252) 0 \le W^{(\xi)}_t \le S^{\mathrm{SR}}_t \qquad\text{for every }t. \tag*{(252)} 0 ≤ W t ( ξ ) ≤ S t SR for every t . (252)
Under P ∞ \mathbb{P}_{\infty} P ∞ , the likelihood ratios are independent, nonnegative, and satisfy E ∞ [ ℓ t ] = 1 \mathbb{E}_{\infty}[\ell_t]=1 E ∞ [ ℓ t ] = 1 . Hence,
E ∞ [ S t S R ] = ∑ j = 1 t E ∞ [ ∏ k = j t ℓ k ] = t < ∞ . (253) \mathbb{E}_{\infty}\left[S^{\mathrm{SR}}_t\right]=\sum_{j=1}^{t}\mathbb{E}_{\infty}\left[\prod_{k=j}^{t}\ell_k\right]=t<\infty. \tag*{(253)} E ∞ [ S t SR ] = j = 1 ∑ t E ∞ k = j ∏ t ℓ k = t < ∞. (253)
Moreover, the recursion S t S R = ( 1 + S t − 1 S R ) ℓ t S^{\mathrm{SR}}_t=(1+S^{\mathrm{SR}}_{t-1})\ell_t S t SR = ( 1 + S t − 1 SR ) ℓ t gives
E ∞ [ S t S R ∣ F t − 1 ] = 1 + S t − 1 S R . (254) \mathbb{E}_{\infty}\left[S^{\mathrm{SR}}_t\mid\mathcal{F}_{t-1}\right]=1+S^{\mathrm{SR}}_{t-1}. \tag*{(254)} E ∞ [ S t SR ∣ F t − 1 ] = 1 + S t − 1 SR . (254)
Therefore, { S t S R − t } t ≥ 0 \{S^{\mathrm{SR}}_t-t\}_{t\ge0} { S t SR − t } t ≥ 0 is an integrable { F t } \{\mathcal{F}_t\} { F t } -martingale.
For n ≥ 1 n\ge1 n ≥ 1 , let
τ n ≜ τ ∧ n . (255) \tau_n \triangleq\tau\wedge n. \tag*{(255)} τ n ≜ τ ∧ n . (255)
Since τ n \tau_n τ n is bounded, optional sampling yields
E ∞ [ S τ n S R ] = E ∞ [ τ n ] . (256) \mathbb{E}_{\infty}\left[S^{\mathrm{SR}}_{\tau_n}\right]=\mathbb{E}_{\infty}[\tau_n]. \tag*{(256)} E ∞ [ S τ n SR ] = E ∞ [ τ n ] . (256)
On { τ ≤ n } \{\tau\le n\} { τ ≤ n } , we have τ n = τ \tau_n=\tau τ n = τ and
S τ n S R = S τ S R ≥ W τ ( ξ ) ≥ A . (257) S^{\mathrm{SR}}_{\tau_n}=S^{\mathrm{SR}}_{\tau}\ge W^{(\xi)}_{\tau}\ge A. \tag*{(257)} S τ n SR = S τ SR ≥ W τ ( ξ ) ≥ A . (257)
Since S τ n S R ≥ 0 S^{\mathrm{SR}}_{\tau_n}\ge0 S τ n SR ≥ 0 everywhere,
S τ n S R ≥ A 1 { τ ≤ n } . (258) S^{\mathrm{SR}}_{\tau_n}\ge A1_{\{\tau\le n\}}. \tag*{(258)} S τ n SR ≥ A 1 { τ ≤ n } . (258)
Combining (256) and (258) gives
E ∞ [ τ n ] ≥ A P ∞ ( τ ≤ n ) . (259) \mathbb{E}_{\infty}[\tau_n]\ge A\mathbb{P}_{\infty}(\tau\le n). \tag*{(259)} E ∞ [ τ n ] ≥ A P ∞ ( τ ≤ n ) . (259)
Because τ n ↑ τ \tau_n\uparrow\tau τ n ↑ τ , monotone convergence and continuity from below imply
E ∞ [ τ ] ≥ A P ∞ ( τ < ∞ ) . (260) \mathbb{E}_{\infty}[\tau]\ge A\mathbb{P}_{\infty}(\tau<\infty). \tag*{(260)} E ∞ [ τ ] ≥ A P ∞ ( τ < ∞ ) . (260)
If P ∞ ( τ < ∞ ) = 1 \mathbb{P}_{\infty}(\tau<\infty)=1 P ∞ ( τ < ∞ ) = 1 , this is the desired inequality. If P ∞ ( τ = ∞ ) > 0 \mathbb{P}_{\infty}(\tau=\infty)>0 P ∞ ( τ = ∞ ) > 0 , then E ∞ [ τ ] = ∞ \mathbb{E}_{\infty}[\tau]=\infty E ∞ [ τ ] = ∞ , and the conclusion again follows.
Proof of Lemma 12
Write τ = τ A , ξ c \tau=\tau^{\mathrm{c}}_{A,\xi} τ = τ A , ξ c , fix θ ∈ Θ s ( ξ ) \theta\in\Theta_{\mathrm{s}}(\xi) θ ∈ Θ s ( ξ ) , and fix an episode onset γ i \gamma_i γ i . Define
Λ i , k ≜ ∏ r = 0 k − 1 ℓ γ i + r , k ∈ { 1 , … , ξ } , (261) \Lambda_{i,k}\triangleq\prod_{r=0}^{k-1}\ell_{\gamma_i+r},\qquad k\in\{1,\ldots,\xi\}, \tag*{(261)} Λ i , k ≜ r = 0 ∏ k − 1 ℓ γ i + r , k ∈ { 1 , … , ξ } , (261)
E i ≜ { τ ≥ γ i } , D i ≜ { γ i ≤ τ < γ i + ξ } , (262) E_i\triangleq\{\tau\ge\gamma_i\},\qquad D_i\triangleq\{\gamma_i\le\tau<\gamma_i+\xi\}, \tag*{(262)} E i ≜ { τ ≥ γ i } , D i ≜ { γ i ≤ τ < γ i + ξ } , (262)
B i ≜ { max 1 ≤ k ≤ ξ Λ i , k ≥ A } . (263) B_i\triangleq\left\{\max_{1\le k\le\xi}\Lambda_{i,k}\ge A\right\}. \tag*{(263)} B i ≜ { 1 ≤ k ≤ ξ max Λ i , k ≥ A } . (263)
At time γ i + k − 1 \gamma_i+k-1 γ i + k − 1 , the quantity Λ i , k \Lambda_{i,k} Λ i , k is one of the nonnegative summands in W γ i + k − 1 ( ξ ) W^{(\xi)}_{\gamma_i+k-1} W γ i + k − 1 ( ξ ) . Thus, if the detector has survived to γ i \gamma_i γ i and B i B_i B i occurs, it stops within the admissible window:
E i ∩ B i ⊆ D i . (264) E_i\cap B_i\subseteq D_i. \tag*{(264)} E i ∩ B i ⊆ D i . (264)
Because τ \tau τ is a stopping time, E i ∈ F γ i − 1 E_i\in\mathcal{F}_{\gamma_i-1} E i ∈ F γ i − 1 . Under every θ ∈ Θ s ( ξ ) \theta\in\Theta_{\mathrm{s}}(\xi) θ ∈ Θ s ( ξ ) , the observations X γ i , … , X γ i + ξ − 1 X_{\gamma_i},\ldots,X_{\gamma_i+\xi-1} X γ i , … , X γ i + ξ − 1 are independent of F γ i − 1 \mathcal{F}_{\gamma_i-1} F γ i − 1 and are i.i.d. according to F 1 F_1 F 1 . Therefore,
P θ ( B i ∣ F γ i − 1 ) = p ˉ ξ ( A ) P θ -a.s. (265) \mathbb{P}_{\theta}(B_i\mid\mathcal{F}_{\gamma_i-1})=\bar{p}_{\xi}(A)\qquad\mathbb{P}_{\theta}\text{-a.s.} \tag*{(265)} P θ ( B i ∣ F γ i − 1 ) = p ˉ ξ ( A ) P θ -a.s. (265)
Conditioning the event inclusion (264) on F γ i − 1 \mathcal{F}_{\gamma_i-1} F γ i − 1 gives
E θ [ 1 D i ∣ F γ i − 1 ] ≥ E θ [ 1 E i 1 B i ∣ F γ i − 1 ] = 1 E i P θ ( B i ∣ F γ i − 1 ) = p ˉ ξ ( A ) 1 E i . (266) \begin{aligned}
\mathbb{E}_{\theta}\left[1_{D_i}\mid\mathcal{F}_{\gamma_i-1}\right]&\ge\mathbb{E}_{\theta}\left[1_{E_i}1_{B_i}\mid\mathcal{F}_{\gamma_i-1}\right]\\
&=1_{E_i}\mathbb{P}_{\theta}\left(B_i\mid\mathcal{F}_{\gamma_i-1}\right)\\
&=\bar{p}_{\xi}(A)1_{E_i}. \tag*{(266)}
\end{aligned} E θ [ 1 D i ∣ F γ i − 1 ] ≥ E θ [ 1 E i 1 B i ∣ F γ i − 1 ] = 1 E i P θ ( B i ∣ F γ i − 1 ) = p ˉ ξ ( A ) 1 E i . (266)
This proves (92).
Suppose P θ ( E i ) > 0 \mathbb{P}_{\theta}(E_i)>0 P θ ( E i ) > 0 . Taking expectations in (266) and using D i ⊆ E i D_i\subseteq E_i D i ⊆ E i yields the Pollak-type bound
P θ ( D i ∣ E i ) ≥ p ˉ ξ ( A ) . (267) \mathbb{P}_{\theta}(D_i\mid E_i)\ge\bar{p}_{\xi}(A). \tag*{(267)} P θ ( D i ∣ E i ) ≥ p ˉ ξ ( A ) . (267)
The same inequality holds history-wise on E i E_i E i . Hence, taking the essential infimum over the surviving pre-onset histories yields the corresponding Lorden-type bound
ess inf F γ i − 1 ; E i P θ ( D i ∣ F γ i − 1 , E i ) ≥ p ˉ ξ ( A ) . (268) \underset{\mathcal{F}_{\gamma_i-1};E_i}{\operatorname{ess\,inf}}\ \mathbb{P}_{\theta}(D_i\mid\mathcal{F}_{\gamma_i-1},E_i)\ge\bar{p}_{\xi}(A). \tag*{(268)} F γ i − 1 ; E i ess inf P θ ( D i ∣ F γ i − 1 , E i ) ≥ p ˉ ξ ( A ) . (268)
Here, ess inf F γ i − 1 ; E i \underset{\mathcal{F}_{\gamma_i-1};E_i}{\operatorname{ess\,inf}} F γ i − 1 ; E i ess inf denotes the essential infimum over the set E i E_i E i .
It remains to verify positive survival under (91). Since F 1 ≪ F 0 F_1\ll F_0 F 1 ≪ F 0 ,
P ∞ ( ℓ 1 ≤ b ) > 0. (269) \mathbb{P}_{\infty}(\ell_1\le b)>0. \tag*{(269)} P ∞ ( ℓ 1 ≤ b ) > 0. (269)
Define
H i ≜ ⋂ t = 1 γ i − 1 { ℓ t ≤ b } . (270) H_i\triangleq\bigcap_{t=1}^{\gamma_i-1}\{\ell_t\le b\}. \tag*{(270)} H i ≜ t = 1 ⋂ γ i − 1 { ℓ t ≤ b } . (270)
with H i = Ω H_i = \Omega H i = Ω when γ i = 1 \gamma_i = 1 γ i = 1 . Every observation before γ i \gamma_i γ i has distribution either F 0 F_0 F 0 or F 1 F_1 F 1 . By independence and the positivity of F 0 ( ℓ 1 ≤ b ) F_0(\ell_1 \le b) F 0 ( ℓ 1 ≤ b ) and F 1 ( ℓ 1 ≤ b ) F_1(\ell_1 \le b) F 1 ( ℓ 1 ≤ b ) ,
P θ ( H i ) > 0. (271) \mathbb{P}_{\theta}(H_i) > 0 . \tag*{(271)} P θ ( H i ) > 0. (271)
On H i H_i H i , for every t < γ i t < \gamma_i t < γ i ,
W t ( ξ ) ≤ ∑ k = 1 min { ξ , t } b k < b 1 − b . (272) W_t^{(\xi)} \le\sum_{k=1}^{\min\{\xi,t\}} b^k < \frac{b}{1-b}. \tag*{(272)} W t ( ξ ) ≤ k = 1 ∑ m i n { ξ , t } b k < 1 − b b . (272)
If (93) holds, then H i ⊆ E i H_i \subseteq E_i H i ⊆ E i , and therefore
P θ ( E i ) ≥ P θ ( H i ) > 0. (273) \mathbb{P}_{\theta}(E_i) \ge\mathbb{P}_{\theta}(H_i) > 0 . \tag*{(273)} P θ ( E i ) ≥ P θ ( H i ) > 0. (273)
The episode-wise bounds (267)–(268) therefore hold for every θ ∈ Θ s ( ξ ) \theta\in\Theta_s(\xi) θ ∈ Θ s ( ξ ) and every i ∈ { 1 , … , s } i \in\{1,\ldots,s\} i ∈ { 1 , … , s } . Summing over i i i and taking the infimum over Θ s ( ξ ) \Theta_s(\xi) Θ s ( ξ ) proves (94).
Proof of Theorem 6
Define, once for the remainder of the proof,
p ˉ ε ≜ p ˉ ξ ε ( ε ) . (274) \bar{p}_{\varepsilon} \triangleq\bar{p}_{\xi_{\varepsilon}}(\varepsilon). \tag*{(274)} p ˉ ε ≜ p ˉ ξ ε ( ε ) . (274)
Step 1: The finite-window crossing probability tends to one. Condition (100) implies that there exists a < I a < I a < I such that, for all sufficiently large ε \varepsilon ε ,
log ε ξ ε ≤ a < I . (275) \frac{\log\varepsilon}{\xi_{\varepsilon}} \le a < I . \tag*{(275)} ξ ε log ε ≤ a < I . (275)
Since the maximum defining p ˉ ε \bar{p}_{\varepsilon} p ˉ ε includes S ξ ε S_{\xi_{\varepsilon}} S ξ ε ,
p ˉ ε ≥ P 1 ( S ξ ε ≥ log ε ) ≥ P 1 ( S ξ ε ξ ε ≥ a ) . (276) \bar{p}_{\varepsilon} \ge\mathbb{P}_1\left(S_{\xi_{\varepsilon}} \ge\log\varepsilon\right) \ge\mathbb{P}_1\left(\frac{S_{\xi_{\varepsilon}}}{\xi_{\varepsilon}} \ge a\right). \tag*{(276)} p ˉ ε ≥ P 1 ( S ξ ε ≥ log ε ) ≥ P 1 ( ξ ε S ξ ε ≥ a ) . (276)
The integrability condition (98) and the strong law of large numbers give
S n n ⟶ I P 1 -a.s. (277) \frac{S_n}{n} \longrightarrow I \qquad\mathbb{P}_1\text{-a.s.} \tag*{(277)} n S n ⟶ I P 1 -a.s. (277)
Since ξ ε → ∞ \xi_{\varepsilon} \to\infty ξ ε → ∞ and a < I a < I a < I , equations (276) –(277) imply
p ˉ ε ⟶ 1. (278) \bar{p}_{\varepsilon} \longrightarrow1 . \tag*{(278)} p ˉ ε ⟶ 1. (278)
Step 2: The stopping time is proper and feasible. Equation (276) implies that the terminal product exceeds ε \varepsilon ε with positive probability under F 1 ⊗ ξ ε F_1^{\otimes\xi_\varepsilon} F 1 ⊗ ξ ε for all sufficiently large ε \varepsilon ε . Since F 1 ⊗ ξ ε ≪ F 0 ⊗ ξ ε F_1^{\otimes\xi_\varepsilon} \ll F_0^{\otimes\xi_\varepsilon} F 1 ⊗ ξ ε ≪ F 0 ⊗ ξ ε ,
q ε ≜ P ∞ ( ∏ r = 1 ξ ε ℓ r ≥ ε ) > 0. (279) q_\varepsilon\triangleq\mathbb{P}_{\infty}\left(\prod_{r=1}^{\xi_\varepsilon}\ell_r \ge\varepsilon\right)>0 . \tag*{(279)} q ε ≜ P ∞ ( r = 1 ∏ ξ ε ℓ r ≥ ε ) > 0. (279)
For m ≥ 1 m \ge1 m ≥ 1 , define the crossing event on the m m m th disjoint block by
C ε , m ≜ { ∏ r = ( m − 1 ) ξ ε + 1 m ξ ε ℓ r ≥ ε } . (280) C_{\varepsilon,m} \triangleq\left\{\prod_{r=(m-1)\xi_\varepsilon+1}^{m\xi_\varepsilon}\ell_r \ge\varepsilon\right\}. \tag*{(280)} C ε , m ≜ ⎩ ⎨ ⎧ r = ( m − 1 ) ξ ε + 1 ∏ m ξ ε ℓ r ≥ ε ⎭ ⎬ ⎫ . (280)
Under P ∞ \mathbb{P}_{\infty} P ∞ , these events are independent and have probability q ε q_\varepsilon q ε . Let
G ε ≜ inf { m ≥ 1 : C ε , m occurs } . (281) G_\varepsilon\triangleq\inf\{m \ge1:C_{\varepsilon,m}\ \text{occurs}\}. \tag*{(281)} G ε ≜ inf { m ≥ 1 : C ε , m occurs } . (281)
Then G ε G_\varepsilon G ε is geometric with parameter q ε q_\varepsilon q ε . If C ε , m C_{\varepsilon,m} C ε , m occurs, the complete product over that block is a summand of W m ξ ε ( ξ ε ) W_{m\xi_\varepsilon}^{(\xi_\varepsilon)} W m ξ ε ( ξ ε ) , and hence
τ ε c ≤ ξ ε G ε . (282) \tau_\varepsilon^{c} \le\xi_\varepsilon G_\varepsilon. \tag*{(282)} τ ε c ≤ ξ ε G ε . (282)
Consequently,
P ∞ ( τ ε c < ∞ ) = 1 , E ∞ [ τ ε c ] ≤ ξ ε q ε < ∞ . (283) \mathbb{P}_{\infty}(\tau_\varepsilon^{c}<\infty)=1,\qquad\mathbb{E}_{\infty}[\tau_\varepsilon^{c}]\le\frac{\xi_\varepsilon}{q_\varepsilon}<\infty. \tag*{(283)} P ∞ ( τ ε c < ∞ ) = 1 , E ∞ [ τ ε c ] ≤ q ε ξ ε < ∞. (283)
Lemma 11 supplies the matching feasibility inequality, so
ε ≤ E ∞ [ τ ε c ] < ∞ . (284) \varepsilon\le\mathbb{E}_{\infty}[\tau_\varepsilon^{c}]<\infty. \tag*{(284)} ε ≤ E ∞ [ τ ε c ] < ∞. (284)
This proves (102) .
Step 3: Minimax convergence and optimality. Since ε → ∞ \varepsilon\to\infty ε → ∞ , condition (93) holds with A = ε A=\varepsilon A = ε for all sufficiently large ε \varepsilon ε . Lemma 12 therefore gives
L Q ( τ ε c ) ≥ s p ˉ ε , Q ∈ { L , P } . (285) L_Q(\tau_\varepsilon^{c}) \ge s\bar{p}_\varepsilon,\qquad Q\in\{L,P\}. \tag*{(285)} L Q ( τ ε c ) ≥ s p ˉ ε , Q ∈ { L , P } . (285)
By feasibility and (96) ,
s p ˉ ε ≤ L Q ( τ ε c ) ≤ V Q ∗ ( ε , ξ ε ; s ) ≤ s . (286) s\bar{p}_\varepsilon\le L_Q(\tau_\varepsilon^{c}) \le V_Q^*(\varepsilon,\xi_\varepsilon;s)\le s . \tag*{(286)} s p ˉ ε ≤ L Q ( τ ε c ) ≤ V Q ∗ ( ε , ξ ε ; s ) ≤ s . (286)
Together with (278) , this proves (103) . It also gives the additive bound
0 ≤ V Q ∗ ( ε , ξ ε ; s ) − L Q ( τ ε c ) ≤ s ( 1 − p ˉ ε ) ⟶ 0 , (287) 0\le V_Q^*(\varepsilon,\xi_\varepsilon;s)-L_Q(\tau_\varepsilon^{c})\le s(1-\bar{p}_\varepsilon)\longrightarrow0 , \tag*{(287)} 0 ≤ V Q ∗ ( ε , ξ ε ; s ) − L Q ( τ ε c ) ≤ s ( 1 − p ˉ ε ) ⟶ 0 , (287)
which proves (104) . Finally, p ˉ ε > 0 \bar{p}_\varepsilon>0 p ˉ ε > 0 for all sufficiently large ε \varepsilon ε , and (286) implies
1 ≥ L Q ( τ ε c ) V Q ∗ ( ε , ξ ε ; s ) ≥ p ˉ ε ⟶ 1. (288) 1\ge\frac{L_Q(\tau_\varepsilon^{c})}{V_Q^*(\varepsilon,\xi_\varepsilon;s)}\ge\bar{p}_\varepsilon\longrightarrow1 . \tag*{(288)} 1 ≥ V Q ∗ ( ε , ξ ε ; s ) L Q ( τ ε c ) ≥ p ˉ ε ⟶ 1. (288)
This proves (105) and completes the proof.
Proof of Corollary 2
For the window sequence in (107) ,
lim sup ε → ∞ log ε ξ ε ≤ I 1 + δ < I . (289) \limsup_{\varepsilon\to\infty}\frac{\log\varepsilon}{\xi_\varepsilon}\le\frac{I}{1+\delta}<I . \tag*{(289)} ε → ∞ lim sup ξ ε log ε ≤ 1 + δ I < I . (289)
Therefore, the conclusions for τ ε , ξ ε c \tau_{\varepsilon,\xi_\varepsilon}^{c} τ ε , ξ ε c follow directly from Theorem 6.
Now consider finite thresholds A ^ ε \widehat{A}_\varepsilon A ε satisfying (108) . Lemma 11 gives
A ^ ε ≤ ε . (290) \widehat{A}_\varepsilon\le\varepsilon. \tag*{(290)} A ε ≤ ε . (290)
We next show that A ^ ε → ∞ \widehat{A}_\varepsilon\to\infty A ε → ∞ . Suppose, to the contrary, that along a subsequence A ^ ε ≤ M \widehat{A}_\varepsilon\le M A ε ≤ M for some finite M > 0 M>0 M > 0 . Since S n / n → I > 0 S_n/n\to I>0 S n / n → I > 0 under P 1 \mathbb{P}_1 P 1 , there exists a finite n n n such that
P 1 ( ∏ r = 1 n ℓ ( Z r ) ≥ M ) > 0. (291) \mathbb{P}_1\left(\prod_{r=1}^{n}\ell(Z_r)\ge M\right)>0 . \tag*{(291)} P 1 ( r = 1 ∏ n ℓ ( Z r ) ≥ M ) > 0. (291)
Absolute continuity implies
q M ≜ P ∞ ( ∏ r = 1 n ℓ r ≥ M ) > 0. (292) q_M\triangleq\mathbb{P}_\infty\left(\prod_{r=1}^{n}\ell_r\ge M\right)>0 . \tag*{(292)} q M ≜ P ∞ ( r = 1 ∏ n ℓ r ≥ M ) > 0. (292)
For all sufficiently large ε \varepsilon ε , ξ ε ≥ n \xi_\varepsilon\ge n ξ ε ≥ n . Applying the event in (292) to successive independent n n n -blocks shows that
E ∞ [ τ A ^ ε , ξ ε c ] ≤ n q M < ∞ . (293) \mathbb{E}_\infty\left[\tau_{\widehat{A}_\varepsilon,\xi_\varepsilon}^{c}\right]\le\frac{n}{q_M}<\infty. \tag*{(293)} E ∞ [ τ A ε , ξ ε c ] ≤ q M n < ∞. (293)
This contradicts (108) as ε → ∞ \varepsilon\to\infty ε → ∞ . Hence,
A ^ ε ⟶ ∞ . (294) \widehat{A}_\varepsilon\longrightarrow\infty. \tag*{(294)} A ε ⟶ ∞. (294)
In particular, (93) holds with A = A ^ ε A=\widehat{A}_\varepsilon A = A ε for all sufficiently large ε \varepsilon ε . Moreover, by (290) and monotonicity in the boundary,
p ˉ ξ ε ( A ^ ε ) ≥ p ˉ ξ ε ( ε ) ⟶ 1. (295) \bar{p}_{\xi_\varepsilon}(\widehat{A}_\varepsilon)\ge\bar{p}_{\xi_\varepsilon}(\varepsilon)\longrightarrow1 . \tag*{(295)} p ˉ ξ ε ( A ε ) ≥ p ˉ ξ ε ( ε ) ⟶ 1. (295)
The exact calibration gives feasibility and finite mean. Applying Lemma 12 and the same sandwich argument as in (286) proves all remaining conclusions.