notforprint* trivial ignore* skipproof noignore*

# Detecting an Intermittent Change of Unknown Duration

Grigory Sokolova, Valentin S. Spivakb, and Alexander G. Tartakovskyc aXavier
University, Cincinnati, OH, USA; bSpace Informatics Laboratory, Moscow
Institute of Physics and Technology, Dolgoprudny, Moscow Region, Russia; cAGT
StatConsult, Los Angeles, California, USA

###### Abstract

Oftentimes in practice, the observed process changes statistical properties at
an unknown point in time and the duration of a change is substantially finite,
in which case one says that the change is intermittent or transient. We
provide an overview of existing approaches for intermittent change detection
and advocate in favor of a particular setting driven by the intermittent
nature of the change. We propose a novel optimization criterion that is more
appropriate for many applied areas such as the detection of threats in
physical-computer systems, near-Earth space informatics, epidemiology,
pharmacokinetics, etc. We argue that controlling the local conditional
probability of a false alarm, rather than the familiar average run length to a
false alarm, and maximizing the local conditional probability of detection is
a more reasonable approach versus a traditional quickest change detection
approach that requires minimizing the expected delay to detection. We adopt
the maximum likelihood (ML) approach with respect to the change duration and
show that several commonly used detection rules (CUSUM, window-limited CUSUM,
and FMA) are equivalent to the ML-based stopping times. We discuss how to
choose design parameters for these rules and provide a comprehensive
simulation study to corroborate intuitive expectations.

###### keywords:

Intermittent change detection; change-point detection; sequential detection;
window-limited CUSUM; FMA

##  1 Introduction

The problem of detecting intermittent (or transient) changes is motivated by a
variety of applications such as aerospace navigation and flight systems
integrity monitoring (Tartakovsky, Nikiforov, and Basseville 2014, Ch 11),
cyber-security Debar, Dacier, and Wespi (1999); Ellis and Speed (2001); Kent
(2000); Peng, Leckie, and Ramamohanarao (2004); Tartakovsky et al. (2006a, b);
Tartakovsky (2014), identification of terrorist activity Raghavan, Galstyan,
and Tartakovsky (2013), industrial monitoring Duncan (1986); Jeske et al.
(2018a), air pollution monitoring Mana et al. (2022), radar, sonar, and
electrooptics surveillance systems Bar-Shalom and Li (1993); Blackman,
Dempster, and Broida (1993); Jeske et al. (2018b); Tartakovsky (2002);
Tartakovsky and Brown (2008), (Tartakovsky 2020, Ch 8). As a result, it has
been of interest to many practitioners for some time. However, in contrast to
classical quickest change-point detection, where one’s aim is to detect
persistent changes in the distribution of the signal as quickly as possible,
minimizing the expected delay to detection assuming the change is in effect
(see, e.g., Tartakovsky, Nikiforov, and Basseville (2014); Tartakovsky (2020)
and references therein) a lot fewer publications are devoted to the sequential
detection of intermittent changes Wang and Willett (2005b, a); Ortner and
Nehorai (2007); Guépié, Fillatre, and Nikiforov (2012); Moustakides (2014);
Guépié, Fillatre, and Nikiforov (2017); Rovatsos, Zou, and Veeravalli (2017);
Mana, Guépié, and Nikiforov (2023).

As opposed to the classical change-point detection problem, transient changes
only last for a finite (often short) time. Several main scenarios motivate
intermittent change detection. In one of them, the under-change mode lasts for
a finite and unknown (possibly random) time and can be detected with a certain
delay even after it ends. Examples of such scenarios may be air pollution,
water contamination, and pharmacokinetics/dynamics. In such a case, the
standard approach to detecting changes that prescribes minimizing an average
detection delay with a given false alarm rate may be appropriate. Another
scenario is when a change is associated with a critical anomaly like a threat
(a terrorist physical or computer attack, military targets/threats, etc.) that
appears and disappears at unknown points in time and should be detected not
only as soon as possible but with a delay not bigger than a prescribed value.
In this second case, if the change is detected with a delay larger than a
given time-to-alert, then it is considered completely missed. For example, if
a threat hits an object, then it is too late to detect it. In this case, a
conventional quickest change detection problem setup is not appropriate;
rather, one aims to maximize the probability of detection within a prescribed
time (or space) interval for a given false alarm rate. There is also a third
scenario where the change may last very long but still it may be required to
detect it in a fixed relatively short interval while maximizing the
probability of detection. An example is target track initiation which should
be performed in a very short interval, while tracks last a very long time and
should be estimated with maximal possible accuracy (see, e.g., Spivak and
Tartakovsky (2020)). Therefore, in some cases, taking the quickest detection
approach (Ebrahimzadeh and Tchamkerten (2015); Zou, Fellouris, and Veeravalli
(2017a, b); Rovatsos, Zou, and Veeravalli (2017)) may seem reasonable; in
other cases, it can be argued (Broder and Schwartz (1990); Mei (2008);
Tartakovsky (2008); Bakhache and Nikiforov (2000); Tartakovsky, Nikiforov, and
Basseville (2014); Tartakovsky (2020)) that a substantially different
criterion is called for. Specifically, one’s objective would be to develop and
study detection rules that locally maximize the probability of detection
(rather than its speed) subject to a constraint on the local probability of
false alarm. As in Tartakovsky (2020); Tartakovsky et al. (2021b), we call
this approach _reliable_ change-point detection.

In this work, we consider the case that the change duration is unknown
(focusing on the case that it is deterministic) and examine how the maximum
likelihood ratio approach for various degrees of information on the duration
of the intermittent change yields some well-known change detection rules.
Specifically, we consider three detection procedures: Cumulative Sum (CUSUM)
procedure, window-limited CUSUM, and finite moving average (FMA) procedure,
and compare their performance in terms of the probability of detection versus
the probability of false alarm.

This paper continues the research on reliable change detection along the lines
started by Guépié, Fillatre, and Nikiforov (2017); Tartakovsky (2020);
Berenkov, Tartakovsky, and Kolessa (2020); Mana, Guépié, and Nikiforov (2023)
and its contribution is as follows:

  1. 1.

We propose a new optimality criterion for reliable change detection of
intermittent changes that maximizes the local conditional probability of
detection for a given local conditional probability of false alarm (PFA).

  2. 2.

We show that the conditional PFA criterion is the most stringent compared to
other popular ones such as controlling average run length (ARL) to false alarm
or unconditional PFA.

  3. 3.

We use the maximum likelihood (ML) principle in the context of intermittent
change detection to derive three popular rules, propose a modification of the
FMA detection algorithm driven by its ML origins and show that it has better
operating characteristics compared to the standard one.

  4. 4.

We propose ways to design the aforementioned rules. In particular, for CUSUM
we adapt the integral equations framework and develop efficient numerical
methods that allow for an almost precise evaluation of its operating
characteristics. For window-limited rules, we provide the means to control
(upper-bound) their local conditional PFA and perform a simulation study to
examine its accuracy.

  5. 5.

We validate our analysis and compare CUSUM, window-limited CUSUM, and two FMA
algorithms through numerical results.

The rest of the paper is organized as follows. In Section 2, we discuss
various formulations of transient change detection problems and how they
relate to each other. We propose one particular formulation and lay the common
ground for the remainder of the paper. In Section 3, we take the maximum
likelihood approach to derive three rules commonly seen in literature in the
context of detecting transient changes: CUSUM, window-limited CUSUM, and FMA.
We further propose a modification of FMA driven by the maximum-likelihood
nature of this rule. In Section 4, we propose methods for the choice of design
parameters for the rules under investigation, each driven by the specific
nature of its detection statistic. In Section 5, we perform a numerical study
for CUSUM, and a Monte Carlo simulation for window-limited CUSUM and FMA, to
assess their operating characteristics and the accuracy of the theoretical
bounds/approximations. Lastly, in Section 6 we draw conclusions and discuss
other avenues for advancing the field of transient change detection.

##  2 Change detection formulations

Before we proceed to address the optimization problem associated with
intermittent change detection, we provide a brief overview of different ways
to look at a large class of change detection criteria. We investigate the
differences and common features of various approaches and justify why we focus
on a particular one.

###  2.1 The general model

We start with a sequence of observations $Y_{1},Y_{2},\dots$. At some unknown
moment in time $\nu\in\\{0,1,2,\dots\\}$ the distribution of the observations
may undergo a change that lasts for an unknown time $N$ (random or
deterministic). More specifically, $\nu$ denotes the serial number of the last
pre-change observation, i.e., $Y_{\nu+1}$ is the first under-change
observation and $Y_{\nu+N}$ is the last under-change observation. Let
$\mathbf{Y}^{k}=(Y_{1},\cdots,Y_{k})$ denote the first $k$ observations and
$\mathcal{F}_{k}=\sigma(\mathbf{Y}^{k})$ denote the corresponding filtration.

The joint density $p_{\nu}(\cdot\mid N=n)$ of the first $k$ observations is of
the form

$\displaystyle\begin{split}p_{\nu}(\mathbf{Y}^{k}\mid
N=n)&=\prod_{t=1}^{k}g(Y_{t}\mid\mathbf{Y}^{t-1})\quad\text{for
$k\leqslant\nu$},\\\ p_{\nu}(\mathbf{Y}^{k}\mid
N=n)&=\prod_{t=1}^{\nu}g(Y_{t}\mid\mathbf{Y}^{t-1})\times\prod_{t=\nu+1}^{k}f(Y_{t}\mid\mathbf{Y}^{t-1})\quad\text{for
$\nu<k\leqslant\nu+n$},\\\ p_{\nu}(\mathbf{Y}^{k}\mid
N=n)&=\prod_{t=1}^{\nu}g(Y_{t}\mid\mathbf{Y}^{t-1})\times\prod_{t=\nu+1}^{\nu+n}f(Y_{t}\mid\mathbf{Y}^{t-1})\times\\!\\!\\!\prod_{t=\nu+n+1}^{k}g(Y_{t}\mid\mathbf{Y}^{t-1})\\\
&\hskip 200.0003pt\text{for $k>\nu+n$},\end{split}$ (1)

where $g(Y_{t}\mid\mathbf{Y}^{t-1})$ is the pre-change and
$f(Y_{t}\mid\mathbf{Y}^{t-1})$ is the under-change conditional densities,
respectively.

In what follows, we write $\operatorname{\mathsf{P}}_{\nu}(\cdot\mid N=n)$ for
the probability measure for the whole sequence $\\{Y_{t},t\geqslant 1\\}$ for
each last pre-change index $\nu\geqslant 0$ and change duration $N=n$, under
which the observed sequence has density $p_{\nu}(\cdot\mid N=n)$ defined in
(1). Let $\operatorname{\mathsf{E}}_{\nu}(\cdot\mid N=n)$ denote the
corresponding expectation. We write $\operatorname{\mathsf{P}}_{\infty}$ and
$\operatorname{\mathsf{E}}_{\infty}$ for the probability measure and the
corresponding expectation under the assumption that the change never happens
($\nu=\infty$).

A change detection procedure $T$ is a stopping time with respect to the
filtration $\\{\mathcal{F}_{k}\\}_{k\geqslant 1}$, i.e.,
$\\{T=k\\}\in\mathcal{F}_{k}$. The ultimate goal is to find a stopping time
that is “best” at detecting the intermittent change subject to certain
constraints. We explore various approaches for measuring false alarms and
correct detection in the next subsections to explain what exactly we
understand by “best” and to properly formulate the optimization problem.

###  2.2 Specific i.i.d. formulation

Throughout the rest of the paper, we consider the case that observations are
independent and each observation shares the same density $g$ under the nominal
regime and a different density $f$ when the change is in effect (see the
diagram below).

$\underbrace{Y_{1},\cdots,Y_{\nu}}_{\text{i.i.d.,
$g$}},~{}\underbrace{Y_{\nu+1},\cdots,Y_{\nu+N}}_{\text{i.i.d.,
$f$}},~{}\underbrace{Y_{\nu+N+1},\cdots}_{\text{i.i.d., $g$}}.$

In this special case, the general non-i.i.d. model given in (1) takes the form

$\displaystyle\begin{split}p_{\nu}(\mathbf{Y}^{k}\mid
N=n)&=\prod_{t=1}^{k}g(Y_{t})\quad\text{for $k\leqslant\nu$},\\\
p_{\nu}(\mathbf{Y}^{k}\mid
N=n)&=\prod_{t=1}^{\nu}g(Y_{t})\times\prod_{t=\nu+1}^{k}f(Y_{t})\quad\text{for
$\nu<k\leqslant\nu+n$},\\\ p_{\nu}(\mathbf{Y}^{k}\mid
N=n)&=\prod_{t=1}^{\nu}g(Y_{t})\times\prod_{t=\nu+1}^{\nu+n}f(Y_{t})\times\\!\\!\\!\prod_{t=\nu+n+1}^{k}g(Y_{t})\quad\text{for
$k>\nu+n$},\end{split}$ (2)

so that under the probability measure
$\operatorname{\mathsf{P}}_{\nu}(\cdot\mid N=n)$ observations
$Y_{1},\dots,Y_{\nu}$ and $Y_{\nu+N+1},Y_{\nu+N+2},\dots$ are i.i.d. with
density $g$ and independent of $Y_{\nu+1},\dots,Y_{\nu+N}$, which are i.i.d.
with density $f$.

The stopping times we consider are based on the maximal likelihood ratio
approach. To facilitate their presentation, introduce the instantaneous
likelihood ratios (LR)

$\displaystyle\Lambda_{k}=f(Y_{k})/g(Y_{k})\qquad\text{for $k=1,2,\cdots$},$
(3)

and the instantaneous log-likelihood ratios $\lambda_{k}=\log(\Lambda_{k})$.

Although problem formulation in Sections 2.3 and 2.5, as well as the
definition of the stopping times in Section 3, applies to the general model
(1), the specific form of their detection statistics as well as results
presented in Sections 4 and 5 assume the i.i.d. model (2).

###  2.3 Classes of procedures

For the comparison between different rules to be fair, one restricts oneself
to a certain class of procedures. We review three such classes. Before we
proceed, we introduce three conventional performance measures for an arbitrary
stopping time $T$ under the no-change assumption: (i) average run length to
false alarm ($\operatorname{\mathsf{ARL}}$); (ii) local unconditional
probability of false alarm ($\operatorname{\mathsf{LPFA}^{\star}}_{m}$); and
(iii) local conditional probability of false alarm
($\operatorname{\mathsf{LPFA}}_{m}$). Specifically,

$\displaystyle\operatorname{\mathsf{ARL}}(T)$
$\displaystyle=\operatorname{\mathsf{E}}_{\infty}(T),$
$\displaystyle\operatorname{\mathsf{LPFA}^{\star}}_{m}(T)$
$\displaystyle=\sup_{\ell\geqslant
0}\operatorname{\mathsf{P}}_{\infty}(\ell<T\leqslant\ell+m),$
$\displaystyle\operatorname{\mathsf{LPFA}}_{m}(T)$
$\displaystyle=\sup_{\ell\geqslant
0}\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid T>\ell).$

The first, average run length to false alarm ($\operatorname{\mathsf{ARL}}$),
commonly appears in persistent change-point detection ($N=\infty$) when one
searches for an optimal stopping time in the class of stopping times

$\displaystyle\mathbb{C}_{\gamma}=\left\\{T\,:\,\operatorname{\mathsf{ARL}}(T)\geqslant\gamma\right\\},$
(4)

for some $\gamma\geqslant 1$. However, this class is appropriate only if the
$\operatorname{\mathsf{P}}_{\infty}$-distribution of the stopping time $T$ is
close to geometric, and may become inappropriate for intermittent change
detection (see, e.g., Mei (2008); Tartakovsky (2008); Tartakovsky, Nikiforov,
and Basseville (2014); Tartakovsky (2020)).

The following alternatives address this issue by focusing on constraining
local probability of false alarm (unconditional and conditional,
respectively):

$\displaystyle\mathbb{C}^{\star}(m,\alpha)$
$\displaystyle=\left\\{T\,:\,\operatorname{\mathsf{LPFA}^{\star}}_{m}(T)\leqslant\alpha\right\\},$
(5) $\displaystyle\mathbb{C}(m,\alpha)$
$\displaystyle=\left\\{T\,:\,\operatorname{\mathsf{LPFA}}_{m}(T)\leqslant\alpha\right\\},$
(6)

for some $m\geqslant 1$ and $0<\alpha<1$.

Let us look into the relationship between the three classes. It turns out that
all three are essentially different, with $\mathbb{C}_{\gamma}$ being the
least restrictive and $\mathbb{C}(m,\alpha)$ the most stringent.

######  Proposition 1.

$\mathbb{C}(m,\alpha)$ is more stringent than $\mathbb{C}^{\star}(m,\alpha)$.
In particular, if $T\in\mathbb{C}(m,\alpha)$, then
$T\in\mathbb{C}^{\star}(m,\alpha)$

###### Proof.

It is not hard to see that
$\mathbb{C}(m,\alpha)\subseteq\mathbb{C}^{\star}(m,\alpha)$ for every
$m\geqslant 1$ and $0<\alpha<1$ since
$\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid
T>\ell)\geqslant\operatorname{\mathsf{P}}_{\infty}(\ell<T\leqslant\ell+m)$ for
all $\ell>0$.

Suppose now that $\mathbb{C}^{\star}(m,\alpha)$ can be covered by
$\mathbb{C}(m^{\prime},\alpha^{\prime})$ for some $m^{\prime}\geqslant 1$ and
$0<\alpha^{\prime}<1$. Consider a stopping time $T_{r}$ such that

$\displaystyle\operatorname{\mathsf{P}}_{\infty}(T_{r}=i)$
$\displaystyle=1/(K+1)\quad$ $\displaystyle\text{for $1\leqslant i\leqslant
K$},$ $\displaystyle\operatorname{\mathsf{P}}_{\infty}(T_{r}=K+j)$
$\displaystyle=r\,(1-r)^{j-1}/(K+1)\quad$ $\displaystyle\text{for $j\geqslant
1$},$

where $K=\left\lceil m/\alpha\right\rceil$. Clearly,
$T_{r}\in\mathbb{C}^{\star}(m,\alpha)$ for any $r$, $0<r<1$. However,

$\displaystyle\operatorname{\mathsf{LPFA}}_{m^{\prime}}(T_{r})$
$\displaystyle\geqslant\sup_{\ell\geqslant
K}\operatorname{\mathsf{P}}_{\infty}(T_{r}\leqslant\ell+m^{\prime}\mid
T_{r}>\ell)=1-(1-r)^{m^{\prime}},$

and $r$ can be chosen so that
$\operatorname{\mathsf{LPFA}}_{m^{\prime}}(T_{r})>\alpha^{\prime}$, which
leads to a contradiction. ∎

Now, when we consider $\mathbb{C}_{\gamma}$, it is intuitively obvious that
large values of the ARL to false alarm do not necessarily guarantee small
values of the maximal probability of false alarm, which has been discussed in
Tartakovsky (2008); Tartakovsky, Nikiforov, and Basseville (2014); Tartakovsky
(2020); Tartakovsky et al. (2021b). The following two propositions further
highlight this relationship.

######  Proposition 2.

$\mathbb{C}(m,\alpha)$ is more stringent than $\mathbb{C}_{\gamma}$. In
particular, if $T\in\mathbb{C}(m,\alpha)$, then $T\in\mathbb{C}_{\gamma}$ for

$\displaystyle\gamma-1=m\left(\frac{1}{\alpha}-1\right).$ (7)

###### Proof.

Fix $m\geqslant 1$ and $0<\alpha<1$, and consider an arbitrary stopping time
$T\in\mathbb{C}(m,\alpha)$:

$\displaystyle\sup_{\ell\geqslant
0}\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid
T>\ell)\leqslant\alpha.$ (8)

Our goal is to show that
$\operatorname{\mathsf{E}}_{\infty}(T)\geqslant\gamma$ for some
$\gamma=\gamma(m,\alpha)$. With very small loss of generality consider only
stopping times that are almost surely positive, i.e.,
$\operatorname{\mathsf{P}}_{\infty}(T=0)=0$.

Using induction

$\displaystyle\operatorname{\mathsf{P}}_{\infty}(T>i+k\,m\mid T>i)$
$\displaystyle=\operatorname{\mathsf{P}}_{\infty}\left(T>[i+(k-1)\,m]+m\mid
T>[i+(k-1)\,m]\right)$
$\displaystyle\quad\times\operatorname{\mathsf{P}}_{\infty}\left(T>i+(k-1)\,m\mid
T>i+(k-1)\,m\right),$

we obtain

$\displaystyle\begin{split}\operatorname{\mathsf{P}}_{\infty}(T>i+k\,m\mid
T>i)=\prod_{j=0}^{k-1}\operatorname{\mathsf{P}}_{\infty}\left(T>[i+jm]+m\mid
T>[i+jm]\right)\geqslant(1-\alpha)^{k},\end{split}$ (9)

where the last inequality follows from the fact that by (8)

$\operatorname{\mathsf{P}}_{\infty}(T>\ell+m\mid T>\ell)\geqslant
1-\alpha\quad\text{for all}~{}\ell\geqslant 1.$

Now,

$\displaystyle\operatorname{\mathsf{E}}_{\infty}(T)$
$\displaystyle=\sum_{\ell=0}^{\infty}\operatorname{\mathsf{P}}_{\infty}(T>\ell)$
$\displaystyle=\sum_{i=0}^{m-1}\sum_{k=0}^{\infty}\operatorname{\mathsf{P}}_{\infty}(T>i+k\,m)$
$\displaystyle=\sum_{i=0}^{m-1}\operatorname{\mathsf{P}}_{\infty}(T>i)\sum_{k=0}^{\infty}\operatorname{\mathsf{P}}_{\infty}(T>i+k\,m\mid
T>i).$

It follows from (9) that for the inner summation

$\displaystyle\sum_{k=0}^{\infty}\operatorname{\mathsf{P}}_{\infty}(T>i+k\,m\mid
T>i)$ $\displaystyle\geqslant\sum_{k=0}^{\infty}(1-\alpha)^{k}=1/\alpha,$

and for the outer summation

$\displaystyle\sum_{i=0}^{m-1}\operatorname{\mathsf{P}}_{\infty}(T>i)$
$\displaystyle\geqslant
1+\sum_{i=1}^{m-1}\operatorname{\mathsf{P}}_{\infty}(T>m)$
$\displaystyle\geqslant 1+\sum_{i=1}^{m-1}(1-\alpha)=\alpha+m(1-\alpha).$

Combining these two inequalities together, we get that

$\displaystyle\operatorname{\mathsf{E}}_{\infty}(T)\geqslant\gamma(m,\alpha)\quad\text{for}~{}\gamma(m,\alpha)=1+m(1-\alpha)/\alpha,$
(10)

which completes the first part of the proof.

On the other hand, if $T\in\mathbb{C}_{\gamma}$, then in general there is no
$\alpha(m,\gamma)$ such that
$\operatorname{\mathsf{LPFA}}_{m}(T)\leqslant\alpha(m,\gamma)$. Indeed,
suppose that $\mathbb{C}_{\gamma}$ can be covered by $\mathbb{C}(m,\alpha)$
for some $m\geqslant 1$ and $0<\alpha<1$. Consider
$T_{r}=\left\lceil\gamma\right\rceil+G_{r}$, where $G_{r}$ is geometrically
distributed with parameter $r$, $\alpha<r<1$. Clearly, $T_{r}\in C_{\gamma}$.
However,

$\operatorname{\mathsf{LPFA}}_{m}(T_{r})\geqslant\sup_{\ell\geqslant\gamma}\operatorname{\mathsf{P}}_{\infty}(T_{r}\leqslant\ell+m\mid
T>\ell)=1-(1-r)^{m}\geqslant r>\alpha,$

which contradicts our assumption that $\mathbb{C}_{\gamma}$ can be covered by
$\mathbb{C}(m,\alpha)$ and completes the proof. ∎

######  Proposition 3.

$\mathbb{C}^{\star}(m,\alpha)$ is more stringent than $\mathbb{C}_{\gamma}$.
In particular, if $T\in\mathbb{C}^{\star}(m,\alpha)$, then
$T\in\mathbb{C}_{\gamma}$ for

$\displaystyle\gamma-1=\frac{m}{2}\left(\left\lfloor\frac{1}{\alpha}\right\rfloor-1\right).$
(11)

###### Proof.

To show that any $\mathbb{C}^{\star}(m,\alpha)$ can be covered by some
$\mathbb{C}_{\gamma}$ fix $m\geqslant 1$ and $0<\alpha<1$ and let $T$ be such
that

$\operatorname{\mathsf{P}}_{\infty}(T=1+jm)=\begin{cases}\alpha\quad&\text{for
$0\leqslant j\leqslant K-1$},\\\ 1-K\alpha&\text{for $j=K$},\end{cases}$

where $K=\left\lfloor 1/\alpha\right\rfloor$. Clearly,
$T\in\mathbb{C}^{\star}(m,\alpha)$ and

$\displaystyle\operatorname{\mathsf{E}}_{\infty}(T)=1+Km-K\,\frac{m\alpha}{2}-K^{2}\,\frac{m\alpha}{2}\geqslant
1+\frac{m}{2}\left(\left\lfloor\frac{1}{\alpha}\right\rfloor-1\right),$

which proves that $T\in\mathbb{C}^{\star}(m,\alpha)$ implies
$T\in\mathbb{C}_{\gamma}$ with $\gamma=\gamma(m,\alpha)$ given by (11).

Now, suppose that $\mathbb{C}_{\gamma}$ can be covered by
$\mathbb{C}(m,\alpha)$ for some $m\geqslant 1$ and $0<\alpha<1$. As before,
consider $T_{r}=\left\lceil\gamma\right\rceil+G_{r}$, where $G_{r}$ is
geometrically distributed with parameter $r$, $\alpha<r<1$. Clearly, $T_{r}\in
C_{\gamma}$. However,

$\operatorname{\mathsf{LPFA}^{\star}}_{m}(T_{r})=\operatorname{\mathsf{P}}_{\infty}(T_{r}\leqslant\left\lceil\gamma\right\rceil+m)=1-(1-r)^{m}\geqslant
r>\alpha,$

which contradicts the assumption and completes the proof. ∎

It is also worth pointing out that class $\mathbb{C}(m,\alpha)$ is the most
natural choice for a practitioner. Indeed, notice that a large value of the
ARL to false alarm $\gamma$ does not necessarily guarantee small values of the
maximal probabilities of false alarm,
$\sup_{\ell}\operatorname{\mathsf{P}}_{\infty}(\ell<T\leqslant\ell+m)$ and
$\sup_{\ell}\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid T>\ell)$,
as has been discussed by Lai (1998), Tartakovsky (2008), and Tartakovsky,
Nikiforov, and Basseville (2014) in detail. Therefore, class
$\mathbb{C}_{\gamma}$ may not be appropriate in a general case. Now, assume
that there is no change and consider a geometrically distributed stopping
time111For example, the stopping times of the CUSUM and Shyriaev-Roberts (SR)
detection procedures that start from the random initial conditions distributed
according to quasi-stationary distributions are geometrically distributed., in
which case there is a one-to-one correspondence between classes
$\mathbb{C}_{\gamma}$ and $\mathbb{C}(m,\alpha)$. Due to its memorylessness
property, it is clear that as long as an alarm has not been raised, one can
ignore the past observations and focus on detecting the change as if one just
started the observation process. This is in contrast to the unconditional
$\mathbb{C}^{\star}(m,\alpha)$ that only takes into account the time when the
procedure is initiated, disregarding the evolution of the observer. Moreover,
in this case, the unconditional probability
$\operatorname{\mathsf{P}}_{\infty}(\ell<T\leqslant\ell+m)$ achieves maximal
value at $\ell=0$ and decays exponentially fast with $\ell$, while the
conditional probability
$\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid T>\ell)$ is constant.
So, it hardly makes sense to maximize unconditional probability which has its
maximum at $\ell=0$ and becomes almost $0$ after a handful of observations.
All aforementioned is true approximately in many cases where the properly
normalized no-change distribution of stopping times is asymptotically
exponential, which in the i.i.d. case is true for several detection procedures
such as CUSUM and SR (see Pollak and Tartakovsky (2009)), SR mixtures when
post-change parameters are unknown (see Yakir (1995)), and for the generalized
likelihood ratio CUSUM even in a substantially non-stationary case (see Liang,
Tartakovsky, and Veeravalli (2022)).

The above argument allows us to conclude that class $\mathbb{C}(m,\alpha)$ is
the most appropriate for most applications even if the ARL to a false alarm
can be used as a measure of false alarms.

###  2.4 The classical quickest change-point detection problem

As discussed in Tartakovsky, Nikiforov, and Basseville (2014), there are
several optimization criteria in the quickest change-point detection problems,
which differ by available prior information and the definition of the false
alarm rate. One popular minimax criterion was introduced by Lorden (1971) in
his seminal paper:

$\inf_{T\in\mathbb{C}_{\gamma}}\sup_{\nu\geqslant
0}\operatorname*{ess\,sup}\operatorname{\mathsf{E}}_{\nu}[T-\nu\mid
T>\nu,Y_{1},\dots,Y_{\nu}].$

It requires minimizing the conditional expected delay to detection
$\operatorname{\mathsf{E}}_{\nu}[T-\nu\mid T>\nu,\mathcal{F}_{\nu}]$ in the
worst-case scenario with respect to both the change point $\nu$ and the
trajectory $(Y_{1},\dots,Y_{\nu})$ of the observed process in the class of
detection procedures $\mathbb{C}_{\gamma}$ with
$\operatorname{\mathsf{ARL}}(T)\geqslant\gamma$. Hereafter
$\operatorname*{ess\,sup}$ stands for essential supremum. Lorden proved that
Page’s CUSUM detection procedure is asymptotically first-order minimax optimal
as $\gamma\to\infty$. Later on, Moustakides (1986) in his ingenious paper
established the exact optimality of CUSUM for any ARL to false alarm
$\gamma\geqslant 1$.

Another popular, less pessimistic minimax criterion is due to Pollak (1985)

$\inf_{T\in\mathbb{C}_{\gamma}}\sup_{\nu\geqslant
0}\operatorname{\mathsf{E}}_{\nu}[T-\nu\mid T>\nu],$

which requires minimizing the conditional expected delay to detection
$\operatorname{\mathsf{E}}_{\nu}[T-\nu\mid T>\nu]$ in the worst-case scenario
with respect to the change point $\nu$ subject to a lower bound $\gamma$ on
the ARL to false alarm. Pollak (1985) showed that the modified Shiryaev-
Roberts (SR) detection procedure that starts from the quasi-stationary
distribution of the SR statistic is third-order asymptotically optimal as
$\gamma\to\infty$, i.e., the best one can attain up to an additive term
$o(1)$, where $o(1)\to 0$ as $\gamma\to\infty$. Later Tartakovsky, Pollak, and
Polunchenko (2012) proved that this is also true for the SR-$r$ procedure that
starts from the fixed but specially designed point $r$. See also Polunchenko
and Tartakovsky (2010) on exact optimality of the SR-$r$ procedure in a
special case.

As mentioned in the introduction, the quickest change detection criteria may
not be appropriate for the detection of transient changes of finite length $N$
in scenarios where detecting the change outside of the interval
$[\nu+1,\nu+N]$ leads to too large a loss associated with missed detection. In
the rest of the paper, we focus on reliable change detection.

###  2.5 Reliable change detection optimization problem

In what follows, we restrict ourselves to class $\mathbb{C}(m,\alpha)$ defined
in (6). The task is to find a stopping time $T^{\star}\in\mathbb{C}(m,\alpha)$
that optimizes the chosen performance measure. Just like there are different
approaches for measuring the probability of false alarm, one can define the
local probability of detection ($\operatorname{\mathsf{LPD}}$) in several
different ways. Since we focus on (6), we do not consider the unconditional
local probability of detection considered, e.g., in Bakhache and Nikiforov
(2000), and only mention two alternatives.

The motivating performance measure introduced by Tartakovsky (2020) (Ch. 5)
considers a random signal duration $N$ with known prior distribution
$\pi=\\{\pi_{k}\\}_{k\geqslant 1}$, and was used, e.g., in Tartakovsky et al.
(2021b). Specifically, the problem is to find a stopping time $T$ that
maximizes

$\displaystyle\inf_{\nu\geqslant
0}\sum_{k=1}^{\infty}\pi_{k}\operatorname*{ess\,inf}\operatorname{\mathsf{P}}_{\nu}(\nu<T\leqslant\nu+k\mid\mathcal{F}_{\nu},N=k),$
(12)

where $\operatorname*{ess\,inf}$ stands for essential infimum. However, we
adopt a different, less pessimistic measure

$\displaystyle\operatorname{\mathsf{LPD}}_{\pi}(T)$
$\displaystyle=\inf_{\nu\geqslant
0}\sum_{k=1}^{\infty}\pi_{k}\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+k\mid
T>\nu,N=k),$ (13)

where $\pi$ is a valid pmf, corresponding either to the prior distribution of
the signal duration if $N$ is random, or, in the case that $N$ is
deterministic, to weights incorporating information about what $N$ could be,
e.g., uniform weights would be appropriate if only the lower and upper bounds
on the change duration are available. Note that weighting detection
probabilities associated with different change durations is essential even in
the case that $N$ is deterministic: if we simply took infimum over all
$\nu\geqslant 0$ and $N\geqslant 1$, the case of $N=1$ would dominate the
problem since $N=1$ corresponds to the shortest (hence most difficult) change
one could try to capture. More formally, this is a direct consequence of the
fact that $\\{T\leqslant n\\}\in\mathcal{F}_{n}$.

One’s objective then is to solve the optimization problem

$\displaystyle\sup_{T\in\mathbb{C}(m,\alpha)}\operatorname{\mathsf{LPD}}_{\pi}(T).$
(14)

One important practical problem is to maximize the probability of detection in
some pre-specified window $M$ (possibly random) that does not exceed $N$, say
detecting track initiation in a small window $M\ll N$. In such scenarios,
rather than setting $\pi$ to denote the pmf of the change duration in (13),
one would set it to be the pmf of the detection window, since
$\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+k\mid T>\nu,M=k\leqslant
N)=\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+k\mid T>\nu,N=k)$. Another
possible motivation for the choice of $\pi$ in the deterministic $N$ case is
mentioned in Section 6 (although we do not address it in this work). Lastly,
we would like to note that the case that $N$ is known has been considered by,
e.g., Guépié, Fillatre, and Nikiforov (2012, 2017); Tartakovsky (2020); Mana,
Guépié, and Nikiforov (2023).

In the remainder of the work, $\mathcal{D}$ denotes the essential support of
$N$ if it is random, or $\mathcal{D}=\left\\{k\,:\,\pi_{k}>0\right\\}$
otherwise.

##  3 Maximal likelihood ratio-based rules

In this section, we review several popular detection procedures that may
appear to be nearly optimal when the probability of false alarm is small.
These procedures are designed, analyzed and compared in Sections 4 and 5.
However, all of them stem from the maximization of likelihood ratios paradigm
in the context of intermittent change detection. Specifically, we consider the
following scenarios.

  * •

No information on the change duration is available (Section 3.1).

  * •

An upper bound on the change duration is known (Section 3.2).

  * •

The change duration is known (Section 3.3).

The three, respectively, give rise to the CUSUM rule; the so-called window-
limited CUSUM (WL CUSUM) rule; and the Finite Moving Average (FMA) procedure.

###  3.1 No information on change duration

Consider the pessimistic case where no information about the change duration
is available. A natural choice of stopping time is based on the maximal
likelihood ratio process for the intermittent change, with maximization over
both the starting point and the endpoint of the change, with no constraints on
the signal duration (except that it hadn’t ended before the observation
started):

$\displaystyle\widetilde{V}_{n}=\max_{-\infty\leqslant k\leqslant
n}\,\max_{\max\\{1,k\\}\leqslant\ell\leqslant
n}\Bigg{[}\sum_{i=k}^{\ell}\lambda_{i}\Bigg{]},$ (15)

where $\lambda_{i}=\log\Lambda_{i}$ denotes the instantaneous log-likelihood
ratio for the $i$th observation (see (3)). Maximization region is illustrated
on the diagram below, where the highlighted region corresponds to the
additional maximization points added when transitioning from
$\widetilde{V}_{n-1}$ to $\widetilde{V}_{n}$ (and also coincides with the
maximization region for the traditional “permanent-change” CUSUM at step $n$).

starts at $k$stops at $\ell$now$1$$2$$\cdots$$n$$1$$\vdots$$n-1$$n$

The corresponding stopping time is

$\displaystyle\widetilde{T}=\widetilde{T}(b)$ $\displaystyle=\inf\\{n\geqslant
1\,:\,\widetilde{V}_{n}\geqslant b\\},$

where $b=b(m,\alpha)$ is chosen so that
$\operatorname{\mathsf{LPFA}}_{m}(\widetilde{T})=\alpha$.

Note that due to the unknown signal duration, the recursive form of (15) is
not as simple as in the conventional (when the change is persistent) CUSUM.
Introducing the conventional CUSUM statistic

$\displaystyle V_{n}$
$\displaystyle=\max\left\\{0,V_{n-1}\right\\}+\lambda_{n}\qquad\text{for
$n\geqslant 1$, with $V_{0}=0$},$ (16)

it is not difficult to show that

$\displaystyle\widetilde{V}_{n}=\max\left\\{\widetilde{V}_{n-1},V_{n}\right\\}\qquad\text{for
$n\geqslant 1$, with $\widetilde{V}_{0}=0$}.$ (17)

In other words, the process $\\{\widetilde{V}_{n}\\}$ is nothing but the
running maximum value of the CUSUM process $\\{V_{n}\\}$. An immediate
consequence is that the stopping time $\widetilde{T}$ coincides with the
classical Page’s CUSUM (Page (1954)) stopping time

$\displaystyle\widetilde{T}(b)=T_{\textsf{CS}}(b)=\inf\big{\\{}n\geqslant
1\,:\,\max_{1\leqslant k\leqslant n}\sum_{i=k}^{n}\lambda_{i}\geqslant
b\big{\\}}=\inf\left\\{n\geqslant 1\,:\,V_{n}\geqslant b\right\\}.$ (18)

###### Proof of recursion.

Consider $\widetilde{V}_{n}$ for $n\geqslant 2$:

$\displaystyle\widetilde{V}_{n}=\max_{1\leqslant k\leqslant
n}\max_{k\leqslant\ell\leqslant
n}\sum_{i=k}^{\ell}\lambda_{i}=\max\Big{\\{}\widetilde{V}_{n-1},\max_{1\leqslant
k\leqslant n}\sum_{i=k}^{n}\lambda_{i}\Big{\\}}.$

The first term covers all changes that ended at or before time $(n-1)$. The
second term takes into account all changes that ended at time $n$ and is
nothing but the “persistent-change” CUSUM with a well-known recursion given by
(16). ∎

###  3.2 Upper bound on change duration

Suppose now that one knows that the change duration cannot exceed a given
window size $M$, $M\geqslant 1$. A reasonable course of actions in such
circumstance is to maximize the likelihood ratio over changes that end after
the observation starts with the signal duration constraint in mind:

$\displaystyle\widetilde{V}_{n:M}=\max_{-M+2\leqslant k\leqslant
n}\,\max_{\max\\{1,k\\}\leqslant\ell\leqslant\min\\{n,k+M-1\\}}\Bigg{[}\sum_{i=k}^{\ell}\lambda_{i}\Bigg{]}.$
(19)

Compared to (15), maximization happens over a strip-like region (rather than
triangular), thus $\widetilde{V}_{n:M}\leqslant\widetilde{V}_{n}$ for all $n$.

starts at $k$stops at $\ell$now$-M+2$$1$$2$$\cdots$$n$$n-1$$n$$M$

Consequently, it leads to a different recursion:

$\displaystyle\widetilde{V}_{n:M}=\max\\{\widetilde{V}_{n-1:M},V_{n:M}\\}\quad\text{for
$n\geqslant 1$, with $\widetilde{V}_{0:M}=0$},$

where

$V_{n:M}=\max_{\max\\{1,n-M+1\\}\leqslant k\leqslant
n}\sum_{i=k}^{n}\lambda_{i}.$

One can think of $\\{V_{n:M}\\}$ as a window-restricted version of the CUSUM
statistic, $\\{V_{n}\\}$, although it no longer assumes a _cumulative sum_
representation. However, it may be implemented by re-running the CUSUM
recursion on the latest $M$ observations with each new observation. As with
(15), the statistic (19) is non-decreasing. The corresponding stopping time is

$T_{\textsf{WL}:M}=\inf\\{n\geqslant 1\,:\,\widetilde{V}_{n:M}\geqslant
b\\}=\inf\\{n\geqslant 1\,:\,V_{n:M}\geqslant b\\},$ (20)

where $b=b(m,\alpha)$ is chosen so that
$\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{WL}:M})=\alpha$. It can be also
rewritten as

$\displaystyle T_{\textsf{WL}:M}=\inf\Big{\\{}n\geqslant
1\,:\,\max_{\max\\{1,n-M+1\\}\leqslant k\leqslant
n}\sum_{i=k}^{n}\lambda_{i}\geqslant b\Big{\\}}.$ (21)

A version of this rule, dubbed window-limited CUSUM (WL CUSUM), was proposed
by Willsky and Jones (1976) and later on extensively studied in various
settings including change-point detection, such as Lai (1998); Guépié,
Fillatre, and Nikiforov (2012, 2017); Tartakovsky (2020); Mana, Guépié, and
Nikiforov (2023).

###  3.3 Change duration is known

In the case that we assume the change duration is known and equal to $M$, the
detection statistic is

$\displaystyle\max_{-M+2\leqslant k\leqslant
n}\left[\sum_{i=\max\\{1,k\\}}^{k+M-1}\lambda_{i}\right].$ (22)

Note that if the change starts early on we try to capture it with truncated
log-likelihood ratio, $\sum_{i=1}^{n}\lambda_{i}$, $1\leqslant n\leqslant
M-1$. We would like to emphasize that we do _not_ consider changes shorter
than $M$, just that for the first $M-1$ observations we only see part of the
whole change. This contrasts with the previous cases (CUSUM and window-limited
CUSUM), where at each moment in time there is at least one change scenario
that is _fully_ within the observation bounds. For this reason, we recommend
that the first $M-1$ thresholds be adjusted to compensate for the unobserved
portion of the change (see figure below).

starts at $k$stops at $\ell$now$-M+2$$1$$n-M+1$$1$$M$$\vdots$$n$

The resulting stopping time can be expressed by

$\displaystyle T_{\textsf{FMA}:M}$ $\displaystyle=\inf\Big{\\{}n\geqslant
1\,:\,\sum_{i=\max\\{1,n-M+1\\}}^{n}\lambda_{i}\geqslant b_{n}\Big{\\}},$ (23)

where $b_{n}=b$ for all $n\geqslant M$, and for $1\leqslant n\leqslant M-1$
are chosen such that

$\operatorname{\mathsf{P}}_{\infty}\Big{(}\sum_{i=1}^{n}\lambda_{i}\geqslant
b_{n}\Big{)}=\operatorname{\mathsf{P}}_{\infty}\Big{(}\sum_{i=1}^{M}\lambda_{i}\geqslant
b\Big{)},$

or, equivalently,

$\displaystyle b_{n}=H_{n}^{-1}\big{(}H_{M}(b)\big{)}\qquad\text{for
$1\leqslant n<M$},$ (24)

where $H_{n}$ is the cdf of $\sum_{i=1}^{n}\lambda_{i}$ under
$\operatorname{\mathsf{P}}_{\infty}$, which in most cases is either known or
amenable to numerical calculation. This rule is a modification of a rule which
is commonly known as Finite Moving Average (FMA for short). A standard
alternative approach, which we advocate against but still consider in our
simulations (Section 5), would be to skip the first $M-1$ observations
altogether (corresponding to the changes that could not be fully observed) and
only stop at times $\geqslant M$.

The later standard FMA rule has been studied extensively, e.g., Lai (1974)
examined it from the quality control perspective, while Egea-Roca et al.
(2018) considered it in the context of intermittent signal detection. In the
special case that $f$ and $g$ are Gaussian the truncated version of FMA is
equivalent to $\inf\\{n\geqslant M\,:\,\sum_{i=n-M+1}^{n}Y_{i}\geqslant c\\}$,
and as such this simplified version has gained some attention as a more
tractable problem by Noonan and Zhigljavsky (2020, 2021).

##  4 Choosing thresholds

One of the first steps in designing any stopping rule $T$ is to ensure that
$T\in\mathbb{C}(m,\alpha)$, that is, its $\operatorname{\mathsf{LPFA}}(T)$ is
upper-bounded by $\alpha$.

There are various approaches that one can take in order to choose the
thresholds of these procedures to ensure that these rules are in class
$\mathbb{C}(m,\alpha)$. One such way takes advantage of the asymptotic
distribution of the stopping times, which under the no-change hypothesis is
often exponential (see, e.g., Pollak and Tartakovsky (2009)). Suppose that
under $\operatorname{\mathsf{P}}_{\infty}$ a stopping time $T$ is
geometrically distributed with parameter $\varrho$, at least approximately.
That is,

$\operatorname{\mathsf{P}}_{\infty}(T=k)=\varrho\,(1-\varrho)^{k-1}\qquad\text{for
$k=1,2,\cdots$.}$

It is not hard to see that in this case the expression
$\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid T>\ell)$ does not
depend on $\ell$, $\ell\geqslant 0$, and

$\operatorname{\mathsf{LPFA}}_{m}(T)=1-(1-\varrho)^{m}.$

Clearly, in this case, there is one-to-one correspondence between
$\operatorname{\mathsf{LPFA}}_{m}(T)$ and $\operatorname{\mathsf{ARL}}(T)$,
and in order to ensure that $T\in\mathbb{C}(m,\alpha)$ it suffices to set

$\operatorname{\mathsf{ARL}}(T)=\frac{1}{1-(1-\alpha)^{1/m}}.$ (25)

Unfortunately, there is only a handful of cases when the no-change
distribution of the stopping time is exactly geometric. Examples include the
Shewhart procedure (Tartakovsky 2020, Sec 5.2), the randomized at $0$ CUSUM
procedure when the CUSUM statistic $V_{n}$ starts not from $V_{0}=0$ but from
the random value $V_{0}$ with the quasi-stationary distribution of the CUSUM
statistic $\operatorname{\mathsf{P}}(V_{0}\leqslant
v)=\lim_{n\to\infty}\operatorname{\mathsf{P}}_{\infty}(V_{n}\leqslant v\mid
T_{\rm CS}>n)$, and the Shiryaev-Roberts-Pollak procedure that starts from the
quasi-stationary distribution of the Shiryaev-Roberts statistic.

Typically, $\operatorname{\mathsf{P}}_{\infty}$-distributions of the properly
normalized stopping times are asymptotically exponential. For example, it
follows from Pollak and Tartakovsky (2009) that $T_{\rm
CS}/\operatorname{\mathsf{ARL}}(T_{\rm CS})$ is asymptotically exponential as
$\operatorname{\mathsf{ARL}}(T_{\rm CS})$ is large. Moreover, asymptotics kick
in for moderate values of $\operatorname{\mathsf{ARL}}$ which are reasonable
for practical applications. Then if the estimate of
$\operatorname{\mathsf{ARL}}$ is available, the approximation of the
$\operatorname{\mathsf{LPFA}}(T)$ can be easily found, e.g., using (25).

However, such a general approach does not take advantage of the structure of
the stopping time. To this end, we review the three rules presented in the
previous section and exploit their properties to propose more reliable and
accurate design methods.

###  4.1 CUSUM design

We begin with the numerical approach for designing the CUSUM detection
procedure given by the stopping time (18),
$T_{\textsf{CS}}=\inf\left\\{n\geqslant 1\,:\,V_{n}\geqslant b\right\\}$,
where the CUSUM statistic satisfies the recursion

$\displaystyle V_{n}=\max\\{0,V_{n-1}\\}+\lambda_{n},\quad n\geqslant 1,\quad
V_{0}=0.$

Note that $V_{n}$ is a homogeneous Markov process. For such stopping times one
does not have to rely on Monte-Carlo methods to choose design parameters.
Instead, one can adopt a numerical framework based on integral equations
developed by Moustakides, Polunchenko, and Tartakovsky (2011), which provides
an accurate deterministic method of evaluating various operating
characteristics with any desired precision. We adapt it for CUSUM (18) in
order to get a handle on both
$\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{CS}})$ and
$\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{CS}})$.

To this end, consider a version of (18) with its recursive statistic
initialized at an arbitrary point $r<b$. Specifically,

$\displaystyle T_{\textsf{CS}}^{\star}(r)=\inf\left\\{n\geqslant
1\,:\,V_{n}^{\star}(r)\geqslant b\right\\},$

where

$V_{n}^{\star}(r)=\max\\{0,V_{n-1}^{\star}(r)\\}+\lambda_{n},\quad
V_{0}^{\star}(r)=r.$

Let $F_{j}$ denote the cdf of $\Lambda_{1}=e^{\lambda_{1}}$ under
$\operatorname{\mathsf{P}}_{j}$ for $j=0,\infty$, and introduce

$\displaystyle\rho_{\ell,\infty}(r)$
$\displaystyle=\operatorname{\mathsf{P}}_{\infty}(T_{\textsf{CS}}^{\star}(r)>\ell),\qquad$
$\displaystyle\rho_{0,\infty}(r)$ $\displaystyle\equiv 1,$
$\displaystyle\rho_{\ell,\nu:n}(r)$
$\displaystyle=\operatorname{\mathsf{P}}_{\nu}\big{(}T_{\textsf{CS}}^{\star}(r)>\ell\mid
N=n\big{)},\qquad$ $\displaystyle\rho_{0,\nu:n}(r)$ $\displaystyle\equiv 1.$

Then, for $\ell\geqslant 1$, denoting $B=e^{b}$, one has

$\displaystyle\rho_{\ell,\infty}(r)$
$\displaystyle=\int_{0}^{B}\rho_{\ell-1,\infty}(x)\,{\rm
d}F_{\infty}\left(\frac{x}{\max\\{1,r\\}}\right),$ (26)

and

$\displaystyle\rho_{\ell,\nu:n}(r)$
$\displaystyle=\int_{0}^{B}\rho_{\ell-1,\nu:n}(x)\,{\rm
d}F_{J(\ell,\nu:n)}\left(\frac{x}{\max\\{1,r\\}}\right),$ (27)

where $J(\ell,\nu:n)=0$ if $\nu+1\leqslant\ell\leqslant\nu+n$, and
$J(\ell,\nu:n)=\infty$ otherwise. In order to find

$\displaystyle\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{CS}})$
$\displaystyle=1-\inf_{\ell\geqslant
0}\frac{\rho_{\ell+m,\infty}(1)}{\rho_{\ell,\infty}(1)},$ (28)
$\displaystyle\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{CS}})$
$\displaystyle=1-\sup_{\ell\geqslant
0}\sum_{k\in\mathcal{D}}\pi_{k}\,\frac{\rho_{\ell+k,\ell:k}(1)}{\rho_{\ell,\ell:k}(1)},$
(29)

it suffices to solve the integral equations (26) and (27). This can be
achieved numerically by linearizing the system (cf. Tartakovsky and
Polunchenko (2008)). Specifically, we partition the interval $[0,B]$ into $N$
sub-intervals with endpoints $0=x_{0}<x_{1}<\cdots<x_{N}<x_{N+1}=B$. Denote
the midpoints of these intervals $r_{i}=(x_{i}+x_{i+1})/2$, and introduce
$\hat{\rho}_{\ell,\infty}$ as piecewise-constant approximation to
$\rho_{\ell,\infty}$ on $[0,B]$ (similarly for $\rho_{\ell,\nu:n}$):

$\hat{\rho}_{\ell,\infty}(x)=\sum_{i=0}^{N}\rho_{\ell,\infty}(r_{i})\,\operatorname{\mathchoice{\rm
1\mskip-4.2mul}{\rm 1\mskip-4.2mul}{\rm 1\mskip-4.6mul}{\rm
1\mskip-5.2mul}}\\{x_{i}<x<x_{i+1}\\}.$

Substituting $\hat{\rho}$’s for $\rho$’s in (26) and (27), one obtains a
system of linear equations for the values of $\rho$ at midpoints $r_{i}$,
$1\leqslant i\leqslant N$, that can be written compactly using matrix
notation:

$\displaystyle\boldsymbol{\hat{\rho}}_{\ell,\infty}$
$\displaystyle=\boldsymbol{K}_{\infty}\cdot\boldsymbol{\hat{\rho}}_{\ell-1,\infty},\qquad$
$\displaystyle\boldsymbol{\hat{\rho}}_{0,\infty}$
$\displaystyle=\boldsymbol{1},$ (30)
$\displaystyle\boldsymbol{\hat{\rho}}_{\ell,\nu:n}$
$\displaystyle=\boldsymbol{K}_{\\!J(\ell,\nu:n)}\cdot\boldsymbol{\hat{\rho}}_{\ell-1,\nu:n},\qquad$
$\displaystyle\boldsymbol{\hat{\rho}}_{0,\nu:n}$
$\displaystyle=\boldsymbol{1}.$ (31)

Here $\boldsymbol{K}_{\infty}$ and $\boldsymbol{K}_{0}$ are $N$-by-$N$
matrices whose $(i,j)$-th elements are

$K_{i,j}=\operatorname{\mathsf{P}}\left[\Lambda_{1}<\frac{x_{j+1}}{\max\\{1,r_{i}\\}}\right]-\operatorname{\mathsf{P}}\left[\Lambda_{1}<\frac{x_{j}}{\max\\{1,r_{i}\\}}\right],\qquad$

for $\operatorname{\mathsf{P}}=\operatorname{\mathsf{P}}_{\infty}$ and
$\operatorname{\mathsf{P}}=\operatorname{\mathsf{P}}_{0}$, respectively;
$\boldsymbol{1}=\left[1,1,\dots,1\right]^{\top}$; and

$\displaystyle\boldsymbol{\hat{\rho}}_{\ell,\infty}$
$\displaystyle=\left[\rho_{\ell,\infty}(r_{1}),\dots,\rho_{\ell,\infty}(r_{N})\right]^{\top},$
$\displaystyle\boldsymbol{\hat{\rho}}_{\ell,\nu:n}$
$\displaystyle=\left[\rho_{\ell,\nu:n}(r_{1}),\dots,\rho_{\ell,\nu:n}(r_{N})\right]^{\top}.$

Thus, solving (30)–(31) yields an approximate solution to (26)–(27).
Computational complexity of solving the system is minimal even for large
values of $N$ and $\ell$ since it can be performed iteratively and only
requires matrix-vector multiplication.

In order to get $\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{CS}})$ and
$\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{CS}})$, we have to examine the
functional dependency of ratio of $\rho$’s on $\ell$. This can be done
numerically by capping $\ell$ at a high enough level (as further described in
Section 5). Numerical evidence suggests that infimum in (28) is attained as
$\ell\to\infty$ when CUSUM is in the quasi-stationary regime, while supremum
in (29) is reached at $\ell=0$. It is worth noting that the quasi-stationary
mode is attained relatively quickly, typically for $\ell$ on the order of
dozens. Consequently, for a given threshold and parameters $m$, $\pi_{k}$, we
get an approximation for $\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{CS}})$
and $\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{CS}})$ through (28) and
(29). Since the process is not computationally expensive, finding the
threshold for which the desired level of false alarms is attained can be
achieved with relative ease.

In addition, the CUSUM procedure allows for an efficient asymptotic analysis,
which can be used to obtain simple approximations for a relatively low false
alarm rate. Indeed, as established by Pollak and Tartakovsky (2009) $T_{\rm
CS}(b)/\operatorname{\mathsf{ARL}}(T_{\rm CS}(b))$ is asymptotically
exponential as $b\to\infty$. Standard renewal-theoretic methods [cf. Siegmund
(1985); Woodroofe (1982); Tartakovsky (2020)] readily apply to obtain that

$\operatorname{\mathsf{ARL}}(T_{\rm
CS}(b))=C^{-1}e^{b}(1+o(1))\quad\text{as}~{}~{}b\to\infty,$

where the constant $C\in(0,1)$ depends on the model and can be computed
explicitly by renewal-theoretic argument [cf. Tartakovsky (2005); Tartakovsky,
Nikiforov, and Basseville (2014)]. In particular, for the Gaussian model when
the pre-change density $g$ is $(0,\sigma^{2})$-normal and the under-change
density $f$ is $(\mu,\sigma^{2})$-normal this constant can be easily computed
numerically from the formula

$\displaystyle
C=\frac{2}{q}\exp\left\\{-2\sum_{t=1}^{\infty}\frac{1}{t}\Phi\left(-\frac{1}{2}\sqrt{qt}\right)\right\\},$
(32)

where $q=\mu^{2}/\sigma^{2}$ is the “signal-to-noise ratio” and
$\Phi(x)=(2\pi)^{-1/2}\int_{-\infty}^{x}\exp\left\\{-t/2\right\\}\rm{d}t$ is
the standard normal cdf. Also, in this case, simple Siegmund’s corrected
Brownian motion approximation [Siegmund (1985)] yields

$C\approx\exp\left\\{-\rho\sqrt{q}\right\\},\quad\rho=0.582597,$

which is sufficiently accurate as long as $q$ is not large (typically for
$q\leqslant 2$). See, e.g., Table 3.1, Sec 3.1.5 in Tartakovsky, Nikiforov,
and Basseville (2014). Therefore, for sufficiently large (typically for
moderate) threshold values we have an approximation

$\displaystyle\operatorname{\mathsf{LPFA}}_{m}(T_{\rm CS}(b))\approx
1-\exp\left\\{-mC/e^{b}\right\\}.$ (33)

Next, by nonlinear renewal theory, the limiting
$\operatorname{\mathsf{P}}_{0}$-distribution of the stopping time
$\tau_{b}=(T_{\rm CS}(b)-b/\mu)\sqrt{b\sigma^{2}/\mu^{3}}$, where
$\mu=\operatorname{\mathsf{E}}_{0}[Y_{1}]$,
$\sigma^{2}=\operatorname{\mathsf{Var}}_{0}(Y_{1})$, is normal:

$\operatorname{\mathsf{P}}_{0}\left\\{\tau_{b}\leqslant
x\right\\}=\Phi(x)\quad\text{as}~{}~{}b\to\infty~{}~{}\text{for
all}~{}x\in(-\infty,\infty)$

(see, e.g., Theorem 2.6.2 in Tartakovsky, Nikiforov, and Basseville (2014)).
Hence, the probability of detection when $\nu=0$ can be approximated as
follows:

$\displaystyle\operatorname{\mathsf{P}}_{0}(T_{\rm CS}(b)\leqslant k\mid
N=k)\approx\Phi\Bigg{(}\frac{k}{\sqrt{b\sigma^{2}/\mu^{3}}}+\frac{b}{\mu}\Bigg{)}.$
(34)

We conjecture that for a variety of i.i.d. models

$\inf_{\nu\geqslant 0}\operatorname{\mathsf{P}}_{\nu}(T_{\rm
CS}(b)\leqslant\nu+k\mid T_{\rm
CS}(b)>\nu,N=k)=\operatorname{\mathsf{P}}_{0}(T_{\rm CS}(b)\leqslant k\mid
N=k),$

which is confirmed by numerical study for the Gaussian example in Section 5.
Thus, using (34), we obtain the following approximation for the minimal
probability of detection

$\displaystyle\operatorname{\mathsf{LPD}}_{\pi}(T_{\rm
CS}(b))\approx\sum_{k\in\mathcal{D}}\pi_{k}\Phi\Bigg{(}\frac{k}{\sqrt{b\sigma^{2}/\mu^{3}}}+\frac{b}{\mu}\Bigg{)}.$
(35)

###  4.2 Window-limited CUSUM design

Unfortunately, the integral equations method described above only works when
the detection statistic has Markovian nature. Window-limited CUSUM, given in
(21),

$\displaystyle T_{\textsf{WL}:M}=\inf\Big{\\{}n\geqslant
1\,:\,\max_{\max\\{1,n-M+1\\}\leqslant k\leqslant
n}\sum_{i=k}^{n}\lambda_{i}\geqslant b\Big{\\}},$

does not have that property, and one has to adopt different approaches. In
particular, we are going to obtain a set of bounds on error probabilities that
would allow one to: (i) control probability of false alarm; and (ii) establish
a lower bound on probability of detection.

A lower bound on $\operatorname{\mathsf{LPD}}$ and upper bounds on the
unconditional probability of false alarm,
$\operatorname{\mathsf{LPFA}^{\star}}$, for a version of WL CUSUM (21) has
been established in Guépié, Fillatre, and Nikiforov (2017); Mana, Guépié, and
Nikiforov (2023) in the case of known signal duration. These results can be
extended and modified to fit our setting. While the idea behind the proof of
the following results is not new, there are several key differences. First,
the stopping times considered by Guépié, Fillatre, and Nikiforov (2017); Mana,
Guépié, and Nikiforov (2023) all had the delay of $M$ observations.
Specifically, their versions of WL CUSUM and FMA could not stop during the
“warm-up” period before the first $M$ observations have been collected.
Consequently, the optimization criterion used in that work maximized the local
probability of detection over changes that start at least at time $M$, in our
notation that would correspond to $\nu\geqslant M$. Our results hold for all
three procedures (WL CUSUM, FMA, and modified FMA) with no restriction on when
the change starts. That distinction is especially important for FMA when its
window size is chosen to be greater than the smallest change duration,
$\inf\mathcal{D}$. Second, we dropped the need to check whether the partial
sums of likelihood ratios are associated.

######  Lemma 1.

For the WL CUSUM rule given by (21) the following bounds hold:

$\displaystyle\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{WL}})$
$\displaystyle\leqslant
1-\Big{[}\prod_{k=1}^{M}\operatorname{\mathsf{P}}_{\infty}\Big{(}\sum_{i=1}^{k}\lambda_{i}<b\Big{)}\Big{]}^{m},$
(36) $\displaystyle\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{WL}})$
$\displaystyle\geqslant\sum_{k\in\mathcal{D}}\pi_{k}\operatorname{\mathsf{P}}_{0}\Big{(}\sum_{i=1}^{k\wedge
M}\lambda_{i}\geqslant b\mid N=k\Big{)},$ (37)

where $k\wedge M=\min\\{k,M\\}$.

###### Proof.

Let $S_{a}^{b}=\sum_{i=a}^{b}\lambda_{i}$ for $1\leqslant a\leqslant b$. Note
that for the i.i.d. model (2) the partial sums $S_{a}^{b}$ are associated
(Robbins 1954; Esary, Proschan, and Walkup 1967, Thm. 5.1) under
$\operatorname{\mathsf{P}}_{\infty}$. We first prove (36). Consider
$\operatorname{\mathsf{LPFA}}_{m}$:

$\displaystyle\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{WL}})$
$\displaystyle=1-\inf_{\ell\geqslant
0}\frac{\operatorname{\mathsf{P}}_{\infty}(T_{\textsf{WL}}>\ell+m)}{\operatorname{\mathsf{P}}_{\infty}(T_{\textsf{WL}}>\ell)}$
$\displaystyle\leqslant 1-\inf_{\ell\geqslant
0}\operatorname{\mathsf{P}}_{\infty}\Big{(}\bigcap_{n=\ell+1}^{\ell+m}\Big{\\{}\max_{1\leqslant
j\leqslant n\wedge M}S_{n-j+1}^{n}<b\Big{\\}}\Big{)}$ $\displaystyle\leqslant
1-\min_{0\leqslant\ell\leqslant
M-1}\prod_{n=\ell+1}^{\ell+m}\prod_{j=1}^{n\wedge
M}\operatorname{\mathsf{P}}_{\infty}\Big{(}S_{n-j+1}^{n}<b\Big{)}$
$\displaystyle=1-\Big{[}\prod_{j=1}^{M}\operatorname{\mathsf{P}}_{\infty}\Big{(}S_{M-j+1}^{M}<b\Big{)}\Big{]}^{m},$

where both inequalities are due to association between partial sums. The
statement (36) follows due to independence of $\lambda$’s. Second, we prove
(37). Clearly,

$\operatorname{\mathsf{P}}_{\nu}(T_{\textsf{WL}}>\nu+k\mid
T>\nu,N=k)=\frac{\operatorname{\mathsf{P}}_{\nu}\Big{(}\bigcap_{n=1}^{\nu+k}\Big{\\{}\displaystyle\max_{1\leqslant
j\leqslant n\wedge M}S_{n-j+1}^{n}<b\Big{\\}}\mid
N=k\Big{)}}{\operatorname{\mathsf{P}}_{\infty}\Big{(}\bigcap_{n=1}^{\nu}\Big{\\{}\displaystyle\max_{1\leqslant
j\leqslant n\wedge M}S_{n-j+1}^{n}<b\Big{\\}}\Big{)}}.$

Let $(k-M)^{+}$ denote $\max\\{0,k-M\\}$. It is not hard to see that

$\bigcap_{n=1}^{\nu+k}\Big{\\{}\max_{1\leqslant j\leqslant n\wedge
M}S_{n-j+1}^{n}<b\Big{\\}}\subseteq\bigcap_{n=1}^{\nu}\Big{\\{}\max_{1\leqslant
j\leqslant n\wedge
M}S_{n-j+1}^{n}<b\Big{\\}}\bigcap\Big{\\{}S_{\nu+1+(k-M)^{+}}^{\nu+k}<b\Big{\\}},$

if all changes ending after $\nu$ are omitted except for the longest one that
starts after $\nu$ and ends at exactly $\nu+k$. Due to independence of
$\lambda$’s

$\displaystyle\operatorname{\mathsf{P}}_{\nu}\Big{(}\bigcap_{n=1}^{\nu+k}\Big{\\{}\max_{1\leqslant
j\leqslant n\wedge M}S_{n-j+1}^{n}<b\Big{\\}}\mid N=k\Big{)}$
$\displaystyle\qquad\leqslant\operatorname{\mathsf{P}}_{\infty}\Big{(}\bigcap_{n=1}^{\nu}\Big{\\{}\max_{1\leqslant
j\leqslant n\wedge
M}S_{n-j+1}^{n}<b\Big{\\}}\Big{)}\operatorname{\mathsf{P}}_{\nu}\Big{(}S_{\nu+1+(k-M)^{+}}^{\nu+k}<b\mid
N=k\Big{)}.$

Consequently,

$\operatorname{\mathsf{P}}_{\nu}(T_{\textsf{WL}}>\nu+k\mid
T>\nu,N=k)\leqslant\operatorname{\mathsf{P}}_{0}\Big{(}S_{1+(k-M)^{+}}^{k}<b\mid
N=k\Big{)},$

and (37) follows. ∎

It is worth noting that for practical purposes the upper bound on the
probability of false alarms (36) is most important, especially in security-
critical applications where one needs to guarantee that the error probability
does not exceed a prescribed level. These bounds are amenable to numerical
calculation and can be evaluated with arbitrary precision without relying on
randomized methods. We further explore the sharpness of both bounds in Section
5, although (37) should be a lot less accurate since it relies on omitting a
noticeable chunk of observation.

###  4.3 FMA design

Recall the generalized FMA rule given in (23):

$\displaystyle T_{\textsf{FMA}:M}$ $\displaystyle=\inf\Big{\\{}n\geqslant
1\,:\,\sum_{i=\max\\{1,n-M+1\\}}^{n}\lambda_{i}\geqslant b_{n}\Big{\\}},$

where the first $(M-1)$ thresholds are chosen according to (24). This rule is
similar to window-limited CUSUM studied in the previous section in that it has
a sliding window structure to its detection statistic. For this reason, bounds
similar to (36)–(37) can be established for FMA (23), although the set of
permissible change duration $\mathcal{D}$ directly affects the choice of $M$.

######  Lemma 2.

For the FMA rule given by (23)–(24) the following upper bound holds:

$\displaystyle\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{FMA}})$
$\displaystyle\leqslant
1-\Big{[}\operatorname{\mathsf{P}}_{\infty}\Big{(}\sum_{i=1}^{M}\lambda_{i}<b\Big{)}\Big{]}^{m}.$
(38)

Furthermore, if $M\leqslant\inf\mathcal{D}$, then

$\displaystyle\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{FMA}})$
$\displaystyle\geqslant\operatorname{\mathsf{P}}_{0}\Big{(}\sum_{i=1}^{M}\lambda_{i}\geqslant
b\mid N=M\Big{)}.$ (39)

Although the proof follows the same lines as that for window-limited CUSUM, it
is worth pointing out several key differences. If there are values in
$\mathcal{D}$ smaller than $M$, the lower bound on
$\operatorname{\mathsf{LPD}}_{\pi}$ is negatively affected and has a different
form than in (39). Indeed, the worst-case performance is then determined by
the shorter changes where partial sums contain terms from both under-change
and pre-change modes. For this reason, we strongly recommend setting
$M=\inf\mathcal{D}$. Finally, we would like to mention that bounds similar to
(38) and (39) can be obtained for the version of FMA where all thresholds are
the same, i.e., $b_{n}=b$ for all $n\geqslant 1$.

##  5 Numerical study and simulations

In this section, we carry out a comparative analysis of several detection
rules. The four procedures of interest are: CUSUM (18); window-limited CUSUM
(21); classical FMA (23) with unadjusted thresholds; and modified FMA (further
everywhere mFMA) with thresholds adjusted according to (24).

Recall the maximum likelihood-based nature of the rules we consider (see
Section 3). Since window-limited CUSUM assumes that an upper bound on the
change duration is known, in the context of this work it makes sense to set
its window size equal to the maximum of all possible change duration values,
i.e., $M=\sup\mathcal{D}$. FMA rules, on the other hand, arise from the
assumption that the change duration is known. Furthermore, Lemma 2 suggests
that its probability of detection might be significantly affected when the
actual change duration is smaller than the assumed putative value. For that
reason, we set the window size equal to the smallest possible change duration
value, i.e., $M=\inf\mathcal{D}$. In Subsection 5.1, we explore how reasonable
the proposed choice of window size is.

Our task is two-fold.

  * •

In Subsection 5.1, we compare how the probability of detection (6) vs. the
probability of false alarm (13) varies between the procedures in question. In
addition to the comparative analysis of four detection procedures, we check
how accurate the theoretical bounds from Lemma 1 and Lemma 2 are for the
operating characteristics of window-limited CUSUM and mFMA.

  * •

In Subsection 5.2, we consider whether the distribution of the stopping times
under $\operatorname{\mathsf{P}}_{\infty}$ for each rule is close to
exponential. To do this, we examine the QQ-plots for all the rules. If
$\operatorname{\mathsf{P}}_{\infty}$-distribution of all rules is
approximately exponential, we can use the approximation (25) relating
$\operatorname{\mathsf{LPFA}}_{m}$ to $\operatorname{\mathsf{ARL}}$. We check
how accurate this approximation is for each detection rule. We also consider
two approximations for the ARL of the classical FMA: Lai’s asymptotic
approximation (Lai (1974)) and Noonan and Zhigljavsky’s continuous-time
approximation (Noonan and Zhigljavsky (2020, 2021)), which does not claim to
be asymptotic. Thus, in addition to assessing the accuracy of said
approximations, we also investigate the asymptotic behavior of the two.

###  5.1 Performance analysis

In this section, we consider the case where the standard Gaussian i.i.d.
sequence undergoes a shift in mean of $1$. Specifically,

$\displaystyle Y_{t}$ $\displaystyle\sim\mathcal{N}(0,1)\qquad\text{for
$t\leqslant\nu$},$ $\displaystyle Y_{t}$
$\displaystyle\sim\mathcal{N}(1,1)\qquad\text{for $\nu+1\leqslant
t\leqslant\nu+N$},$ $\displaystyle Y_{t}$
$\displaystyle\sim\mathcal{N}(0,1)\qquad\text{for $t<\nu+N$}.$

It is worth noting that this model has been verified for near-Earth space
informatics when it is necessary to identify streaks of low observable space
objects with telescopes in plain images that appear and disappear at unknown
points in time and space Tartakovsky et al. (2021a).

We consider two cases for the potential change duration:

  1. 1.

varying from $5$ to $10$, i.e., $N\in\mathcal{D}=\\{5,6,\cdots,10\\}$; and

  2. 2.

varying from $7$ to $15$, i.e., $N\in\mathcal{D}=\\{7,8,\cdots,15\\}$.

In the first case, we set $\operatorname{\mathsf{LPFA}}$ window to $m=10$ and
in the second case $m=15$. In both cases, we assume a uniform prior $\pi$ in
$\operatorname{\mathsf{LPD}}$ (13).

To obtain the operating characteristics of CUSUM we use the integral equations
framework described above with $10^{4}$–by–$10^{4}$ matrices, which provides
extreme precision. Detection statistics of other procedures do not allow for
recursive expression, so we fall back to Monte Carlo simulations. For a valid
comparison of the rules, the threshold for each procedure is chosen so that

$\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{CS}})\approx\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{WL}})\approx\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{FMA}})\approx\operatorname{\mathsf{LPFA}}_{m}(T_{\textsf{mFMA}}).$

When estimating $\operatorname{\mathsf{LPFA}}_{m}(T)$ we must find out where
the supremum of $\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid
T>\ell)$ as a function of $\ell$ is attained. Figure 1 shows
$\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid T>\ell)$ as a
function of $\ell$ for all four rules for the case
$\mathcal{D}=\\{5,6,\cdots,10\\}$ and $m=10$. Note that for the CUSUM and the
WL CUSUM algorithms the maximum is attained in the quasi-stationary mode, as
expected. For the FMA algorithm it peaks at $M-1$, while for mFMA this is no
longer the case, although its maximum is attained early on.

Figure 1: The PFA $\operatorname{\mathsf{P}}_{\infty}(T\leqslant\ell+m\mid
T>\ell)$ vs $\ell$ with $m=10$.

For each rule $T$ in question (except for CUSUM), for estimating
$\operatorname{\mathsf{LPFA}}_{m}(T)$ we use Monte Carlo simulations to
estimate its (unconditional) pmf. To ensure accuracy, we run the simulations
until at least $1000$ observations have been collected for each of the events
$\left\\{T=j\right\\}$, $j\leqslant 30$. Clearly,

$\hat{p}_{j}=\frac{1}{K}\sum_{k=1}^{K}\operatorname{\mathchoice{\rm
1\mskip-4.2mul}{\rm 1\mskip-4.2mul}{\rm 1\mskip-4.6mul}{\rm
1\mskip-5.2mul}}\left\\{T_{k}>j\right\\}$

are unbiased estimators of $\operatorname{\mathsf{P}}_{\infty}(T>j)$. We use
$\hat{p}_{j+m}/\hat{p}_{j}$ to estimate
$\operatorname{\mathsf{P}}_{\infty}(T>j+m\mid T>j)$. We use second (resp.
first) order Taylor approximation of $\hat{p}_{j+m}/\hat{p}_{j}$ about
$\operatorname{\mathsf{P}}_{\infty}(T>j+m\mid T>j)$ to estimate its expected
value (resp. variance). Since
$\operatorname{\mathsf{Cov}}_{\infty}(\hat{p}_{j},\hat{p}_{j+m})=\operatorname{\mathsf{P}}_{\infty}(T>j+m)\operatorname{\mathsf{P}}_{\infty}(T\leqslant
j)/K$ these approximations yield

$\displaystyle\operatorname{\mathsf{E}}_{\infty}\Big{(}\frac{\hat{p}_{j+m}}{\hat{p}_{j}}\Big{)}$
$\displaystyle\approx\operatorname{\mathsf{P}}_{\infty}(T>j+m\mid T>j),$
$\displaystyle\operatorname{\mathsf{Var}}_{\infty}\Big{(}\frac{\hat{p}_{j+m}}{\hat{p}_{j}}\Big{)}$
$\displaystyle\approx\frac{\operatorname{\mathsf{P}}_{\infty}(T>j+m\mid
T>j)\,\operatorname{\mathsf{P}}_{\infty}(T\leqslant j+m\mid
T>j)}{K\,\operatorname{\mathsf{P}}_{\infty}(T>j)},$

so we do not need to correct for bias and have a handle on the standard error.
The standard error varies depending on the values of
$\operatorname{\mathsf{LPFA}}_{m}(T)$. However, the relative values are almost
the same and for different procedures do not exceed the following values:

  * •

for the first case: WL CUSUM – $1\%$, FMA – $1\%$, mFMA – $0.9\%$; and

  * •

for the second case: WL CUSUM – $0.8\%$, FMA – $0.8\%$, mFMA – $0.7\%$.

To estimate $\operatorname{\mathsf{LPD}}_{\pi}$ we must find out at what $\nu$
in the equation (13) the infimum is attained. Simulations (for WL CUSUM and
FMA) and numerical analysis (for CUSUM) suggest that minimum in (13) is
reached when $\nu=0$ for all procedures except for mFMA, for which it is
attained before $\nu=5$ in both scenarios (see Figure 2 for the case
$\mathcal{D}=\\{5,6,\cdots,10\\}$).

(a) CUSUM

(b) WL CUSUM

(c) FMA

(d) mFMA

Figure 2: Probability $\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+k\mid
T>\nu,N=k)$ vs $k$ for the four detection rules with different $\nu$ when
$\operatorname{\mathsf{LPFA}}_{m}\approx 0.1$.

Figure 3 illustrates how the minimal value
$\inf_{\nu}\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+k\mid T>\nu,N=k)$
depends on $k$ for all algorithms when $\mathcal{D}=\\{5,6,\cdots,10\\}$ and
$\operatorname{\mathsf{LPFA}}_{m}\approx 0.05$. For CUSUM, WL CUSUM, and FMA
the minimal value of the probability
$\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+k\mid T>\nu,N=k)$ is attained
at $\nu=0$ while for mFMA it is attained at $\nu=2$. The WL CUSUM procedure
performs better than CUSUM. The mFMA performs better than the classical FMA.
Not surprisingly, FMA and mFMA (which are by design tuned to
$\inf\mathcal{D}$) perform significantly better than its competitors at low
values of the change duration, while at larger values of the change duration
WL CUSUM and CUSUM take the lead.

Figure 3: Comparison of $\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+k\mid
T>\nu,N=k)$ vs $k$ for FMA, mFMA, CUSUM, WL CUSUM with
$\operatorname{\mathsf{LPFA}}_{m}\approx 0.05$ for the case
$\mathcal{D}=\\{5,6,\cdots,10\\}$. For each procedure $\nu$ is chosen where
the infimum in (13) is reached.

The comparison of all rules showing $\operatorname{\mathsf{LPD}}$ as a
function of $\operatorname{\mathsf{LPFA}}$ for the case
$\mathcal{D}=\\{5,6,\cdots,10\\}$ is presented in Table 5.1 and Figure 4. Here
$\operatorname{\mathsf{SE}}(T_{\textsf{WL}})$,
$\operatorname{\mathsf{SE}}(T_{\textsf{FMA}})$, and
$\operatorname{\mathsf{SE}}(T_{\textsf{mFMA}})$ are standard errors when
evaluating $\operatorname{\mathsf{LPD}}_{\pi}$ for the three procedures.

Operating characteristics of the WL CUSUM, CUSUM and FMA algorithms for
$\mathcal{D}=\\{5,6,\cdots,10\\}$ .  $\operatorname{\mathsf{LPFA}}_{m}$
$10^{-1}$ $5\cdot\\!10^{-2}$ $2\cdot\\!10^{-2}$ $10^{-2}$ $5\cdot\\!10^{-3}$
$10^{-3}$ $10^{-4}$ $\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{WL}})$
0.7444 0.6350 0.4970 0.3950 0.3139 0.1730 0.0639
$\operatorname{\mathsf{SE}}(T_{\textsf{WL}})$ 0.0013 0.0016 0.0017 0.0016
0.0015 0.0010 0.0005 $\operatorname{\mathsf{LPD}}_{\pi}^{ie}(T_{\textsf{CS}})$
0.7415 0.6326 0.4769 0.3655 0.2794 0.1290 0.0305
$\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{FMA}})$ 0.7291 0.6214 0.4719
0.3841 0.2977 0.1558 0.0514 $\operatorname{\mathsf{SE}}(T_{\textsf{FMA}})$
0.0014 0.0016 0.0018 0.0017 0.0014 0.0009 0.0003
$\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{mFMA})}$ 0.7672 0.6631 0.5126
0.4181 0.3258 0.1666 0.0556 $\operatorname{\mathsf{SE}}(T_{\textsf{mFMA}})$
0.0012 0.0016 0.0018 0.0018 0.0015 0.0009 0.003

Figure 4: Comparison of operating characteristics
($\operatorname{\mathsf{LPD}}$ vs $\operatorname{\mathsf{LPFA}}$) of the FMA,
mFMA, CUSUM and WL CUSUM procedures for $\mathcal{D}=\\{5,6,\cdots,10\\}$;
horizontal axis log-scale.

Figure 4 shows that the window-limited CUSUM procedure performs better than
the classic CUSUM procedure. Moreover, the difference increases when
$\operatorname{\mathsf{LPFA}}\to 0$. It also shows that the mFMA procedure
performs better than the classic FMA. However, as expected, the difference
decreases when $\operatorname{\mathsf{LPFA}}\to 0$. The mFMA procedure
performs much better than its competitors at not quite small
$\operatorname{\mathsf{LPFA}}$ values, while the window-limited CUSUM
procedure performs significantly better than its competitors at
$\operatorname{\mathsf{LPFA}}\to 0$. However, when
$\operatorname{\mathsf{LPFA}}$ tends to zero, the values of
$\operatorname{\mathsf{LPD}}$ are rather poor for practical purposes. More
often in practice, the duration of the change is longer, as in the second case
where $N\in\mathcal{D}=\\{7,8,\cdots,15\\}$.

The comparison of all rules showing $\operatorname{\mathsf{LPD}}$ as a
function of $\operatorname{\mathsf{LPFA}}$ for
$\mathcal{D}=\\{7,8,\cdots,15\\}$ is presented in Table 5.1 and Figure 5.

Operating characteristics of the WL CUSUM, CUSUM and FMA algorithms for
$\mathcal{D}=\\{7,8,\cdots,15\\}$.  $\operatorname{\mathsf{LPFA}}_{m}$
$10^{-1}$ $5\cdot\\!10^{-2}$ $2\cdot\\!10^{-2}$ $10^{-2}$ $5\cdot\\!10^{-3}$
$10^{-3}$ $10^{-4}$ $\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{WL}})$
0.8549 0.7829 0.6770 0.5842 0.5129 0.3250 0.1629
$\operatorname{\mathsf{SE}}(T_{\textsf{WL}})$ 0.0007 0.0010 0.0012 0.0013
0.0013 0.0012 0.0008 $\operatorname{\mathsf{LPD}}_{\pi}^{ie}(T_{\textsf{CS}})$
0.8551 0.7812 0.6676 0.5738 0.4953 0.3167 0.1370
$\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{FMA}})$ 0.8514 0.7680 0.6528
0.5552 0.4716 0.2824 0.1205 $\operatorname{\mathsf{SE}}(T_{\textsf{FMA}})$
0.0007 0.0010 0.0013 0.0014 0.0014 0.0011 0.0006
$\operatorname{\mathsf{LPD}}_{\pi}(T_{\textsf{mFMA}})$ 0.8734 0.7945 0.6797
0.5813 0.4947 0.2962 0.1262 $\operatorname{\mathsf{SE}}(T_{\textsf{mFMA}})$
0.0007 0.0009 0.0012 0.0014 0.0015 0.0012 0.0046

Figure 5: Comparison of operating characteristics
($\operatorname{\mathsf{LPD}}$ vs $\operatorname{\mathsf{LPFA}}$) of the FMA,
mFMA, CUSUM and WL CUSUM for $\mathcal{D}=\\{7,8,\cdots,15\\}$; horizontal
axis log-scale.

The conclusions that were made in the first case hold for other values of the
anomaly duration. However, for more realistic values of the change duration,
the $\operatorname{\mathsf{LPD}}$ values are noticeably higher.

To corroborate the recommended choice of window size (see Section 3) for
window-limited CUSUM (maximum of all possible change duration values, i.e.,
$M=\sup\mathcal{D}$) and for mFMA (smallest possible change duration values,
i.e., $M=\inf\mathcal{D}$), we performed a numerical comparison of the
performance ($\operatorname{\mathsf{LPD}}$ vs $\operatorname{\mathsf{LPFA}}$)
of the considered rules tuned to different window size $M$. Figure 6 shows
that the window-limited CUSUM procedure, for which the window size is equal to
the maximum of all possible change duration values, i.e., $M=10$, performs
better than the window-limited CUSUM procedure, for which the window size is
$M=5$. In contrast, the mFMA procedure, for which the window size is equal to
the smallest possible change duration value, i.e., $M=5$, performs better than
the mFMA procedure, for which the window size is equal to $M=10$.

Figure 6: Performance comparison ($\operatorname{\mathsf{LPD}}$ vs
$\operatorname{\mathsf{LPFA}}$) for mFMA and WL CUSUM tuned to different
window sizes $M$ for the case where change duration varies
$\mathcal{D}=\\{5,6,\cdots,10\\}$.

The results of the comparison operating characteristics of WL CUSUM and mFMA
obtained by using Lemma 1 and Lemma 2 (theoretical bounds for the operating
characteristics) and by Monte Carlo simulations are presented in Table 5.1 and
Table 5.1, respectively. As expected, the upper bounds are very conservative.

Operating characteristics for WL CUSUM (theoretical bounds vs MC simulations).
Upper bound for LPFA theoretical bounds 0.4724 0.2507 0.0939 0.0413 0.0174 MC
simulations 0.0999 0.0497 0.0195 0.0096 0.0049 Lower bound for LPD theoretical
bounds 0.612 0.521 0.403 0.320 0.246 MC simulations 0.744 0.635 0.490 0.389
0.304

Operating characteristics for mFMA (theoretical bounds vs MC simulations).
Upper bound for LPFA theoretical bounds 0.1617 0.0806 0.0294 0.0136 0.0067 MC
simulations 0.0985 0.0493 0.0191 0.0097 0.0049 Lower bound for LPD theoretical
bounds 0.551 0.438 0.304 0.224 0.166 MC simulations 0.767 0.664 0.514 0.407
0.321

###  5.2 Asymptotic exponentiality of stopping times

We now investigate whether the distribution of the stopping times of change
detection procedures under $\operatorname{\mathsf{P}}_{\infty}$ (i.e., under
the no-change hypothesis) is close to exponential. We use QQ plots to assess
whether this is the case. Specifically, we plot the empirical quantiles of the
observed stopping time against the theoretical quantiles of the geometric
distribution with parameter $K/\sum_{i=1}^{K}T_{i}$, where $T_{i}$’s are the
generated stopping times. To accomplish this we perform Monte Carlo
simulations with $10^{7}$ runs for each of the four detection rules with
thresholds chosen so that the $\operatorname{\mathsf{ARL}}$ of each detection
procedure is approximately equal to $200$. Window-limited CUSUM and FMA are
configured as in our first scenario, i.e., to detect a change of duration from
$5$ to $10$. For each Monte Carlo run, we get the stopping time assuming the
change never occurs. The QQ plots in Figure 7 suggest that the distributions
are indeed close to geometric even for moderate values of the ARL to false
alarm.

(a) FMA

(b) Modified FMA

(c) CUSUM

(d) WL CUSUM

Figure 7: Quantile-Quantile (QQ) plots for FMA, Modified FMA, CUSUM, WL CUSUM
when $\operatorname{\mathsf{ARL}}\approx 200$. The $x$-axis shows the
theoretical quantiles of the geometric distribution with parameter $\approx
1/200$ and the $y$-axis shows the quantiles of distributions of the observed
stopping times for each of the four detection rules.

Hence, the following approximation to $\operatorname{\mathsf{LPFA}}_{m}$ may
be used:

$\displaystyle\operatorname{\mathsf{LPFA}}_{exp}(T)=1-\Bigg{(}1-\frac{1}{\operatorname{\mathsf{ARL}}(T)}\Bigg{)}^{m}.$
(40)

This allows one to estimate $\operatorname{\mathsf{LPFA}}$ by using
$\operatorname{\mathsf{ARL}}$, which significantly reduces the computational
burden associated with MC simulations in Section 5.1. Comparison of
$\operatorname{\mathsf{LPFA}}_{exp}$ obtained using approximation (40) and
simulated $\operatorname{\mathsf{ARL}}$ with MC estimate
$\operatorname{\mathsf{LPFA}}_{mc}$, as described in Section 5.1, is presented
in Table 5.2. As can be seen, the approximation (40) is very accurate for all
change detection rules. Thus, this approximation is useful in most practical
problems, simplifying the selection of thresholds.

MC simulations vs asymptotic approximation for
$\operatorname{\mathsf{LPFA}}_{m}$.
$\operatorname{\mathsf{LPFA}}_{mc}(T_{\textsf{WL}})$ $9.91\cdot\\!10^{-2}$
$9.45\cdot\\!10^{-3}$ $10.1\cdot\\!10^{-4}$ $9.6\cdot\\!10^{-5}$
$\operatorname{\mathsf{LPFA}}_{exp}(T_{\textsf{WL}})$ $9.31\cdot\\!10^{-2}$
$9.31\cdot\\!10^{-3}$ $10.0\cdot\\!10^{-4}$ $9.9\cdot\\!10^{-5}$ Deviation,
$\%$ 6.0 1.5 0.9 3.3 $\operatorname{\mathsf{LPFA}}_{ie}(T_{\textsf{CS}})$
$9.79\cdot\\!10^{-2}$ $10.4\cdot\\!10^{-3}$ $10.2\cdot\\!10^{-4}$
$9.7\cdot\\!10^{-5}$ $\operatorname{\mathsf{LPFA}}_{exp}(T_{\textsf{CS}})$
$9.45\cdot\\!10^{-2}$ $10.1\cdot\\!10^{-3}$ $10.3\cdot\\!10^{-4}$
$10.8\cdot\\!10^{-5}$ Deviation, $\%$ 3.5 2.3 1.0 11.8
$\operatorname{\mathsf{LPFA}}_{mc}(T_{\textsf{FMA}})$ $9.81\cdot\\!10^{-2}$
$10.2\cdot\\!10^{-3}$ $9.70\cdot\\!10^{-4}$ $9.3\cdot\\!10^{-5}$
$\operatorname{\mathsf{LPFA}}_{exp}(T_{\textsf{FMA}})$ $8.78\cdot\\!10^{-2}$
$9.81\cdot\\!10^{-3}$ $9.70\cdot\\!10^{-4}$ $9.7\cdot\\!10^{-5}$ Deviation,
$\%$ 10.5 4.0 0.1 3.7 $\operatorname{\mathsf{LPFA}}_{mc}(T_{\textsf{mFMA}})$
$9.72\cdot\\!10^{-2}$ $10.1\cdot\\!10^{-3}$ $9.60\cdot\\!10^{-4}$
$9.3\cdot\\!10^{-5}$ $\operatorname{\mathsf{LPFA}}_{exp}(T_{\textsf{mFMA}})$
$9.33\cdot\\!10^{-2}$ $10.1\cdot\\!10^{-3}$ $9.70\cdot\\!10^{-4}$
$9.2\cdot\\!10^{-5}$ Deviation, $\%$ 4.1 0.2 0.9 0.7

Next, we study accuracy of two known approximations for
$\operatorname{\mathsf{ARL}}$ of the classical FMA – specifically, Lai’s
asymptotic approximation (Lai (1974)) and Noonan and Zhigljavsky’s
approximation (Noonan and Zhigljavsky (2020)).

Noonan and Zhigljavsky studied a rule they dubbed the MOSUM test. In the case
of Gaussian observations, this procedure is equivalent to the classical FMA
test. Otherwise, MOSUM compares the observed signal, rather than the log-
likelihood ratio process, to a threshold. Their approximation to the
$\operatorname{\mathsf{ARL}}$ of $T_{\textsf{FMA}}$ is as follows:

$\displaystyle\operatorname{\mathsf{ARL}}_{N-Zh}(T_{\textsf{FMA}})=-\frac{M\cdot
F(2,h,h_{M})}{\theta_{M}(h)^{2}\log(\theta_{M}(h))}+M,$ (41)

where $h=b+M/2$, $h_{M}=h+0.8239/\sqrt{M}$, $b$ is the threshold in (23), and

$\displaystyle
F(1,h,h_{M})=\Phi(h)\Phi(h_{M})-\varphi(h_{M})\left[h\Phi(h)+\varphi(h)\right].$

Here $\Phi$ is the standard normal cdf, $\varphi$ is the standard normal pdf,
and

$\displaystyle F(2,h,h_{M})$
$\displaystyle=\frac{\varphi^{2}(h_{M})}{2}\left[(h^{2}-1+\sqrt{\pi}h)\Phi(h)+(h+\sqrt{\pi})\varphi(h)\right]-$
$\displaystyle{}-\varphi(h_{M})\Phi(h_{M})\left[(h+h_{M})\Phi(h)+\varphi(h)\right]+\Phi(h)\Phi^{2}(h_{M})+$
$\displaystyle{}+\int_{0}^{\infty}\Phi(h-x)\left[\varphi(h_{M}+x)\Phi(h_{M}-x)-\sqrt{\pi}\varphi^{2}(h_{M})\Phi(\sqrt{2}x)\right]dx,$

with $\theta_{M}(h)=F(2,h,h_{M})\big{/}F(1,h,h_{M})$.

Lai’s approximation for $\operatorname{\mathsf{ARL}}$ of $T_{\textsf{FMA}}$
has a much simpler expression:

$\displaystyle\operatorname{\mathsf{ARL}}_{Lai}(T_{\textsf{FMA}})=(1-\Phi((b+M/2)/\sqrt{M}))^{-1}.$
(42)

Despite its simplicity, it is asymptotically exact, in that
$\operatorname{\mathsf{ARL}}_{Lai}(T_{\textsf{FMA}})\to\operatorname{\mathsf{E}}_{\infty}(T_{\textsf{FMA}})$
as $b\to\infty$.

For both approximations, we used the scenario that was used in the first case
when the change duration varies from $5$ to $10$, i.e.,
$N\in\mathcal{D}=\\{5,6,\cdots,10\\}$. We run a Monte Carlo simulation (with
$10^{6}$ runs) for various threshold values and look at how simulated results
align with the predictions. The results are presented in Table 5.2.

MC simulations of $\operatorname{\mathsf{ARL}}(T_{\textsf{FMA}})$ vs. its
approximation $\operatorname{\mathsf{ARL}}_{N-Zh}$ and
$\operatorname{\mathsf{ARL}}_{Lai}$.  Threshold 2.25 2.89 3.70 4.18 4.67 5.71
7.00 $\operatorname{\mathsf{ARL}}(T_{\textsf{FMA}})$ 109.63 211.47 545.50
1026.43 2032.5 10488 108960
$\operatorname{\mathsf{ARL}}_{N-Zh}(T_{\textsf{FMA}})$ 114.11 217.36 555.88
1047.30 2077.6 10902 115490 Deviation, $\%$ 4.08 2.78 1.90 2.03 2.22 3.95 5.99
$\operatorname{\mathsf{ARL}}_{Lai}(T_{\textsf{FMA}})$ 59.44 126.17 359.36
713.09 1477.7 8325.4 92946 Deviation, $\%$ 45.78 40.34 34.12 30.53 27.29 20.62
14.70

It is clear that Lai’s approximation gives poor accuracy for small threshold
values. As the threshold increases, the deviation of the estimate by Lai’s
approximation from the estimate by Monte Carlo simulations decreases, as
expected. Noonan and Zhigljavsky’s approximation gives good results: deviation
from Monte Carlo simulations does not exceed $6\%$. However, for large
thresholds, the deviation of the estimate by Noonan and Zhigljavsky’s
approximation from the estimate by Monte Carlo simulations increases. From
this, we can conclude that, unlike Lai’s approximation, Noonan and
Zhigljavsky’s approximation is not asymptotic. Thus, using (40) and (41) may
be recommended to a practitioner working in the low
$\operatorname{\mathsf{ARL}}$ setting, while Lai’s approximation (42) may be
used as a conservative asymptotically exact lower bound for the
$\operatorname{\mathsf{ARL}}$ of FMA regardless of threshold.

##  6 Conclusions and discussion

We provided a review of existing change detection frameworks and performance
measures and examined their relevance for detecting intermittent changes. A
thorough discussion as to the differences between these settings prompted us
to propose one specific choice of false alarm and correct detection measures.
The formulation handles changes of unknown duration, whether the length of
change is deterministic or random. Furthermore, the transient nature of the
signal coupled with the maximum likelihood principle yielded three detection
rules that are equivalent to three stopping times popular in literature:
CUSUM, window-limited CUSUM, and FMA. In addition, a particular property when
maximizing the likelihood ratio for FMA brought to light a modification of the
FMA rule that, to the best of our knowledge, has not been considered before.
The simulation study further supported the conjecture that the modified FMA is
superior to the classical one.

We presented ways to design each of the detection rules and performed a
comparative numerical analysis between the four. The window-limited CUSUM
procedure shows operating characteristics better than the CUSUM procedure, and
the modified FMA procedure performs better than the classic FMA. For low
values of the change duration FMA and modified FMA perform significantly
better than their competitors. The modified FMA performs significantly better
than the others. For the CUSUM procedure, very accurate performance estimates
can be obtained by solving integral equations. For the window-limited CUSUM
and the modified FMA, we obtained theoretical bounds on both
$\operatorname{\mathsf{LPFA}}$ and $\operatorname{\mathsf{LPD}}$. The former
not only allows one to control the false alarm rate and thus choose a
threshold that guarantees that the rate does not exceed a prescribed value,
but also turned out to be reasonably accurate. The bound on
$\operatorname{\mathsf{LPD}}$, however, is typically rough and not recommended
for practical purposes.

An important direction of further research would involve the case of
deterministic signal duration $N$ and the choice of $\pi$ in (13). One
possible motivation could be as follows. Consider a family of oracle rules
$\\{T_{N^{\star}}\,:\,N^{\star}\geqslant 1\\}$ that are tuned to a particular
change duration $N^{\star}$, i.e., solve

$\sup_{T\in\mathbb{C}(m,\alpha)}\inf_{\nu\geqslant
0}\operatorname{\mathsf{P}}_{\nu}(T\leqslant\nu+N^{\star}\mid
T>\nu,N=N^{\star}).$

Then $\pi$ should be chosen so that compared to _any_ oracle rule
$T_{N^{\star}}$, $N^{\star}\in\mathcal{D}$, the loss in performance of a rule
satisfying (14) should remain bounded as $\alpha\to 0$ with $m$ either fixed
or $m=m(\alpha)\to\infty$ at a certain rate.

Another interesting avenue of research would be to investigate the connection
between formulation (12), (14) and formulation (13), (14) in the asymptotic
setting.

## References

  * Bakhache and Nikiforov (2000) Bakhache, Bacem, and Igor Nikiforov. 2000. “Reliable Detection of Faults in Measurement Systems.” _International Journal of Adaptive Control and Signal Processing_ 14: 683 – 700.
  * Bar-Shalom and Li (1993) Bar-Shalom, Y., and X. R. Li. 1993. _Estimation and Tracking: Principles, Techniques and Software_. Artech House Radar Library. Boston-London: Artech House.
  * Berenkov, Tartakovsky, and Kolessa (2020) Berenkov, N. R., A. G. Tartakovsky, and A. E. Kolessa. 2020. “Reliable Detection of Dynamic Anomalies With Application to Extracting Faint Space Object Streaks From Digital Frames.” In _2020 International Conference on Engineering and Telecommunication (EnT-MIPT 2020)_ , Dolgoprudny, Russia, 25-26 November.
  * Blackman, Dempster, and Broida (1993) Blackman, S. S., R. J. Dempster, and T. J. Broida. 1993. “Multiple Hypothesis Track Confirmation for Infrared Surveillance Systems.” _IEEE Transactions on Aerospace and Electronic Systems_ 29 (3): 810–823.
  * Broder and Schwartz (1990) Broder, Bruce, and Stuart C. Schwartz. 1990. “Quickest Detection Procedures and Transient Signal Detection.” .
  * Debar, Dacier, and Wespi (1999) Debar, H., M. Dacier, and A. Wespi. 1999. “Toward a Taxonomy of Intrusion Detection Systems.” _Computer Networks_ 31 (8): 805–822.
  * Duncan (1986) Duncan, Acheson Johnston. 1986. _Quality Control and Industrial Statistics (5th ed.)_. Richard D. Irwin Professional Publishing, Inc.
  * Ebrahimzadeh and Tchamkerten (2015) Ebrahimzadeh, Ehsan, and Aslan Tchamkerten. 2015. “Sequential Detection of Transient Changes in Stochastic Systems Under a Sampling Constraint.” _2015 IEEE International Symposium on Information Theory (ISIT)_ 156–160.
  * Egea-Roca et al. (2018) Egea-Roca, Daniel, José A. López-Salcedo, Gonzalo Seco-Granados, and H. Vincent Poor. 2018. “Performance Bounds for Finite Moving Average Tests in Transient Change Detection.” _IEEE Transactions on Signal Processing_ 66 (6): 1594–1606.
  * Ellis and Speed (2001) Ellis, Juanita, and Tim Speed. 2001. _The Internet Security Guidebook: From Planning to Deployment_. Academic Press.
  * Esary, Proschan, and Walkup (1967) Esary, J. D., F. Proschan, and D. W. Walkup. 1967. “Association of Random Variables, With Applications.” _Annals of Mathematical Statistics_ 38 (5): 1466–1474.
  * Guépié, Fillatre, and Nikiforov (2012) Guépié, Blaise Kévin, Lionel Fillatre, and Igor Nikiforov. 2012. “Sequential Detection of Transient Changes.” _Sequential Analysis_ 31 (4): 528–547.
  * Guépié, Fillatre, and Nikiforov (2017) Guépié, Blaise Kévin, Lionel Fillatre, and Igor Nikiforov. 2017. “Detecting a Suddenly Arriving Dynamic Profile of Finite Duration.” _IEEE Transactions on Information Theory_ 63 (5): 3039–3052.
  * Jeske et al. (2018a) Jeske, Daniel R., Nathaniel T. Steven, Alexander G. Tartakovsky, and James D. Wilson. 2018a. “Statistical Methods for Network Surveillance.” _Applied Stochastic Models in Business and Industry_ 34 (4): 425–445. Discussion Paper.
  * Jeske et al. (2018b) Jeske, Daniel R., Nathaniel T. Steven, James D. Wilson, and Alexander G. Tartakovsky. 2018b. “Statistical Network Surveillance.” _Wiley StatsRef: Statistics Reference Online_ 1–12.
  * Kent (2000) Kent, S. 2000. “On the Trail of Intrusions Into Information Systems.” _IEEE Spectrum_ 37 (12): 52–56.
  * Lai (1974) Lai, Tze Leung. 1974. “Control Charts Based on Weighted Sums.” _Annals of Statistics_ 2 (1): 134–147.
  * Lai (1998) Lai, Tze Leung. 1998. “Information Bounds and Quick Detection of Parameter Changes in Stochastic Systems.” _IEEE Transactions on Information Theory_ 44 (7): 2917–2929.
  * Liang, Tartakovsky, and Veeravalli (2022) Liang, Yuchen, Alexander G. Tartakovsky, and Venugopal V. Veeravalli. 2022. “Quickest Change Detection With Non-Stationary Post-Change Observations.” _IEEE Transactions on Information Theory_ 68: Early Access.
  * Lorden (1971) Lorden, Gary. 1971. “Procedures for Reacting to a Change in Distribution.” _Annals of Mathematical Statistics_ 42 (6): 1897–1908.
  * Mana et al. (2022) Mana, Fatima Ezzahra, Blaise Kévin Guépié, Raphaèle Deprost, Eric Herber, and Igor Nikiforov. 2022. “The Air Pollution Monitoring by Sequential Detection of Transient Changes.” _IFAC Papers online_ 55-5: 60–65.
  * Mana, Guépié, and Nikiforov (2023) Mana, Fatima Ezzahra, Blaise Kévin Guépié, and Igor Nikiforov. 2023. “Sequential Detection of an Arbitrary Transient Change Profile by the FMA Test.” _Sequential Analysis_ 1–21.
  * Mei (2008) Mei, Yajun. 2008. “Is Average Run Length to False Alarm Always an Informative Criterion?” _Sequential Analysis_ 27 (4): 354–376.
  * Moustakides (1986) Moustakides, George V. 1986. “Optimal Stopping Times for Detecting Changes in Distributions.” _Annals of Statistics_ 14 (4): 1379–1387.
  * Moustakides (2014) Moustakides, George V. 2014. “Multiple Optimality Properties of the Shewhart Test.” _Sequential Analysis_ 33 (3): 318–344.
  * Moustakides, Polunchenko, and Tartakovsky (2011) Moustakides, George V., Aleksey S. Polunchenko, and Alexander G. Tartakovsky. 2011\. “A Numerical Approach to Performance Analysis of Quickest Change-Point Detection Procedures.” _Statistica Sinica_ 21 (2): 571–596.
  * Noonan and Zhigljavsky (2020) Noonan, Jack, and Anatoly Zhigljavsky. 2020. “Power of the MOSUM Test for Online Detection of a Transient Change in Mean.” _Sequential Analysis_ 39 (2): 269–293.
  * Noonan and Zhigljavsky (2021) Noonan, Jack, and Anatoly Zhigljavsky. 2021. “Approximations for the Boundary Crossing Probabilities of Moving Sums of Random Variables.” _Methodology and Computing in Applied Probability_ 23 (3): 873–892.
  * Ortner and Nehorai (2007) Ortner, M., and A. Nehorai. 2007. “A Sequential Detector for Biochemical Release in Realistic Environments.” _IEEE Transactions on Signal Processing_ 55 (8): 4173-4182.
  * Page (1954) Page, E. S. 1954. “Continuous Inspection Schemes.” _Biometrika_ 41 (1–2): 100–114.
  * Peng, Leckie, and Ramamohanarao (2004) Peng, Tao, Christopher Leckie, and Kotagiri Ramamohanarao. 2004. “Proactively Detecting Distributed Denial of Service Attacks Using Source IP Address Monitoring.” In _Networking 2004_ , edited by Nikolas Mitrou, Kimon Kontovasilis, George N. Rouskas, Ilias Iliadis, and Lazaros Merakos, Vol. 3042 of _Lecture Notes in Computer Science_ , 771–782. Berlin, DE: Springer-Verlag.
  * Pollak and Tartakovsky (2009) Pollak, M., and A. G. Tartakovsky. 2009. “Asymptotic Exponentiality of the Distribution of First Exit Times for a Class of Markov Processes With Applications to Quickest Change Detection.” _Theory of Probability and its Applications_ 53 (3): 430–442.
  * Pollak (1985) Pollak, Moshe. 1985. “Optimal Detection of a Change in Distribution.” _Annals of Statistics_ 13 (1): 206–227.
  * Polunchenko and Tartakovsky (2010) Polunchenko, A. S., and A. G. Tartakovsky. 2010. “On Optimality of the Shiryaev–Roberts Procedure for Detecting a Change in Distribution.” _Annals of Statistics_ 38 (6): 3445–3457.
  * Raghavan, Galstyan, and Tartakovsky (2013) Raghavan, V., A. Galstyan, and A. G. Tartakovsky. 2013. “Hidden Markov Models for the Activity Profile of Terrorist Groups.” _Annals of Applied Statistics_ 7: 2402–24307.
  * Robbins (1954) Robbins, H. E. 1954. “A Remark on the Joint Distribution of Cumulative Sums.” _Annals of Mathematical Statistics_ 25: 614–616.
  * Rovatsos, Zou, and Veeravalli (2017) Rovatsos, Georgios, Shaofeng Zou, and Venugopal V. Veeravalli. 2017. “Quickest Change Detection Under Transient Dynamics.” In _2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings_ , ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, Jun., 4785–4789. Institute of Electrical and Electronics Engineers Inc.
  * Siegmund (1985) Siegmund, David. 1985. _Sequential Analysis: Tests and Confidence Intervals_. Series in Statistics. New York, USA: Springer-Verlag.
  * Spivak and Tartakovsky (2020) Spivak, V.S., and A. G. Tartakovsky. 2020. “Efficient Algorithm for Initialization of Object Tracks Based on Changepoint Detection Method.” In _2020 International Conference on Engineering and Telecommunication (EnT-MIPT 2020)_ , Dolgoprudny, Russia, 25-26 November.
  * Tartakovsky (2005) Tartakovsky, A. G. 2005. “Asymptotic Performance of a Multichart CUSUM Test Under False Alarm Probability Constraint.” In _Proceedings of the 44th IEEE Conference Decision and Control and European Control Conference (CDC-ECC’05), Seville, SP_ , 320–325. IEEE, Omnipress CD-ROM.
  * Tartakovsky (2014) Tartakovsky, A. G. 2014. “Rapid Detection of Attacks in Computer Networks by Quickest Changepoint Detection Methods.” In _Data Analysis for Network Cyber-Security_ , edited by N. Adams and N. Heard, 33–70. London, UK: Imperial College Press.
  * Tartakovsky (2020) Tartakovsky, A. G. 2020. _Sequential Change Detection and Hypothesis Testing: General Non-i.i.d. Stochastic Models and Asymptotically Optimal Rules_. Monographs on Statistics and Applied Probability 165. Boca Raton, London, New York: Chapman & Hall/CRC Press, Taylor & Francis Group.
  * Tartakovsky and Brown (2008) Tartakovsky, A. G., and J. Brown. 2008. “Adaptive Spatial-Temporal Filtering Methods for Clutter Removal and Target Tracking.” _IEEE Transactions on Aerospace and Electronic Systems_ 44 (4): 1522–1537.
  * Tartakovsky, Nikiforov, and Basseville (2014) Tartakovsky, A. G., I. V. Nikiforov, and M. Basseville. 2014. _Sequential Analysis: Hypothesis Testing and Changepoint Detection_. Monographs on Statistics and Applied Probability. Boca Raton, London, New York: Chapman & Hall/CRC Press.
  * Tartakovsky et al. (2021a) Tartakovsky, A.G., N.R. Berenkov, A.E. Kolessa, and I.V. Nikiforov. 2021a. “Optimal Sequential Detection of Signals With Unknown Appearance and Disappearance Points in Time.” _IEEE Transactions on Signal Processing_ 69: 2653–2662.
  * Tartakovsky (2002) Tartakovsky, Alexander G. 2002. “An Efficient Adaptive Sequential Procedure for Detecting Targets.” In _Proceedings of the IEEE Aerospace Conference, Big Sky, MT, USA_ , edited by David A. Williamson, Vol. 4, Mar., 1581–1596. IEEE.
  * Tartakovsky (2008) Tartakovsky, Alexander G. 2008. “Discussion on “Is Average Run Length to False Alarm Always an Informative Criterion?” by Yajun Mei.” _Sequential Analysis_ 27 (4): 396–405.
  * Tartakovsky et al. (2021b) Tartakovsky, Alexander G., Nikita R. Berenkov, Alexei E. Kolessa, and Igor V. Nikiforov. 2021b. “Optimal Sequential Detection of Signals With Unknown Appearance and Disappearance Points in Time.” _IEEE Transactions on Signal Processing_ 69: 2653–2662.
  * Tartakovsky, Pollak, and Polunchenko (2012) Tartakovsky, Alexander G., Moshe Pollak, and Aleksey S. Polunchenko. 2012. “Third-order Asymptotic Optimality of the Generalized Shiryaev–Roberts Changepoint Detection Procedures.” _Theory of Probability and its Applications_ 56 (3): 457–484.
  * Tartakovsky and Polunchenko (2008) Tartakovsky, Alexander G., and Aleksey S. Polunchenko. 2008. “Quickest Changepoint Detection in Distributed Multisensor Systems Under Unknown Parameters.” In _Proceedings of the 11th IEEE International Conference on Information Fusion, Cologne, DE_ , Jul.
  * Tartakovsky et al. (2006a) Tartakovsky, Alexander G., Boris L. Rozovskii, Rudolf B. Blaźek, and Hongjoong Kim. 2006a. “Detection of Intrusions in Information Systems by Sequential Change-point Methods.” _Statistical Methodology_ 3 (3): 252–293.
  * Tartakovsky et al. (2006b) Tartakovsky, Alexander G., Boris L. Rozovskii, Rudolf B. Blaźek, and Hongjoong Kim. 2006b. “A Novel Approach to Detection of Intrusions in Computer Networks Via Adaptive Sequential and Batch-sequential Change-point Detection Methods.” _IEEE Transactions on Signal Processing_ 54 (9): 3372–3382.
  * Wang and Willett (2005a) Wang, Z.J., and P. Willett. 2005a. “Detecting Transients of Unknown Length.” In _2005 IEEE Aerospace Conference_ , 2236–2247.
  * Wang and Willett (2005b) Wang, Z.J., and P. Willett. 2005b. “A Variable Threshold Page Procedure for Detection of Transient Signals.” _IEEE Transactions on Signal Processing_ 53 (11): 4397–4402.
  * Willsky and Jones (1976) Willsky, Alan S., and Harold L. Jones. 1976. “A Generalized Likelihood Ratio Approach to the Detection and Estimation of Jumps in Linear Systems.” _IEEE Transactions on Automatic Control_ 21 (1): 108–112.
  * Woodroofe (1982) Woodroofe, Michael. 1982. _Nonlinear Renewal Theory in Sequential Analysis_. Vol. 39 of _CBMS-NSF Regional Conference Series in Applied Mathematics_. Philadelphia, PA, USA: SIAM.
  * Yakir (1995) Yakir, B. 1995. “A Note on the Run Length to False Alarm of a Change-point Detection Policy.” _Annals of Statistics_ 23 (1): 272–281.
  * Zou, Fellouris, and Veeravalli (2017a) Zou, Shaofeng, Georgios Fellouris, and Venugopal V. Veeravalli. 2017a. “Asymptotic Optimality of D-CuSum for Quickest Change Detection Under Transient Dynamics.” In _2017 IEEE International Symposium on Information Theory, ISIT 2017_ , IEEE International Symposium on Information Theory - Proceedings, 08, 2263–2267. Institute of Electrical and Electronics Engineers Inc.
  * Zou, Fellouris, and Veeravalli (2017b) Zou, Shaofeng, Georgios Fellouris, and Venugopal V. Veeravalli. 2017b. “Quickest Change Detection Under Transient Dynamics: Theory and Asymptotic Analysis.” _IEEE Transactions on Information Theory_ PP.