# Quickest Anomaly Detection in Sensor Networks With Unlabeled Samples

Zhongchang Sun Shaofeng Zou  This paper was presented in part at the 2021 IEEE
International Symposium on Information Theory [1].Zhongchang Sun and Shaofeng
Zou are with the Department of Electrical Engineering, University at Buffalo,
Buffalo, NY 14228 USA (e-mail<EMAIL_ADDRESS>szou3@buffalo.edu).

###### Abstract

The problem of quickest anomaly detection in networks with unlabeled samples
is studied. At some unknown time, an anomaly emerges in the network and
changes the data-generating distribution of some unknown sensor. The data
vector received by the fusion center at each time step undergoes some unknown
and arbitrary permutation of its entries (unlabeled samples). The goal of the
fusion center is to detect the anomaly with minimal detection delay subject to
false alarm constraints. With unlabeled samples, existing approaches that
combines local cumulative sum (CuSum) statistics cannot be used anymore.
Several major questions include whether detection is still possible without
the label information, if so, what is the fundamental limit and how to achieve
that. Two cases with static and dynamic anomaly are investigated, where the
sensor affected by the anomaly may or may not change with time. For the two
cases, practical algorithms based on the ideas of mixture likelihood ratio
and/or maximum likelihood estimate are constructed. Their average detection
delays and false alarm rates are theoretically characterized. Universal lower
bounds on the average detection delay for a given false alarm rate are also
derived, which further demonstrate the asymptotic optimality of the two
algorithms.

###### Index Terms:

Quickest change detection, unlabeled samples, permuted samples, asymptotically
optimal, fundamental limits.

##  I Introduction

In large-scale sensor networks, samples may lack of label information such as
identity due to, e.g., malicious attacks and limited communication resources.
For example, wireless ad-hoc sensor networks are usually vulnerable to
spoofing attacks [2], and samples received by the fusion center may then lose
their label information. Furthermore, in large-scale Internet-of-things (IoT)
networks, where devices are commonly small and low-cost sensing devices
powered by battery with limited communication bandwidth, and are usually
deployed in a massive scale, the communication overhead of identifying
individual sensors increases drastically as the number of sensors grows [3].
However, these battery-powered IoT devices are usually expected to survive for
years without battery change. In this case, message delivered to the fusion
center may be constrained not to contain the identity information. For the
same reason, the data transmitted to the fusion center is usually quantized to
be in a finite alphabet. Furthermore, in social sensing applications,
participants may choose to be anonymous in order to protect privacy, i.e.,
sharing the data without including identity information. Motivated by these
applications, there is a recent surge of interest in the problem of signal
processing with unlabeled data (see e.g., [4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15, 16, 17]), which refers to various signal processing problems where the
data vector undergoes an unknown permutation of its entries, and the original
position of each datum in the vector is unknown.

In this paper, we investigate the problem of quickest anomaly detection in
sensor networks with unlabeled samples. Specifically, at some unknown time, an
anomaly emerges in the network and leads to a change in the data-generating
distribution of some unknown sensor. The fusion center sequentially receives
unlabeled (arbitrarily permuted) samples from all the sensors at each time
step. The goal of the fusion center is to detect the anomaly as quickly as
possible, subject to false alarm constraints. This problem is of particular
relevance to applications where an anomaly affects some sensor in the network,
and the affected sensor may change over time [18], e.g., surveillance system,
intrusion detection, environmental change (air/water quality) detection, rumor
detection, and seismic wave detection.

###  I-A Contributions and Major Challenges

The first part of this paper focuses on the static anomaly, where the sensor
affected by the anomaly does not change with time, but which sensor is
affected is still unknown. We consider the detection delay under the worst-
case affected sensor. The goal here is to minimize the detection delay subject
to false alarm constraints. The major challenges here are two-fold. First of
all, the labels of the samples are unknown, and is time-varying. Second, even
if the labels are known, i.e., each sample is associated with its sensor, the
sensor the anomaly affects is still unknown. For this problem, we construct a
generalized mixture CuSum (GM-CuSum) algorithm. The basic idea is to estimate
the unknown identity of the affected sensor using the maximum likelihood
estimate (MLE), and further employ a mixture likelihood w.r.t. all possible
labels. We prove that the GM-CuSum is second-order asymptotically optimal.

The second part of this paper focuses on a general and more challenging
setting with dynamic anomaly, where the sensor affected by the anomaly changes
with time. Here, we refer to the sequence of sensors affected by the anomaly
over time as the trajectory of the anomaly. We consider the detection delay
under the worst-case trajectory. Compared to the static setting, the
additional challenge is that the affected sensor changes with time, and thus
the change is not persistent at any particular sensor. Therefore, estimating
the identity of the affected sensor over time is not applicable. We then
propose a Bayesian approach to address the challenge raised by the unknown
trajectory of the anomaly, and find the optimal weight to construct a weighted
mixture CuSum algorithm. We prove that the weighted mixture CuSum algorithm is
first-order asymptotically optimal.

We also conduct extensive numerical results to demonstrate the performance of
our proposed algorithms. The numerical results show that for the static
setting, our GM-CuSum algorithm outperforms a heuristic Bayesian mixture CuSum
algorithm; the optimal weighted mixture CuSum algorithm also performs well for
the static setting; and for the dynamic setting, our optimal weighted mixture
CuSum algorithm outperforms an arbitrarily weighted one and the GM-CuSum
algorithm. These numerical results validate our theoretical optimality
results.

###  I-B Related Work

The quickest change detection (QCD) problem in sensor networks with labeled
samples was extensively studied in the literature, e.g., [19, 20, 21, 22, 23,
24, 25, 26, 27, 28, 29, 30, 31] where the fusion center knows the identity of
each sample, i.e., knows which sensor that each sample is from. Therefore, one
CuSum algorithm can be implemented at each sensor and then be combined to make
the decision. This type of algorithms were shown to be asymptotically optimal
for various settings. In this paper, we investigate the setting with unlabeled
samples, where at each time step samples are arbitrarily permuted, and the
permutation is time-varying. The fusion center does not know which sensor each
sample comes from, and then cannot implement a CuSum algorithm for each
sensor.

Various learning and inference problems with unlabeled data has been studied
in the literature [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], which
mainly focus on the offline setting with non-sequential data. Here we only
review several closely related ones on detection problems. In [6], hypothesis
testing with unlabeled samples are studied, where two practical algorithms,
the unlabeled log-likelihood ratio test and the generalized likelihood ratio
test are proposed. A more specific problem is studied in [7] where samples
follow Bernoulli distribution and an approximated log-likelihood test based on
the central limit theorem was proposed. In [4], the binary hypothesis testing
problem with unlabeled samples was studied, and an optimal mixture likelihood
ratio test (MLRT) was developed. In [5], the bandwidth-constrained QCD problem
with unlabeled samples was investigated, where each sensor sends 1-bit
quantized feedback to the fusion center. In [17], the QCD problem with
unlabeled samples was studied where the change affects all the sensors
simultaneously. In this paper, we investigate a more practical scenario where
an anomaly may not affect all the sensors, which is of particular interest in
the distributed setting, and the anomaly may also be dynamic, and affect
different sensors at different times, e.g., a moving target in surveillance
system.

Existing studies of quickly detecting a dynamic change mostly focus on the
labeled setting, e.g., [27, 32, 33]. Our problem is similar to the one in [33]
but we focus on unlabeled samples. Our major technical challenge is due to the
additional ambiguity of unknown labels. The QCD problem with a slowly changing
post-change distribution was studied in [34, 35], whereas in this paper, the
anomaly can move arbitrarily fast.

With unlabeled samples, our problem is also related to the composite QCD
problem with unknown pre- and post-change parameters e.g., [36, 37, 22, 38].
Our work is different from the existing literature. Due to unlabeled samples
and the dynamic nature of the anomaly, the unknown parameter, i.e., the
identify and the label of the affected sensor, is time-varying. Therefore, the
generalized likelihood approach which estimates the unknown parameters using
their MLEs may not perform well. Moreover, unlike studies in [36, 37, 38]
where the distributions are assumed to belong to the exponential family, we do
not have any assumptions on the distributions.

##  II Problem formulation

Consider a network monitored in real time by a set of $n$ heterogeneous
sensors. These sensors can be clustered into $K$ types, and each type $k$ has
$n_{k}$ sensors, $1\leq k\leq K$. The data generating distributions of samples
from type $k$ sensors are denoted by $p_{\theta,k}$, $\theta\in\\{0,1\\}$,
which are known to the fusion center. At some unknown time $\nu$, an anomaly
emerges in the network, and changes the data-generating distributions of the
sensors. If a sensor of type $k$ is affected by the anomaly, then its samples
are generated by $p_{1,k}$, otherwise, by $p_{0,k}$. The goal is to detect the
anomaly as quickly as possible subject to false alarm constraints. We focus on
the case with unlabeled samples, where the data vector at each time step
undergoes an unknown permutation of its entries, and the original position of
each datum in the vector is unknown to the fusion center. In other words, the
fusion center does not know which type of sensors that each sample comes from,
and therefore, does not know the sample’s exact data-generating distribution.

After the anomaly emerges, one sensor of an unknown type is affected by the
anomaly. Based on whether the sensor is affected by the anomaly and the type
of the sensor, we rearrange the sensors into $2K$ groups. The first $K$ groups
consists of sensors that are not affected by the anomaly; and the second $K$
groups consists of sensors that are affected by the anomaly. Specifically, for
sensors in group $1\leq k\leq K$, their samples are generated by $p_{0,k}$,
and for sensors in group $K<k\leq 2K$, their samples samples are generated by
$p_{1,k-K}$.

Denote by $X^{n}[t]=\\{X_{1}[t],\ldots,X_{n}[t]\\}$ the $n$ arbitrarily
permuted samples at time $t$ received by the fusion center. We assume that
$X_{1}[t],\ldots,X_{n}[t]$ are independent, and $X^{n}[{t_{1}}]$ is
independent from $X^{n}[{t_{2}}]$ for any $t_{1}\neq t_{2}$. Note that
$X_{i}[t]$ is not necessarily the sample from sensor $i$ since samples are
permuted/unlabeled.

Let $\mathcal{K}=\\{1,2,\cdots,K\\}$. Denote by
$S[t]\in\mathcal{K}\cup\\{0\\}$ the type of the affected sensor at $t$. For
notational convenience, we use $S[t]=0$ to denote the case when there is no
anomaly, i.e., $t<\nu$. Let $\bm{S}\triangleq\\{S[t]\\}^{\infty}_{t=1}$ denote
the trajectory of the anomaly. Here $\bm{S}$ is unknown to the decision maker.
Even if the trajectory of the anomaly $\bm{S}$ is given, the distribution of
$X^{n}[t]$ still cannot be fully specified due to lack of label information.
To characterize the distribution of $X^{n}[t]$, we define a label function
$\sigma_{t}^{S[t]}:\\{1,\ldots,n\\}\rightarrow\\{1,\ldots,K,S[t]+K\\}$. This
function associates sample $X_{i}[t]$, $1\leq i\leq n$, to group $j$ for some
$j\in\\{1,2,\ldots,K,K+S[t]\\}$, i.e., specifies the probability distribution
of $X_{i}[t]$. Specifically, if $\sigma_{t}^{S[t]}(i)=j$, then

$\displaystyle X_{i}[t]\sim\left\\{\begin{array}[]{ll}p_{0,j},&\text{ if
}1\leq j\leq K,\\\ p_{1,j-K},&\text{ if }K<j\leq 2K.\end{array}\right.$ (3)

Here $\sigma_{t}^{S[t]}$ can be interpreted as the inverse of the permutation
applied to the data vector. We further note that $\sigma_{t}^{S[t]}$ is
unknown to the decision maker, and changes with time.

Let $\Omega_{\bm{S}}=\\{\sigma^{S[1]}_{1},...,\sigma^{S[\infty]}_{\infty}\\}$
be the labels when the trajectory of the anomaly is ${\bm{S}}$, which is
unknown. Let $\mathbb{P}^{{\bm{S}},\nu}_{\Omega_{\bm{S}}}$ and
$\mathbb{E}^{{\bm{S}},\nu}_{\Omega_{\bm{S}}}$ denote the probability measure
and the corresponding expectation when the change point is at $\nu$ and the
samples received by the fusion center is permuted according to the label
$\Omega_{\bm{S}}$ (see Appendix A for more details). We further let
$\mathbb{P}^{\infty}_{\Omega}$ and $\mathbb{E}^{\infty}_{\Omega}$ denote the
probability measure and the corresponding expectation when there is no change,
i.e., $\nu=\infty$, where $\Omega=\Omega_{\bm{S}}$ with $S[t]=0,\forall t\geq
1$.

We extend Lorden’s criterion [39], and define the worst-case average detection
delay (WADD) and the worst-case average running length (WARL) for any stopping
time $\tau$:

$\displaystyle\text{WADD}(\tau)$ $\displaystyle=\sup_{\nu\geq
1}\sup_{\bm{S}}\sup_{\Omega_{\bm{S}}}\text{esssup}\mathbb{E}^{{\bm{S}},\nu}_{\Omega_{\bm{S}}}[(\tau-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]],$
$\displaystyle\text{WARL}(\tau)$
$\displaystyle=\inf_{\Omega}\mathbb{E}^{\infty}_{\Omega}[\tau],$ (4)

where $\mathbf{X}^{n}[t_{1},t_{2}]=\\{X^{n}[t_{1}],\cdots,X^{n}[t_{2}]\\}$,
for any $t_{1}\leq t_{2}$. The goal is to design a stopping rule that
minimizes the WADD subject to a constraint on the WARL:

$\displaystyle\inf_{\tau:\text{WARL}(\tau)\geq\gamma}\text{WADD}(\tau),$ (5)

where $\gamma>0$ is a pre-specified threshold. Here the false alarm constraint
is to guarantee that under all possible sample permutations, the average
running length to a false alarm is always lower bounded by $\gamma$, and
$1/\gamma$ can be interpreted as the false alarm rate.

##  III Static Anomaly

We first investigate the case with static anomaly, i.e., the sensor affected
by the anomaly does not change with time. In this case, for any $t\geq\nu$,
$S[t]=k$ for some unknown type $k$. Then, for all
$j\in\\{1,2,\cdots,K,k+K\\}$, there are $\left(\begin{subarray}{c}n\\\
n_{1},\ldots,n_{k}-1,\ldots,n_{K},1\end{subarray}\right)$ possible
$\sigma_{t}^{k}$ to associate each sample with a data-generating distribution,
and we denote the collection of all possible labels by $\mathcal{S}_{n,{k}}$
(see Appendix A for more details). Before the anomaly emerges, i.e., $t<\nu$,
the samples $X^{n}[t]$ follows the distribution

$\displaystyle\mathbb{P}_{0,\sigma_{t}^{0}}(X^{n}[t])\overset{\Delta}{=}\prod_{i=1}^{n}p_{0,\sigma_{t}^{0}(i)}(X_{i}[t]),$
(6)

for some unknown $\sigma_{t}^{0}\in\mathcal{S}_{n,0}$. At time $t\geq\nu$,
$S[t]=k$, $X^{n}[t]$ follows the distribution

$\displaystyle\mathbb{P}^{k}_{\sigma^{k}_{t}}(X^{n}[t])\overset{\Delta}{=}$
$\displaystyle\prod\limits_{\begin{subarray}{c}i:\sigma_{t}^{k}(i)\leq
K\end{subarray}}p_{0,\sigma^{k}_{t}(i)}(X_{i}[t])\times\prod\limits_{\begin{subarray}{c}i:\sigma_{t}^{k}(i)>K\end{subarray}}p_{1,\sigma^{k}_{t}(i)-K}(X_{i}[t]),$
(7)

for some unknown $\sigma^{k}_{t}\in\mathcal{S}_{n,{k}}$. Let
$\Omega_{k}=\\{\sigma_{1}^{0},\ldots,\sigma_{\nu-1}^{0},\sigma_{\nu}^{k},\ldots,\sigma_{\infty}^{k}\\}$
be the labels over time, when the anomaly emerges at $\nu$ (similarly defined
as $\Omega_{\bm{S}}$). Let $\mathbb{P}^{k,\nu}_{\Omega_{k}}$ denote the
probability measure when the change point is at $\nu$ and the samples are
generated according to (6), (7) and $\Omega_{k}$. We further let
$\mathbb{E}^{k,\nu}_{\Omega_{k}}$ denotes the corresponding expectation.

Then, the WADD for any stopping time $\tau$ can be written as

$\displaystyle\text{WADD}(\tau)=\sup_{\nu\geq
1}\sup_{k}\sup_{\Omega_{k}}\text{esssup}\mathbb{E}^{k,\nu}_{\Omega_{k}}[(\tau-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]].$

The WARL is defined in the same way as in (4).

The goal is to design a stopping rule that minimizes the WADD subject to a
constraint on the WARL:

$\displaystyle\inf_{\tau:\text{WARL}(\tau)\geq\gamma}\text{WADD}(\tau).$ (8)

###  III-A Universal Lower Bound on WADD

We first derive a universal lower bound on WADD for any $\tau$ satisfying the
false alarm constraint:
$\inf_{\Omega}\mathbb{E}^{\infty}_{\Omega}[\tau]\geq\gamma$.

Let $I_{k}=D(\widetilde{\mathbb{P}}_{k}||\widetilde{\mathbb{P}}_{0})$ denote
the Kullback-Leibler (KL) divergence between two mixture distributions
$\widetilde{\mathbb{P}}^{k}=\frac{1}{\mid{\mathcal{S}_{n,k}}\mid}\sum_{\sigma\in{\mathcal{S}_{n,k}}}\mathbb{P}^{k}_{\sigma}$
and
$\widetilde{\mathbb{P}}_{0}=\frac{1}{\mid{\mathcal{S}_{n,0}}\mid}\sum_{\sigma\in{\mathcal{S}_{n,0}}}\mathbb{P}_{0,\sigma}$.
Here, $\widetilde{\mathbb{P}}^{k}$ is the uniform mixture of all possible
distributions when the affected sensor is from group $k$. Let
$I^{*}=\min_{1\leq k\leq K}I_{k}$. We then have the following theorem.

######  Theorem 1.

As $\gamma\rightarrow\infty$,

$\displaystyle\inf_{\tau:\text{WARL}(\tau)\geq\gamma}\text{WADD}(\tau)\geq\frac{\log\gamma}{I^{*}}+O(1).$
(9)

The proof of Theorem 1 can be found in Appendix B. The main challenges in the
proof of Theorem 1 is due to the worst-case over all labels and affected
sensors in WADD and WARL. From Theorem 1, it can be seen that the WADD for
problem (8) is lower bounded by $\frac{\log\gamma}{I^{*}}+O(1)$ for any
stopping rule that satisfy the constraint on WARL. Theorem 1 motivates us to
find the $k$ that minimizes $I_{k}$, i.e., achieves $I^{*}$, and design an
algorithm to achieve this universal lower bound.

###  III-B Generalized Mixture CuSum Algorithm

In this section, we construct an algorithm that achieves the universal lower
bound asymptotically.

A first idea is to use the MLE to estimate the unknown label $\sigma_{t}^{k}$
and the unknown affected sensor $k$. In the static setting, $k$ does not
change with time, however, $\sigma_{t}^{k}$ changes with time, thus a direct
MLE for $\sigma_{t}^{k}$ at each time $t$ may not work well. Therefore, we
take a mixture approach w.r.t. the unknown label, and then take a MLE approach
w.r.t. the unknown affected sensor. Our algorithm is constructed as follows.

Let $W[t]=\max_{k\in\mathcal{K}}\max_{1\leq j\leq
t}\sum^{t}_{i=j}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}[i])}{\widetilde{\mathbb{P}}_{0}(X^{n}[i])}$.
We then define the GM-CuSum stopping time as follows:

$\displaystyle T_{G}=\inf\\{t:W[t]\geq b\\},$ (10)

where $b>0$ is the threshold. Here $W[t]$ can be updated efficiently. We keep
$K$ CuSums in parallel. Note that this can be done recursively. Let
$W_{k}[t]=\max_{1\leq j\leq
t}\sum\limits^{t}_{i=j}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}[i])}{\widetilde{\mathbb{P}}_{0}(X^{n}[i])}$.
The test statistic $W[t]$ has the following recursion:

$\displaystyle
W[t+1]=\max_{k\in\mathcal{K}}\bigg{\\{}(W_{k}[t])^{+}+\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}[t+1])}{\widetilde{\mathbb{P}}_{0}(X^{n}[t+1])}\bigg{\\}},$
(11)

where $W_{k}[0]=0$ for any $k\in\mathcal{K}$. We then take their maximum over
$k$ as $W[t]$.

In the following, we show 1) the WARL lower bound of $T_{G}$ and 2) the WADD
upper bound of $T_{G}$ in the following theorem.

######  Theorem 2.

1) Let $b=\log({K\gamma})$ in (10). Then $\text{WARL}(T_{G})\geq\gamma$; and
2) As $\gamma\rightarrow\infty$,
$\text{WADD}(T_{G})\leq\frac{\log\gamma}{I^{*}}+O(1).$

The proof of Theorem 2 can be found in Appendix C.

The proof of the lower bound on WARL is based on Doob’s submartingale
inequality [40] and the optional sampling theorem [40]. The major challenge
lies in that we consider the worst-case label. A key property we develop and
use in the proof of the WARL lower bound is that under the pre-change
distribution $\mathbb{P}_{0,\sigma_{t}^{0}}$, for any $k\in\mathcal{K}$, the
expectation of the mixture likelihood ratio
$\mathbb{E}_{{0,\sigma^{0}}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
is invariant for different $\sigma^{0}$’s.

Theorem 2 suggests that to meet the WARL constraint, $b$ should be chosen such
that $b=\log{K\gamma}$.

Based on Theorem 1 and Theorem 2, we then establish the second-order
asymptotic optimality of $T_{G}$ in the following theorem.

######  Theorem 3.

$T_{G}$ is second-order asymptotically optimal for the problem in (8).

###### Proof.

By Theorem 1 and Theorem 2, we establish the second-order asymptotic
optimality of $T_{G}$. ∎

##  IV Quickest Dynamic Anomaly Detection

In this section, we consider the general problem with a dynamic anomaly, where
the sensor affected by the anomaly changes with time. The GM-CuSum algorithm
designed for static anomaly may not work well anymore since the sensor
affected by the anomaly changes with time.

###  IV-A Universal Lower Bound on WADD

Define the following weighted mixture distribution:
$\widetilde{\mathbb{P}}^{\bm{\beta}}(X^{n})=\sum_{k=1}^{K}\beta_{k}\widetilde{\mathbb{P}}^{k}(X^{n}),$
where $\bm{\beta}=\\{\beta_{k}\\}_{k=1}^{K}$, $0\leq\beta_{k}\leq 1$ and
$\sum_{k=1}^{K}\beta_{k}=1$. Denote by $I_{\bm{\beta}}$ the KL divergence
between $\widetilde{\mathbb{P}}^{\bm{\beta}}$ and
$\widetilde{\mathbb{P}}_{0}$. Let
$\bm{\beta^{*}}=\mathop{\arg\min}_{\bm{\beta}}I_{\bm{\beta}}$.

For the universal lower bound on WADD, we have the following theorem.

######  Theorem 4.

As $\gamma\rightarrow\infty$, we have that

$\displaystyle\inf_{\tau:\text{WARL}(\tau)\geq\gamma}\text{WADD}(\tau)\geq\frac{\log\gamma}{I_{\bm{\beta^{*}}}}(1+o(1)).$
(12)

The proof of Theorem 4 can be found in Appendix D.

It can be seen from Theorem 4 that the WADD for the problem in (5) is lower
bounded by $\frac{\log\gamma}{I_{\bm{\beta^{*}}}}(1+o(1))$ for large $\gamma$.
This motivates us to apply the optimal weight $\bm{\beta^{*}}$ to design an
algorithm that can achieves the WADD lower bound asymptotically. Moreover, we
have that $I^{*}\geq I_{\bm{\beta^{*}}}$ which implies that a dynamic anomaly
is more difficult to detect than a static anomaly.

###  IV-B Weighted Mixture CuSum

In the static setting, the unknown affected sensor can be estimated by its
MLE. However, in the dynamic setting, the affected sensor changes with time,
and the MLE approach may not work well. Theorem (4) motivates us to tackle the
unknown anomaly trajectory using a Bayesian approach where the probability
that the $k$-th group is affected by the anomaly is $\beta_{k}^{*}$. We then
construct our weighted mixture CuSum algorithm as follows. Define the log of
weighted mixture likelihood ratio using $\bm{\beta^{*}}$:

$\displaystyle\ell_{\bm{\beta^{*}}}(X^{n})=\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}.$
(13)

It can be easily shown that $\ell_{\bm{\beta^{*}}}(X^{n})$ is invariant to any
permutations on $X^{n}$, i.e., for any permutation
$\pi(X^{n})=(X_{\pi(1)},X_{\pi(2)},\ldots,X_{\pi(n)})$,
$\ell_{\bm{\beta^{*}}}(X^{n})=\ell_{\bm{\beta^{*}}}(\pi(X^{n}))$. This is due
to the fact that $\ell_{\bm{\beta^{*}}}(X^{n})$ takes the sum over all
possible group assignments thus is invariant to the actual permutation of
samples.

We then construct the following weighted mixture CuSum algorithm:

$\displaystyle T_{\bm{\beta^{*}}}(b)=\inf\Big{\\{}t:\max\limits_{1\leq j\leq
t+1}\sum_{i=j}^{t}\ell_{\bm{\beta}^{*}}(X^{n}[i])\geq b\Big{\\}}.$ (14)

Let $\widehat{W}[t]=\max\limits_{1\leq j\leq
t+1}\sum_{i=j}^{t}\ell_{\bm{\beta}^{*}}(X^{n}[i])$. The test statistic
$\widehat{W}[t]$ has the following recursion:
$\widehat{W}[t+1]=(\widehat{W}[t])^{+}+\ell_{\bm{\beta}^{*}}(X^{n}[t+1]),\widehat{W}[0]=0.$

Note that different from the way that we handle the unknown and time-varying
label $\sigma$, here, for the unknown type of the affected sensor, we take the
mixture according to $\beta^{*}$ instead of a uniform distribution over
$\mathcal{K}$. As will be shown later both theoretically in Theorem 6 and
numerically in Section V, taking a uniform mixture over $\mathcal{K}$ may not
lead to the optimal performance.

Let $\widetilde{\mathbb{E}}^{k}$ and $\widetilde{\mathbb{E}}_{0}$ denote the
expectation under the probability $\widetilde{\mathbb{P}}^{k}$ and
$\widetilde{\mathbb{P}}_{0}$ respectively. The following property of
$\bm{\beta^{*}}$ plays an important role in developing the asymptotic
optimality of the weighted mixture CuSum algorithm.

######  Lemma 1.

For any $k\in\mathcal{K}$,

$\displaystyle\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}\geq
I_{\bm{\beta^{*}}}.$ (15)

The proof of Lemma 1 can be found in Appendix E.

In the following, we provide a heuristic explanation of how $\widehat{W}[t]$
evolves in the pre- and post-change regimes. We first argue that
$\mathbb{E}^{k}_{\sigma^{k}}[\ell_{\bm{\beta^{*}}}(X^{n})]$ is invariant for
different $\sigma^{k}$’s. Specifically, let $\mathbb{E}^{k}_{\sigma^{k}}$
denote the expectation under $\mathbb{P}^{k}_{\sigma^{k}}$, where a sensor of
type $k$ is affected, and the data received is labeled according to
$\sigma^{k}$. For any $\pi$, let $\hat{\sigma}^{k}=\sigma^{k}\circ\pi$. Then
$\mathbb{E}^{k}_{\sigma^{k}}[\ell_{\bm{\beta^{*}}}(\pi(X^{n}))]=\mathbb{E}^{k}_{\sigma^{k}\circ\pi}[\ell_{\bm{\beta^{*}}}(X^{n})]=\mathbb{E}^{k}_{\hat{\sigma}^{k}}[\ell_{\bm{\beta^{*}}}(X^{n})]$.
For any $\hat{\sigma}^{k}\in{\mathcal{S}_{n,k}}$, a $\pi$ can always be found
so that $\sigma^{k}\circ\pi=\hat{\sigma}^{k}$. Thus, for any
$\sigma^{k},\hat{\sigma}^{k}\in{\mathcal{S}_{n,k}}$,
$\mathbb{E}^{k}_{\hat{\sigma}^{k}}[\ell_{\bm{\beta^{*}}}(X^{n})]=\mathbb{E}^{k}_{\sigma^{k}}[\ell_{\bm{\beta^{*}}}(X^{n})]$.
Therefore, $\mathbb{E}^{k}_{\sigma^{k}}[\ell_{\bm{\beta^{*}}}(X^{n})]$ is
invariant for different $\sigma^{k}$’s. Then, under the pre-change
distribution $\mathbb{P}_{0,\sigma_{t}^{0}}$, the expectation of the weighted
mixture likelihood ratio
$\mathbb{E}_{{0,\sigma_{t}^{0}}}[\ell_{\bm{\beta^{*}}}(X^{n})]$ is invariant
for different $\sigma^{0}_{t}$’s, we have that

$\displaystyle\mathbb{E}_{{0,\sigma_{t}^{0}}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
$\displaystyle=\frac{1}{\mid{\mathcal{S}_{n,0}}\mid}\sum_{\sigma^{0}_{t}\in{\mathcal{S}_{n,0}}}\mathbb{E}_{{0,\sigma_{t}^{0}}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
$\displaystyle=\widetilde{\mathbb{E}}_{0}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
$\displaystyle=-D(\widetilde{\mathbb{P}}_{0}||\widetilde{\mathbb{P}}^{\bm{\beta^{*}}})\leq
0.$ (16)

Therefore, before the change time $\nu$, $\widehat{W}[t]$ has a negative
drift. Similarly, from Lemma 1, after the change time $\nu$, under any group
assignment $\Omega_{\bm{S}}$ and trajectory $\bm{S}$, $\widehat{W}[t]$ has a
positive drift whose expectation is no less than $I_{\bm{\beta^{*}}}$, and
evolves towards $\infty$.

The following theorem establishes 1) the WARL lower bound of
$T_{\bm{\beta^{*}}}$, and 2) the WADD upper bound of $T_{\bm{\beta^{*}}}$.

######  Theorem 5.

1) For $T_{\bm{\beta^{*}}}$ defined in (14), let $b=\log\gamma$, then
$\text{WARL}(T_{\bm{\beta^{*}}})\geq\gamma$.

2) As $\gamma\rightarrow\infty$, we have that

$\displaystyle\text{WADD}(T_{\bm{\beta^{*}}})\leq\frac{\log\gamma}{I_{\bm{\beta^{*}}}}(1+o(1)).$
(17)

The proof of Theorem 5 can be found in Appendix F. The proof of Theorem 5 is
based on the Weak Law of Large Numbers for the weighted mixture likelihood
ratio similarly to [37]. The major challenge lies in that here we are
interested in the worst-case label and the worst-case anomaly trajectory. Note
that in our problem, the label and the affected sensor change with time.
Therefore, it’s challenging to explicitly characterize the worst-case label
and anomaly trajectory for $T_{\bm{\beta^{*}}}$. To show the asymptotically
optimal performance of $T_{\bm{\beta^{*}}}$, instead of finding the worst-case
label and anomaly trajectory, we apply the symmetric property of
$T_{\bm{\beta^{*}}}$ and Lemma 1 to show that the WADD and WARL of
$T_{\bm{\beta^{*}}}$ are bounded under all possible labels and trajectories.

We then establish the first-order asymptotic optimality of
$T_{\bm{\beta}^{*}}$ in the following theorem.

######  Theorem 6.

$T_{\bm{\beta}^{*}}$ is first-order asymptotically optimal for problem (5).

###### Proof.

Combining Theorem 4 and Theorem 5, we establish the first-order asymptotic
optimality of $T_{\bm{\beta}^{*}}$. ∎

If we apply $T_{\bm{\beta^{*}}}$ (designed for the dyanmic setting) to the
static setting, the WADD of $T_{\bm{\beta^{*}}}$ can also be upper bounded by
$\frac{\log\gamma}{I_{\bm{\beta^{*}}}}(1+o(1))$. However, $T_{\bm{\beta^{*}}}$
may not be asymptotically optimal. On the other hand, in the dynamic setting,
the sensor affected by the anomaly changes with time, and thus the MLE may not
work well. Therefore, the weighted mixture CuSum algorithm works better than
the GM-CuSum.

##  V Simulation Results

We first consider the static setting. We show an example evolution path of the
GM-CuSum algorithm. We set $n=2$ and $K=2$. For type I sensors, the pre- and
post-change distributions are $\mathcal{B}(10,0.3)$ and $\mathcal{B}(10,0.4)$,
respectively, where $\mathcal{B}$ denotes binomial distribution. For type II
sensors, the pre- and post-change distributions are $\mathcal{B}(10,0.8)$ and
$\mathcal{B}(10,0.6)$, respectively. We set the change point to be 500 and
$b=20$. We plot one sample evolution path of the GM-CuSum algorithm when one
sensor of type one is affected. It can be seen from Fig. 4 that before the
change point, the test statistic fluctuates around zero, and after the change
point, it starts to increase with a positive drift.

Figure 1: Evolution path of the GM-CuSum algorithm.

Figure 2: Comparison of the three algorithms in static setting: $n=4,K=2$.

Figure 3: Comparison of the three algorithms in static setting: $n=8,K=2$.

Figure 4: Comparison of the three algorithms in static setting: $n=4,K=4$.

Figure 5: Comparison of the three algorithms in static setting: $n=8,K=4$.

Figure 6: Evolution path of the weighted mixture CuSum algorithm.

Figure 7: Comparison of the three algorithms in dynamic setting: $n=4,K=2$.

Figure 8: Comparison of the three algorithms in dynamic setting: $n=8,K=2$.

We then compare our GM-CuSum algorithm with a Bayesian mixture CuSum algorithm
$T_{B}=\inf\Big{\\{}t:\max_{1\leq j\leq
t}\sum^{t}_{i=j}\log\frac{\frac{1}{|\mathcal{K}|}\sum_{k\in\mathcal{K}}\widetilde{\mathbb{P}}^{k}(X^{n}[i])}{\widetilde{\mathbb{P}}_{0}(X^{n}[i])}\geq
b\Big{\\}}$ and the optimal weighted mixture CuSum algorithm. We plot the WADD
as a function of the WARL under the worst-case static trajectory.

We consider four cases with different number of sensors and types. For the
cases where there are two types of sensors, for type I sensors, the pre- and
post-change distributions are $\mathcal{B}(10,0.2)$ and $\mathcal{B}(10,0.5)$,
for type II sensors, the pre- and post-change distributions are
$\mathcal{B}(10,0.8)$ and $\mathcal{B}(10,0.6)$, respectively. We plot the
figures for the cases where each type has two sensors and each type has four
sensors in Fig. 4 and Fig. 4, respectively. For the cases where there are four
types of sensors, for type I sensors, the pre- and post-change distributions
are $\mathcal{B}(10,0.2)$ and $\mathcal{B}(10,0.8)$, for type II sensors, the
pre- and post-change distributions are $\mathcal{B}(10,0.3)$ and
$\mathcal{B}(10,0.6)$, for type III sensors, the pre- and post-change
distributions are $\mathcal{B}(10,0.5)$ and $\mathcal{B}(10,0.9)$, for type IV
sensors, the pre- and post-change distributions are $\mathcal{B}(10,0.4)$ and
$\mathcal{B}(10,0.7)$ respectively. We plot the figures for the cases where
each type has one sensor and each type has two sensors in Fig. 4 and Fig. 8,
respectively. We apply the Monte-Carlo approximation idea to obtain the
optimal weight for our optimal weighted mixture CuSum algorithm. We repeat the
experiment for 5000 times.

It can be seen from Fig. 4, Fig. 4, Fig. 4 and Fig. 8 that our GM-CuSum
outperforms the Bayesian algorithm and the performance of the optimal weighted
mixture CuSum algorithm are close to the GM-CuSum algorithm. The simulation
results show that our optimal weighted mixture CuSum algorithm are also robust
under the static setting. Moreover, the relationship between the WADD and log
of the WARL is linear, which validates our theoretical results.

We then consider the dynamic anomaly. We use the same parameters of
distributions as in the static setting. We first show an evolution path of the
weighted mixture CuSum algorithm under a random trajectory ${\bm{S}}$ in Fig.
8. To generate this random trajectory ${\bm{S}}$, at each time step, let the
probability that one sensor of type I is affected be $0.8$ and the probability
that one sensor of type II is affected be $0.2$. Similar to the GM-CuSum,
before the change point, the test statistic fluctuates around zero, and after
the change point, it starts to increase with a positive drift.

Figure 9: Comparison of the three algorithms in dynamic setting: $n=4,K=4$.

Figure 10: Comparison of the three algorithms in dynamic setting: $n=8,K=4$.

Figure 11: Optimal Weighted CuSum Algorithm under Different Trajectories.

We then compare our optimal weighted mixture CuSum algorithm with an arbitrary
weighted mixture CuSum, i.e., replace $\bm{\beta^{*}}$ in (14) with some
arbitrarily $\bm{\beta}$, e.g., $\bm{\beta}=(\frac{1}{2},\frac{1}{2})$ for the
case with two types and the GM-CuSum. Here, we plot the average detection
delay (ADD) and the average run length (ARL) for some randomly generated
trajectories. It can be seen from Fig. 8, Fig. 8, Fig. 11 and Fig. 11 that our
optimal weighted mixture CuSum algorithm outperforms the Bayesian weighted
mixture CuSum algorithm and the GM-CuSum. The relationship between the WADD
and log of the WARL is linear. It can also be observed that the GM-CuSum
algorithm does not perform well under the dynamic setting.

We then compare the performance of our weighted mixture CuSum algorithm under
two different trajectories. We choose $n=2$ and $K=2$. For type I sensors, the
pre- and post-change distributions are $\mathcal{B}(10,0.3)$ and
$\mathcal{B}(10,0.4)$, respectively. For type II sensors, the pre- and post-
change distributions are $\mathcal{B}(10,0.8)$ and $\mathcal{B}(10,0.6)$,
respectively. For trajectory 1, at each time, let the probability that one
sensor of type one is affected be $0.8$ and the probability that one sensor of
type two is affected be $0.2$. For trajectory 2, at each time, let the
probability that one sensor of type one is affected be $0.2$ and the
probability that one sensor of type two is affected be $0.8$. We plot the ADD
as function of the ARL. It can be seen from Fig. 11 that for two different
trajectories, our optimal weighted mixture CuSum algorithm have the same
performance, which demonstrates the robustness of our optimal weighted mixture
CuSum algorithm under different trajectories.

##  VI conclusion

In this paper, we investigated the problem of quickest detection of an anomaly
in networks with unlabeled samples. We first investigated the case with a
static anomaly. We used the MLE to estimate the type of the affected sensor. A
GM-CuSum algorithm was proposed. We showed that it is second-order
asymptotically optimal. We then extended our study to the case with a dynamic
anomaly, that is, the affected sensor changes with time. We proposed a
weighted mixture CuSum algorithm, and proved that it is first-order
asymptotically optimal. Our approaches provide useful insights for general
(sequential) statistical inference problems with unlabeled samples.

## Appendix A

Before the anomaly emerges, i.e., $t<\nu$, there are $n_{k}$ sensors in group
$k$, $\forall 1\leq k\leq K$, and 0 sensors in group $k$, $\forall K<k\leq
2K$. Then, there are in total $\left(\begin{subarray}{c}n\\\
n_{1},\ldots,n_{K}\end{subarray}\right)$ possible $\sigma_{t}^{S[t]}$:
$\\{1,\ldots,n\\}\rightarrow\\{1,\ldots,K\\}$ satisfying
$|\\{i:\sigma_{t}^{S[t]}(i)=k\\}|=n_{k}$, for any $k=1,\ldots,K$. We denote
the collection of all such labels by $\mathcal{S}_{n,0}$. After the anomaly
emerges, i.e., $t\geq\nu$, one sensor of type $S[t]\neq 0$ is affected by
anomaly. Therefore, the number of sensors in group $S[t]$ and $S[t]+K$ are
$n_{S[t]}-1$ and 1 respectively. Then, there are
$\left(\begin{subarray}{c}n\\\
n_{1},\ldots,n_{S[t]}-1,\ldots,n_{K},1\end{subarray}\right)$ possible
$\sigma_{t}^{S[t]}$: $\\{1,\ldots,n\\}\rightarrow\\{1,\ldots,K,S[t]+K\\}$
satisfying

$\displaystyle|\\{i:\sigma_{t}^{S[t]}(i)=k\\}|=\left\\{\begin{array}[]{ll}n_{k},&\text{
if }1\leq k\leq K\text{and}\ k\neq S[t],\\\ n_{k}-1,&\text{ if }k=S[t],\\\
1,&\text{ if }k=S[t]+K,\\\ 0,&\text{ otherwise}.\end{array}\right.$

We then denote the collection of all such labels by $\mathcal{S}_{n,S[t]}$.

Before the anomaly emerges, i.e., $t<\nu$, the samples $X^{n}[t]$ follows the
distribution

$\displaystyle\mathbb{P}_{0,\sigma_{t}^{0}}(X^{n}[t])=\prod_{i=1}^{n}p_{0,\sigma_{t}^{0}(i)}(X_{i}[t]),$
(18)

for some unknown $\sigma_{t}^{0}\in\mathcal{S}_{n,0}.$ At time $t\geq\nu$,
$X^{n}[t]$ follows the distribution

$\displaystyle\mathbb{P}^{S[t]}_{\sigma^{S[t]}_{t}}(X^{n}[t])\overset{\Delta}{=}$
$\displaystyle\prod\limits_{\begin{subarray}{c}i:\sigma^{S[t]}_{t}(i)\leq
K\end{subarray}}p_{0,\sigma^{S[t]}_{t}(i)}(X_{i}[t])\times\prod\limits_{\begin{subarray}{c}i:\sigma_{t}^{S[t]}(i)>K\end{subarray}}p_{1,\sigma^{S[t]}_{t}(i)-K}(X_{i}[t]),$
(19)

for some unknown $\sigma^{S[t]}_{t}\in\mathcal{S}_{n,S[t]}$.

##  Appendix B Proof of Theorem 1

Consider a simple QCD problem with a pre-change distribution
$\widetilde{\mathbb{P}}_{0}$ and a post-change distribution
$\widetilde{\mathbb{P}}^{k}$, respectively. Define the
$\widetilde{\text{WADD}}_{k}$ and $\widetilde{\text{ARL}}$ for any stopping
rule $\tau$ as follows:

$\displaystyle\widetilde{\text{WADD}}_{k}(\tau)$
$\displaystyle=\sup\limits_{\nu\geq
1}\text{esssup}\widetilde{\mathbb{E}}^{k,\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]],$
$\displaystyle\widetilde{\text{ARL}}(\tau)$
$\displaystyle=\widetilde{\mathbb{E}}^{\infty}[\tau],$ (20)

where $\widetilde{\mathbb{E}}^{k,\nu}$ denotes the expectation when the change
is at $\nu$, the pre- and post-change distributions are
$\widetilde{\mathbb{P}}_{0}$ and $\widetilde{\mathbb{P}}^{k}$, and
$\widetilde{\mathbf{X}}^{n}[t]$ for $1\leq t\leq\nu-1$ are i.i.d. from
$\widetilde{\mathbb{P}}_{0}$, $\widetilde{\mathbb{E}}^{\infty}$ denotes the
expectation when there is no change and samples are generated according to
$\widetilde{\mathbb{P}}_{0}$.

For any $1\leq k\leq K$, consider another QCD problem with a pre-change
distribution $\mathbb{P}_{0,\sigma_{t}^{0}}$ and a post-change distribution
$\mathbb{P}^{k}_{\sigma_{t}^{k}}$, respectively. For this pair of pre- and
post-change distributions, define the ${\text{WADD}}_{k}$ and WARL for any
stopping rule $\tau$ as follows:

$\displaystyle\text{WADD}_{k}(\tau)$ $\displaystyle=\sup_{\nu\geq
1}\sup\limits_{\Omega_{k}}\text{esssup}\mathbb{E}^{k,\nu}_{\Omega_{k}}[(\tau-\nu)^{+}|{\mathbf{X}}^{n}[1,\nu-1]],$
$\displaystyle\text{WARL}(\tau)$
$\displaystyle=\inf\limits_{\Omega}{\mathbb{E}}^{\infty}_{\Omega}[\tau].$ (21)

For any $1\leq k\leq K$ and any $\tau$ satisfying
$\text{WARL}(\tau)\geq\gamma$, it can be shown that

$\displaystyle\text{WADD}(\tau)$
$\displaystyle=\sup_{k\in\mathcal{K}}\text{WADD}_{k}(\tau)$
$\displaystyle\geq\sup_{\nu\geq
1}\sup_{\Omega_{k}}\text{esssup}\mathbb{E}^{k,\nu}_{\Omega_{k}}[(\tau-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]]$
$\displaystyle\geq\sup\limits_{\nu\geq
1}\text{esssup}\widetilde{\mathbb{E}}^{k,\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]]$
$\displaystyle=\widetilde{\text{WADD}}_{k}(\tau).$ (22)

The second inequality is due to the fact that for any $\tau$,
$\text{WADD}_{k}(\tau)\geq\widetilde{\text{WADD}}_{k}(\tau)$ [17, eq. (18)].
Similarly, we have that for any $\tau$,
$\text{WARL}(\tau)\leq\widetilde{\text{ARL}}(\tau)$ [17, eq. (18)]. It then
follows that for any $k\in\mathcal{K}$,

$\displaystyle\inf_{\tau:\text{WARL}(\tau)\geq\gamma}\text{WADD}(\tau)$
$\displaystyle\geq\inf_{\tau:\widetilde{\text{ARL}}(\tau)\geq\gamma}\widetilde{\text{WADD}}_{k}(\tau)$
$\displaystyle\geq\frac{\log\gamma}{I_{k}}+O(1),\ \text{as}\
\gamma\rightarrow\infty.$ (23)

The last inequality is due to the universal lower bound on WADD for a simple
QCD problem[37]. We then have that

$\displaystyle\inf_{\tau:\text{WARL}(\tau)\geq\gamma}\text{WADD}(\tau)\geq\frac{\log\gamma}{I^{*}}+O(1),\
\text{as}\ \gamma\rightarrow\infty.$ (24)

##  Appendix C Proof of Theorem 2

For any $m\geq 0$, let $r_{0}=0$ and define the stopping time

$\displaystyle
r_{m+1}=\inf\Big{\\{}t>r_{m}:\sup\limits_{k}\sum\limits^{t}_{i=r_{m}+1}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\leq
0\Big{\\}}.$ (25)

For any permutation $\pi(X^{n})=(X_{\pi(1)},X_{\pi(2)},\ldots,X_{\pi(n)})$, we
have that
$\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}=\log\frac{\widetilde{\mathbb{P}}^{k}(\pi(X^{n}))}{\widetilde{\mathbb{P}}_{0}(\pi(X^{n}))}$.
For any $\pi$, let $\hat{\sigma}^{0}=\sigma^{0}\circ\pi$, where “$\circ$”
denotes the composition of two functions. Then
$\mathbb{E}_{0,\sigma^{0}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{k}(\pi(X^{n}))}{\widetilde{\mathbb{P}}_{0}(\pi(X^{n}))}\Big{]}=\mathbb{E}_{0,\sigma^{0}\circ\pi}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}=\mathbb{E}_{0,\hat{\sigma}^{0}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$.
For any $\hat{\sigma}^{0}\in{\mathcal{S}_{n,0}}$, a $\pi$ can always be found
so that $\sigma^{0}\circ\pi=\hat{\sigma}^{0}$. Thus, for any
$\sigma^{0},\hat{\sigma}^{0}\in{\mathcal{S}_{n,0}}$,
$\mathbb{E}_{0,\hat{\sigma}^{0}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}=\mathbb{E}_{0,\sigma^{0}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}.$

We then have that for any $\sigma^{0}\in{\mathcal{S}_{n,0}}$,

$\displaystyle\mathbb{E}_{0,\sigma^{0}}\Big{[}\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
$\displaystyle=\frac{1}{\mid{\mathcal{S}_{n,0}}\mid}\sum\limits_{\sigma^{0}\in{\mathcal{S}_{n,0}}}\mathbb{E}_{0,\sigma^{0}}\Big{[}\frac{\widetilde{\mathbb{P}}^{k}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
$\displaystyle=\frac{1}{\mid{\mathcal{S}_{n,0}}\mid}\sum\limits_{\sigma^{0}\in{\mathcal{S}_{n,0}}}\int\frac{\widetilde{\mathbb{P}}^{k}(x^{n})}{\widetilde{\mathbb{P}}_{0}(x^{n})}\cdot\mathbb{P}_{0,\sigma^{0}}(x^{n})\mathrm{d}x^{n}$
$\displaystyle=\int\frac{\widetilde{\mathbb{P}}^{k}(x^{n})}{\widetilde{\mathbb{P}}_{0}(x^{n})}\cdot\widetilde{\mathbb{P}}_{0}(x^{n})\mathrm{d}x^{n}$
$\displaystyle=\int\widetilde{\mathbb{P}}^{k}(x^{n})\mathrm{d}x^{n}=1.$ (26)

Therefore, for any $\Omega$ and $t>r_{m}$,

$\displaystyle\mathbb{E}_{\Omega}^{\infty}\Bigg{[}\prod\limits_{i=r_{m}+1}^{t+1}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\Bigg{|}\mathcal{F}_{t}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\Omega}^{\infty}\Bigg{[}\prod\limits_{i=r_{m}+1}^{t}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\cdot\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{t+1})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{t+1})}\Bigg{|}\mathcal{F}_{t}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\Omega}^{\infty}\Bigg{[}\prod\limits_{i=r_{m}+1}^{t}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\Bigg{|}\mathcal{F}_{t}\Bigg{]}\cdot\mathbb{E}_{0,\sigma^{0}}\Bigg{[}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{t+1})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{t+1})}\Bigg{|}\mathcal{F}_{t}\Bigg{]}$
$\displaystyle=\prod\limits_{i=r_{m}+1}^{t}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\cdot\mathbb{E}_{0,\sigma^{0}}\Bigg{[}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{t+1})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{t+1})}\Bigg{]}$
$\displaystyle=\prod\limits_{i=r_{m}+1}^{t}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}.$
(27)

Therefore,
$\Big{\\{}\prod\limits_{i=r_{m}+1}^{t}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})},\mathcal{F}_{t},t>r_{m}\Big{\\}}$
is a martingale under $\mathbb{P}_{\Omega}^{\infty}$ for any $\Omega$ with
mean 1.

We then have that for any $\Omega$,

$\displaystyle\mathbb{P}_{\Omega}^{\infty}\Bigg{\\{}\sup\limits_{k}\sum\limits^{t}_{i=r_{m}+1}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\geq
b\ \text{for some}\ t>r_{m}\Bigg{|}\mathcal{F}_{r_{m}}\Bigg{\\}}$
$\displaystyle\leq\sum\limits_{k=1}^{K}\mathbb{P}_{\Omega}^{\infty}\Bigg{\\{}\sum\limits^{t}_{i=r_{m}+1}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\geq
b\ \text{for some}\ t>r_{m}\Bigg{|}\mathcal{F}_{r_{m}}\Bigg{\\}}$
$\displaystyle=\sum\limits_{k=1}^{K}\mathbb{P}_{\Omega}^{\infty}\Bigg{\\{}\prod\limits^{t}_{i=r_{m}+1}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\geq
e^{b}\ \text{for some}\ t>r_{m}\Bigg{|}\mathcal{F}_{r_{m}}\Bigg{\\}}$
$\displaystyle\leq
K\frac{\mathbb{E}_{0,\sigma^{0}}\Big{[}\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{r_{m}+1})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{r_{m}+1})}\Big{]}}{e^{b}}=Ke^{-b},$
(28)

where the last inequality is due to Doob’s submartingale inequality[40] and
the optional sampling theorem[40].

Let $M=\inf\Big{\\{}m\geq 0:r_{m}<\infty\ \text{and}\
\sup\limits_{k}\sum\limits^{t}_{i=r_{m}+1}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}\geq
b\ \text{for some}\ t>r_{m}\Big{\\}}$. We have that for any $\Omega$,

$\displaystyle\mathbb{P}_{\Omega}^{\infty}\big{(}M\geq
m+1|\mathcal{F}_{r_{m}}\big{)}$
$\displaystyle\geq\mathbb{P}_{\Omega}^{\infty}\Bigg{\\{}\sup\limits_{k}\sum\limits^{t}_{i=r_{m}+1}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}_{i})}{\widetilde{\mathbb{P}}_{0}(X^{n}_{i})}<b\
\text{for all}\ t>r_{m}\Bigg{|}\mathcal{F}_{r_{m}}\Bigg{\\}}$
$\displaystyle\geq 1-Ke^{-b}.$ (29)

We then have that for any $\Omega$,

$\displaystyle\mathbb{P}_{\Omega}^{\infty}(M>m)$
$\displaystyle=\mathbb{E}_{\Omega}^{\infty}\Big{[}\mathbb{P}_{\Omega}^{\infty}\big{(}M\geq
m+1|\mathcal{F}_{r_{m}}\big{)}\cdot\mathbbm{1}_{\\{M\geq m\\}}\Big{]}$
$\displaystyle\geq(1-Ke^{-b})\mathbb{P}_{\Omega}^{\infty}(M>m-1)$
$\displaystyle\geq(1-Ke^{-b})^{2}\mathbb{P}_{\Omega}^{\infty}(M>m-2)$
$\displaystyle\geq(1-Ke^{-b})^{m}\mathbb{P}_{\Omega}^{\infty}(M>0)$
$\displaystyle=(1-Ke^{-b})^{m}.$ (30)

It then follows that

$\displaystyle\text{WARL}(T_{G})$
$\displaystyle=\inf\limits_{\Omega}\mathbb{E}_{\Omega}^{\infty}[T_{G}]\geq\inf\limits_{\Omega}\mathbb{E}_{\Omega}^{\infty}[M]$
$\displaystyle\geq\inf\limits_{\Omega}\sum_{m=0}^{\infty}\mathbb{P}_{\Omega}^{\infty}(M>m)$
$\displaystyle\geq\sum_{m=0}^{\infty}(1-Ke^{-b})^{m}=\frac{e^{b}}{K}.$ (31)

Let $b=\log K\gamma$, we have that $\text{WARL}(T_{G})\geq\gamma$. Let $T_{k}$
be the mixture CuSum algorithm for problem in (B):

$\displaystyle T_{k}=\inf\bigg{\\{}t:\max\limits_{1\leq j\leq
t}\sum\limits^{t}_{i=j}\log\frac{\widetilde{\mathbb{P}}^{k}(X^{n}[i])}{\widetilde{\mathbb{P}}_{0}(X^{n}[i])}\geq
b\bigg{\\}}.$ (32)

It then follows that for any $1\leq k\leq K$,

$\displaystyle\text{WADD}_{k}(T_{G})$ $\displaystyle=\sup_{\nu\geq
1}\sup_{\Omega_{k}}\text{esssup}\mathbb{E}^{k,\nu}_{\Omega_{k}}[(T_{G}-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]]$
$\displaystyle\leq\sup_{\nu\geq
1}\sup_{\Omega_{k}}\text{esssup}\mathbb{E}^{k,\nu}_{\Omega_{k}}[(T_{k}-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]]$
$\displaystyle\leq\frac{\log b}{I_{k}}+O(1),$ (33)

where the last equality is because of the exact optimality of the mixture
CuSum algorithm (see Theorem 1 in [17]).

To satisfy the WARL constraint, choose $b=\log{K\gamma}$, we then have that

$\displaystyle\text{WADD}(T_{G})$
$\displaystyle=\sup\limits_{k\in\mathcal{K}}\text{WADD}_{k}(T_{G})\leq\sup\limits_{k\in\mathcal{K}}\text{WADD}_{k}(T_{k})$
$\displaystyle=\sup\limits_{k\in\mathcal{K}}\frac{\log K\gamma}{I_{k}}+O(1)$
$\displaystyle=\frac{\log\gamma}{I^{*}}+\frac{\log K}{I^{*}}+O(1),\ \text{as}\
\gamma\rightarrow\infty.$ (34)

##  Appendix D Proof of Theorem 4

For any trajectory ${\bm{S}}$ and stopping time $\tau$, define the WADD and
WARL

$\displaystyle\text{WADD}_{\bm{S}}(\tau)$ $\displaystyle=\sup_{\nu\geq
1}\sup_{\Omega_{\bm{S}}}\text{esssup}\mathbb{E}^{{\bm{S}},\nu}_{\Omega_{\bm{S}}}[(\tau-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]],$
$\displaystyle\text{ARL}(\tau)$
$\displaystyle=\inf_{\Omega}\mathbb{E}_{\Omega}^{\infty}[\tau].$ (35)

Consider QCD problem with a pre-change distribution
$\widetilde{\mathbb{P}}_{0}=\frac{1}{\mid{\mathcal{S}_{n,0}}\mid}\sum_{\sigma^{0}\in{\mathcal{S}_{n,0}}}\mathbb{P}_{0,\sigma^{0}}$
and a post-change distribution
$\widetilde{\mathbb{P}}^{S[t]}=\frac{1}{\mid{\mathcal{S}_{n,{S[t]}}}\mid}\sum_{\sigma^{S[t]}\in{\mathcal{S}_{n,{S[t]}}}}\mathbb{P}^{S[t]}_{\sigma^{S[t]}}$,
respectively. For this pair of pre- and post-change distributions and any
trajectory ${\bm{S}}$, define the $\widetilde{\text{WADD}}_{\bm{S}}$ and
$\widetilde{\text{ARL}}_{\bm{S}}$ for any stopping rule $\tau$:

$\displaystyle\widetilde{\text{WADD}}_{\bm{S}}(\tau)$
$\displaystyle=\sup_{\nu\geq
1}\text{esssup}\widetilde{\mathbb{E}}^{\bm{S},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]],$
$\displaystyle\widetilde{\text{ARL}}(\tau)$
$\displaystyle=\widetilde{\mathbb{E}}^{\infty}[\tau].$ (36)

where $\widetilde{\mathbb{E}}^{\bm{S},\nu}$ denotes the expectation when
change point is $\nu$, before the change point, the data follows distribution
$\widetilde{\mathbb{P}}_{0}$ and after the change point, at time $t$, the data
follows the distribution $\widetilde{\mathbb{P}}^{S[t]}$, and
$\widetilde{\mathbf{X}}^{n}[1,\nu-1]$ are i.i.d. from
$\widetilde{\mathbb{P}}_{0}$; and $\widetilde{\mathbb{E}}^{\infty}$ denote the
expectation when for any $t\geq 0$, the data follows distribution
$\widetilde{\mathbb{P}}_{0}$, i.e., $\nu=\infty$.

Consider another QCD problem with pre-change distribution
$\widetilde{\mathbb{P}}_{0}$ and post-change distribution
$\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}$. Under this pair of pre- and post-
change distributions, for any stopping time $\tau$, define worst-case average
detection delay and average running length as follows:

$\displaystyle\widetilde{\text{WADD}}_{\bm{\beta^{*}}}(\tau)$
$\displaystyle=\sup_{\nu\geq
1}\text{esssup}\widetilde{\mathbb{E}}^{\bm{\beta^{*}},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]],$
$\displaystyle\widetilde{\text{ARL}}(\tau)$
$\displaystyle=\widetilde{\mathbb{E}}^{\infty}[\tau].$ (37)

In QCD problems, ARL only depends on the pre-change distribution. Therefore,
for any stopping time $\tau$, problems in (4) and (D) have the same ARL,
problems in (D) and (D) have the same ARL. Let $\mathcal{C}_{\gamma}$ denotes
the collection of all stopping times $\tau$ that satisfy
$\text{ARL}(\tau)\geq\gamma$ and $\widetilde{\mathcal{C}}_{\gamma}$ denotes
the collection of all stopping times $\tau$ that satisfy
$\widetilde{\text{ARL}}(\tau)\geq\gamma$. Our goal is to prove that

$\displaystyle\inf_{\tau\in\mathcal{C}_{\gamma}}\text{WADD}(\tau)\geq\inf_{\tau\in\widetilde{\mathcal{C}}_{\gamma}}\widetilde{\text{WADD}}_{\bm{\beta^{*}}}(\tau)\sim\frac{\log\gamma}{I_{\bm{\beta^{*}}}}(1+o(1)).$
(38)

Construct a new sequence of random variables
$\\{\widehat{X}^{n}[t]\\}_{t=1}^{\infty}$. Before the change point,
$\widehat{X}^{n}[t]$ are i.i.d. according to the mixture distribution
$\widetilde{\mathbb{P}}_{0}=\frac{1}{\mid{\mathcal{S}_{n,0}}\mid}\sum_{\sigma^{0}\in{\mathcal{S}_{n,0}}}\mathbb{P}_{0,\sigma^{0}}$.
After the change point, i.e., $t\geq\nu$, $\widehat{X}^{n}[t]$ follows the
distribution $\mathbb{P}^{S[t]}_{\sigma^{S[t]}_{t}}$ for some
$\sigma^{S[t]}_{t}\in{\mathcal{S}_{n,{S[t]}}}$. Specifically,

$\displaystyle\widehat{X}^{n}[t]\sim\left\\{\begin{array}[]{ll}\widetilde{\mathbb{P}}_{0},&\text{
if }t<\nu,\\\ \mathbb{P}^{S[t]}_{\sigma^{S[t]}_{t}},&\text{ if
}t\geq\nu.\end{array}\right.$ (41)

For any stopping time $\tau$ and any ${\bm{S}}$, define the worst-case average
detection delay for the model in (41) as follows:

$\displaystyle\widehat{\text{WADD}_{\bm{S}}}(\tau)=$
$\displaystyle\sup\limits_{\nu\geq
1}\sup_{\sigma_{\nu}^{S[\nu]},...,\sigma_{\infty}^{S[\infty]}}\text{esssup}{\widehat{\mathbb{E}}}^{{\bm{S}},\nu}_{\sigma_{\nu}^{S[\nu]},...,\sigma_{\infty}^{S[\infty]}}[(\tau-\nu)^{+}|\widehat{\mathbf{X}}^{n}[1,\nu-1]],$
(42)

where
$\widehat{\mathbb{E}}^{{\bm{S}},\nu}_{\sigma_{\nu}^{S[\nu]},...,\sigma_{\infty}^{S[\infty]}}$
denotes the expectation when the data is distributed according to (41).

Let
$\widetilde{\text{WADD}}(\tau)=\sup\limits_{{\bm{S}}}\widetilde{\text{WADD}}_{\bm{S}}(\tau)$.
To prove (38), we will first show that for any ${\bm{S}}$,
${\text{WADD}_{\bm{S}}}(\tau)=\widehat{\text{WADD}_{\bm{S}}}(\tau)$, and then
show that
$\widehat{\text{WADD}_{\bm{S}}}(\tau)\geq\widetilde{\text{WADD}_{\bm{S}}}(\tau)$.
We will then complete our proof by showing that for any $\tau$ and
$\bm{\beta}$,
$\widetilde{\text{WADD}}(\tau)\geq\widetilde{\text{WADD}}_{\bm{\beta}}(\tau)$.

Step 1. Denote by $\mathcal{M}$ the collection of all
$\\{\sigma_{1}^{0},...,\sigma_{\nu-1}^{0}\\}$, and $\mu$ is an element in
$\mathcal{M}$. When the trajectory is ${\bm{S}}$, denote by
$\mathcal{N}_{\bm{S}}$ the collection of all
$\\{\sigma_{\nu}^{S[\nu]},...,\sigma_{\infty}^{S[\infty]}\\}$, and $\omega$ is
an element in $\mathcal{N}_{\bm{S}}$. Then, the $\text{WADD}_{\bm{S}}$ can be
written as

$\displaystyle\text{WADD}_{\bm{S}}(\tau)$ $\displaystyle=\sup\limits_{\nu\geq
1}\sup_{\Omega_{\bm{S}}}\text{esssup}{\mathbb{E}}^{{\bm{S}},\nu}_{\Omega_{\bm{S}}}[(\tau-\nu)^{+}|{\mathbf{X}}^{n}[1,\nu-1]]$
$\displaystyle=\sup\limits_{\nu\geq
1}\sup_{\omega\in\mathcal{N}_{\bm{S}}}\sup\limits_{\mu\in\mathcal{M}}\text{esssup}{\mathbb{E}}^{{\bm{S}},\nu}_{\omega}[(\tau-\nu)^{+}|{\mathbf{X}}^{n}[1,\nu-1]],$

where $\mathbb{E}^{{\bm{S}},\nu}_{\omega}$ denotes the expectation when change
point is $\nu$, the trajectory is ${\bm{S}}$, and after the change point, the
data follows distribution
$\prod_{t=\nu}^{\infty}\mathbb{P}^{S[t]}_{\sigma^{S[t]}_{t}}$. We note that
$\widehat{X}^{n}[t]$ and $X^{n}[t]$, for $t\geq\nu$, have the same
distribution $\mathbb{P}^{S[t]}_{\sigma^{S[t]}_{t}}$. Therefore, the
difference between $\text{WADD}_{\bm{S}}$ and $\widehat{\text{WADD}_{\bm{S}}}$
lies in that they take esssup with respect to different distributions, i.e.,
the distributions of $\mathbf{X}^{n}[1,\nu-1]$ and
$\mathbf{\widehat{X}}^{n}[1,\nu-1]$ are different. Let
$f_{\omega}(\mathbf{X}^{n}[1,\nu-1])$ denote
${\mathbb{E}}^{{\bm{S}},\nu}_{\omega}[(\tau-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]]$.
Then, $\text{WADD}_{\bm{S}}$ and $\widehat{\text{WADD}_{\bm{S}}}$ can be
written as

$\displaystyle\text{WADD}_{\bm{S}}(\tau)$ $\displaystyle=\sup\limits_{\nu\geq
1}\sup_{\omega\in\mathcal{N}_{\bm{S}}}\sup_{\mu\in\mathcal{M}}\text{esssup}f_{\omega}({\mathbf{X}}^{n}[1,\nu-1]),$
$\displaystyle\widehat{\text{WADD}_{\bm{S}}}(\tau)$
$\displaystyle=\sup\limits_{\nu\geq
1}\sup_{\omega\in\mathcal{N}_{\bm{S}}}\text{esssup}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1]).$
(43)

It then suffices to show that for any $\omega\in\mathcal{N}_{S}$,
$\sup_{\mu\in\mathcal{M}}\text{esssup}f_{\omega}({\mathbf{X}}^{n}[1,\nu-1])=\text{ess}\sup
f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1]).$

For any $\omega\in\mathcal{N}_{\bm{S}}$ and $\mu\in\mathcal{M}$, let

$\displaystyle b_{\omega,\mu}$
$\displaystyle=\text{esssup}f_{\omega}({\mathbf{X}}^{n}[1,\nu-1])$
$\displaystyle=\inf\\{b:\mathbb{P}_{\mu}(f_{\omega}({\mathbf{X}}^{n}[1,\nu-1])>b)=0\\},$
(44)

where $\mathbb{P}_{\mu}$ denotes the probability measure when the data is
generated from
$\mathbb{P}_{0,\sigma_{1}^{0}},...,\mathbb{P}_{0,\sigma_{\nu-1}^{0}}$ before
change point $\nu$.

Let
$b^{*}_{\omega}=\text{esssup}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])$.
It can be shown that

$\displaystyle b^{*}_{\omega}$
$\displaystyle=\inf\bigg{\\{}b:\int_{\textbf{x}^{n}[1,\nu-1]}\mathbbm{1}_{\\{f_{\omega}(\textbf{x}^{n}[1,\nu-1])>b\\}}\times\mathrm{d}\prod_{t=1}^{\nu-1}\widetilde{\mathbb{P}}_{0}(x^{n}(t))=0\bigg{\\}}$
$\displaystyle=\inf\bigg{\\{}b:\int_{\textbf{x}^{n}[1,\nu-1]}\mathbbm{1}_{\\{f_{\omega}(\textbf{x}^{n}[1,\nu-1])>b\\}}\times\mathrm{d}\prod_{t=1}^{\nu-1}\frac{1}{\mid{\mathcal{S}_{n,0}}\mid}\sum_{\sigma_{t}^{0}\in{\mathcal{S}_{n,0}}}{\mathbb{P}}_{0,\sigma_{t}^{0}}(x^{n}(t))=0\bigg{\\}}$
$\displaystyle=\inf\bigg{\\{}b:\int_{\textbf{x}^{n}[1,\nu-1]}\mathbbm{1}_{\\{f_{\omega}(\textbf{x}^{n}[1,\nu-1])>b\\}}\times\mathrm{d}\frac{1}{\mid\mathcal{M}\mid}\sum_{\mu\in\mathcal{M}}{\mathbb{P}}_{\mu}(\textbf{x}^{n}[1,\nu-1])=0\bigg{\\}}$
$\displaystyle=\inf\bigg{\\{}b:\frac{1}{\mid\mathcal{M}\mid}\sum_{\mu\in\mathcal{M}}{\mathbb{P}}_{\mu}(f_{\omega}({{\mathbf{X}}}^{n}[1,\nu-1])>b)=0\bigg{\\}}.$

It then follows that for any $\mu\in\mathcal{M}$, and
$\omega\in\mathcal{N}_{S}$,
${\mathbb{P}}_{\mu}(f_{\omega}({{\mathbf{X}}}^{n}[1,\nu-1])>b^{*}_{\omega})=0.$
Therefore, for any $\mu\in\mathcal{M}$, we have that $b_{\omega,\mu}\leq
b^{*}_{\omega}$. Then

$\displaystyle\sup\limits_{\mu\in\mathcal{M}}b_{\omega,\mu}\leq
b^{*}_{\omega}.$ (45)

Conversely, for any $\mu\in\mathcal{M}$, we have that
$\mathbb{P}_{\mu}\Big{(}f_{\omega}({\mathbf{X}}^{n}[1,\nu-1])>\sup\limits_{\mu\in\mathcal{M}}b_{\omega,\mu}\Big{)}=0.$
Then,
$\frac{1}{\mid\mathcal{M}\mid}\sum_{\mu\in\mathcal{M}}\mathbb{P}_{\mu}\Big{(}f_{\omega}({\mathbf{X}}^{n}[1,\nu-1])>\sup\limits_{\mu\in\mathcal{M}}b_{\omega,\mu}\Big{)}=0.$
This further implies that

$\displaystyle
b^{*}_{\omega}\leq\sup\limits_{\mu\in\mathcal{M}}b_{\omega,\mu}.$ (46)

Combining (45) and (46), we have that
$\sup_{\mu\in\mathcal{M}}b_{\omega,\mu}=b^{*}_{\omega},$ and thus
$\sup_{\mu\in\mathcal{M}}\text{esssup}f_{\omega}({\mathbf{X}}^{n}[1,\nu-1])=\text{esssup}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1]).$
This implies that for any $\tau$,

$\displaystyle\text{WADD}_{\bm{S}}(\tau)=\widehat{\text{WADD}_{\bm{S}}}(\tau).$
(47)

Step 2. The next step is to show that
$\widehat{\text{WADD}}_{\bm{S}}(\tau)\geq\widetilde{\text{WADD}}_{\bm{S}}(\tau)$.
We will first show that
$\sup_{\omega\in\mathcal{N}_{\bm{S}}}{\text{esssup}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])}\geq{\text{esssup}\sup_{\omega\in\mathcal{N}_{\bm{S}}}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])}.$
Denote by $\widetilde{\mathbb{P}}^{\nu}$ the probability measure when the
change is at $\nu$, the pre- and post-change distributions are
$\widetilde{\mathbb{P}}_{0}$ and $\widetilde{\mathbb{P}}^{S[t]}$ at time $t$,
respectively. Let
$\hat{b}=\sup_{\omega\in\mathcal{N}_{\bm{S}}}{\text{esssup}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])}$.
For any $\omega\in\mathcal{N}_{\bm{S}}$, we have that
$\widetilde{\mathbb{P}}^{\nu}\Big{(}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])>\hat{b}\Big{)}=0.$
Since $\mathcal{N}_{\bm{S}}$ is countable, and a countable union of sets of
measure zero has measure zero, we then have that

$\displaystyle\widetilde{\mathbb{P}}^{\nu}\Big{(}\sup\limits_{\omega\in\mathcal{N}_{\bm{S}}}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])>\hat{b}\Big{)}$
$\displaystyle\leq\widetilde{\mathbb{P}}^{\nu}\Big{(}\cup_{\omega\in\mathcal{N}_{\bm{S}}}\big{\\{}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])>\hat{b}\big{\\}}\Big{)}=0.$
(48)

Therefore,

$\displaystyle\hat{b}$
$\displaystyle=\sup\limits_{\omega\in\mathcal{N}_{\bm{S}}}\text{esssup}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])$
$\displaystyle\geq\text{esssup}\sup\limits_{\omega\in\mathcal{N}_{\bm{S}}}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1]).$
(49)

Before the change point $\nu$, $\widehat{X}^{n}[t]$ and $\widetilde{X}^{n}[t]$
follow the same distribution. For any $T\geq\nu+1$, we have that

$\displaystyle\sup_{\begin{subarray}{c}\\{\sigma_{\nu}^{S[\nu]},\cdots,\sigma_{T}^{S[T]}\\}\\\
\in\mathcal{S}_{n,S[\nu]}\times,\cdots,\times\mathcal{S}_{n,S[T]}\end{subarray}}\sum_{t=\nu+1}^{T}(t-\nu)\mathbb{P}^{{\bm{S}},\nu}_{\sigma_{\nu}^{S[\nu]},\cdots,\sigma_{T}^{S[T]}}(\tau=t|\widehat{\mathbf{X}}^{n}[1,\nu-1])$
$\displaystyle\geq\sum_{t=\nu+1}^{T}(t-\nu)\frac{1}{\mid\mathcal{S}_{n,S[\nu]}\mid\times\cdots\times\mid\mathcal{S}_{n,S[T]}\mid}\sum\limits_{\begin{subarray}{c}\\{\sigma_{\nu}^{S[\nu]},\cdots,\sigma_{T}^{S[T]}\\}\\\
\in\mathcal{S}_{n,S[\nu]}\times,\cdots,\times\mathcal{S}_{n,S[T]}\end{subarray}}\mathbb{P}^{{\bm{S}},\nu}_{\sigma_{\nu}^{S[\nu]},\cdots,\sigma_{T}^{S[T]}}(\tau=t|\widehat{\mathbf{X}}^{n}[1,\nu-1])$
$\displaystyle=\sum_{t=\nu+1}^{T}(t-\nu)\widetilde{\mathbb{P}}^{\bm{S},\nu}(\tau=t|\widetilde{\mathbf{X}}^{n}[1,\nu-1]),$
(50)

where
$\mathbb{P}_{\sigma_{\nu}^{S[\nu]},...,\sigma_{T}^{S[T]}}^{{\bm{S}},\nu}$
denotes the probability measure when change point is $\nu$, the trajectory is
${\bm{S}}$, the observations from time $\nu$ to time $T$ are generated
according to
${\mathbb{P}}^{S[\nu]}_{\sigma_{\nu}^{S[\nu]}},...,{\mathbb{P}}^{S[T]}_{\sigma_{T}^{S[T]}}$.
As $T\rightarrow\infty$, we have that

$\displaystyle
f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])\geq\widetilde{\mathbb{E}}^{\bm{S},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]],$
(51)

From (D) and (51), we have that

$\displaystyle\widehat{\text{WADD}_{\bm{S}}}(\tau)$
$\displaystyle=\sup\limits_{\omega\in\mathcal{N}_{\bm{S}}}\text{esssup}f_{\omega}(\widehat{\mathbf{X}}^{n}[1,\nu-1])$
$\displaystyle\geq\text{esssup}\widetilde{\mathbb{E}}^{\bm{S},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]]$
$\displaystyle=\widetilde{\text{WADD}}_{\bm{S}}(\tau).$ (52)

Combining (47) and (D), it follows that

$\displaystyle\text{WADD}_{\bm{S}}(\tau)=\widehat{\text{WADD}_{\bm{S}}}(\tau)\geq\widetilde{\text{WADD}_{\bm{S}}}(\tau).$
(53)

This holds for any trajectory ${\bm{S}}$. It then follows that

$\displaystyle\text{WADD}(\tau)$ $\displaystyle=\sup_{\nu\geq
0}\sup_{\Omega_{\bm{S}}}\sup_{\bm{S}}\text{esssup}\mathbb{E}^{{\bm{S}},\nu}_{\Omega_{\bm{S}}}[(\tau-\nu)^{+}|\mathbf{X}^{n}[1,\nu-1]]$
$\displaystyle\geq\sup_{\nu\geq
0}\sup_{\bm{S}}\text{esssup}\widetilde{\mathbb{E}}^{\bm{S},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]]$
$\displaystyle=\widetilde{\text{WADD}}(\tau).$ (54)

Step 3. The last step is to show that for any $\tau$ and any $\bm{\beta}$,
$\widetilde{\text{WADD}}(\tau)\geq\widetilde{\text{WADD}}_{\bm{\beta}}(\tau)$.
Firstly, we will show that

$\displaystyle\sup_{\bm{S}}\text{esssup}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}$
$\displaystyle\geq\text{esssup}\sup_{\bm{S}}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}.$
(55)

Let
$c=\sup_{\bm{S}}\text{esssup}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}$.
Denote by $\Lambda_{\bm{S}}$ the collection of all trajectory ${\bm{S}}$. For
any ${\bm{S}}$, we have that

$\displaystyle\widetilde{\mathbb{P}}^{\nu}\Big{(}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}>c\Big{)}=0.$
(56)

Since $\Lambda_{\bm{S}}$ is countable, it then follows that

$\displaystyle\widetilde{\mathbb{P}}^{\nu}\Big{(}\sup\limits_{\bm{S}}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}>c\Big{)}$
$\displaystyle\leq\widetilde{\mathbb{P}}^{\nu}\Big{(}\cup_{{\bm{S}}\in\Lambda_{\bm{S}}}\big{\\{}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}>c\big{\\}}\Big{)}=0.$

Therefore,

$\displaystyle c$
$\displaystyle=\sup\limits_{{\bm{S}}}\text{esssup}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}$
$\displaystyle\geq\text{esssup}\sup\limits_{{\bm{S}}}\widetilde{\mathbb{E}}^{\bm{S},\nu}\big{[}(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]\big{]}.$
(57)

For any $T\geq\nu+1$, we have that

$\displaystyle\sup_{{\bm{S}}}\sum_{t=\nu+1}^{T}(t-\nu)\widetilde{\mathbb{P}}^{S[\nu],...,S[T]}(\tau=t|\widetilde{\mathbf{X}}^{n}[1,\nu-1])$
$\displaystyle\geq\sum_{t=\nu+1}^{T}(t-\nu)\sum_{\\{S[\nu],...,S[T]\\}\in\Lambda_{\bm{S}}^{\bigotimes(T-\nu+1)}}\beta_{S[\nu]}\times\cdots\times\beta_{S[T]}\widetilde{\mathbb{P}}^{S[\nu],...,S[T]}(\tau=t|\widetilde{\mathbf{X}}^{n}[1,\nu-1])$
$\displaystyle=\sum_{t=\nu+1}^{T}(t-\nu)\widetilde{\mathbb{P}}^{\bm{\beta},\nu}(\tau=t|\widetilde{\mathbf{X}}^{n}[1,\nu-1]),$
(58)

where $\widetilde{\mathbb{P}}^{S[\nu],...,S[T]}$ denotes the probability
measure when the trajectory is ${\bm{S}}$, the observations from time $\nu$ to
time $T$ are generated according to
$\widetilde{{\mathbb{P}}}^{S[\nu]},...,\widetilde{\mathbb{P}}^{S[T]}$. As
$T\rightarrow\infty$, we have

$\displaystyle\sup_{\bm{S}}\widetilde{\mathbb{E}}^{\bm{S},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]]$
$\displaystyle\geq\widetilde{\mathbb{E}}^{\bm{\beta},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]].$
(59)

From (D) and (D), we have that

$\displaystyle\widetilde{\text{WADD}}(\tau)$
$\displaystyle=\sup\limits_{\bm{S}}\text{esssup}\widetilde{\mathbb{E}}^{\bm{S},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]]$
$\displaystyle\geq\text{esssup}\widetilde{\mathbb{E}}^{\bm{\beta},\nu}[(\tau-\nu)^{+}|\widetilde{\mathbf{X}}^{n}[1,\nu-1]]$
$\displaystyle=\widetilde{\text{WADD}}_{\bm{\beta}}(\tau).$ (60)

Combining (D) and (D), we have that for any $\tau$ and $\bm{\beta}$

$\displaystyle\text{WADD}(\tau)\geq\widetilde{\text{WADD}}(\tau)\geq\widetilde{\text{WADD}}_{\bm{\beta}}(\tau).$
(61)

For any $T\geq 1$, we have that

$\displaystyle\inf_{\begin{subarray}{c}\\{\sigma_{1}^{0},...,\sigma_{T}^{0}\\}\\\
\in{\mathcal{S}_{n,0}}^{\bigotimes
T}\end{subarray}}\sum_{t=1}^{T}t\mathbb{P}^{\infty}_{\sigma_{1}^{0},...,\sigma_{T}^{0}}(\tau=t)$
$\displaystyle\leq\sum_{t=1}^{T}t\frac{1}{\mid{\mathcal{S}_{n,0}}\mid^{T}}\sum\limits_{\begin{subarray}{c}\\{\sigma_{1}^{0},...,\sigma_{T}^{0}\\}\\\
\in{\mathcal{S}_{n,0}}^{\bigotimes
T}\end{subarray}}\mathbb{P}^{\infty}_{\sigma_{1}^{0},...,\sigma_{T}^{0}}(\tau=t)$
$\displaystyle=\sum_{t=1}^{T}t\widetilde{\mathbb{P}}^{\infty}(\tau=t).$ (62)

As $T\rightarrow\infty$, we have that
$\text{ARL}(\tau)\leq\widetilde{\text{ARL}}(\tau)$.

Therefore, for any stopping time $\tau$ satisfying
$\text{ARL}(\tau)\geq\gamma$, it will also satisfy
$\widetilde{\text{ARL}}(\tau)\geq\gamma$. We then have that
$\mathcal{C}_{\gamma}\subseteq\widetilde{\mathcal{C}}_{\gamma}$.

Since (61) holds for any $\bm{\beta}$, it holds for $\bm{\beta^{*}}$. Problem
(D) is a classical QCD problem. From the asymptotic lower bound analysis in
[37], we have that for large $\gamma$,

$\displaystyle\inf_{\tau\in\mathcal{C}_{\gamma}}\text{WADD}(\tau)\geq\inf_{\tau\in\widetilde{\mathcal{C}}_{\gamma}}\widetilde{\text{WADD}}_{\bm{\beta}^{*}}(\tau)\sim\frac{\log\gamma}{I_{\bm{\beta^{*}}}}(1+o(1)).$
(63)

##  Appendix E Proof of Lemma 1

The minimization of $I_{\bm{\beta}}$ is to solve the following problem:

$\displaystyle\inf_{\bm{\beta}}\quad I_{\bm{\beta}}\quad$
$\displaystyle\text{s.t.}\quad-\beta_{k}$ $\displaystyle\leq 0,\ \text{for}\
k\in[1,K]$ (64) $\displaystyle\sum_{k=1}^{K}\beta_{k}-1$ $\displaystyle=0.$

This is a convex optimization problem with linear constraints. Define the
Lagrange function $L(\bm{\beta},\eta,\bm{\mu})$:

$\displaystyle
L(\bm{\beta},\eta,\bm{\mu})=I_{\bm{\beta}}+\eta\Big{(}\sum_{k=1}^{K}\beta_{k}-1\Big{)}-\sum_{k=1}^{K}\mu_{k}\beta_{k}.$
(65)

The minimizer $\bm{\beta^{*}}$ satisfies the Karush–Kuhn–Tucker(KKT)
conditions: $\mu_{k},\ \beta_{k}^{*}\geq 0,\ \mu_{k}\beta_{k}^{*}=0,\
\sum_{k=1}^{K}\beta_{k}^{*}-1=0$ and

$\displaystyle\frac{\partial
L}{\partial\beta_{k}}|_{\bm{\beta^{*}}}=\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}+1+\eta-\mu_{k}=0,$
(66)

where $\widetilde{\mathbb{E}}^{k}$ denotes the expectation under the
distribution $\widetilde{\mathbb{P}}^{k}$.

When $\beta_{k}^{*}>0$, we have $\mu_{k}=0$. Therefore, for any
$k,k^{\prime}\in\mathcal{K}$ with $\beta_{k}^{*},\beta_{k^{\prime}}^{*}>0$, we
have

$\displaystyle\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}=\widetilde{\mathbb{E}}^{k^{\prime}}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}=-(1+\eta).$

The set $\mathcal{K}$ can be divided into two disjoint parts $\mathcal{K}_{1}$
and $\mathcal{K}_{2}$. All $k$ in $\mathcal{K}_{1}$ satisfy $\beta_{k}^{*}>0$
while all $k$ in $\mathcal{K}_{2}$ have $\beta_{k}^{*}=0$. We have that

$\displaystyle I_{\bm{\beta^{*}}}$
$\displaystyle=\sum_{k=1}^{K}\beta_{k}^{*}\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
$\displaystyle=\sum_{k\in
K_{1}}\beta_{k}^{*}\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}$
$\displaystyle=\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]},\
\text{for all}\ k\in\mathcal{K}_{1}.$ (67)

For all $k\in\mathcal{K}_{2}$, $\beta_{k}^{*}=0$. By the KKT conditions, we
have that $\mu_{k}\geq 0$. Therefore, for any $k\in\mathcal{K}_{2}$,
$\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}+1+\eta=\mu_{k}\geq
0.$ We then have that for any $k\in\mathcal{K}_{2}$,

$\displaystyle\widetilde{\mathbb{E}}^{k}\Big{[}\log\frac{\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}(X^{n})}{\widetilde{\mathbb{P}}_{0}(X^{n})}\Big{]}\geq
I_{\bm{\beta^{*}}}.$ (68)

##  Appendix F Proof of Theorem 5

Due to the fact that the test statistic $\max_{1\leq k\leq
t+1}\sum_{i=k}^{t}\ell_{\bm{\beta}^{*}}(X^{n}_{i})$ has initial value 0 and
remains non-negative, the delay is largest when the change happens at $\nu=0$.
Therefore, for any ${\bm{S}}$, we have that

$\displaystyle\text{WADD}_{\bm{S}}(T_{\bm{\beta^{*}}})$
$\displaystyle=\sup_{\nu\geq
0}\sup_{\Omega_{\bm{S}}}\text{esssup}\mathbb{E}_{\Omega_{\bm{S}}}^{{\bm{S}},\nu}\big{[}(T_{\bm{\beta^{*}}}-\nu)^{+}\mid\mathbf{X}^{n}[1,\nu-1]\big{]}$
$\displaystyle=\sup_{\Omega_{\bm{S}}}\mathbb{E}^{{\bm{S}},0}_{\Omega_{\bm{S}}}[T_{\bm{\beta^{*}}}].$
(69)

For any $T\geq\nu+1$, we have that

$\displaystyle\sup_{\begin{subarray}{c}\\{\sigma_{1}^{S[1]},\cdots,\sigma_{T}^{S[T]}\\}\\\
\in\mathcal{S}_{n,S[1]}\times,\cdots,\times\mathcal{S}_{n,S[T]}\end{subarray}}\sum_{t=1}^{T}t\mathbb{P}_{\sigma_{1}^{S[1]},\cdots,\sigma_{T}^{S[T]}}^{{\bm{S}},0}(T_{\bm{\beta^{*}}}=t)$
$\displaystyle=\sum_{t=1}^{T}t\frac{1}{\mid\mathcal{S}_{n,S[1]}\mid\times\cdots\times\mid\mathcal{S}_{n,S[T]}\mid}\sum\limits_{\begin{subarray}{c}\\{\sigma_{1}^{S[1]},\cdots,\sigma_{T}^{S[T]}\\}\\\
\in\mathcal{S}_{n,S[1]}\times,\cdots,\times\mathcal{S}_{n,S[T]}\end{subarray}}\mathbb{P}_{\sigma_{1}^{S[1]},\cdots,\sigma_{T}^{S[T]}}^{{\bm{S}},0}(T_{\bm{\beta^{*}}}=t)$
$\displaystyle=\sum_{t=1}^{T}t\widetilde{\mathbb{P}}^{\bm{S},0}(T_{\bm{\beta^{*}}}=t).$
(70)

As $T\rightarrow\infty$, we have that

$\displaystyle\sup_{\Omega_{\bm{S}}}\mathbb{E}^{{\bm{S}},0}_{\Omega_{\bm{S}}}[T_{\bm{\beta^{*}}}]=\widetilde{\mathbb{E}}^{\bm{S},0}[T_{\bm{\beta^{*}}}]=\widetilde{\text{WADD}_{\bm{S}}}(T_{\bm{\beta^{*}}}).$
(71)

For any ${\bm{S}}$, we have
$\text{WADD}_{\bm{S}}(T_{\bm{\beta^{*}}})=\widetilde{\text{WADD}_{\bm{S}}}(T_{\bm{\beta^{*}}})$.
Therefore,
$\text{WADD}(T_{\bm{\beta^{*}}})=\widetilde{\text{WADD}}(T_{\bm{\beta^{*}}})$
by taking sup over ${\bm{S}}$ on both sides. It then follows that

$\displaystyle\text{WADD}(T_{\bm{\beta^{*}}})=\widetilde{\text{WADD}}(T_{\bm{\beta^{*}}})=\sup_{\bm{S}}\widetilde{\mathbb{E}}^{\bm{S},0}[T_{\bm{\beta^{*}}}].$
(72)

Let $0<\epsilon<I_{\bm{\beta^{*}}}$ and
$n_{b}=\frac{b}{I_{\bm{\beta^{*}}}-\epsilon}$. For any trajectory ${\bm{S}}$,
from the sum-integral inequality, we have that

$\displaystyle\widetilde{\mathbb{E}}^{\bm{S},0}\Big{[}\frac{T_{\bm{\beta^{*}}}}{n_{b}}\Big{]}$
$\displaystyle=\int_{0}^{\infty}\widetilde{\mathbb{P}}^{\bm{S},0}\Big{(}\frac{T_{\bm{\beta^{*}}}}{n_{b}}>x\Big{)}\mathrm{d}x$
$\displaystyle\leq\sum^{\infty}_{t=1}\widetilde{\mathbb{P}}^{\bm{S},0}(T_{\bm{\beta^{*}}}>tn_{b})+1.$
(73)

For any ${\bm{S}}$, we have that

$\displaystyle\widetilde{\mathbb{P}}^{\bm{S},0}(T_{\bm{\beta^{*}}}>tn_{b})$
$\displaystyle=\widetilde{\mathbb{P}}^{\bm{S},0}\bigg{(}\max_{1\leq k\leq
tn_{b}}\max_{1\leq i\leq
k}\sum_{j=i}^{k}\ell_{\bm{\beta^{*}}}(X^{n}_{j})<b\bigg{)}$
$\displaystyle\leq\widetilde{\mathbb{P}}^{\bm{S},0}\bigg{(}\max_{1\leq i\leq
mn_{b}}\sum_{j=i}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})<b,\forall
m\in[t]\bigg{)}$
$\displaystyle\leq\widetilde{\mathbb{P}}^{\bm{S},0}\bigg{(}\sum_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})<b,\forall
m\in[t]\bigg{)}$
$\displaystyle=\widetilde{\mathbb{P}}^{\bm{S},0}\Bigg{(}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}<I_{\bm{\beta^{*}}}-\epsilon,\forall
m\in[t]\Bigg{)}$
$\displaystyle=\prod_{m=1}^{t}\widetilde{\mathbb{P}}^{\bm{S},0}\Bigg{(}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}<I_{\bm{\beta^{*}}}-\epsilon\Bigg{)}.$
(74)

It then follows that

$\displaystyle\sup_{\bm{S}}\sum_{t=1}^{\infty}\widetilde{\mathbb{P}}^{\bm{S},0}(T_{\bm{\beta^{*}}}>tn_{b})$
$\displaystyle\leq\sup_{\bm{S}}\sum_{t=1}^{\infty}\prod_{m=1}^{t}\widetilde{\mathbb{P}}^{\bm{S},0}\bigg{(}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}<I_{\bm{\beta^{*}}}-\epsilon\bigg{)}.$

Then we will bound
$\widetilde{\mathbb{P}}^{\bm{S},0}\bigg{(}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}<I_{\bm{\beta^{*}}}-\epsilon\bigg{)}$.

Let
$I_{{\bm{S}}_{m}}=\widetilde{\mathbb{E}}^{\bm{S},0}\bigg{[}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta}^{*}}(X^{n}_{j})}{n_{b}}\bigg{]}$.
From (E) and (68), we have that

$\displaystyle I_{{\bm{S}}_{m}}$
$\displaystyle=\widetilde{\mathbb{E}}^{\bm{S},0}\Bigg{[}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta}^{*}}(X^{n}_{j})}{n_{b}}\Bigg{]}$
$\displaystyle=\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\widetilde{\mathbb{E}}^{S[j]}\bigg{[}\frac{\ell_{\bm{\beta}^{*}}(X^{n}_{j})}{n_{b}}\bigg{]}$
$\displaystyle=\frac{1}{n_{b}}\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\widetilde{\mathbb{E}}^{S[j]}\big{[}\ell_{\bm{\beta}^{*}}(X^{n}_{j})\big{]}\geq
I_{\bm{\beta^{*}}}.$ (75)

It then follows that for any ${\bm{S}}$ and $m$

$\displaystyle\widetilde{\mathbb{P}}^{\bm{S},0}\Bigg{(}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}<I_{\bm{\beta^{*}}}-\epsilon\Bigg{)}$
$\displaystyle\leq\widetilde{\mathbb{P}}^{\bm{S},0}\Bigg{(}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}<I_{{\bm{S}}_{m}}-\epsilon\Bigg{)}$
$\displaystyle\leq\widetilde{\mathbb{P}}^{\bm{S},0}\Bigg{(}\Bigg{|}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}-I_{{\bm{S}}_{m}}\Bigg{|}>\epsilon\Bigg{)}.$
(76)

Assume that
$\max_{k\in[1,K]}\widetilde{\mathbb{E}}^{k}\bigg{[}\ell_{\bm{\beta^{*}}}(X^{n})^{2}\bigg{]}<\infty.$
Let
$\sigma^{2}=\max_{k\in[1,K]}\text{Var}_{\widetilde{\mathbb{P}}^{k}}(\ell_{\bm{\beta^{*}}}(X^{n}))$
where $\text{Var}_{\widetilde{\mathbb{P}}^{k}}$ denotes the variance under the
distribution $\widetilde{\mathbb{P}}^{k}$. By Chebychev’s inequality,

$\displaystyle\widetilde{\mathbb{P}}^{\bm{S},0}\Bigg{(}\Bigg{|}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}-I_{{\bm{S}}_{m}}\Bigg{|}>\epsilon\Bigg{)}$
$\displaystyle\leq\text{Var}_{\widetilde{\mathbb{P}}^{\bm{S}}}\Bigg{(}\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\ell_{\bm{\beta^{*}}}(X^{n}_{j})}{n_{b}}\Bigg{)}\frac{1}{\epsilon^{2}}$
$\displaystyle=\frac{1}{\epsilon^{2}n_{b}^{2}}\sum_{j=(m-1)n_{b}+1}^{mn_{b}}\text{Var}_{\widetilde{\mathbb{P}}^{S[j]}}(\ell_{\bm{\beta^{*}}}(X^{n}_{j}))$
$\displaystyle\leq\frac{\sum\limits_{j=(m-1)n_{b}+1}^{mn_{b}}\sigma^{2}}{n_{b}^{2}\epsilon^{2}}=\frac{\sigma^{2}}{n_{b}\epsilon^{2}}.$
(77)

Let $\delta=\frac{\sigma^{2}}{n_{b}\epsilon^{2}}$. From (F) and (F), we have
that

$\displaystyle\sup_{\bm{S}}\widetilde{\mathbb{E}}^{\bm{S},0}\Big{[}\frac{T_{\bm{\beta^{*}}}}{n_{b}}\Big{]}$
$\displaystyle\leq
1+\sup_{\bm{S}}\sum^{\infty}_{t=1}\widetilde{\mathbb{P}}^{\bm{S},0}(T_{\bm{\beta^{*}}}>tn_{b})$
$\displaystyle\leq
1+\sum_{t=1}^{\infty}(\frac{\sigma^{2}}{n_{b}\epsilon^{2}})^{t}$
$\displaystyle=1+\sum_{t=1}^{\infty}\delta^{t}=\frac{1}{1-\delta}.$ (78)

Therefore, we have

$\displaystyle\sup_{\bm{S}}\widetilde{\mathbb{E}}^{\bm{S},0}\Big{[}T_{\bm{\beta^{*}}}\Big{]}\leq\frac{b}{(I_{\bm{\beta^{*}}}-\epsilon)(1-\delta)}.$
(79)

(79) holds for all $\epsilon$. It then follows that as $b\rightarrow\infty$,

$\displaystyle\text{WADD}(T_{\bm{\beta^{*}}})=\sup_{\bm{S}}\widetilde{\mathbb{E}}^{\bm{S},0}\Big{[}T_{\bm{\beta^{*}}}\Big{]}\leq\frac{b}{I_{\bm{\beta^{*}}}}(1+o(1)).$
(80)

For the ARL lower bound, for any $T\geq 1$, we have that

$\displaystyle\inf_{\begin{subarray}{c}\\{\sigma_{1}^{0},...,\sigma_{T}^{0}\\}\\\
\in{\mathcal{S}_{n,0}}^{\bigotimes
T}\end{subarray}}\sum_{t=1}^{T}t\mathbb{P}^{\infty}_{\sigma_{1}^{0},...,\sigma_{T}^{0}}(T_{\bm{\beta}^{*}}=t)$
$\displaystyle=\sum_{t=1}^{T}t\frac{1}{\mid{\mathcal{S}_{n,0}}\mid^{T}}\sum\limits_{\begin{subarray}{c}\\{\sigma_{1}^{0},...,\sigma_{T}^{0}\\}\\\
\in{\mathcal{S}_{n,0}}^{\bigotimes
T}\end{subarray}}\mathbb{P}^{\infty}_{\sigma_{1}^{0},...,\sigma_{T}^{0}}(T_{\bm{\beta}^{*}}=t)$
$\displaystyle=\sum_{t=1}^{T}t\widetilde{\mathbb{P}}^{\infty}(T_{\bm{\beta}^{*}}=t).$
(81)

As $T\rightarrow\infty$, we have that
$\text{WARL}(T_{\bm{\beta}^{*}})=\widetilde{\text{ARL}}(T_{\bm{\beta}^{*}}).$
$T_{\bm{\beta}^{*}}$ is the CuSum algorithm for a simple QCD problem with pre-
change distribution $\widetilde{\mathbb{P}}_{0}$ and post-change distribution
$\widetilde{\mathbb{P}}^{\bm{\beta^{*}}}$. From the optimal property of CuSum
algorithm in [39] and [41], we have that when $b=\log\gamma$,
$\text{WARL}(T_{\bm{\beta}^{*}})=\widetilde{\text{ARL}}(T_{\bm{\beta}^{*}})\geq\gamma.$

## References

  * [1] Z. Sun and S. Zou, “Quickest dynamic anomaly detection in anonymous heterogeneous sensor networks,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 106–111, 2021.
  * [2] T. E. Humphreys, B. M. Ledvina, M. L. Psiaki, B. W. O’Hanlon, P. M. Kintner, et al., “Assessing the spoofing threat: Development of a portable gps civilian spoofer,” in Proceedings of the 21st International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2008), pp. 2314–2325, 2008.
  * [3] L. Keller, M. J. Siavoshani, C. Fragouli, K. Argyraki, and S. Diggavi, “Identity aware sensor networks,” in Proc. Int. Conf. Commun., Computing Control Appl., pp. 2177–2185, IEEE, 2009.
  * [4] W. N. Chen and I. H. Wang, “Anonymous heterogeneous distributed detection: Optimal decision rules, error exponents, and the price of anonymity,” IEEE Trans. Inform. Theory, vol. 65, no. 11, pp. 7390–7406, 2019.
  * [5] W. Li and Y. Huang, “Bandwidth-constrained distributed quickest change detection in heterogeneous sensor networks: Anonymous vs non-anonymous settings,” arXiv preprint arXiv: 2202.02697, 2022.
  * [6] S. Marano and P. K. Willett, “Algorithms and fundamental limits for unlabeled detection using types,” IEEE Trans. Signal Proc., vol. 67, no. 8, pp. 2022–2035, 2019.
  * [7] S. Marano and P. Willett, “Making decisions by unlabeled bits,” IEEE Trans. Signal Proc., vol. 68, pp. 2935–2947, 2020.
  * [8] J. Unnikrishnan, S. Haghighatshoar, and M. Vetterli, “Unlabeled sensing with random linear measurements,” IEEE Trans. Inform. Theory, vol. 64, no. 5, pp. 3237–3253, 2018.
  * [9] S. Haghighatshoar and G. Caire, “Signal recovery from unlabeled samples,” IEEE Trans. Signal Proc., vol. 66, no. 5, pp. 1242–1257, 2017.
  * [10] A. Abid, A. Poon, and J. Zou, “Linear regression with shuffled labels,” arXiv preprint arXiv:1705.01342, 2017.
  * [11] V. Emiya, A. Bonnefoy, L. Daudet, and R. Gribonval, “Compressed sensing with unknown sensor permutation,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), pp. 1040–1044, IEEE, 2014.
  * [12] Z. Liu and J. Zhu, “Signal detection from unlabeled ordered samples,” IEEE Commun. Lett., vol. 22, no. 12, pp. 2431–2434, 2018.
  * [13] A. Pananjady, M. J. Wainwright, and T. A. Courtade, “Linear regression with shuffled data: Statistical and computational limits of permutation recovery,” IEEE Trans. Inform. Theory, vol. 64, no. 5, pp. 3286–3300, 2017\.
  * [14] G. Elhami, A. Scholefield, B. B. Haro, and M. Vetterli, “Unlabeled sensing: Reconstruction algorithm and theoretical guarantees,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), pp. 4566–4570, Ieee, 2017\.
  * [15] Y. M. Lu and M. N. Do, “A theory for sampling signals from a union of subspaces,” IEEE Trans. Signal Proc., vol. 56, no. 6, pp. 2334–2345, 2008\.
  * [16] G. Wang, J. Zhu, R. S. Blum, P. Willett, S. Marano, V. Matta, and P. Braca, “Signal amplitude estimation and detection from unlabeled binary quantized samples,” IEEE Trans. Signal Proc., vol. 66, no. 16, pp. 4291–4303, 2018\.
  * [17] Z. Sun, S. Zou, R. Zhang, and Q. Li, “Quickest change detection in anonymous heterogeneous sensor networks,” IEEE Trans. Signal Proc., vol. 70, pp. 1041–1055, 2022.
  * [18] G. Rovatsos, G. V. Moustakides, and V. V. Veeravalli, “Quickest detection of moving anomalies in sensor networks,” IEEE J. Sel. Areas Inf. Theory, vol. 2, no. 2, pp. 762–773, 2021.
  * [19] A. G. Tartakovsky and V. V. Veeravalli, “Change-point detection in multichannel and distributed systems,” Applied Sequential Methodologies: Real-World Examples with Data Analysis, vol. 173, pp. 339–370, 2004.
  * [20] 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 Trans. Signal Proc., vol. 54, no. 9, pp. 3372–3382, 2006.
  * [21] Y. Mei, “Efficient scalable schemes for monitoring a large number of data streams,” Biometrika, vol. 97, no. 2, pp. 419–433, 2010.
  * [22] Y. Xie and D. Siegmund, “Sequential multi-sensor change-point detection,” Ann. Statist., pp. 670–692, 2013.
  * [23] G. Fellouris and G. Sokolov, “Second-order asymptotic optimality in multisensor sequential change detection,” IEEE Trans. Inform. Theory, vol. 62, no. 6, pp. 3662–3675, 2016.
  * [24] V. Raghavan and V. V. Veeravalli, “Quickest change detection of a Markov process across a sensor array,” IEEE Trans. Inform. Theory, vol. 56, no. 4, pp. 1961–1981, 2010.
  * [25] O. Hadjiliadis, H. Zhang, and H. V. Poor, “One shot schemes for decentralized quickest change detection,” IEEE Trans. Inform. Theory, vol. 55, no. 7, pp. 3346–3359, 2009.
  * [26] M. Ludkovski, “Bayesian quickest detection in sensor arrays,” Seq. Anal., vol. 31, no. 4, pp. 481–504, 2012.
  * [27] S. Zou, V. V. Veeravalli, J. Li, and D. Towsley, “Quickest detection of dynamic events in networks,” IEEE Trans. Inform. Theory, vol. 66, no. 4, pp. 2280–2295, 2020.
  * [28] V. V. Veeravalli, “Decentralized quickest change detection,” IEEE Trans. Inform. Theory, vol. 47, no. 4, pp. 1657–1665, 2001.
  * [29] A. G. Tartakovsky and V. V. Veeravalli, “Asymptotically optimal quickest change detection in distributed sensor systems,” Seq. Anal., vol. 27, no. 4, pp. 441–475, 2008.
  * [30] S. Zou, V. V. Veeravalli, J. Li, D. Towsley, and A. Swami, “Distributed quickest detection of significant events in networks,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), pp. 8454–8458, 2019.
  * [31] L. Xie, S. Zou, Y. Xie, and V. V. Veeravalli, “Sequential (quickest) change detection: Classical results and new directions,” IEEE J. Sel. Areas Inf. Theory, vol. 2, no. 2, pp. 494–514, 2021.
  * [32] G. Rovatsos, G. Moustakides, and V. Veeravalli, “Quickest detection of a dynamic anomaly in a sensor network,” in Proc. Asilomar Conf. Signals, Systems and Computers, pp. 98–102, 2019.
  * [33] G. Rovatsos, S. Zou, and V. V. Veeravalli, “Sequential algorithms for moving anomaly detection in networks,” Seq. Anal., vol. 39, no. 1, pp. 6–31, 2020.
  * [34] S. Zou, G. Fellouris, and V. V. Veeravalli, “Quickest change detection under transient dynamics: Theory and asymptotic analysis,” IEEE Trans. Inform. Theory, vol. 65, no. 3, pp. 1397–1412, 2018.
  * [35] R. Zhang, R. Yao, Y. Xie, and F. Qiu, “Quickest detection of cascading failure,” arXiv preprint arXiv:1911.05610, 2019.
  * [36] D. Siegmund and E. S. Venkatraman, “Using the generalized likelihood ratio statistic for sequential detection of a change-point,” Ann. Statist., pp. 255–271, 1995.
  * [37] T. L. Lai, “Information bounds and quick detection of parameter changes in stochastic systems,” IEEE Trans. Inform. Theory, vol. 44, no. 7, pp. 2917–2929, 1998.
  * [38] T. Banerjee and V. V. Veeravalli, “Data-efficient minimax quickest change detection with composite post-change distribution,” IEEE Trans. Inform. Theory, vol. 61, no. 9, pp. 5172–5184, 2015.
  * [39] G. Lorden, “Procedures for reacting to a change in distribution,” Ann. Math. Statist., vol. 42, no. 6, pp. 1897–1908, 1971.
  * [40] D. Williams, Probability with Martingales.  Cambridge University Press, 1991.
  * [41] G. V. Moustakides, “Optimal stopping times for detecting changes in distributions,” Ann. Statist., vol. 14, no. 4, pp. 1379–1387, 1986.