# Worst-Case Misidentification Control in Sequential Change Diagnosis using
the min-CuSum

Austin Warner and Georgios Fellouris This research was supported by the US
National Science Foundation under grant AMPS 1736454 through the University of
Illinois Urbana-Champaign. Some parts of this paper were presented at the
International Symposium on Information Theory (ISIT) 2022 [1].A. Warner and G.
Fellouris are with the Department of Statistics of the University of Illinois
Urbana-Champaign. Email<EMAIL_ADDRESS>
###### Abstract

The problem of sequential change diagnosis is considered, where a sequence of
independent random elements is accessed sequentially, there is an abrupt
change in its distribution at some unknown time, and there are two main
operational goals: to quickly detect the change and, upon stopping, to
accurately identify the post-change distribution among a finite set of
alternatives. The algorithm that raises an alarm as soon as the CuSum
statistic that corresponds to one of the post-change alternatives exceeds a
certain threshold is studied. When the data are generated over independent
channels and the change can occur in only one of them, its worst-case with
respect to the change point conditional probability of misidentification,
given that there was not a false alarm, is shown to decay exponentially fast
in the threshold. As a corollary, in this setup, this algorithm is shown to
asymptotically minimize Lorden’s detection delay criterion, simultaneously for
every possible post-change distribution, within the class of schemes that
satisfy prescribed bounds on the false alarm rate and the worst-case
conditional probability of misidentification, as the former goes to zero
sufficiently faster than the latter. Finally, these theoretical results are
also illustrated in simulation studies.

##  I Introduction

The problem of quickly detecting a change in sequentially acquired data dates
back to the pioneering works of Shewhart [2] and Page [3] and is motivated by
a wide range of engineering and scientific applications. Examples of such
applications can be found in industrial process quality control [4, 5, 6],
target detection and identification [7, 8], integrity monitoring of navigation
systems [9, 10], target tracking [11], network intrusion detection [12, 13],
bioterrorism [14, 15], genomics [16]. In most of these applications, there are
typically many possible types of change and it is useful, if not critical, to
not only detect the change quickly, but also to correctly identify the type of
change upon stopping. The problem of simultaneously detecting a change in the
distribution of sequentially collected data and identifying the correct post-
change distribution among a finite set of alternatives is known as sequential
change diagnosis.

One of the first algorithms for the problem of sequential change detection,
where the identification aspect is not present, was Page’s Cumulative Sum
(CuSum) algorithm [3]. In the case of iid data before and after the change
with completely specified distributions, this algorithm admits a recursive
structure, which is very convenient for its practical implementation.
Moreover, it minimizes Lorden’s criterion[17], i.e., the worst-case
conditional expected detection delay with respect to both the change point and
the observations up to it, subject to a user-specified bound on the false
alarm rate [18].

When the post-change distribution is not completely specified but it is
assumed to belong to a finite collection of plausible distributions, one can
compute the CuSum statistic for each possible post-change distribution and
declare that the change has occurred as soon as one of them becomes larger
than some threshold [3, 19]. This algorithm, referred to in this work as the
min-CuSum, achieves the optimal detection delay, in Lorden’s sense, to (at
least) a first-order asymptotic approximation as the false alarm rate goes to
zero [17]. It has been studied, in particular, in the case of the two-sided
problem, where there is either an increase or decrease in the mean of the
observations after the change (e.g., [20, 21, 22]), as well as in the case of
the multichannel problem, where there are several independent data sources,
e.g., a sensor network, and the change may occur in one or more of them [23,
24, 12, 13, 25, 26].

The first scheme that was proposed for the sequential change diagnosis problem
was based on a generalization of the CuSum algorithm, and termed the
“Generalized CuSum” [27]. However, unlike the original CuSum, this algorithm
does not admit a recursive structure even in the iid setting and its required
number of operations per time instant grows linearly with the number of all
already collected observations. Since the change can take a very long time to
occur, the Generalized CuSum needs to be modified to be applicable in
practice. One such modification is to restrict the required number of
operations at each time instant, as suggested in [28]. A different
modification was introduced in [29], according to which an alarm is raised as
soon as the CuSum statistics of a post-change hypothesis against the pre-
change and all other post-change alternatives exceed a certain threshold. The
latter algorithm is referred to as the “Matrix CuSum,” as it requires the
parallel computation of a matrix of CuSum statistics. A modification of the
latter was proposed in [30], which resets the Matrix CuSum statistics
according to an adaptive window. A recursive algorithm which requires only the
computation of the original min-CuSum statistics was introduced in [31].
According to it, an alarm is raised as soon as the CuSum statistic of a
certain post-change alternative against the pre-change exceeds the
corresponding statistic of any other post-change alternative by a certain
threshold. Moreover, the sequential change diagnosis problem has been
considered in the special case of the multichannel problem, but under general
stochastic models in [32, 33].

Unlike the min-CuSum, which requires a number of operations that is linear in
the number of post-change hypotheses, the above algorithms require a number of
calculations per time instant that is quadratic in the number of post-change
hypotheses. This can be a disadvantage in certain applications where the
change diagnosis problem is relevant, as for example in the case of a relative
large sensor network. It is also worth noting that, in the latter context, the
min-CuSum admits a decentralized implementation [26], i.e., it requires the
sensors to communicate to a fusion center only to report that they have raised
an alarm. On the contrary, all the above change diagnosis algorithms require
that, at each time instant, each sensor communicate its data continuously to
the fusion center.

The above practical considerations, together with the strong theoretical
support in the context of the sequential change detection problem, can explain
why the min-CuSum is often used in practice as an ad-hoc solution to the
sequential change diagnosis problem [34, 35, 36]. However, the theoretical
understanding of its performance as a change diagnosis scheme is relatively
limited. Its identification rule was shown to be a strongly consistent
estimator of the true post-change distribution in [37], whereas its
probability of misidentification was studied in the two-sided problem in [38],
and was claimed to decay exponentially as a function of the tuning threshold
in a special case of the multichannel problem in [39, Chapter 9.2]. However,
all these results and statements refer to the case where the change occurs as
soon as monitoring begins. While this corresponds to the worst-case scenario
for the detection delay, this is not the case for the task of identification.
Thus, the above results do not provide any guarantees regarding the
conditional probability of wrong identification given that there has not been
a false alarm by the time of the change.

Our first contribution in the present paper is that, in the context of the
general sequential change diagnosis problem, we bound the conditional
probability of false identification, given that there has not been a false
alarm by the time of the change. Specifically, we show, under certain
conditions, that this probability decays at most exponentially / quadratically
in the threshold if the post-change distributions are “closer” / “as close” to
the pre-change distribution than to each other (in the sense of Kullback-
Leibler divergence).

Based on this general result we show that, in the multichannel problem in
which the change can occur only in one channel, the worst-case (with respect
to the change-point) conditional probability of false identification decays
exponentially fast in the threshold. As a result, we show that the min-CuSum
asymptotically minimizes Lorden’s criterion, simultaneously for every possible
post-change distribution, within the class of schemes that satisfy prescribed
bounds on the false alarm rate and the worst-case (with respect to the change-
point) conditional probability of misidentification, as the former goes to
zero sufficiently faster than the former.

The remainder of the paper is organized as follows. In Section II, we
formulate the problem of sequential change diagnosis. In Section III, we
describe the min-CuSum algorithm, review its properties, and provide intuition
on its performance in the sequential change diagnosis problem. In Section IV,
we state the theoretical results of the paper. In Section V, we examine the
conditional misidentification probability of the min-CuSum in two simulation
studies, and in Section VI we conclude. Appendixes A–C contain proofs of the
main and supporting results.

We end this section by introducing some notation that we use throughout the
paper. Thus, $\mathbb{N}$ and $\mathbb{N}_{0}$ are the sets of of positive and
non-negative integers, respectively, and $\mathbb{R}$ is the set of real
numbers. For $x\in\mathbb{R}$, $x^{+}$ is its positive part, i.e.,
$x^{+}\equiv\max\\{x,0\\}.$ We denote by $x\wedge y$ the minimum of $x,y$. If
$(x_{n}),(y_{n})$ are two sequences of positive numbers, then $x_{n}\sim
y_{n}$ stands for $x_{n}/y_{n}\to 1$ as $n\to\infty$. The indicator function
is written as $\mathds{1}(\cdot)$.

##  II Problem Statement

Let $X\equiv\\{X_{n},\,n\in\mathbb{N}\\}$ be a sequence of independent
$\mathbb{S}$-valued random elements, where $\mathbb{S}$ is an arbitrary Polish
space. For each $n\in\mathbb{N}$, we denote by $\mathcal{F}_{n}$ the
$\sigma$-algebra generated by the first $n$ observations, i.e.,
$\mathcal{F}_{n}\equiv\sigma(X_{1},\ldots,X_{n})$, and by $\mathcal{F}_{0}$
the trivial $\sigma$-algebra.

We assume that each term of $X$ has a density with respect to a
$\sigma$-finite measure $\lambda$, which is $f$ up to and including some
deterministic time $\nu\in\mathbb{N}_{0}$ and $g$ after $\nu$. The change
point, $\nu$, is completely unknown, but we assume that the pre-change
density, $f$, is completely specified and that there is a finite collection of
possible post-change distributions, i.e.,

$g\in\\{g_{i},\,i\in\mathcal{I}\\},$ (1)

where $\mathcal{I}$ is an arbitrary finite set. Moreover, we assume that, for
each $i,j\in\mathcal{I}$ with $i\neq j$, the Kullback-Leibler divergences

$\displaystyle\begin{split}I_{i}&\equiv\int_{\mathbb{S}}\log(g_{i}/f)\,g_{i}\,d\lambda,\\\
I_{ij}&\equiv\int_{\mathbb{S}}\log(g_{i}/g_{j})\,g_{i}\,d\lambda,\end{split}$
(2)

are positive and finite.

We denote by $\mathbb{P}_{\infty}$ the distribution of $X$, and by
$\mathbb{E}_{\infty}$ the corresponding expectation, when the change never
occurs, i.e., when $X$ is a sequence of independent random elements with
common density $f$. Moreover, we denote by $\mathbb{P}_{\nu,i}$ the
distribution of $X$, and by $\mathbb{E}_{\nu,i}$ the corresponding
expectation, when the change occurs at time $\nu$ and the post-change density
is $g_{i}$. For simplicity, when the change occurs from the very beginning, we
suppress the dependence on the change point and set
$\mathbb{P}_{i}\equiv\mathbb{P}_{0,i}$ and
$\mathbb{E}_{i}\equiv\mathbb{E}_{0,i}$.

We assume that the terms of the sequence $X$ are observed sequentially and
that the problem is to quickly detect the change and, at the same time, to
identify the correct post-change distribution. Thus, we need to specify a
random time, $T$, at which we declare that the change has occurred, and an
$\mathcal{I}$-valued random variable, $D$, that represents our decision
regarding the post-change density at the time of stopping. That is, for any
$n\in\mathbb{N}$ and $i\in\mathcal{I}$, on the event $\\{T=n,D=i\\}$ the alarm
is raised and $g_{i}$ is declared as the correct post-change density after
having taken $n$ observations. We refer to such a pair $(T,D)$ as a diagnosis
procedure if $T$ is an $\\{\mathcal{F}_{n}\\}$-stopping time and $D$ is
$\mathcal{F}_{T}$-measurable, i.e., if

$\\{T=n\\},\\{T=n,D=i\\}\in\mathcal{F}_{n}\quad\forall\;n\in\mathbb{N},\,i\in\mathcal{I}.$

Without loss of generality, we restrict ourselves to stopping times that are
not almost surely bounded under ${\mathbb{P}}_{\nu,i}$, for any
$\nu\in\mathbb{N}$, $i\in\mathcal{I}$, and we denote by $\mathcal{C}$ the
family of all diagnosis procedures.

We measure the ability of $(T,D)\in\mathcal{C}$ to avoid false alarms using
the average number of observations until stopping under
${\mathbb{P}}_{\infty}$, i.e., ${\mathbb{E}}_{\infty}[T]$, and we denote by
$\mathcal{C}(\alpha)$ the subfamily of diagnosis procedures that control the
expected time until stopping under ${\mathbb{P}}_{\infty}$ by at least
$1/\alpha$, i.e.,

$\mathcal{C}(\alpha)\equiv\\{(T,D)\in\mathcal{C}:{\mathbb{E}}_{\infty}[T]\geq
1/\alpha\\},$

where $\alpha\in(0,1)$ is a user-specified value that represents tolerance to
false alarms.

To measure the ability of $(T,D)\in\mathcal{C}$ to identify the post-change
density $g_{i}$ when the change occurs at time $\nu$, we use the conditional
probability of an incorrect identification given that there was no false
alarm, i.e., ${\mathbb{P}}_{\nu,i}(D\neq i\,|\,T>\nu)$, and we denote by
$\mathcal{C}(\alpha,\beta)$ the subfamily of diagnosis procedures in
$\mathcal{C}(\alpha)$ that control the worst-case conditional probability of
false identification below $\beta$, i.e.,

$\displaystyle\left\\{(T,D)\in\mathcal{C}(\alpha):\max_{i\in\mathcal{I}}\sup_{\nu\in\mathbb{N}_{0}}{\mathbb{P}}_{\nu,i}(D\neq
i\,|\,T>\nu)\leq\beta\right\\},$ (3)

where $\beta\in(0,1)$ is a user-specified value that represents tolerance to
false identifications.

Finally, to measure the ability of $(T,D)\in\mathcal{C}$ to quickly detect the
change when the post-change density is $g_{i}$ for some ${i\in\mathcal{I}}$,
we adopt Lorden’s criterion [17] and employ the worst-case conditional
expected detection delay with respect to both the change point and the data up
to the change:

$\mathcal{J}_{i}[T]\equiv\sup_{\nu\in\mathbb{N}_{0}}\operatorname*{esssup}{\mathbb{E}}_{\nu,i}[T-\nu\,|\,\mathcal{F}_{\nu},T>\nu].$
(4)

Our goal in this work is to show that, under certain conditions, the min-CuSum
achieves

$\inf_{(T,D)\in\mathcal{C}(\alpha,\beta)}\mathcal{J}_{i}[T],$ (5)

simultaneously for every ${i\in\mathcal{I}}$, to a first-order asymptotic
approximation as $\alpha$ and $\beta$ go to zero, as long as $\alpha$ goes to
zero sufficiently faster than $\beta$.

We next provide two setups in which the above sequential change diagnosis
problem arises naturally.

###  II-A The Multichannel Setup

Suppose that $d$ independent data channels are simultaneously monitored and
there is a change in the marginal distributions of an unknown subset of them
at some unknown time, $\nu$. Specifically, suppose that channel
$j\in\\{1,\ldots,d\\}$ generates a sequence of independent
$\mathbb{S}_{j}$-valued random elements, where $\mathbb{S}_{j}$ is some Polish
space, and let $X_{j,n}$ denote the observation from channel $j$ at time $n$.
If the change does not occur in channel $j$, then $X_{j,n}$ has density
$p_{j}$ with respect to a $\sigma$-finite measure $\lambda_{j}$ on
$\mathbb{S}_{j}$ for every $n\in\mathbb{N}$. On the the other hand, if the
change does occur in that channel at time $\nu$, then the density of $X_{j,n}$
is $p_{j}$ for $n\leq\nu$ and $q_{j}$ for $n>\nu$. We assume that, for each
$j\in\mathcal{I}$, the densities $p_{j}$ and $q_{j}$ have positive and finite
Kullback-Leibler divergences, i.e.,

$\displaystyle\begin{split}&\int_{\mathbb{S}_{j}}\log(q_{j}/p_{j})\,q_{j}\;d\lambda_{j}\in(0,\infty),\\\
&\int_{\mathbb{S}_{j}}\log(p_{j}/q_{j})\,p_{j}\;d\lambda_{j}\in(0,\infty).\end{split}$
(6)

This is a special case of the general setup we consider, where

$\displaystyle X_{n}$
$\displaystyle=(X_{1,n},X_{2,n},\ldots,X_{d,n})\in\mathbb{S}\equiv\mathbb{S}_{1}\otimes\cdots\otimes\mathbb{S}_{d},$
(7)

and the pre-change density is

$f(x_{1},\ldots,x_{d})=\prod_{j=1}^{d}p_{j}(x_{j}),\quad(x_{1},\ldots,x_{d})\in\mathbb{S}.$
(8)

We next consider two special cases for the post-change regime. In the first
one, the change is assumed to occur in only one channel. In the second, there
is no prior information about the number of affected channels, which means
that the change may occur in any possible subset of channels.

####  II-A1 Single-Fault

If the change can occur in only one channel, as it is often assumed in the
literature (e.g., [33, 32]), then $\mathcal{I}=\\{1,\ldots,d\\}$ and, for each
$i\in\mathcal{I}$, $g_{i}$ is the post-change density when the fault occurs in
sensor $i$, i.e., for $(x_{1},\ldots,x_{d})\in\mathbb{S}$,

$g_{i}(x_{1},\ldots,x_{d})=q_{i}(x_{i})\prod_{\begin{subarray}{c}j\in\\{1,\ldots,d\\}\\\
j\neq i\end{subarray}}p_{j}(x_{j}).$ (9)

In this case, the Kullback-Leibler divergences in (2) take the form

$\displaystyle\begin{split}I_{i}&=\int_{\mathbb{S}_{i}}\log(q_{i}/p_{i})\,q_{i}\;d\lambda_{i},\\\
I_{ij}&=\int_{\mathbb{S}_{i}}\log(q_{i}/p_{i})\,q_{i}\;d\lambda_{i}+\int_{\mathbb{S}_{j}}\log(p_{j}/q_{j})\,p_{j}\;d\lambda_{j}.\end{split}$
(10)

####  II-A2 Concurrent-Fault

When there is no prior information about the number of channels that are
affected by the change, as for example in [40, 41, 23], then $\mathcal{I}$ is
the family of all non-empty subsets of $\\{1,\ldots,d\\}$ and there are
$2^{d}-1$ possibilities for the post-change density. Specifically, if
${i=\\{c_{1},\ldots,c_{p}\\}}$ where $c_{1},\ldots,c_{p}\in\\{1,\ldots,d\\}$,
then $g_{i}$ represents the post-change density when the the change occurs in
channels $c_{1},\ldots,c_{p}$, i.e.,

$g_{i}(x_{1}\ldots,x_{d})=\prod_{t\in i}q_{t}(x_{t})\;\times\;\prod_{t\notin
i}p_{t}(x_{t}),$ (11)

where $(x_{1},\ldots,x_{d})\in\mathbb{S}$, in which the Kullback-Leibler
divergences in (2) take the form

$\displaystyle\begin{split}I_{i}&=\sum_{t\in
i}\int_{\mathbb{S}_{t}}\log(q_{t}/p_{t})q_{t}\;d\lambda_{t},\\\
I_{ij}&=\sum_{t\in i\setminus
j}\int_{\mathbb{S}_{t}}\log(q_{t}/q_{t})q_{t}\;d\lambda_{t}\,\\\ &+\sum_{t\in
j\setminus
i}\int_{\mathbb{S}_{t}}\log(p_{t}/q_{t})p_{t}\;d\lambda_{t}.\end{split}$ (12)

###  II-B The Two-Sided Setup

Suppose that there is a single stream of observations, whose distibution is
specified up to an unknown parameter, and, at some unknown time, there is
either an increase or a decrease in the value of this parameter. For
simplicity, consider the case that the underlying distribution belongs to a
one-parameter exponential family. To be specific, let $h$ be a density with
respect to $\nu$ and let $\varphi$ denote its cumulant generating function,
i.e.,

$\varphi(\gamma)\equiv\log\int_{\mathbb{S}}\exp\\{\gamma
x\\}h(x)\,\nu(dx),\quad\gamma\in\mathbb{R}.$

Suppose that the essential domain of $\psi$, $\Gamma$, is non-empty, i.e.,

$\Gamma\equiv\\{\gamma\in\mathbb{R}:\varphi(\gamma)<\infty\\}\neq\emptyset,$
(13)

and, for any $\gamma\in\Gamma$, consider the following density

$h_{\gamma}(x)\equiv h(x)\exp\\{\gamma x-\varphi(\gamma)\\},\quad
x\in\mathbb{R}.$ (14)

Let $\gamma_{0},\gamma_{1},\gamma_{2}\in\Gamma$. If the initial parameter is
$\gamma_{0}$ and changes to either $\gamma_{1}$ or $\gamma_{2}$, then

$f=h_{\gamma_{0}},\quad g_{1}=h_{\gamma_{1}},\quad g_{2}=h_{\gamma_{2}},$ (15)

and the Kullback-Leibler divergences in (2), for $i,j\in\\{1,2\\}$, take the
following form:

$\displaystyle\begin{split}I_{i}&={\mathbb{E}}_{i}\left[\log\left(\frac{h_{\gamma_{i}}(X_{1})}{h_{\gamma_{0}}(X_{1})}\right)\right]\\\
&=(\gamma_{i}-\gamma_{0})\,\varphi^{\prime}(\gamma_{i})-(\varphi(\gamma_{i})-\varphi(\gamma_{0})),\\\
\end{split}$ (16)

$\displaystyle\begin{split}I_{ij}&={\mathbb{E}}_{i}\left[\log\left(\frac{h_{\gamma_{i}}(X_{1})}{h_{\gamma_{j}}(X_{1})}\right)\right]\\\
&=(\gamma_{i}-\gamma_{j})\,\varphi^{\prime}(\gamma_{i})-(\varphi(\gamma_{i})-\varphi(\gamma_{j})).\end{split}$
(17)

##  III The min-CuSum Algorithm

In this section, we introduce the min-CuSum algorithm and provide some
intuition regarding its performance in the sequential change diagnosis
problem. In what follows, for every $n\in\mathbb{N}$ and $i,j\in\mathcal{I}$
with $j\neq i$ we set

$\displaystyle\begin{split}\Lambda_{i}(n)\equiv\frac{g_{i}(X_{n})}{f(X_{n})},\quad&\ell_{i}(n)\equiv\log\Lambda_{i}(n),\\\
\Lambda_{ij}(n)\equiv\frac{g_{i}(X_{n})}{g_{j}(X_{n})},\quad&\ell_{ij}(n)\equiv\log\Lambda_{ij}(n).\end{split}$
(18)

###  III-A Min-CuSum for Sequential Change Detection

Page’s CuSum algorithm [3] for detecting a change from $f$ to $g_{i}$, for
some $i\in\mathcal{I}$, raises an alarm as soon as the statistic

$\displaystyle Y_{i}(n)$ $\displaystyle\equiv\max_{0\leq m\leq
n}\sum_{u=m+1}^{n}\ell_{i}(u),\quad n\in\mathbb{N},$ (19)

exceeds a threshold $b_{i}>0$, i.e., at

$\displaystyle\begin{split}\sigma_{i}(b_{i})\equiv\inf\\{n\geq 1:Y_{i}(n)\geq
b_{i}\\},\end{split}$ (20)

where we adopt the convention $\sum_{n+1}^{n}=0$. An important property of
this stopping rule concerning its implementation in practice is that its
statistic can be computed via the following recursion:

$\displaystyle Y_{i}(n)$
$\displaystyle=\left(Y_{i}(n-1)+\ell_{i}(n)\right)^{+},\quad n\in\mathbb{N},$
(21)

with $Y_{i}(0)=0$. Moreover, it was shown in [18] to minimize
$\mathcal{J}_{i}$ in $\mathcal{C}(\alpha)$, i.e.,

$\displaystyle\mathcal{J}_{i}\left[\sigma_{i}(b)\right]=\inf_{(T,D)\in\mathcal{C}(\alpha)}\mathcal{J}_{i}[T],$
(22)

as long as the false alarm constraint is satisfied with equality.

Of course, this algorithm is directly applicable in our setup only when
$|\mathcal{I}|=1$. When $|\mathcal{I}|>1$, a straightforward way to detect the
change is to run in parallel the $|\mathcal{I}|$ CuSum statistics,
$Y_{1},\ldots,Y_{|\mathcal{I}|}$, and stop as soon as one of them exceeds its
corresponding threshold, i.e., at

$\min_{i\in\mathcal{I}}\sigma_{i}(b_{i}).$

In what follows, for the sake of simplicity, we consider equal thresholds,
i.e., we set $b_{1}=\cdots=b_{|\mathcal{I}|}=b$, and we refer to the stopping
time

$\sigma(b)\equiv\min_{i\in\mathcal{I}}\sigma_{i}(b)$ (23)

as the “min-CuSum” stopping time. For this stopping time, it is known (see the
proof of [42, Theorem 1]) that, for any $b>0$,

$\displaystyle{\mathbb{E}}_{\infty}[\sigma(b)]$ $\displaystyle\geq
e^{b}/|\mathcal{I}|,$ (24)

thus, it is clear that for any $\alpha\in(0,1)$ we have
$\sigma(b_{\alpha})\in\mathcal{C}(\alpha)$ where

$b_{\alpha}\equiv|\log\alpha|+\log|\mathcal{I}|.$ (25)

Moreover, it is well known (see, e.g., [17]) that the worst-case scenario for
the conditional expected delay (4) of the min-CuSum is achieved when the
change occurs from the beginning, i.e., for every $i\in\mathcal{I}$ and $b>0$,

$\displaystyle\mathcal{J}_{i}\left[\sigma(b)\right]={\mathbb{E}}_{i}[\sigma(b)]$
(26)

and that $\sigma(b_{\alpha})$ minimizes $\mathcal{J}_{i}$ in
$\mathcal{C}(\alpha)$, for every ${i\in\mathcal{I}}$, to a first-order
asymptotic approximation as $\alpha\to 0$. In particular,

$\displaystyle\mathcal{J}_{i}\left[\sigma(b_{\alpha})\right]\sim\frac{|\log\alpha|}{I_{i}}\sim\inf_{(T,D)\in\mathcal{C}(\alpha)}\mathcal{J}_{i}[T]$
(27)

for every $i\in\mathcal{I}$ as $\alpha\to 0$.

###  III-B Min-CuSum for Sequential Change Diagnosis

For any $b>0$, the stopping time $\sigma(b)$ is associated with a natural
identification rule, which is to select the post-change alternative that
corresponds to the largest CuSum statistic at the time of stopping, i.e.,

$\widehat{\sigma}(b)\in\operatorname*{arg\,max}_{i\in\mathcal{I}}Y_{i}(\sigma(b)),$
(28)

solving ties, if any, in some arbitrary way. In other words, the post-change
distribution is declared to be the one that corresponds to the CuSum statistic
that first crosses the threshold $b$. Thus, for any $b>0$,
$(\sigma(b),\widehat{\sigma}(b))$ is a sequential change diagnosis procedure,
which we will still refer to as the min-CuSum, as its implementation is the
same as for the pure change-detection problem. The only (but main) difference
is that in the context of change diagnosis the threshold $b$ must be selected
to satisfy a false identification constraint in addition to the false alarm
constraint.

Before stating our theoretical results regarding the performance of min-CuSum
as a change diagnosis procedure, it is useful to provide some intuition on the
behavior of the CuSum statistics, $Y_{i},i\in\mathcal{I}$.

First of all, since each $Y_{i}$ tends to return to 0 before the change, none
of them will, in general, be large at the time of the change. Now, suppose
that the true post-change density is $g=g_{j}$. Then, for every $n>\nu$ and
$i\in\mathcal{I}$ with $i\neq j$ we have

$\displaystyle\begin{split}{\mathbb{E}}_{j}[\ell_{j}(n)]&=I_{j},\\\
{\mathbb{E}}_{j}[\ell_{i}(n)]&=I_{j}-I_{ji}.\\\ \end{split}$ (29)

This means that the “correct” CuSum statistic, $Y_{j}$, grows after the change
essentially like a random walk with positive drift, $I_{j}$. On the other
hand, the post-change behavior of an “incorrect” CuSum statistic, $Y_{i}$,
depends on the sign of $I_{j}-I_{ji}$, which reflects whether the true post-
change density, $g_{j}$, is closer, in the sense of KL divergence, to the pre-
change density, $f$, or to the true post-change distribution, $g_{i}$.

  * •

If $I_{j}<I_{ji}$, then $g_{j}$ is closer to $f$ than $g_{i}$ and $Y_{i}$
behaves in the post-change regime as in the pre-change regime, i.e., it tends
to return to zero.

  * •

If $I_{j}=I_{ji}$, then $g_{i}$ and $f$ have the same “distance” from $g_{j}$
and $Y_{i}$ becomes a driftless random walk reflected at the origin.
Therefore, while it still does not systematically grow after the change, it
will take much more time to return to 0 than before the change occurred.

  * •

If $I_{j}>I_{ji}$, then $g_{j}$ is closer to $g_{i}$ than $f$ and $Y_{i}$
behaves similarly to $Y_{j}$, i.e., it grows essentially like a random walk
with positive drift $I_{j}-I_{ji}$, which is notably less than the drift of
$Y_{j}$.

We continue by applying this discussion in the context of each of the
scenarios presented in Section II-A and Section II-B, namely, the single-fault
and concurrent-fault multichannel problems, as well as the two-sided problem.

  * •

We consider, first, the single-fault multichannel problem presented in Section
II-A1, in which case $\mathcal{I}=\\{1,\ldots,d\\}$, where $d$ is the number
of channels. Then, from (10) we can see that

$\displaystyle I_{j}$
$\displaystyle<I_{ji}\quad\forall\;i,j\in\mathcal{I},\,i\neq j.$ (30)

Thus, in this context, the values of all “incorrect” statistics will tend to
be small after the change.

  * •

We consider, next, the concurrent-fault multichannel problem presented in
Section II-A2, with $d=3$ channels. Since this case is more complex, we assume
for the sake of illustration that $p_{i}=p$ and $q_{i}=q$ for $i=1,\ldots,d,$
and that the pre- and post-change distributions are Gaussian with standard
deviation one and mean zero and one, respectively, i.e.,

$p=\mathcal{N}(0,1),\quad q=\mathcal{N}(1,1).$ (31)

We assume that the fault occurs in channels $1$ and $2$, i.e.,
$g=g_{\\{1,2\\}}$. Then, we obtain from (12) and the symmetry of the Gaussian
KL-number that

$\displaystyle\begin{split}I_{\\{1,2\\}}&<I_{\\{1,2\\},\\{3\\}},\\\
I_{\\{1,2\\}}&=I_{\\{1,2\\},\\{1,3\\}},\\\
I_{\\{1,2\\}}&>I_{\\{1,2\\},\\{2\\}}.\\\ \end{split}$ (32)

Thus, we expect that, after the change, $Y_{\\{3\\}}$ will tend to return to
zero, whereas $Y_{\\{1,3\\}}$ will not grow in a systematic way, but it will
take much longer to return to zero. The statistic $Y_{\\{2\\}}$ will grow
roughly linearly but at a slower rate than the “correct” statistic,
$Y_{\\{1,2\\}}$. In Fig. 1 we plot a path of these statistics when the change
occurs at time ${\nu=50}$ with ${g=g_{\\{1,2\\}}}.$

  * •

In the two-sided problem of Subsection II-B, by (16)–(17), we have

$\displaystyle\begin{split}I_{ji}-I_{j}&=(\gamma_{0}-\gamma_{i})\,\varphi^{\prime}(\gamma_{j})-(\varphi(\gamma_{0})-\varphi(\gamma_{i}))\,\\\
&=(\gamma_{0}-\gamma_{i})\left[\varphi^{\prime}(\gamma_{j})-\frac{\varphi(\gamma_{0})-\varphi(\gamma_{i})}{\gamma_{0}-\gamma_{i}}\right].\end{split}$
(33)

This implies that $I_{j}<I_{ji}$, which means that the “incorrect” statistic
tends to remain small after the change occurs. To see that this inequality
indeed holds, note that since $\varphi$ is differentiable in the interior of
$\Gamma$, there exists some $\gamma_{i}^{*}$ between $\gamma_{0}$ and
$\gamma_{i}$ such that

$\varphi^{\prime}(\gamma_{i}^{*})=\frac{\varphi(\gamma_{0})-\varphi(\gamma_{i})}{\gamma_{0}-\gamma_{i}},$
(34)

and, consequently,

$I_{ji}-I_{j}=(\gamma_{0}-\gamma_{i})\left[\varphi^{\prime}(\gamma_{j})-\varphi^{\prime}(\gamma_{i}^{*})\right].$
(35)

By the strict convexity of $\varphi$ it follows that if
$\gamma_{i}<\gamma_{0}<\gamma_{j},$ then

$\varphi^{\prime}(\gamma_{j})-\varphi^{\prime}(\gamma_{i}^{*})>0\quad\&\quad\gamma_{0}-\gamma_{i}>0,$
(36)

whereas if $\gamma_{j}<\gamma_{0}<\gamma_{i}$, then

$\varphi^{\prime}(\gamma_{j})-\varphi^{\prime}(\gamma_{i}^{*})<0\quad\&\quad\gamma_{0}-\gamma_{i}<0,$
(37)

which proves that, indeed, $I_{j}<I_{ji}$.

Figure 1: Sample paths of some CuSum statistics in the concurrent-fault
multichannel problem with $d=3$ channels and the change occurs in the first
two of them, i.e., $g=g_{\\{1,2\\}}$, at time $\nu=50$.

##  IV Main Results

In this section we establish our theoretical results. We first establish a
non-asymptotic upper bound on the conditional probability of mistakenly
selecting $g_{i}$ when the true post-change density is $g_{j}$, given that
there has not been a false alarm at the time of the change, where
$i,j\in\mathcal{I}$ with $j\neq i$. This is established when $g_{j}$ is
closer—in the sense of Kullback-Leibler divergence—to the pre-change density
$f$ than to $g_{i}$, i.e., ${I_{j}\leq I_{ji}}$. To obtain this result, we
make the following second-moment assumption

$\int\left(\big{(}\log(g_{i}/f)\big{)}^{+}\right)^{2}g_{i}\,d\lambda<\infty,$
(38)

and we also make certain assumptions on the cumulant-generating function of
$\ell_{i}(n)$ under ${\mathbb{P}}_{j}$,

$\psi_{ij}(\theta)\equiv\log\left({\mathbb{E}}_{j}\left[\exp[\theta\,\ell_{i}(1)]\right]\right),\quad\theta\in\mathbb{R}.$
(39)

The following theorem relates the relative distances between $g_{i},g_{j},$
and $f$ to the conditional probability of misidentication as a function of the
threshold $b$.

######  Theorem 1.

Fix $i,j\in\mathcal{I},i\neq j$, $b>0$, and let $\nu\geq 0$ such that

${\mathbb{P}}_{\infty}(Y_{i}(\nu)\geq x\;|\;\sigma(b)>\nu)\leq
e^{-x}\quad\text{for all}\;x\geq 0.$ (40)

  * (i)

Suppose that ${I_{j}<I_{ji}}$ and that $\psi_{ij}$ has a positive root
$r_{ij}$.

    * (a)

If $r_{ij}>1$, then

$\displaystyle\begin{split}{\mathbb{P}}_{\nu,j}(\widehat{\sigma}(b)=i\;&|\;\sigma(b)>\nu)\\\
&\leq\frac{r_{ij}}{r_{ij}-1}\,e^{-b}\,(1+\phi(b)),\end{split}$ (41)

where $\phi(b)$ does not depend on $\nu$ and goes to $0$ as $b\to\infty$.

    * (b)

If $r_{ij}\in(0,1]$, then

$\displaystyle\begin{split}{\mathbb{P}}_{\nu,j}(\widehat{\sigma}(b)&=i\;|\;\sigma(b)>\nu)\\\
&\leq(r_{ij}+1/I_{j})\,b\,e^{-r_{ij}b}(1+\phi(b)),\end{split}$ (42)

where $\phi(b)$ is as above.

  * (ii)

If ${I_{j}=I_{ji}}$ and $\psi_{ij}$ is finite on an open interval containing
$0$, then

${\mathbb{P}}_{\nu,j}(\widehat{\sigma}(b)=i\;|\;\sigma(b)>\nu)\leq\widetilde{C}\,b^{-1}\,\left(1+\phi(b)\right),$
(43)

where $\phi(b)$ is as in (i) and $\widetilde{C}$ is a constant.

###### Proof:

Appendix B. ∎

To the best of our understanding, condition (40) is assumed implicitly in the
proof of the false identification control of the Vector CuSum [31, Theorem 2],
as discussed in [30]. This condition is satisfied, trivially, when $\nu=0$.
Indeed, it is well known that, for all $i\in\mathcal{I}$ and
$n\in\mathbb{N}_{0}$,

${\mathbb{P}}_{\infty}(Y_{i}(n)\geq x)\leq e^{-x}\quad\text{ for all }x\geq
0.$ (44)

However, it is unclear to us whether this is the case, in general, for other
values of $\nu$. We next show condition (40) is indeed satisfied for every
$\nu\geq 0$ in the multichannel setup in the case of a single fault.

###  IV-A The Single Fault Multichannel Setup

We next apply Theorem 1 to the case of the single-fault multichannel problem
introduced in Section II-A1. In this setup, we show that the worst-case—with
respect to the change-point—conditional probability of misidentification of
the min-CuSum decays exponentially fast in the threshold $b$ and, as a result,
the min-CuSum achieves (5), simultaneously for every ${i\in\mathcal{I}}$, as
$\alpha$ goes to 0 sufficiently faster than $\beta$.

######  Corollary 1.1.

Consider the single-fault multichannel problem of Section II-A1 and suppose
that, for every $i\in\mathcal{I}$,

$\displaystyle\int_{\mathbb{S}_{i}}\left(\log^{2}(q_{i}/p_{i})\right)q_{i}\,d\lambda_{i}<\infty.$

  1. (i)

For any $b>0$,

$\displaystyle\max_{j\in\mathcal{I}}\sup_{\nu\in\mathbb{N}_{0}}{\mathbb{P}}_{\nu,j}(\widehat{\sigma}(b)\neq
j\,|\,\sigma(b)>\nu)\leq$ $\displaystyle C\,b\,e^{-b}\,(1+\phi(b)),$

where $\phi(b)$ is a function of $b$ that does not depend on $\nu$ and goes to
$0$ as ${b\to\infty}$, and

$C\equiv({|\mathcal{I}|}-1)\left(1+\max_{i\in\mathcal{I}}(1/I_{i})\right).$
(45)

  2. (ii)

Suppose also that $\alpha$ and $\beta$ satisfy

$C\,b_{\alpha}\,e^{-b_{\alpha}}\left(1+\phi(b_{\alpha})\right)\leq\beta,$ (46)

where $C$ and $\phi$ are defined as above, and $b_{\alpha}$ is defined as in
(25). Then,

$\left(\sigma(b_{\alpha}),\widehat{\sigma}(b_{\alpha})\right)\in\mathcal{C}(\alpha,\beta)\quad\forall\,\alpha\in(0,1)$
(47)

and, for every $i\in\mathcal{I}$,

$\mathcal{J}_{i}[\sigma(b_{\alpha})]\sim\inf_{(T,D)\in\mathcal{C}(\alpha,\beta)}\mathcal{J}_{i}[T]\quad\text{
as }\alpha\to 0.$ (48)

###### Proof:

(i) By Boole’s inequality, for any $j\in\mathcal{I}$ we have

${\mathbb{P}}_{\nu,j}\left(\widehat{\sigma}(b)\neq
j\,|\,\sigma(b)>\nu\right)\leq\sum_{i\neq
j}{\mathbb{P}}_{\nu,j}\left(\widehat{\sigma}(b)=i\,|\,\sigma(b)>\nu\right).$

Therefore, it suffices to show that, for every $j\in\mathcal{I}$, (42) holds
with $r_{ij}=1$ for every $\nu\in\mathbb{N}_{0}$, $i\in\mathcal{I}$, $b>0$. In
what follows we fix $\nu,i,j,b$.

We first show that condition (40) holds for every $\nu\geq 0$. Indeed, for all
$x\geq 0$ we have

$\displaystyle{\mathbb{P}}_{\infty}(Y_{i}(\nu)\geq x\,|\,\sigma(b)>\nu)$
$\displaystyle={\mathbb{P}}_{\infty}(Y_{i}(\nu)\geq
x\,|\,\sigma_{j}(b)>\nu\;\text{for every}\;j\in\mathcal{I})$
$\displaystyle={\mathbb{P}}_{\infty}(Y_{i}(\nu)\geq x\;|\;\sigma_{i}(b)>\nu)$
$\displaystyle\leq{\mathbb{P}}_{\infty}(Y_{i}(\nu)\geq x).$

The first equality follows by the definition of $\sigma(b)$ and the second by
the independence of the channels, whereas the inequality follows by [43,
Theorem 1], since $Y_{i}$ is a non-negative stochastically monotone Markov
process (Lemma 5 in Appendix C).

We have already seen that in this multichannel setup we have $I_{j}<I_{ji}$
for every $i,j\in\mathcal{I}$ with $i\neq j$ (recall (30)). Therefore, in view
of Theorem 1(i), it remains to show that each $\psi_{ij}$ has root equal to
$1$. Indeed, for each $i\in\mathcal{I}$, the likelihood ratio $\Lambda_{i}(n)$
defined in (18) takes the following form:

$\displaystyle\Lambda_{i}(n)$
$\displaystyle=\frac{q_{i}(X_{i,n})}{p_{i}(X_{i,n})},\quad\;n\in\mathbb{N},$

and, consequently,

$\displaystyle\exp[\psi_{ij}(1)]$
$\displaystyle={\mathbb{E}}_{j}[\exp[\ell_{i}(1)]]$
$\displaystyle={\mathbb{E}}_{j}\left[\frac{q_{i}(X_{i,n})}{p_{i}(X_{i,n})}\right]=\int(q_{i}/p_{i})\,p_{i}\,d\lambda_{i}=1.$

(ii) For any $\alpha,\beta\in(0,1)$, we have
$\mathcal{C}(\alpha,\beta)\subseteq\mathcal{C}(\alpha)$, therefore

$\inf_{(T,D)\in\mathcal{C}(\alpha,\beta,\mathbb{N}_{0})}\mathcal{J}_{i}[T]\geq\inf_{(T,D)\in\mathcal{C}(\alpha)}\mathcal{J}_{i}[T].$
(49)

In view of (27), it suffices to show that
${\sigma(b_{\alpha})\in\mathcal{C}(\alpha,\beta)}$ when $\beta$ satisfies
(46), which follows by Corollary 1.1(i). ∎

###  IV-B The Two-Sided Setup

We next apply Theorem 1 to the two-sided setup of Subsection II-B. In this
case, we have already seen that condition (30) holds for every
$i,j\in\mathcal{I}$ with $i\neq j$. Moreover, by the definition of $\psi_{ij}$
in (39) we have

$\displaystyle\begin{split}\psi_{ij}(\theta)&\equiv\log\int\exp\left\\{\theta\log\frac{h_{\gamma_{j}}}{f}\right\\}\;h_{\gamma_{i}}\;\nu(dx)\\\
&=\varphi(\theta(\gamma_{j}-\gamma_{0})+\gamma_{i})-\theta(\varphi(\gamma_{j})-\varphi(\gamma_{0}))-\varphi(\gamma_{i}),\end{split}$
(50)

Since $\psi_{ij}$ is finite, strictly convex, and differentiable on $\Gamma$
with

${\psi_{ij}^{\prime}(0)={\mathbb{E}}_{j}[\ell_{i}(1)]}=I_{1}-I_{12}<0,$

$\psi_{ij}$ has a positive root when $\Gamma=\mathbb{R}$. Thus, the
probability of misidentification will decay exponentially in the threshold
$b$, depending on the roots of $\psi_{ij}.$ In the following corollary, we
specialize this result to the mean-shift of a Gaussian sequence, where we
explicitly compute the misidentification rate from Theorem 1.

######  Corollary 1.2.

Consider the two-sided problem with $h_{\gamma}=N(\gamma,1)$ and
$\gamma_{0}=0,$ and $\gamma_{1}<0<\gamma_{2}$. For any $b>0$ and
$\nu\in\mathbb{N}_{0}$ for which (40) holds we have

$\max_{j=1,2}\sup_{\nu\in\mathbb{N}_{0}}{\mathbb{P}}_{\nu,j}\left(\widehat{\sigma}(b)\neq
j\,|\,\sigma(b)>\nu\right)\leq C^{*}e^{-b}(1+\phi(b)),$ (51)

where

$C^{*}=1+\frac{1}{2}\max\left\\{\frac{|\gamma_{1}|}{|\gamma_{2}|},\frac{|\gamma_{2}|}{|\gamma_{1}|}\right\\}$

and $\phi(b)$ is as in Theorem 1.

###### Proof:

It follows from (33)–(37) that (30) holds, so it remains to compute the roots
of $\psi_{ij}$ using (50). Since ${\varphi(\gamma)=\gamma^{2}/2},$ solving
$\psi_{ij}(\theta)=0$ for $\theta$ yields
${\theta=1+2|\gamma_{j}/\gamma_{i}|}$. Finally, using Theorem 1(i)(a), the
proof is complete. ∎

##  V Simulation Studies

In this section, we simulate two variations of the multichannel problem
introduced in Section II-A, with three data channels, i.e., $d=3$. In the
first study we consider the single-fault multichannel problem of Section
II-A1, i.e., $\mathcal{I}=\\{1,\ldots,d\\}$, and in the second study the
concurrent-fault multichannel problem of Section II-A2, i.e., $\mathcal{I}$ is
the set of all non-empty subsets of $\\{1,\ldots,d\\}$. In both studies, the
pre- and post-change distributions of the channels are assumed to be Gaussian,
as in (31).

###  V-A Single-Fault Multichannel Problem

In this study, we consider the case where the fault occurs in channel 1 only
i.e., $g=g_{1}$. Due to symmetry, there is no reason to consider the case
where $g=g_{2}.$ For $\nu=0,20$, and $100$, we simulate $10^{4}$ paths of the
CuSum statistics $Y_{i},i\in\mathcal{I}$, where $g=g_{1},$ in order to
estimate

${\mathbb{P}}_{\nu,1}\left(\widehat{\sigma}(b)\neq 1\,|\,\sigma(b)>\nu\right)$
(52)

as a function of $b$. We report the results in Fig. 2. For each change point,
the conditional probability of misidentification goes to zero as $b$
increases, and the decay appears exponential in $b$. The conditional
probability of misidentification increases as $\nu$ increases, with a
noticeable difference between the cases of ${\nu=0}$ and ${\nu=20}$. However,
the estimated probabilities when ${\nu=20}$ and ${\nu=100}$ are nearly
indistinguishable. We also include a curve obtained from the first-order term
${C}be^{-b}$ in the upper bound from Corollary 1.1, where in particular
straight-forward calculation shows that ${C=6}$.

Figure 2: For the single-fault multichannel problem, the conditional
probability of misidentification, given that there was not a false alarm, is
plotted as a function of the threshold $b$, for several values of the change
point, ${\nu=0,20,100}$. Standard errors are represented with error bars, and
only every fourth error bar is included for the sake of visual clarity. The
first-order term of the theoretical upper bound for the worst-case conditional
probability of misidentification is also plotted.

###  V-B Concurrent-Fault Multichannel Problem

In this study, we analyze the case where the fault occurs in channels 1 and 2
simultaneously, i.e., $g=g_{\\{1,2\\}}$, in the spirit of Section III-B. For
${\nu=0,20,}$ and $100$, we simulate $10^{4}$ paths of the CuSum statistics
$Y_{i},i\in\mathcal{I},$ in order to estimate the overall probability of
misidentification,

${\mathbb{P}}_{\nu,\\{1,2\\}}\left(\widehat{\sigma}(b)\neq\\{1,2\\}\,|\,\sigma(b)>\nu\right),$
(53)

as well as the probability of incorrectly identifying each of
$g_{\\{2\\}},g_{\\{1,3\\}},$ and $g_{\\{3\\}}$ as the post-change
distribution, i.e.,

${\mathbb{P}}_{\nu,\\{1,2\\}}\left(\widehat{\sigma}(b)=k\,|\,\sigma(b)>\nu\right)$
(54)

for ${k=\\{2\\},\\{1,3\\},\\{3\\}}$.

In Fig. 3, we report the overall probability of misidentification (53) for
$\nu=0,20,$ and $100$. As in the single-fault study, this is smaller for
$\nu=0$ than for $\nu=20$, whereas it is essentially the same for $\nu=20$ and
$\nu=100$.

In Fig. 4, we report the “partial” probabilities of misidentification in (54)
for ${\nu=100}$. We see that these are ordered in the way suggested by (32),
with $g_{\\{2\\}}$ being more frequently incorrectly identified as the post-
change distribution than $g_{\\{1,3\\}}$, and the latter more frequently
identified as the post-change distribution than $g_{\\{3\\}}$.

Figure 3: For the concurrent-fault multichannel problem, the overall
conditional probability of misidentification is plotted, when the true post-
change distribution is $g_{\\{1,2\\}}$. The curves are plotted as functions of
the threshold $b$, and the three curves correspond to the cases of $\nu=0,20,$
and $100$. Standard errors are represented with error bars, and only every
fourth error bar is included for the sake of visual clarity. Figure 4: The
three curves correspond to the conditional probabilities of identifying
$g_{\\{2\\}},g_{\\{1,3\\}}$, and $g_{\\{3\\}}$ as the post-change
distribution, given that there was not a false alarm, when the true post-
change distribution is $g_{\\{1,2\\}}.$ These curves are plotted as functions
of the threshold $b$, and the change time is $\nu=100$. Standard errors are
represented with error bars, and only every fourth error bar is included for
the sake of visual clarity.

##  VI Conclusion

In this work, we study the min-CuSum algorithm in the context of the
sequential change diagnosis, where it is desirable to not only detect the
change but also to isolate the post-change regime among a finite set of
alternatives. In the special case that the data are collected over independent
channels and the change occurs in one of the channels, we show that the
conditional probability of misidentification decays exponentially in the
threshold, uniformly for all possible change points. Our results imply a
similar result for the two-sided problem in an exponential family, under a
certain technical condition whose verification remains an open problem.

The sequential change diagnosis algorithm we consider in this work can be
naturally extended to more general, pre-change and post-change models that
allow for composite hypotheses and/or non-iid data. A theoretical analysis in
such cases is an interesting subject for future work. Moreover, another
interesting direction for further research is the study of decentralized
sequential change diagnosis algorithms in the context of the multichannel
problem. For example, suppose it is known a priori that the change will occur
in exactly $M$ channels, and consider the algorithm that stops as soon as $M$
CuSum statistics have crossed the threshold, as in [44]. Our results in the
present paper cover the special case where $M=1$. An analysis in the case
where the change can occur in more than one channels simultaneously, i.e.,
$M>1$, is an open problem.

##  Appendix A Properties of CuSum stopping times

Throughout this appendix we fix $b>0$ and $i,j\in\mathcal{I}$ such that $i\neq
j$. We recall from Section III that $\sigma_{i}(b)$ is the CuSum stopping
time, with threshold $b$, for detecting a change from $f$ to $g_{i}$, i.e.,

$\displaystyle\sigma_{i}(b)$
$\displaystyle\equiv\inf\\{n\in\mathbb{N}:Y_{i}(n)\geq b\\}.$

We use the following notation for the log-likelihood ratios for
$n\in\mathbb{N}$:

$Z_{i}(n)\equiv\sum_{k=1}^{n}\ell_{i}(k).$ (55)

It is known (e.g., [39, Section 8.2.6.5]) that the expected value of
$\sigma_{i}$ admits the following lower bounds when the change occurs at at
$\nu=0$ and the true post-change hypothesis is $g_{j}$:

  * •

If $I_{j}<I_{ji}$ and $\psi_{ij}$ has a positive root $r_{ij}$, then

${\mathbb{E}}_{j}[\sigma_{i}(b)]\geq e^{r_{ij}b}.$ (56)

  * •

If $I_{j}=I_{ji}$ and $\psi_{ij}$ is finite on an interval containing zero,
then

${\mathbb{E}}_{j}[\sigma_{i}(b)]\geq\frac{b^{2}}{{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]}.$
(57)

We next develop analogous lower bounds in the case that $Y_{i}$ is initialized
from some value $x$ in $[0,b]$. Specifically, we denote by $L_{ij}(x;b)$ the
expectation under ${\mathbb{P}}_{j}$ of $\sigma_{i}(b)$, when $Y_{i}$ is
initialized from some $x\in[0,b]$, i.e.,

$L_{ij}(x;b)\equiv{\mathbb{E}}_{j}[\sigma_{i}(b)\,|\,Y_{i}(0)=x],\quad
x\in[0,b].$ (58)

Clearly, $L(\,\cdot\,;b)$ is a non-increasing function (see also Lemma 5), so
that

$L_{ij}(x;b)\leq L_{ij}(0;b)\equiv{\mathbb{E}}_{j}[\sigma_{i}(b)],\quad
x\in[0,b].\\\ $ (59)

To provide explicit lower bounds on the function $L_{ij}(x;b)$, as well as to
bound ${\mathbb{E}}_{j}[\sigma_{j}(b)]$, we introduce the following
quantities:

$\displaystyle\begin{split}B_{j}&\equiv{\mathbb{E}}_{j}\Big{[}\left((\ell_{j})^{+}\right)^{2}\Big{]}/I_{j}^{2},\\\
\omega_{ij}&\equiv\sup_{t\geq
0}{\mathbb{E}}_{j}\left[\ell_{i}(1)-t\,|\,\ell_{i}(1)\geq t\right],\\\
\tilde{\omega}_{ij}&\equiv-\inf_{t\leq
0}{\mathbb{E}}_{j}\left[\ell_{i}(1)-t\,|\,\ell_{i}(1)-t\leq
0\right].\end{split}$ (60)

The quantity $B_{j}$ is Lorden’s upper bound on the excess over a positive
threshold of the random walk $Z_{j}$ under ${\mathbb{P}}_{j}$ [45]. In
particular, we have

${\mathbb{E}}_{j}[\sigma_{j}(b)]\leq\frac{b}{I_{j}}+B_{j}.$ (61)

The quantity $\omega_{ij}$ is a bound for the expected overshoot of the random
walk $Z_{i}$ under ${\mathbb{P}}_{j}$ above a non-negative threshold, and it
is finite when $\psi_{ij}$ has a positive root (see [46]). Similarly,
$\tilde{\omega}_{ij}$ is a bound on the expected undershoot $\omega_{ij}$ of
the random walk $Z_{i}$ above a non-positive threshold under
${\mathbb{P}}_{j}$, and it is finite when $\psi_{ij}$ is finite on an open
interval containing zero.

######  Lemma 2.

  * (i)

If $I_{j}<I_{ji}$ and $\psi_{ij}$ has a positive root $r_{ij}$, then

$L_{ij}(x;b)\geq\l_{ij}(x;b),\quad\text{ for all }x\in[0,b],$

where

$\displaystyle\begin{split}l_{ij}(x;b)&\equiv\frac{x-e^{-r_{ij}(b-x)}(b+\omega_{ij})}{I_{ji}-I_{j}}\\\
&+(1-e^{-r_{ij}(b-x)})\;L_{ij}(0;b).\end{split}$ (62)

  * (ii)

If ${I_{ji}=I_{j}}$ and $\psi_{ij}$ is finite on an interval containing zero,
then

$L_{ij}(x\,;\,b)\geq u_{ij}(x\,;\,b),$ (63)

where

$\displaystyle
u_{ij}(x;b)\equiv\frac{b-x}{b+\omega_{ij}+\tilde{\omega}_{ij}}\times\left(\frac{xb}{{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]}+L_{ij}(0;b)\right).$
(64)

###### Proof:

We denote by ${(T_{i}(x),\delta_{i}(x))}$ the stopping time and decision of
the sequential probability ratio test (SPRT) of $g_{i}$ vs $f$ with boundaries
zero and $b$ when the corresponding statistic is initialized from
${x\in[0,b]}$, i.e.,

$\displaystyle T_{i}(x)$
$\displaystyle=\inf\\{n\in\mathbb{N}:Z_{i}(n)\notin(-x,b-x)\\}$
$\displaystyle\delta_{i}(x)$ $\displaystyle=\begin{cases}0,\quad\text{if}\quad
Z_{i}(T_{i}(x))\leq-x\\\ 1,\quad\text{if}\quad Z_{i}(T_{i}(x))\geq b-x,\\\
\end{cases}$

and we set

$p(x)\equiv{\mathbb{P}}_{j}(\delta_{i}(x)=1).$

After initializing the CuSum from $x$, the CuSum statistic is equivalent to an
SPRT with stopping boundaries being the positive threshold and zero. If the
CuSum statistic crosses the positive threshold, the process terminates,
whereas if it reaches zero, the process “restarts”, and as a result [47,
Section 5.2.2.1] we have:

$L_{ij}(x;b)={\mathbb{E}}_{j}\big{[}T_{i}(x)\big{]}+(1-p(x))L_{ij}(0;b),\quad
x\in[0,b].$ (65)

We now prove parts (i) and (ii) separately, in each case providing first an
upper bound on $p(x)$ and then a lower bound on ${\mathbb{E}}_{j}[T_{i}(x)].$

Proof of (i) This proof is similar to parts of the proof of [31, Theorem 2].
Since

$\left\\{\exp\left[r_{ij}\,Z_{i}(n)\right],n\in\mathbb{N}\right\\}$

is a non-negative ${\mathbb{P}}_{j}$-martingale with expectation $1$, by the
definition of $p(x)$ and Ville’s supermartingale inequality we have

$p(x)\leq{\mathbb{P}}_{j}\left(\sup_{n\geq 1}Z_{i}(n)>b-x\right)\leq
e^{-r_{ij}(b-x)}.$ (66)

Comparing with the desired inequality, it is enough to show that

${\mathbb{E}}_{j}[T_{i}(x)]\geq\frac{x-p(x)(b+\omega_{ij})}{I_{ji}-I_{j}},\quad\forall
x\in[0,b].$ (67)

This can be shown by modifying the proof of the upper bound for
${\mathbb{E}}_{j}\big{[}Z_{i}(T_{i}(x))\big{]}$ in [39, Section 3.1.2] in view
of the fact that ${\mathbb{E}}_{j}[\ell_{i}(1)]=I_{j}-I_{ji}<0.$

Proof of (ii) Since ${\mathbb{E}}_{j}[\ell_{i}(1)]=0$ and
${\mathbb{E}}_{j}[T_{i}(x)]<\infty$, by Wald’s identity and the law of total
probability we have

$\displaystyle\begin{split}0&={\mathbb{E}}_{j}[Z_{i}(T_{i}(x))]\\\
&={\mathbb{E}}_{j}[Z_{i}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\geq b-x]\;p(x)\\\
&\quad+{\mathbb{E}}_{j}[Z_{i}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\leq-x]\;(1-p(x)).\end{split}$
(68)

By the definition of conditional expectation,

$\displaystyle\begin{split}{\mathbb{E}}_{j}[Z_{i}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\geq
b-x]&\geq b-x\\\
{\mathbb{E}}_{j}[Z_{i}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\leq-x]&\leq-x.\end{split}$
(69)

By the definitions of $\omega_{ij}$ and $\tilde{\omega}_{ij}$ given in (60) we
also have

$\displaystyle\begin{split}{\mathbb{E}}_{j}[Z_{i}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\geq
b-x]&\leq b-x+\omega_{ij}\\\
{\mathbb{E}}_{j}[Z_{i}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\leq-x]&\geq-(x+\tilde{\omega}_{ij}).\end{split}$
(70)

Solving (68) for $p(x)$ and using (69) and (70), we conclude that

$p(x)\geq\frac{x}{b+\omega_{ij}+\tilde{\omega}}_{ij}.$ (71)

By solving (68) for $1-p(x)$, we can use (69) and (70) to show that

$1-p(x)\geq\frac{b-x}{b+\omega_{ij}+\tilde{\omega}_{ij}}.$ (72)

Combining (72) with (65) we have

$L_{ij}(x;b)\geq{\mathbb{E}}_{j}[T_{i}(x)]+\frac{b-x}{b+\omega_{ij}+\tilde{\omega}_{ij}}\,L_{ij}(0;b).$
(73)

It remains to lower bound ${\mathbb{E}}_{j}[T_{i}(x)]$. Since, by assumption,
${\mathbb{E}}_{j}[\ell_{i}^{2}(1)]$ is finite, by Wald’s identity for the
second moment we obtain

$\displaystyle\begin{split}&{\mathbb{E}}_{j}[T_{i}(x)]=\frac{{\mathbb{E}}_{j}[Z_{i}^{2}(T_{i}(x))]}{{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]}\\\
&=\frac{{\mathbb{E}}_{j}[Z_{i}^{2}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\geq
b-x]\,p(x)}{{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]}\\\
&\quad+\frac{{\mathbb{E}}_{j}[Z_{i}^{2}(T_{i}(x))\,|\,Z_{i}(T_{i}(x))\leq-x]\,(1-p(x))}{{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]}\\\
&\geq\frac{(b-x)^{2}\,p(x)+x^{2}\,(1-p(x))}{{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]},\end{split}$
(74)

where for the inequality we use (69). Combining (74) with (71)–(72), we obtain
the desired inequality. ∎

By direct calculation, we can obtain the following bounds on the derivatives
of $u_{ij}$ and $l_{ij}$, will will be useful later.

######  Lemma 3.

  * •

If $I_{j}<I_{ji}$ and $\psi_{ij}(\theta)$ has positive root $r_{ij}$, then

$\displaystyle 0<-l^{\prime}_{ij}(x;b)$ $\displaystyle\leq
r_{ij}e^{-r_{ij}(b-x)}\left(\frac{b+\omega_{ij}}{I_{ji}-I_{j}}+L_{ij}(0;b)\right).$

  * •

If $I_{j}=I_{ij}$ and $\psi_{ij}$ is finite on an open interval containing
zero, then

$\displaystyle-u_{ij}^{\prime}(x\,;\,b)$
$\displaystyle=\frac{L_{ij}(0;b)}{b+\omega_{ij}+\tilde{\omega}_{ij}}\,+\,\frac{xb-(b^{2}-xb)}{{\mathbb{E}}_{j}[\ell_{i}(1)^{2}]\,(b+\omega_{ij}+\tilde{\omega}_{ij})}$
$\displaystyle\leq\frac{L_{ij}(0;b)}{b+\omega_{ij}+\tilde{\omega}_{ij}}+\frac{xb}{{\mathbb{E}}_{j}[\ell_{i}(1)^{2}]\,(b+\omega_{ij}+\tilde{\omega}_{ij})}.$

##  Appendix B Proof of Theorem 1

We start with a lemma that shows that when $b$ is large enough, a relevant
conditional probability is non-zero.

######  Lemma 4.

Fix $i,j\in\mathcal{I}$ with $i\neq j.$ Assume either that $I_{ji}>I_{j}$ and
$\psi_{ij}$ has a positive root, or that ${I_{ji}=I_{j}}$ and $\psi_{ij}$ is
finite around zero. Let $\nu$ be such that (40) holds, at least for $b$ large
enough. If $b$ is large enough, then

${\mathbb{P}}_{\nu,j}(\sigma_{i}(b)>\sigma_{j}(b)\,|\,\sigma(b)>\nu)>0.$

###### Proof:

To make the notation lighter, we write $\sigma$ and $\sigma_{i}$ in place of
$\sigma(b)$ and $\sigma_{i}(b)$. We first observe that, by the law of total
probability,

$\displaystyle{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}\,|\,\sigma>\nu)$
$\displaystyle\geq{\mathbb{P}}_{\nu,j}(Y_{i}(\nu)\leq b/2\,|\,\sigma>\nu)\,$
$\displaystyle\quad\times{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}\,|\,Y_{i}(\nu)\leq
b/2,\sigma>\nu),$

so it is enough to show that each of the two terms in the lower bound is non-
zero. Since $Y_{i}(\nu)$ has the same distribution under
${\mathbb{P}}_{\infty}$ as under ${\mathbb{P}}_{\nu,j}$, condition (40)
implies that

${\mathbb{P}}_{\nu,j}(Y_{i}(\nu)\leq b/2\,|\,\sigma>\nu)\geq 1-e^{-b/2}>0.$
(75)

Thus, it remains to show that the second term in the upper bound is also
positive. For this, we apply the law of total expectation and we write

$\displaystyle\begin{split}{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}\,|\,Y_{i}(\nu)\leq
b/2,\sigma>\nu)=\\\
{\mathbb{E}}_{\nu,j}\left[{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}\,|\,\mathcal{F}_{\nu},\sigma>\nu)\,\big{|}\,Y_{i}(\nu)\leq
b/2,\,\sigma>\nu\right].\end{split}$ (76)

When $\sigma>\nu$, the stopping times $\sigma_{i},\sigma_{j}$ depend on
$\mathcal{F}_{\nu}$ only through $Y_{i}(\nu)$ and $Y_{j}(\nu)$, thus we can
write

$\displaystyle\begin{split}{\mathbb{E}}_{\nu,j}\left[{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}\,|\,\mathcal{F}_{\nu},\sigma>\nu)\,\big{|}\,Y_{i}(\nu)\leq
b/2,\,\sigma>\nu\right]\\\
={\mathbb{E}}_{\nu,j}\left[G(Y_{i}(\nu),Y_{j}(\nu))\,\big{|}\,Y_{i}(\nu)\leq
b/2,\,\sigma>\nu\right],\end{split}$ (77)

where $G$ is defined as the function

$\displaystyle G(y_{i},y_{j})$
$\displaystyle\equiv{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}\,|\,Y_{i}(\nu)=y_{i},\,Y_{j}(\nu)=y_{j})$
$\displaystyle={\mathbb{P}}_{j}(\sigma_{i}>\sigma_{j}\,|\,Y_{i}(0)=y_{i},\,Y_{j}(0)=y_{j}),$

where the equality is due to the data being iid after the change. This
function, $G$, is decreasing in $y_{i}$ and increasing in $y_{j}$. Thus, for
all values of $Y_{i}(\nu),Y_{j}(\nu)$ in ${\\{Y_{i}(\nu)\leq
b/2,\,\sigma>\nu\\}}$,

$\displaystyle G(Y_{i}(\nu),Y_{j}(\nu))$ $\displaystyle\geq G(b/2,0).$ (78)

In particular,

$G(b/2,0)={\mathbb{P}}_{j}(\sigma_{i}>\sigma_{j}\,|\,Y_{i}(0)=b/2,\,Y_{j}(0)=0).$
(79)

Combining (76), (77), (78), and (79), and the monotonicity of expectation, it
follows that

$\displaystyle{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}|\,Y_{i}(\nu)\leq
b/2,\sigma>\nu)$
$\displaystyle\geq{\mathbb{P}}_{j}(\sigma_{i}>\sigma_{j}\,|\,Y_{i}(0)=b/2),$

where it is understood that $Y_{j}(0)=0$. Now, we claim that

${\mathbb{P}}_{j}(\sigma_{i}(b)>\sigma_{j}(b)\,|\,Y_{i}(0)=b/2)\geq{\mathbb{P}}_{j}(\sigma_{i}(b/2)>\sigma_{j}(b)).$

Indeed, $\sigma_{i}(b)$ with $Y_{i}(0)=b/2$ is stochastically larger than
$\sigma_{i}(b/2)$ with initialization at zero since, in both cases, the
statistic $Y_{i}$ must increase by $b/2$ to reach the threshold. However, in
the first case, the statistic $Y_{i}$ can decrease below its initialization at
$b/2$, whereas $Y_{i}$ is reflected at its initialization in the second case,
and is therefore pathwise larger.

Thus, it remains to show that

${\mathbb{P}}_{j}(\sigma_{i}(b/2)>\sigma_{j}(b))>0.$

In order to do so, we argue by contradiction and suppose that
$\sigma_{i}(b/2)\leq\sigma_{j}(b)$ with probability one under
${\mathbb{P}}_{j}$. It follows from this assumption and (61) that

${\mathbb{E}}_{j}[\sigma_{i}(b/2)]\leq{\mathbb{E}}_{j}[\sigma_{j}(b)]\leq\frac{b}{I_{j}}+B_{j}.$
(80)

However, by either (56) or (57), depending on whether $I_{ij}$ is greater than
or equal to $I_{j}$, we have that

$\displaystyle\text{ either}\quad{\mathbb{E}}_{j}[\sigma_{i}(b/2)]$
$\displaystyle\geq\exp[r_{ij}b/2]$ $\displaystyle\text{ or
}\quad{\mathbb{E}}_{j}[\sigma_{i}(b/2)]$ $\displaystyle\geq
b^{2}/(4{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]).$

Since these both contradict (80) for sufficiently large $b$, the proof is
complete. ∎

Finally, we prove Theorem 1 using the definitions and lemmas used thus far in
the appendixes.

###### Proof:

We follow the same method as in the proof of [31, Theorem 2]. Without loss of
generality, we assume that $b$ is large enough so that Lemma 4 holds. Indeed,
for smaller $b$, the function $\phi(b)$ can be trivially selected to make the
upper bound greater than one. To lighten the notation, we suppress dependence
on $b$ and simply write $\widehat{\sigma}$, $\sigma$, and $\sigma_{i}$ instead
of $\widehat{\sigma}(b)$, $\sigma(b)$, and $\sigma_{i}(b)$, respectively.

From Lemma 4 and the law of total expectation we obtain:

$\displaystyle\begin{split}&{\mathbb{P}}_{\nu,j}(\sigma_{i}\leq\sigma_{j}\,|\;\sigma>\nu)\\\
&=1-{\mathbb{P}}_{\nu,j}(\sigma_{i}>\sigma_{j}\,|\,\sigma>\nu)\\\
&=1-\frac{{\mathbb{E}}_{\nu,j}[\sigma_{i}-\sigma_{j}\wedge\sigma_{i}\,|\,\sigma>\nu]}{{\mathbb{E}}_{\nu,j}[\sigma_{i}-\sigma_{j}\,|\,\sigma>\nu,\sigma_{i}>\sigma_{j}]}.\end{split}$
(81)

On the event

$\\{\sigma>\nu,\;\sigma_{i}>\sigma_{j}\\}\in\mathcal{F}_{\sigma_{j}}$

we have

$\nu<\sigma\leq\sigma_{j}<\sigma_{i},$

and the difference ${\sigma_{i}-\sigma_{j}}$ is a function of
$Y_{i}(\sigma_{j})$ and ${\\{X_{n},n>\sigma_{j}\\}}$. Recalling the definition
of $L_{ij}$ in (58) we then have

$\displaystyle{\mathbb{E}}_{\nu,j}\left[\sigma_{i}-\sigma_{j}\,|\,\sigma>\nu,\sigma_{i}>\sigma_{j},\mathcal{F}_{\sigma_{j}}\right]$
$\displaystyle=L_{ij}(Y_{i}(\sigma_{j})\,;\,b)\;\cdot\;\mathds{1}(\\{\sigma>\nu,\sigma_{i}>\sigma_{j}\\})$
$\displaystyle\leq L_{ij}(0;b)={\mathbb{E}}_{j}[\sigma_{i}],$

where the inequality holds because $L_{ij}(\,\cdot\,;\,b)$ is a non-increasing
function (note that $Y_{i}(\sigma_{j})<b$ on $\\{\sigma_{i}>\sigma_{j}\\}$),
and the final equality follows by definition. By the law of iterated
expectation and the monotonicity of expectation it then follows that

$\displaystyle{\mathbb{E}}_{\nu,j}$
$\displaystyle\left[\sigma_{i}-\sigma_{j}\,|\,\sigma>\nu,\sigma_{i}>\sigma_{j}\right]\leq{\mathbb{E}}_{j}[\sigma_{i}].$
(82)

Combining (81)–(82), we conclude that:

$\displaystyle{\mathbb{P}}_{\nu,j}(\sigma_{i}\leq\sigma_{j}\,|\,\sigma>\nu)$
$\displaystyle\leq
1-\frac{{\mathbb{E}}_{\nu,j}[\sigma_{i}-\sigma_{j}\wedge\sigma_{i}\,|\,\sigma>\nu]}{{\mathbb{E}}_{j}[\sigma_{i}]},$

and adding and subtracting $\nu$ in the numerator of the fraction in the upper
bound we further have

$\displaystyle\begin{split}{\mathbb{P}}_{\nu,j}(\sigma_{i}\leq\sigma_{j}\,|\,\sigma>\nu)\leq\frac{{\mathbb{E}}_{j}[\sigma_{i}]-{\mathbb{E}}_{\nu,j}[\sigma_{i}-\nu\,|\,\sigma>\nu]}{{\mathbb{E}}_{j}[\sigma_{i}]}\,\\\
+\,\frac{{\mathbb{E}}_{\nu,j}[\sigma_{j}\wedge\sigma_{i}-\nu\,|\,\sigma>\nu]}{{\mathbb{E}}_{j}[\sigma_{i}]}.\end{split}$
(83)

For the first term in the upper bound, we observe that on the event
$\\{\sigma>\nu\\}$ we have $Y_{i}(\nu)<b$ and that $\sigma_{i}-\nu$ is a
positive-valued function of $Y_{i}(\nu)$ and $X_{\nu+1},X_{\nu+2},\ldots$. As
a result,

$\displaystyle\begin{split}&{\mathbb{E}}_{\nu,j}[\sigma_{i}-\nu\,|\,\mathcal{F}_{\nu},\sigma>\nu]\\\
&=L_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\cdot\mathds{1}(\\{\sigma>\nu\\}),\end{split}$ (84)

and by another application of the law of iterated expectation we obtain

$\displaystyle{\mathbb{E}}_{\nu,j}[\sigma_{i}-\nu\,|\,\sigma>\nu]={\mathbb{E}}_{\infty}\left[L_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right],$ (85)

where in the equality we have also used the fact that $Y_{i}(\nu)$ has the
same distribution under ${\mathbb{P}}_{\nu,j}$ and ${\mathbb{P}}_{\infty}$.
For the second second term of (83), we observe that

${\mathbb{E}}_{\nu,j}[\sigma_{j}\wedge\sigma_{i}-\nu\,|\,\sigma>\nu]\leq{\mathbb{E}}_{\nu,j}[\sigma_{j}-\nu\,|\,\sigma>\nu]\leq{\mathbb{E}}_{j}[\sigma_{j}].$

Thus, we conclude that

$\displaystyle\begin{split}&{\mathbb{P}}_{\nu,j}(\sigma_{i}\leq\sigma_{j}\,|\,\sigma>\nu)\\\
&\leq\frac{{\mathbb{E}}_{j}[\sigma_{i}]-{\mathbb{E}}_{\infty}\left[L_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right]}{{\mathbb{E}}_{j}[\sigma_{i}]}+\frac{{\mathbb{E}}_{j}[\sigma_{j}]}{{\mathbb{E}}_{j}[\sigma_{i}]}.\end{split}$
(86)

We bound each of these two terms separately in (i) and (ii).

Proof of part (i) Suppose ${I_{ji}>I_{j}}$, and that $\psi_{ij}$ has a
positive root. We first bound the second term of (86). From (61) and (56) we
obtain

$\frac{{\mathbb{E}}_{j}[\sigma_{j}]}{{\mathbb{E}}_{j}[\sigma_{i}]}\leq
e^{-r_{ij}b}\left(\frac{b}{I_{j}}+B_{j}\right),$ (87)

thus, it remains to upper bound the first term in (86). For this, we recall
the definitions of $L_{ij}$ and $l_{ij}$ in (58) and (62). From Lemma 2 we
then have

$\displaystyle\begin{split}&{\mathbb{E}}_{j}[\sigma_{i}]-{\mathbb{E}}_{\infty}\left[L_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right]\\\ &\leq L_{ij}(0\,;\,b)-l_{ij}(0\,;\,b)\\\
&+{\mathbb{E}}_{\infty}\left[l_{ij}(0\,;\,b)-l_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right].\end{split}$ (88)

From (62) it follows that

$L_{ij}(0\,;\,b)-l_{ij}(0\,;\,b)=e^{-r_{ij}b}\left[\frac{b+\omega_{ij}}{I_{ji}-I_{j}}+L_{ij}(0\,;\,b)\right].$
(89)

To bound the second term in the upper bound in (88), we proceed as follows:

$\displaystyle\begin{split}&{\mathbb{E}}_{\infty}\left[l_{ij}(0\,;\,b)-l_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right]\\\
&={\mathbb{E}}_{\infty}\left[-\int_{0}^{b}l_{ij}^{\prime}(x\,;\,b)\,\mathds{1}(\\{Y_{i}(\nu)\geq
x\\})dx\,\Big{|}\,\sigma>\nu\right]\\\
&=-\int_{0}^{b}l_{ij}^{\prime}(x\,;\,b)\,{\mathbb{P}}_{\infty}(Y_{i}(\nu)\geq
x\,|\,\sigma>\nu)\;dx\\\
&\leq-\int_{0}^{b}l_{ij}^{\prime}(x\,;\,b)\,e^{-x}\;dx\\\
&\leq\left(\frac{b+\omega_{ij}}{I_{ji}-I_{j}}+L_{ij}(0;b)\right)r_{ij}e^{-r_{ij}b}\int_{0}^{b}e^{x(r_{ij}-1)}dx.\end{split}$
(90)

The first equality follows from the Fundamental Theorem of Calculus, the
second by Tonelli’s theorem, the first inequality from the assumption that
(40) holds, and the third one from the bound on $-l^{\prime}_{ij}$ in Lemma 3.
The integral in the upper bound of (90) is upper bounded by

$\begin{cases}b,\quad&\text{if}\quad r_{ij}\leq 1\\\
\frac{1}{r_{ij}-1}e^{-(1-r_{ij})b},\quad&\text{if}\quad r_{ij}>1.\end{cases}$
(91)

In view of this, we distinguish two cases depending on whether $r_{ij}>1$ or
$r_{ij}\leq 1$.

When $r_{ij}>1$, from (88)–(91) it follows that the numerator of the first
term in (86) is upper bounded by

$\displaystyle\left(\frac{b+\omega_{ij}}{I_{ji}-I_{j}}+L_{ij}(0\,;\,b)\right)\cdot\Big{(}e^{-r_{ij}b}+\frac{r_{ij}}{r_{ij}-1}e^{-b}\Big{)}$
(92)

and, as a result, in view of (56), and the fact that
$L_{i}j(0;b)\equiv{\mathbb{E}}_{j}[\sigma_{i}(b)]$, the first term in (86) is
upper bounded by

$\displaystyle\left(e^{-r_{ij}b}\,\frac{b+\omega_{ij}}{I_{ji}-I_{j}}+1\right)\cdot\left(e^{-r_{ij}b}+e^{-b}\frac{r_{ij}}{r_{ij}-1}\right).$
(93)

Combining this with (86) and (87), we conclude that

${\mathbb{P}}_{\nu,j}(\sigma_{i}\leq\sigma_{j}\,|\,\sigma>\nu)\leq
e^{-b}\frac{r_{ij}}{r_{ij}-1}(1+\phi_{ij}(b)),$ (94)

where

$\displaystyle\phi_{ij}(b)$ $\displaystyle\equiv
e^{-b(r_{ij}-1)}\frac{r_{ij}-1}{r_{ij}}\,\left(\frac{b}{I_{j}}+B_{j}+1\right)$
$\displaystyle\quad+\left(\frac{b+\omega_{ij}}{I_{ji}-I_{j}}\right)\left(e^{-r_{ij}b}+\frac{r_{ij}-1}{r_{ij}}e^{-2r_{ij}b+b}\right),$

which is a positive function that goes to zero as $b\to\infty$ and does not
depend on $\nu$.

When $r_{ij}\leq 1$, from (88)–(91) it follows that the numerator of the first
term in (86) is upper bounded by

$\left(\frac{b+\omega_{ij}}{I_{ji}-I_{j}}+L_{ij}(0\,;\,b)\right)\,e^{-r_{ij}b}\,\Big{(}r_{ij}b+1\Big{)}$

and, as a result, in view of (56), the first term in (86) is upper bounded by

$\left(e^{-r_{ij}b}\,\frac{b+\omega_{ij}}{I_{ji}-I_{j}}+1\right)e^{-r_{ij}b}\,\Big{(}r_{ij}b+1\Big{)}.$

Combining this with (86) and (87), we conclude that

${\mathbb{P}}_{\nu,j}(\sigma_{i}\leq\sigma_{j}\,|\,\sigma>\nu)\leq\\\
b\,e^{-r_{ij}b}\left(r_{ij}+\frac{1}{I_{j}}\right)\,(1+\zeta_{ij}(b)),$

where $\zeta_{ij}(b)$ is a positive function that goes to zero as $b\to\infty$
which does not depend on $\nu.$

Proof of part (ii) We now assume that ${\mathbb{E}}_{j}[\ell_{i}(1)]=0$ and
that $\psi_{ij}$ is finite around 0. As before, we bound each term in the
upper bound of (86). For the second, from (57) and (61) we obtain

$\begin{split}\frac{{\mathbb{E}}_{j}[\sigma_{j}]}{{\mathbb{E}}_{j}[\sigma_{i}]}&\leq\frac{{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]}{b^{2}}\,\left(\frac{b}{I_{j}}+B_{j}\right).\end{split}$
(95)

For the first one, we recall the definition of $u_{ij}$ from (64). Then, from
Lemma 2 it follows that

$\displaystyle\begin{split}&{\mathbb{E}}_{j}[\sigma_{i}]-{\mathbb{E}}_{\infty}\left[L_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right]\\\ &\leq L_{ij}(0\,;\,b)-u_{ij}(0\,;\,b)\\\
&\quad+{\mathbb{E}}_{\infty}\left[u_{ij}(0\,;\,b)-u_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right].\end{split}$ (96)

By (64) we have:

$L_{ij}(0\,;\,b)-u_{ij}(0\,;\,b)=L_{ij}(0\,;\,b)\,\frac{\omega_{ij}+\tilde{\omega}_{ij}}{b+\omega_{ij}+\tilde{\omega}_{ij}}.$
(97)

Moreover, we can upper bound the second term in (96) as follows:

$\displaystyle\begin{split}&{\mathbb{E}}_{\infty}\left[u_{ij}(0\,;\,b)-u_{ij}(Y_{i}(\nu)\wedge
b\,;\,b)\,|\,\sigma>\nu\right]\\\
&={\mathbb{E}}_{\infty}\left[\int_{0}^{b}-u^{\prime}_{ij}(x\,;\,b)\mathds{1}(\\{Y_{i}(\nu)\geq
x\\})dx\,\big{|}\,\sigma>\nu\right]\\\
&=\int_{0}^{b}-u^{\prime}_{ij}(x\,;\,b)\,{\mathbb{P}}_{\infty}(Y_{i}(\nu)\geq
x\,\big{|}\,\sigma>\nu)dx\\\
&\leq\int_{0}^{b}-u^{\prime}_{ij}(x\,;\,b)\,e^{-x}\;dx\\\
&\leq\frac{L_{ij}(0;b)}{b+\omega_{ij}+\tilde{\omega}_{ij}}+\frac{b}{{\mathbb{E}}_{j}[\ell_{i}(1)^{2}]\,(b+\omega_{ij}+\tilde{\omega}_{ij})}.\end{split}$
(98)

The first equality follows by the Fundamental Theorem of Calculus and the
second by Tonelli’s theorem. The first inequality follows by the assumption
that (40) holds, and the second by the upper bound on $-u^{\prime}_{ij}$ in
Lemma 3. From (96)–(98) and (57) , and the fact that
$L_{ij}(0;b)\equiv{\mathbb{E}}_{j}[\sigma_{i}]$, it then follows that the
first term in (86) is upper bounded by

$\displaystyle\frac{\omega_{ij}+\tilde{\omega}_{ij}}{b+\omega_{ij}+\tilde{\omega}_{ij}}+\frac{1}{b(b+\omega_{ij}+\tilde{\omega}_{ij})}$
$\displaystyle\leq\frac{(1+\omega_{ij}+\tilde{\omega}_{ij})}{b}+\frac{1}{b^{2}},$

where the last inequality follows from the fact that $\omega_{ij}$ and
$\tilde{\omega}_{ij}$ are non-negative. Combining this with (86) and (95), we
arrive at

$\displaystyle{\mathbb{P}}_{\nu,j}(\sigma_{i}\leq\sigma_{j}\,|\,\sigma>\nu)$
$\displaystyle\leq\widetilde{C}\,b^{-1}\,\left(1+\xi_{ij}(b)\right),$

where

$\displaystyle\widetilde{C}$ $\displaystyle\equiv
1+\omega_{ij}+\tilde{\omega}_{ij}+\frac{{\mathbb{E}}_{j}[\ell_{i}(1)^{2}]}{I_{j}}$
$\displaystyle\xi_{ij}(b)$
$\displaystyle\equiv\left(B_{j}\,{\mathbb{E}}_{j}[\ell_{i}^{2}(1)]+1\right)/(\widetilde{C}\,b).$

The latter is a positive function that goes to zero as $b\to\infty$ and does
not depend on $\nu$, so this completes the proof. ∎

##  Appendix C Stochastic Monotonicity of the CuSum

######  Lemma 5.

For all $i\in\mathcal{I}$, the CuSum process ${\\{Y_{i}(n),n\in\mathbb{N}\\}}$
is a non-negative stochastically monotone Markov process under
${\mathbb{P}}_{\infty}.$

###### Proof:

Specifically, we show that

${{\mathbb{P}}_{\infty}(Y_{i}(1)\geq y\,|\,Y_{i}(0)=x)}$

is non-decreasing and right-continuous in $x$ for all $y\geq 0$.

By the definition of the CuSum statistic,

${\mathbb{P}}_{\infty}(Y_{i}(1)\geq
y\,|\,Y_{i}(0)=x)={\mathbb{P}}_{\infty}((\ell_{i}(1)+x)^{+}\geq y).$ (99)

For $y=0$,

${\mathbb{P}}_{\infty}((\ell_{i}(1)+x)^{+}\geq y)=1\,\quad\text{ for all }x.$
(100)

On the other hand, for $y>0,$

${\mathbb{P}}_{\infty}((\ell_{i}(1)+x)^{+}\geq
y)={\mathbb{P}}_{\infty}(\ell_{i}(1)\geq y-x),$ (101)

which is non-decreasing in $x$ for all $y>0$.

Let $\epsilon>0$ and fix $x\geq 0$ and $y>0$. (When $y=0$, the probability is
constant with respect to $x$.) We show right-continuity:

$\displaystyle{\mathbb{P}}_{\infty}(Y_{i}(1)\geq
y\,|\,Y_{i}(0)=x+\epsilon)-{\mathbb{P}}_{\infty}(Y_{i}(1)\geq
y\,|\,Y_{i}(0)=x)$ $\displaystyle={\mathbb{P}}_{\infty}(\ell_{i}(1)\geq
y-(x+\epsilon))-{\mathbb{P}}_{\infty}(\ell_{i}(1)\geq y-x)$
$\displaystyle={\mathbb{P}}_{\infty}((y-x)-\epsilon\leq\ell_{i}(1)<(y-x)),$

but

${\mathbb{P}}_{\infty}((y-x)-\epsilon\leq\ell_{i}(1)<(y-x))\to 0\text{ as
}\epsilon\to 0.$

∎

## References

  * [1] A. Warner and G. Fellouris, “Cusum for sequential change diagnosis,” in _2022 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2022, pp. 486–491.
  * [2] W. A. Shewhart, _Economic control of quality of manufactured product_. Macmillan And Co Ltd, London, 1931.
  * [3] E. S. Page, “Continuous inspection schemes,” _Biometrika_ , vol. 41, no. 1/2, pp. 100–115, 1954.
  * [4] A. Bissell, “Cusum techniques for quality control,” _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , vol. 18, no. 1, pp. 1–25, 1969.
  * [5] D. M. Hawkins, P. Qiu, and C. W. Kang, “The changepoint model for statistical process control,” _Journal of quality technology_ , vol. 35, no. 4, pp. 355–366, 2003.
  * [6] S. Joe Qin, “Statistical process monitoring: basics and beyond,” _Journal of Chemometrics: A Journal of the Chemometrics Society_ , vol. 17, no. 8-9, pp. 480–502, 2003.
  * [7] J. Ru, V. P. Jilkov, X. R. Li, and A. Bashi, “Detection of target maneuver onset,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 45, no. 2, pp. 536–554, 2009.
  * [8] S. S. Blackman, “Multiple hypothesis tracking for multiple target tracking,” _IEEE Aerospace and Electronic Systems Magazine_ , vol. 19, no. 1, pp. 5–18, 2004.
  * [9] I. Nikiforov, V. Varavva, and V. Kireichikov, “Application of statistical fault detection algorithms to navigation systems monitoring,” _Automatica_ , vol. 29, no. 5, pp. 1275–1290, 1993.
  * [10] B. Bakhache and I. Nikiforov, “Reliable detection of faults in navigation systems,” in _Proceedings of the 38th IEEE Conference on Decision and Control_ , vol. 5. IEEE, 1999, pp. 4976–4981.
  * [11] A. G. Tartakovsky, X. R. Li, and G. Yaralov, “Sequential detection of targets in multichannel systems,” _IEEE Transactions on Information Theory_ , vol. 49, no. 2, pp. 425–445, 2003.
  * [12] A. G. Tartakovsky, B. L. Rozovskii, R. B. Blažek, and H. Kim, “Detection of intrusions in information systems by sequential change-point methods,” _Statistical Methodology_ , vol. 3, no. 3, pp. 252–293, 2006.
  * [13] A. G. Tartakovsky, B. L. Rozovskii, R. B. Blazek, and H. Kim, “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_ , vol. 54, no. 9, pp. 3372–3382, 2006.
  * [14] H. Rolka, H. Burkom, G. F. Cooper, M. Kulldorff, D. Madigan, and W.-K. Wong, “Issues in applied statistics for public health bioterrorism surveillance using multiple data streams: research needs,” _Statistics in Medicine_ , vol. 26, no. 8, pp. 1834–1856, 2007.
  * [15] S. E. Fienberg and G. Shmueli, “Statistical issues and challenges associated with rapid detection of bio-terrorist attacks,” _Statistics in Medicine_ , vol. 24, no. 4, pp. 513–529, 2005.
  * [16] D. Siegmund, “Change-points: from sequential detection to biology and back,” _Sequential Analysis_ , vol. 32, no. 1, pp. 2–14, 2013.
  * [17] G. Lorden _et al._ , “Procedures for reacting to a change in distribution,” _The Annals of Mathematical Statistics_ , vol. 42, no. 6, pp. 1897–1908, 1971.
  * [18] G. V. Moustakides _et al._ , “Optimal stopping times for detecting changes in distributions,” _The Annals of Statistics_ , vol. 14, no. 4, pp. 1379–1387, 1986.
  * [19] G. A. Barnard, “Control charts and stochastic processes,” _Journal of the Royal Statistical Society: Series B (Methodological)_ , vol. 21, no. 2, pp. 239–257, 1959.
  * [20] R. A. Khan, “On cumulative sum procedures and the sprt with applications,” _Journal of the Royal Statistical Society: Series B (Methodological)_ , vol. 46, no. 1, pp. 79–85, 1984.
  * [21] V. Dragalin, “The design and analysis of 2-cusum procedure,” _Communications in Statistics-Simulation and Computation_ , vol. 26, no. 1, pp. 67–81, 1997.
  * [22] O. Hadjiliadis and V. Moustakides, “Optimal and asymptotically optimal cusum rules for change point detection in the brownian motion model with multiple alternatives,” _Theory of Probability & Its Applications_, vol. 50, no. 1, pp. 75–85, 2006.
  * [23] G. Fellouris and G. Sokolov, “Second-order asymptotic optimality in multisensor sequential change detection,” _IEEE Transactions on Information Theory_ , vol. 62, no. 6, pp. 3662–3675, 2016.
  * [24] A. G. Tartakovsky, “Asymptotic performance of a multichart cusum test under false alarm probability constraint,” in _Proceedings of the 44th IEEE Conference on Decision and Control_. IEEE, 2005, pp. 320–325.
  * [25] A. G. Tartakovsky and V. V. Veeravalli, “Asymptotically optimal quickest change detection in distributed sensor systems,” _Sequential Analysis_ , vol. 27, no. 4, pp. 441–475, 2008.
  * [26] O. Hadjiliadis, H. Zhang, and H. V. Poor, “One shot schemes for decentralized quickest change detection,” _IEEE Transactions on Information Theory_ , vol. 55, no. 7, pp. 3346–3359, 2009.
  * [27] I. V. Nikiforov, “A generalized change detection problem,” _IEEE Transactions on Information theory_ , vol. 41, no. 1, pp. 171–187, 1995.
  * [28] T. L. Lai, “Sequential multiple hypothesis testing and efficient fault detection-isolation in stochastic systems,” _IEEE Transactions on Information Theory_ , vol. 46, no. 2, pp. 595–608, 2000.
  * [29] T. Oskiper and H. V. Poor, “Online activity detection in a multiuser environment using the matrix cusum algorithm,” _IEEE Transactions on Information Theory_ , vol. 48, no. 2, pp. 477–493, 2002.
  * [30] A. Warner and G. Fellouris, “Sequential change diagnosis revisited and the adaptive matrix cusum,” _Bernoulli_ , In Press.
  * [31] I. V. Nikiforov, “A simple recursive algorithm for diagnosis of abrupt changes in random signals,” _IEEE Transactions on Information Theory_ , vol. 46, no. 7, pp. 2740–2746, 2000.
  * [32] A. G. Tartakovsky, “An asymptotic theory of joint sequential changepoint detection and identification for general stochastic models,” _IEEE Transactions on Information Theory_ , 2021.
  * [33] S. M. Pergamenchtchikov, A. G. Tartakovsky, and V. S. Spivak, “Minimax and pointwise sequential changepoint detection and identification for general stochastic models,” _Journal of Multivariate Analysis_ , vol. 190, p. 104977, 2022.
  * [34] Y. C. Chen, T. Banerjee, A. D. Dominguez-Garcia, and V. V. Veeravalli, “Quickest line outage detection and identification,” _IEEE Transactions on Power Systems_ , vol. 31, no. 1, pp. 749–758, 2015.
  * [35] Y. Wang, Q. Liu, E. Mihankhah, C. Lv, and D. Wang, “Detection and isolation of sensor attacks for autonomous vehicles: Framework, algorithms, and validation,” _IEEE Transactions on Intelligent Transportation Systems_ , 2021\.
  * [36] X. Yang, N. Chen, and C. Zhai, “A control chart approach to power system line outage detection under transient dynamics,” _IEEE Transactions on Power Systems_ , vol. 36, no. 1, pp. 127–135, 2020.
  * [37] D. Han and F. Tsung, “Detection and diagnosis of unknown abrupt changes using cusum multi-chart schemes,” _Sequential Analysis_ , vol. 26, no. 3, pp. 225–249, 2007.
  * [38] R. A. Khan, “A note on page’s two-sided cumulative sum procedure,” _Biometrika_ , vol. 68, no. 3, pp. 717–719, 1981.
  * [39] A. Tartakovsky, I. Nikiforov, and M. Basseville, _Sequential analysis: Hypothesis testing and changepoint detection_. CRC Press, 2014.
  * [40] Y. Mei, “Efficient scalable schemes for monitoring a large number of data streams,” _Biometrika_ , vol. 97, no. 2, pp. 419–433, 2010.
  * [41] Y. Xie and D. Siegmund, “Sequential multi-sensor change-point detection,” in _2013 Information Theory and Applications Workshop (ITA)_. IEEE, 2013, pp. 1–20.
  * [42] A. G. Tartakovsky and V. V. Veeravalli, “An efficient sequential procedure for detecting changes in multichannel and distributed systems,” in _Proceedings of the Fifth International Conference on Information Fusion. FUSION 2002._ , vol. 1. IEEE, 2002, pp. 41–48.
  * [43] M. Pollak and D. Siegmund, “Convergence of quasi-stationary to stationary distributions for stochastically monotone markov processes,” _Journal of Applied Probability_ , vol. 23, no. 1, pp. 215–220, 1986.
  * [44] S. Banerjee and G. Fellouris, “Decentralized sequential change detection with ordered cusums,” in _2016 IEEE International Symposium on Information Theory (ISIT)_ , 2016, pp. 36–40.
  * [45] G. Lorden, “On excess over the boundary,” _The Annals of Mathematical Statistics_ , vol. 41, no. 2, pp. 520–527, 1970.
  * [46] M. C. Bryson, “Heavy-tailed distributions: properties and tests,” _Technometrics_ , vol. 16, no. 1, pp. 61–68, 1974.
  * [47] M. Basseville, I. V. Nikiforov _et al._ , _Detection of abrupt changes: theory and application_. Prentice Hall Englewood Cliffs, 1993, vol. 104.