# Round Robin Active Sequential Change Detection
for Dependent Multi-Channel Data

Anamitra Chaudhuri, Georgios Fellouris, and Ali Tajer This work was supported
in part by the U.S. National Science Foundation through grant NSF ATD
1737962.The results in this paper were presented in part at the 2021 IEEE
International Symposium on Information Theory (ISIT) [1]. Anamitra Chaudhuri
is with the Department of Statistics, Texas A&M University, College Station,
TX 77843 (e-mail: ac27@tamu.edu).Georgios Fellouris is with the Department of
Statistics, University of Illinois at Urbana Champaign, Champaign, IL 61820
(e-mail: fellouri@illinois.edu).Ali Tajer is with the Department of
Electrical, Computer, and Systems Engineering, Rensselaer Polytechnic
Institute, Troy, NY 12180 (e-mail: tajer@ecse.rpi.edu).

###### Abstract

This paper considers the problem of sequentially detecting a change in the
joint distribution of multiple data sources under a sampling constraint.
Specifically, the channels or sources generate observations that are
independent over time, but not necessarily independent at any given time
instant. The sources follow an initial joint distribution, and at an unknown
time instant, the joint distribution of an unknown subset of sources changes.
Importantly, there is a hard constraint that only a fixed number of sources
are allowed to be sampled at each time instant. The goal is to sequentially
observe the sources according to the constraint, and stop sampling as quickly
as possible after the change while controlling the false alarm rate below a
user-specified level. The sources can be selected dynamically based on the
already collected data, and thus, a policy for this problem consists of a
joint sampling and change-detection rule. A non-randomized policy is studied,
and an upper bound is established on its worst-case conditional expected
detection delay with respect to both the change point and the observations
from the affected sources before the change. It is shown that, in certain
cases, this rule achieves first-order asymptotic optimality as the false alarm
rate tends to zero, simultaneously under every possible post-change
distribution and among all schemes that satisfy the same sampling and false
alarm constraints. These general results are subsequently applied to the
problems of (i) detecting a change in the marginal distributions of (not
necessarily independent) information sources, and (ii) detecting a change in
the covariance structure of Gaussian information sources.

###### Index Terms:

Sequential change-point detection, Sampling constraint, Asymptotic optimality,
CUSUM, Quickest online change-point detection, Multi-channel detection,
Dependent data streams, Correlation change.

##  I Introduction

In statistical decision-making, growth in the data’s complexity, dimension,
and scale increases the data acquisition and computational costs, if not
rendering them prohibitive altogether. Enforcing proper data-acquisition
(sampling) constraints is a natural measure to contain such costs. For
example, when the data of interest become available at multiple locations or
sources, it may be practical and economically efficient to take observations
from only a small fraction of these locations. There are many areas in science
and engineering where these types of scenarios arise, e.g., multi-sensor
networks, surveillance systems, cyber security, and power grids. Such sampling
constraints have been considered in the sequential anomaly
detection/identification problem [2, 3, 4, 5, 6], where the processes of
interest are assumed to be statistically independent, and the goal is to
identify the anomalous ones. Similar constraints are imposed in [7] and [8],
where only one source is sampled at each time instant, and observations from
different sources are assumed to exhibit temporal dependence. Furthermore,
such sampling constraints can be embedded into the general framework of
“sequential design of experiments” (see, e.g., [9] and [10]).

A related problem to sequential testing is that of sequential change
detection, where the goal is to detect as quickly as possible a change in the
distribution of the underlying process [11, 12]. The problem of sequential
change detection with controlled sensing, that is, in the presence of a set of
actions that can influence the distribution of the observations, has been
considered in [13] and [14]. The concrete setup where there are multiple
independent sources of observations, the change affects the distributions of
an unknown subset of them, and it is possible to sample only a fixed number of
sources at each time instant has been considered in [15, 16, 17, 18, 19, 20].
In the first four references, the sampled processes are statistically
independent, whereas in the latter, the change can affect the dependence
structure of a subset of these processes. Some other relevant works in the
sequential literature involving inference regarding the observed processes’
dependence structure are [21, 22, 23, 24].

In this paper, we assume that there are $K$ sources generating data that are
independent over time but not necessarily across sources. That is, the samples
from two different sources, generated at the same time, are not necessarily
independent. We assume that the samples initially follow a completely
specified joint distribution until an unknown time instant at which the joint
distribution of an unknown subset of sources changes. The post-change regime
is not necessarily completely specified, but a finite set of post-change
alternatives is postulated. The objective is to sequentially detect this
change as quickly as possible while controlling the false alarm rate, under
the constraint that only $m$ sources can be sampled at each time instant,
where $m$ is a user-specified integer smaller than $K$.

This problem can be embedded into the general framework of sequential change
detection problems with controlled sensing, where the action at each time
instant is the selection of the sampled sources. In this context, an
asymptotically optimal procedure can be obtained by employing a sufficiently
frequent random exploration of the action space and using a sufficiently large
memory of past observations [14]. Our focus in the present paper is on a
computationally simple procedure that does not employ any randomization and
does not require memory of any past observations. According to it, a family of
size-$m$ subsets of sources is specified, and its members, to which we refer
as units, are sampled in a round-robin manner. For each unit, a cumulative sum
(CUSUM)-like statistic, which enjoys a recursive structure, is computed, and
if its value exceeds a pre-specified threshold, then an alarm indicating that
the change has occurred is raised; if its value becomes smaller or equal to 0,
the next unit is sampled; otherwise, the same unit continues being sampled.

The motivating question for this paper is the following: under what
conditions, if any, is this computationally simple procedure also
statistically efficient? To answer this and quantify this test’s detection
performance, we adopt a version of Lorden’s criterion [25], in which the
worst-case conditional expected detection delay is considered with respect to
the change-point and the data until the change only from the affected sources.
Then, under certain conditions on the pre-and post-change distributions, we
establish a non-asymptotic upper bound for the above policy with respect to
this delay metric. Subsequently, we show that, in certain cases, this policy
is first-order asymptotically optimal, as the false alarm rate goes to $0$,
within the class of all procedures that satisfy the user-specified sampling
and false alarm constraints. In particular, this occurs if (i) the post-change
distribution is completely specified for every unit, (ii) either a single unit
is affected by the change or the signal-to-noise ratio is the same for all
affected units, and (iii) the family of units includes the size-$m$ subset of
sources that is the affected the most by the change.

We specialize this general asymptotic theory to two concrete setups. The first
one is the problem of detecting a change in the marginal distributions of
multiple, not necessarily independent data sources. In fact, the policy that
we study in this work is inspired by, and also generalizes, the ones
considered in [5], and more recently in [15, 17]. Specifically, it reduces to
the policy presented in [15] when, in particular, (i) it is possible to sample
_only one of them_ at each time instant $(m=1)$, and (ii) there is a
completely specified post-change distribution for each source. In [15], this
scheme was shown to be second-order asymptotically optimal, i.e., to achieve
up to a constant term the optimal worst-case delay that would be achievable
were all sources sampled at all times, when only one source is affected by the
change. On the contrary, we do not compare the policy’s performance with that
of the optimal policy in the full-sampling case, which is not attainable in
general. Instead, we compare it with the optimal one in the family of policies
that satisfy the same sampling constraints. Thus, we show that the rule in
[15] is first-order asymptotically optimal not only when a single source is
affected by the change but also when any possible number of data sources
experience the change as long as the signal-to-noise ratio is the same in all
of them.

The formulation in the paper is not limited to the case that the change
affects the marginal distributions of the sources. In fact, one of the
motivating problems for this work is the detection of a change in the
dependence structure. Thus, the second concrete setup to which we apply the
general theory is that of detecting a change in the correlation structure of
multiple Gaussian information sources. The theoretical results in this setup
are also illustrated in certain simulation studies, which provide further
insights.

The remainder of our paper is organized as follows. In Section II, we
formulate the problem. In Section III, we establish a general universal
asymptotic lower bound on the worst-case conditional expected detection delay.
In Section IV, we introduce and analyze the policy that we study in the
present work. Next, we apply the previous results to the problems of (i)
detecting a change in the marginal distributions of multiple, not necessarily
independent, sources in Section V, and (ii) detecting a change in the
correlation structure of Gaussian information sources in Section VI. In
Section VII, we present the results of three simulation studies, and in
Section VIII, we provide concluding discussions. The proofs and the technical
details are relegated to the appendices.

We collect some notations that are used throughout the paper. We denote the
set of natural numbers by $\mathbb{N}$, i.e., $\mathbb{N}:=\\{1,2,\dots\\}$,
and for any $n\in\mathbb{N}$ we set $[n]:=\\{1,\dots,n\\}$. We denote the set
of real numbers by $\mathbb{R}$ and for any $a,b\in\mathbb{R}$, we set $a\vee
b\equiv\max\\{a,b\\}$ and $a\wedge b\equiv\min\\{a,b\\}$. The cardinality of a
finite set $A$ is represented by $|A|$. For a square matrix $M$, we denote its
determinant by $\det(M)$. For any $p\in\mathbb{N}$, we denote by
$N_{p}(\mu,\Sigma)$ the $p$-variate Gaussian distribution with mean vector
$\mu$ and covariance matrix $\Sigma$, and omit the subscript when $p=1$. We
denote by $\mathds{1}$ the indicator function, and for any $k\in\mathbb{N}$,
$\boldsymbol{1}_{k}$ denotes the $k$-dimensional vector of all ones. Finally,
for any sequences of positive numbers $(x_{n})$ and $(y_{n})$, we write
$x_{n}\sim y_{n}$ for $\lim_{n}(x_{n}/y_{n})=1$ and $x_{n}\lesssim y_{n}$ for
$\limsup_{n}(x_{n}/y_{n})\leq 1.$

##  II Problem Formulation

###  II-A Multi-channel change-point model

We consider $K$ data sources or channels that generate sequences of random
elements sequentially and independently over time. For each $n\in\mathbb{N}$,
we denote the random element whose value is generated by source $k\in[K]$ at
time $n$ by $X^{k}_{n}$, and we set $X_{n}:=(X^{1}_{n},\dots,X^{K}_{n})$. We
refer to the distribution of $X_{n}$ as the _global_ distribution at time $n$,
and we assume that it changes at an unknown, deterministic time
$\nu\in\\{0,1,\ldots,\\}$. We denote the pre-change global distribution by
${\sf F}$ and the post-change global distribution by ${\sf G}$. Thus, we have

$\displaystyle X_{n}\sim\begin{cases}{\sf F},\ &\text{for}\ n\leq\nu\\\ {\sf
G},\ &\text{for}\ n>\nu\end{cases}\ .$ (1)

We assume that while the pre-change distribution, ${\sf F}$, is completely
specified, this is not the case for the post-change distribution. To emphasize
this, we define $\mathcal{G}$ as the family that encompasses all plausible
post-change global distributions. We emphasize that the change does not
necessarily affect all sources, and the subset of sources whose joint
distribution changes is unknown. To formalize this, for any $E\subseteq[K]$ we
denote the set of samples from the sources in $E$ at time $n\in\mathbb{N}$ by
$X_{n}^{E}$, i.e., $X^{E}_{n}:=\\{X^{k}_{n}:k\in E\\}$. Furthermore, we denote
the distributions of $X_{n}^{E}$ under ${\sf F}$ and ${\sf G}\in\mathcal{G}$
by ${\sf F}^{E}$ and ${\sf G}^{E}$, respectively. We refer to the former as
the _local_ distribution of $E$ before the change and to the latter as the
_local_ distribution of $E$ after the change under ${\sf G}$. Therefore, when
the global post-change distribution is ${\sf G}\in\mathcal{G}$, a subset of
sources $E\subseteq[K]$ experiences the change if and only if its local
distributions under ${\sf F}$ and ${\sf G}$ are different, that is,

if $\displaystyle\quad{\sf G}^{E}={\sf F}^{E},\quad\text{then}\quad
X_{n}^{E}\sim{\sf F}^{E},\ \ \text{for every}\ n\in\mathbb{N}\ ,$ (2) if
$\displaystyle\quad{\sf G}^{E}\neq{\sf F}^{E},\quad\text{then}\quad
X_{n}^{E}\sim\begin{cases}{\sf F}^{E}\ &\text{for}\ n\leq\nu\\\ {\sf G}^{E}\
&\text{for}\ n>\nu\end{cases}\ .$ (3)

Finally, for any $E\subseteq[K]$ we denote the family of all plausible post-
change local distributions of $E$ by $\mathcal{G}^{E}$, i.e.,

$\displaystyle\mathcal{G}^{E}:=\\{{\sf G}^{E}:{\sf G}\in\mathcal{G},\;{\sf
G}^{E}\neq{\sf F}^{E}\\}\ .$ (4)

###  II-B Sequential change detection with dynamic sampling control

The problem we consider in this work is the detection of the change as quickly
as possible under the hard constraint that _only $m$ of the $K$ sources can be
sampled at any time instant_. That is, at each time $n\in\mathbb{N}$ until
stopping, only $m$ coordinates of $X_{n}$ are observed. These coordinates,
nevertheless, are selected dynamically, based on the already collected
observations. Thus, at each time instant we have two intertwined tasks: (i) to
decide whether to terminate the sampling process declaring that the change has
occurred (_detection task_) or to continue sampling, and (ii) when the
decision is to continue sampling, to also select the sources to be sampled
next (_sampling task_).

To formalize these two tasks, we denote the family of subsets of $[K]$ with
cardinality $m$ by $\mathcal{K}_{m}$, i.e.,

$\displaystyle\mathcal{K}_{m}$ $\displaystyle:=\\{A\subseteq[K]:\;|A|=m\\}\ .$
(5)

Subsequently, we define a _sampling rule_ as a sequence
$S:=\\{S_{n}:\;n\in\mathbb{N}\\}$, where each $S_{n}$ is a
$\mathcal{K}_{m}$-valued random variable that represents the set of the $m$
sources that we select to sample at time $n\in\mathbb{N}$, and is a function
of the collected data up to time $n-1$, i.e.,
$\\{X_{t}^{S_{t}}:\;t\in[n-1]\\}$. We emphasize that a sampling rule $S$
induces the filtration of the collected observations, which can be defined
recursively as follows:

$\displaystyle\mathcal{F}_{n}^{S}:=\sigma\left(\mathcal{F}_{n-1}^{S},X_{n}^{S_{n}}\right),\quad
n\in\mathbb{N}\ ,$ (6)

where $\mathcal{F}_{0}^{S}$ is a $\sigma$-algebra independent of
$\\{X_{n}:n\in\mathbb{N}\\}$. The problem, subsequently, is to specify a
sampling rule, $S$, and an $\\{\mathcal{F}^{S}_{n}\\}$-measurable stopping
time, $T$, at which it is declared that a change has occurred. That is, $T$
must be a positive, integer-valued random variable such that
$\\{T=n\\}$$\in\mathcal{F}^{S}_{n}$ for every $n\in\mathbb{N}$. We refer to
such a pair $(S,T)$ as a joint sequential sampling rule and change-detection
policy, and we denote by $\Delta$ the family of all such policies.

###  II-C Change detection criteria

We next introduce the metrics that we adopt in order to quantify the false
alarm rate and the speed of detection of a policy. To this end, we denote the
underlying probability measure when there is no change by
$\mathbb{P}_{\infty}$, i.e.,

$\displaystyle\mathbb{P}_{\infty}={\sf F}\times{\sf F}\times\dots\ ,$ (7)

and denote the underlying probability measure when the change happens at time
$\nu$ and the global post-change distribution is ${\sf G}$ by
$\mathbb{P}_{\nu}^{{\sf G}}$, i.e.,

$\displaystyle\mathbb{P}_{\nu}^{{\sf G}}$
$\displaystyle=\underset{\nu}{\underbrace{{\sf F}\times\ldots\times{\sf
F}}}\times{\sf G}\times{\sf G}\times\ldots\ .$ (8)

Accordingly, we denote by $\mathbb{E}_{\nu}^{{\sf G}}$ and
$\mathbb{E}_{\infty}$ the expectations under $\mathbb{P}_{\nu}^{{\sf G}}$ and
$\mathbb{P}_{\infty}$, respectively. To control the false alarm rate, we focus
on policies whose expected time until raising an alarm when there is no change
is at least $\gamma$, where $\gamma>1$ is a user-specified level. Thus, such
policies belong to

$\displaystyle\Delta(\gamma):=\\{(S,T)\in\Delta:\;\mathbb{E}_{\infty}[T]\geq\gamma\\}\
.$ (9)

To describe the delay in detecting the change, we adopt a modified version of
Lorden’s criterion [25], as in [15]. Specifically, for each ${\sf
G}\in\mathcal{G}$ we denote by $\mathcal{A}({\sf G})$ the family of subsets of
$[K]$ of size $m$ whose local distributions are affected when the post-change
global distribution is ${\sf G}$, as described in (1), i.e.,

$\displaystyle\mathcal{A}({\sf G}):=\\{E\in\mathcal{K}_{m}:\;{\sf
G}^{E}\neq{\sf F}^{E}\\}\ .$ (10)

Without loss of generality, we assume that this set is non-empty, i.e.,
$|\mathcal{A}({\sf G})|\geq 1$ for every ${\sf G}\in\mathcal{G}$. Accordingly,
for a policy $(S,T)$ we denote by $D^{{\sf G}}(S,T)$ the worst-case (with
respect to the change-point) conditional expected detection delay given the
worst possible history of observations up to the change-point from the sources
whose distributions are affected by the change when the post-change global
distribution is ${\sf G}$. Specifically,

$D^{{\sf G}}(S,T):=\sup_{\nu\geq 0}\ \text{esssup}\ \mathbb{E}^{{\sf
G}}_{\nu}\left[T-\nu\,|\,\mathcal{F}^{S}_{\nu}({\sf G}),T>\nu\right]\,,$ (11)

where $\mathcal{F}_{\nu}^{S}({\sf G})$ is the $\sigma$-algebra generated by
the sources in $\mathcal{A}({\sf G})$, defined in (10), up to time $\nu$ when
the sources are sampled according to the sampling rule $S$, i.e.,

$\displaystyle\mathcal{F}_{\nu}^{S}({\sf
G}):=\sigma\left(S_{t},X_{t}^{S_{t}}:t\in[\nu],\;\;S_{t}\in\mathcal{A}({\sf
G})\right)\ .$ (12)

###  II-D Distributional assumptions

Throughout the paper, we assume that for every ${\sf G}\in\mathcal{G}$ and
$E\in\mathcal{A}({\sf G})$ the local distributions ${\sf G}^{E}$ and ${\sf
F}^{E}$ are mutually absolutely continuous, and we denote the Kullback-Leibler
(KL) divergence between ${\sf G}^{E}$ and ${\sf F}^{E}$ by
$\mathcal{I}^{E}_{0}({\sf G})$, i.e.,

$\displaystyle\mathcal{I}^{E}_{0}({\sf G}):=\int\log\left(\frac{d{\sf
G}^{E}}{d{\sf F}^{E}}\right)d{\sf G}^{E}\ .$ (13)

We refer to $\mathcal{I}^{E}_{0}({\sf G})$ as the _information number_
corresponding to $E$ under ${\sf G}$, as it measures how much the local
distribution of $E$ gets affected when the global distribution changes from
${\sf F}$ to ${\sf G}$.

##  III Universal Asymptotic Lower Bound

In this section, we fix an arbitrary ${\sf G}\in\mathcal{G}$ and state an
asymptotic, as $\gamma\to\infty$, lower bound on

$\inf_{(S,T)\in\Delta(\gamma)}D^{{\sf G}}(S,T)\ ,$ (14)

which is the optimal, among all policies in $\Delta(\gamma)$, worst-case
conditional expected detection delay when the global post-change distribution
is ${\sf G}$. This lower bound is inversely proportional to the information
number that corresponds to the subset in $\mathcal{A}({\sf G})$, defined in
(10), whose local distribution is altered the most under the change. The proof
combines ideas and techniques from [9] and [26]. As in the former, we need to
make the following second-moment assumption:

$\displaystyle\int\left(\log\frac{d{\sf G}^{E}}{d{\sf F}^{E}}\right)^{2}d{\sf
G}^{E}<\infty\quad\forall\;E\in\mathcal{A}({\sf G})\ .$ (15)

######  Theorem III.1 (Universal asymptotic lower bound)

If (15) holds, then as $\gamma\to\infty$ we have

$\displaystyle\inf_{(S,T)\in\Delta(\gamma)}D^{{\sf
G}}(S,T)\geq\frac{\log\gamma}{\max_{E\in\mathcal{A}({\sf
G})}\mathcal{I}^{E}_{0}({\sf G})}(1+o(1))\ .$ (16)

###### Proof:

See Appendix B.
∎

##  IV Round Robin Active Sequential Detection Policy

In this section, we introduce the policy $(\tilde{S},\tilde{T})$, and refer it
as Round Robin CUSUM due to the nature of its sampling rule. Under certain
assumptions it achieves the asymptotic lower bound of the previous section up
to a multiplicative constant and, in certain cases, with equality. For this
purpose, we first fix an arbitrary, non-empty subset of $\mathcal{K}_{m}$,
which we denote by ${\cal U}$. We refer to the members of ${\cal U}$ as units.
For each unit $E\in{\cal U}$, we assume that $\mathcal{G}^{E}$ defined in (4),
i.e., the family of all plausible post-change local distributions of $E$, is
non-empty and finite. We denote the mixture over all its members by ${\sf
H}^{E}$, i.e.,

$\displaystyle{\sf H}^{E}:=\frac{1}{|\mathcal{G}^{E}|}\sum_{{\sf
P}\in\mathcal{G}^{E}}{\sf P}\ ,$ (17)

and for every $n\in\mathbb{N}$ we denote the log-likelihood ratio of ${\sf
H}^{E}$ versus ${\sf F}^{E}$ based on $X_{n}^{E}$ by $\xi_{n}^{E}$ , i.e.,

$\displaystyle\xi_{n}^{E}:=$ $\displaystyle\log\frac{d{\sf H}^{E}}{d{\sf
F}^{E}}(X_{n}^{E})\ .$ (18)

###  IV-A Description of the policy

First, we fix an arbitrary permutation of the units, $E_{1},\ldots,E_{|{\cal
U}|}$, and a constant $A>0$. The first unit in the above permutation is
sampled first, i.e., $\tilde{S}_{1}=E_{1}$. Then, for each time
$n\in\mathbb{N}$ up to stopping, the following CUSUM-like statistic is
computed,

$\displaystyle Y_{n}=\max\left\\{Y_{n-1},0\right\\}+\xi_{n}^{\tilde{S}_{n}}\
,\quad\text{where}\qquad Y_{0}=0\ .$ (19)

Based on the value of $Y_{n}$ we distinguish the following cases:

  1. 1.

If $Y_{n}\in(0,A)$, then the same unit continues being sampled at the next
time instant, i.e., $\tilde{S}_{n+1}=\tilde{S}_{n}$.

  2. 2.

If $Y_{n}\leq 0$, then the next unit in the chosen permutation is sampled at
the next time instant, i.e.,

$\displaystyle\tilde{S}_{n+1}=\begin{cases}E_{d+1}&\text{if}\;\;\tilde{S}_{n}=E_{d}\;\;\text{and}\;\;d<|{\cal
U}|\\\ E_{1}&\text{if}\;\;\tilde{S}_{n}=E_{|{\cal U}|}\end{cases}\ .$ (20)

  3. 3.

If $Y_{n}\geq A$, then an alarm is raised and sampling is terminated.

Thus, the stopping time of this procedure is

$\displaystyle\tilde{T}:=\inf\left\\{n\in\mathbb{N}:\;Y_{n}\geq A\right\\}\ .$
(21)

Algorithm 1 Round Robin CUSUM Policy $(\tilde{S},\tilde{T})$

1: Fix an arbitrary permutation $\left(E_{1},\ldots,E_{|{\cal U}|}\right)$

2: Set $A>0$

3: Set $Y\leftarrow 0$

4: Set $\xi\leftarrow 0$

5: Set $d\leftarrow 1$

6: Set $n\leftarrow 0$

7: $\textbf{while }\;Y<A\;\textbf{ do}$

8: $n\leftarrow n+1$

9: $\tilde{S}\leftarrow E_{d}$

10: $\xi\leftarrow\log\frac{d{\sf H}^{E}}{d{\sf F}^{E}}(X_{n}^{\tilde{S}})$

11: $Y\leftarrow\max\left\\{Y,0\right\\}+\xi$

12: $\textbf{if }\;Y<0\;\textbf{ then}$

13: $d\leftarrow(d+1)\;\;{\rm mod}\;|{\cal U}|$

14: end if

15: return $\tilde{T}=n$

###  IV-B Performance Analysis

We start analyzing the performance of $(\tilde{S},\tilde{T})$ by first
establishing its false alarm control.

######  Theorem IV.1 (False alarm control)

For every $\gamma>1$ we have $(\tilde{S},\tilde{T})\in\Delta(\gamma)$ when
$A=\log\gamma$.

###### Proof:

See Appendix D.
∎

Next, we establish an asymptotic, as $A\to\infty$, upper bound on the worst-
case conditional expected detection delay of $(\tilde{S},\tilde{T})$ under an
arbitrary post-change global distribution ${\sf G}\in\mathcal{G}$. For this,
at least one unit must be affected by the change, i.e.,

$\displaystyle\mathcal{A}({\sf G})\cap{\cal U}\neq\emptyset\ .$ (22)

Furthermore, for every unit $E$, the statistic $\xi_{n}^{E}$, defined in (18),
needs to have negative and finite drift when $n\leq\nu$, i.e., before the
change. That is,

$\displaystyle\mathcal{J}^{E}_{\infty}$ $\displaystyle:={\sf
E}_{\infty}[\xi_{1}^{E}]=\int\log\left(\frac{d{\sf F}^{E}}{d{\sf
H}^{E}}\right)d{\sf F}^{E}\in(0,\infty)\ ,\qquad\text{for every}\quad
E\in{\cal U}\ .$ (23)

Finally, for every affected unit $E$, $\xi_{n}^{E}$ needs to have positive and
finite drift when $n>\nu$, i.e., after the change. That is,

$\displaystyle\mathcal{J}^{E}_{0}({\sf G})$ $\displaystyle:={\sf E}_{0}^{{\sf
G}}[\xi_{1}^{E}]=\int\log\left(\frac{d{\sf H}^{E}}{d{\sf F}^{E}}\right)d{\sf
G}^{E}\in(0,\infty)\ ,\qquad\text{for every}\quad E\in\mathcal{A}({\sf
G})\cap{\cal U}\ .$ (24)

The following proposition and its corollary provide sufficient conditions for
the validity of (23)-(24).

###### Proposition 1

Assumptions (23)-(24) hold if the following conditions are satisfied:

  * (i)

for every $E\in{\cal U}$, ${\sf H}^{E}\neq{\sf F}^{E}$ and
$\mathcal{J}_{\infty}^{E}<\infty$; and

  * (ii)

for every $E\in\mathcal{A}({\sf G})\cap{\cal U}$, the expectation of
$\xi_{1}^{E}$ is finite and the same under any ${\sf P}\in\mathcal{G}^{E}$.

###### Proof:

When condition (i) is satisfied, assumption (23) holds directly by the
definition of $\mathcal{J}^{E}_{\infty}$ in (23), and the positivity of
Kullback-Leibler divergence when the two distributions are different. Next,
for every $E\in\mathcal{A}({\sf G})\cap{\cal U}$ we have

$\displaystyle\mathcal{J}^{E}_{0}({\sf G})$
$\displaystyle=\int\log\left(\frac{d{\sf H}^{E}}{d{\sf F}^{E}}\right)\,d{\sf
G}^{E}$ (25) $\displaystyle=\frac{1}{|\mathcal{G}^{E}|}\sum_{{\sf
P}\in\mathcal{G}^{E}}\int\log\left(\frac{d{\sf H}^{E}}{d{\sf
F}^{E}}\right)\,d{\sf P}$ (26) $\displaystyle=\int\log\left(\frac{d{\sf
H}^{E}}{d{\sf F}^{E}}\right)\,d\left(\frac{1}{|\mathcal{G}^{E}|}\sum_{{\sf
P}\in\mathcal{G}^{E}}{\sf P}\right)$ (27)
$\displaystyle=\int\log\left(\frac{d{\sf H}^{E}}{d{\sf F}^{E}}\right)\,d{\sf
H}^{E}>0\ .$ (28)

The second equality holds because ${\sf G}\in\mathcal{G}$, and by condition
(ii), it follows that all terms of the sum are equal. The third one holds by
the additivity of the integral, and the last one holds due to the definition
of ${\sf H}^{E}$ in (17). The inequality, i.e., the positivity of
$\mathcal{J}^{E}_{0}({\sf G})$, holds by the positivity of Kullback-Leibler
divergence when the two distributions are different and condition (i), which
states that ${\sf H}^{E}\neq{\sf F}^{E}$. Finally, the finiteness of
$\mathcal{J}^{E}_{0}({\sf G})$ follows from the finiteness of the expectations
in condition (ii).
∎

###### Corollary IV.1

Assumptions (23)-(24) hold if the following conditions are satisfied:

  * (i)

for every $E\in{\cal U}$, $\mathcal{G}^{E}$ is a singleton, and
$\mathcal{J}_{\infty}^{E}<\infty$,

  * (ii)

for every $E\in\mathcal{A}({\sf G})\cap{\cal U}$, $\mathcal{I}_{0}^{E}({\sf
G})<\infty$.

###### Proof:

When condition (i) is satisfied, by the definitions of $\mathcal{G}^{E}$ in
(4) and ${\sf H}^{E}$ in (17) we have ${\sf H}^{E}\neq{\sf F}^{E}$ for every
$E\in{\cal U}$. This implies that condition (i) in Proposition 1 holds.
Furthermore, for every $E\in\mathcal{A}({\sf G})\cap{\cal U}$, since
$\mathcal{G}^{E}$ is a singleton, we clearly have $\mathcal{G}^{E}=\\{{\sf
G}^{E}\\}$. This, according to (17), implies that ${\sf H}^{E}={\sf G}^{E}$,
and hence, under condition (ii),

$\displaystyle\mathcal{J}^{E}_{0}({\sf G})=\int\log\left(\frac{d{\sf
H}^{E}}{d{\sf F}^{E}}\right)d{\sf G}^{E}=\int\log\left(\frac{d{\sf
G}^{E}}{d{\sf F}^{E}}\right)d{\sf G}^{E}=\mathcal{I}^{E}_{0}({\sf G})<\infty\
.$ (29)

Therefore, condition (ii) in Proposition 1 holds. The proof is complete.
∎

We next state the asymptotic upper bound on the worst-case conditional
expected detection delay of $(\tilde{S},\tilde{T})$ as $A\to\infty$.

######  Theorem IV.2 (Asymptotic upper bound on detection delay)

If (22)-(24) hold, then, as $A\to\infty$, we have

$\displaystyle D^{{\sf G}}(\tilde{S},\tilde{T})\leq\max_{E\in\mathcal{A}({\sf
G})\cap{\cal U}}\;\frac{A}{\mathcal{J}^{E}_{0}({\sf G})}+o(A)\ .$ (30)

###### Proof:

See Appendix E.
∎

In what follows, for simplicity, we set $A=\log\gamma$. Theorem IV.1 states
that this choice ensures $(\tilde{S},\tilde{T})\in\Delta(\gamma)$.

###  IV-C Asymptotic optimality

As before, we fix an arbitrary post-change global distribution ${\sf
G}\in\mathcal{G}$. We define the asymptotic relative efficiency of
$(\tilde{S},\tilde{T})$ as

$\displaystyle{\sf ARE}^{{\sf
G}}(\tilde{S},\tilde{T}):=\limsup_{\gamma\to\infty}\;\frac{D^{{\sf
G}}(\tilde{S},\tilde{T})}{\inf\\{D^{{\sf G}}(S,T):(S,T)\in\Delta(\gamma)\\}}\
,$ (31)

and we say that $(\tilde{S},\tilde{T})$ is asymptotically optimal under ${\sf
G}$ if, as $\gamma\to\infty$, we have

$\displaystyle D^{{\sf G}}(\tilde{S},\tilde{T})\sim\inf\\{D^{{\sf
G}}(S,T):(S,T)\in\Delta(\gamma)\\}\ .$ (32)

Based on Theorem IV.2, and the universal asymptotic lower bound in Theorem
III.1, we next obtain an upper bound on the asymptotic relative efficiency of
$(\tilde{S},\tilde{T})$, and establish sufficient conditions for its
asymptotic optimality.

###### Theorem IV.3

Suppose (15) holds.

  * (i)

If (22)-(24) hold, then

$\displaystyle{\sf ARE}^{{\sf
G}}(\tilde{S},\tilde{T})\leq\frac{\max\\{\mathcal{I}^{E}_{0}({\sf
G}):E\in\mathcal{A}({\sf G})\\}}{\min\\{\mathcal{J}^{E}_{0}({\sf
G}):E\in\mathcal{A}({\sf G})\cap{\cal U}\\}}\ .$ (33)

  * (ii)

If, also, $\mathcal{G}^{E}$ is a singleton for every $E\in\mathcal{A}({\sf
G})\cap{\cal U}$, and

$\displaystyle\max_{E\in\mathcal{A}({\sf G})}\;\mathcal{I}^{E}_{0}({\sf
G})=\min_{E\in\mathcal{A}({\sf G})\cap{\cal U}}\;\mathcal{I}^{E}_{0}({\sf G})\
,$ (34)

then $(\tilde{S},\tilde{T})$ is asymptotically optimal under ${\sf G}$.

###### Proof:

(i) This follows directly from the asymptotic upper bound (30) in Theorem
IV.2, and the asymptotic lower bound (16) in Theorem III.1. (ii) If
$\mathcal{G}^{E}$ is a singleton for every $E\in\mathcal{A}({\sf G})\cap{\cal
U}$, then $\mathcal{J}^{E}_{0}({\sf G})=\mathcal{I}^{E}_{0}({\sf G})$ for
every $E\in\mathcal{A}({\sf G})\cap{\cal U}$ (recall (29)), and the upper
bound in (33) is equal to 1 if and only if (34) holds.
∎

###### Remark IV.1

Given that there is at least one unit that is affected by the change, i.e.,
(22) holds, condition (34) clearly holds when $\mathcal{I}^{E}_{0}({\sf G})$
is the same (and finite) for every $E\in\mathcal{A}({\sf G})$. This is,
trivially, the case when the local distribution changes in only one element of
$\mathcal{K}_{m}$, i.e., $|\mathcal{A}({\sf G})|=1$.

###### Corollary IV.2

Suppose there is at least one unit affected by the change, i.e., (22) holds,
and for every unit there are unique pre-change and post-change local
distributions ${\sf F}^{*}$ and ${\sf G}^{*}$ respectively, i.e.,

$\displaystyle\begin{split}{\sf F}^{E}&:={\sf F}^{*}\ ,\qquad\text{for
every}\quad E\in{\cal U}\ ,\\\ {\sf G}^{E}&:={\sf G}^{*}\ ,\qquad\text{for
every}\quad E\in\mathcal{A}({\sf G})\cap{\cal U}\ ,\end{split}$ (35)

such that

$\displaystyle\int\log\left(\frac{d{\sf G}^{*}}{d{\sf F}^{*}}\right)d{\sf
G}^{*}$ $\displaystyle<\infty\ \qquad\text{and}\qquad\int\log\left(\frac{d{\sf
F}^{*}}{d{\sf G}^{*}}\right)d{\sf F}^{*}<\infty\ .$ (36)

Then, conditions (23)-(24) are satisfied. Additionally, if (15) also holds,
and either ${\cal U}=\mathcal{K}_{m}$ or, more generally,

$\displaystyle\max_{E\in\mathcal{A}({\sf G})}\mathcal{I}^{E}_{0}({\sf
G})=\int\log\left(\frac{d{\sf G}^{*}}{d{\sf F}^{*}}\right)d{\sf G}^{*}\ ,$
(37)

then $(\tilde{S},\tilde{T})$ is asymptotically optimal under ${\sf G}$.

###### Proof:

For every $E\in{\cal U}$ we have $\mathcal{G}^{E}=\\{{\sf G}^{*}\\}$.
Furthermore, when (36) holds, we have

$\displaystyle\mathcal{J}^{E}_{\infty}$
$\displaystyle=\int\log\left(\frac{d{\sf F}^{*}}{d{\sf G}^{*}}\right)d{\sf
F}^{*}<\infty\qquad\text{for every}\quad E\in{\cal U}\ ,$ (38)
$\displaystyle\mathcal{I}^{E}_{0}({\sf G})$
$\displaystyle=\int\log\left(\frac{d{\sf G}^{*}}{d{\sf F}^{*}}\right)d{\sf
G}^{*}<\infty\qquad\text{for every}\quad E\in\mathcal{A}({\sf G})\cap{\cal U}\
.$ (39)

Thus, following Corollary IV.1, conditions (23)-(24) are satisfied.
Furthermore, for every $E\in\mathcal{A}({\sf G})\cap{\cal U}$ we have
$\mathcal{G}^{E}=\\{{\sf G}^{*}\\}$, i.e., $\mathcal{G}^{E}$ is a singleton,
and

$\displaystyle\mathcal{I}^{E}_{0}({\sf G})=\int\log\left(\frac{d{\sf
G}^{*}}{d{\sf F}^{*}}\right)d{\sf G}^{*}\ .$ (40)

Thus, condition (34) holds when (37) holds, which is clearly always the case
when ${\cal U}=\mathcal{K}_{m}$. ∎

###  IV-D A non-asymptotic upper bound

Under slightly stronger moment assumptions, we can establish an explicit, non-
asymptotic upper bound for the worst-case detection delay of the Round Robin
CUSUM policy. To be specific, for every unit $E\in{\cal U}$ we introduce the
first descending and ascending ladder variables of the random walk with
increments $\\{\xi_{t}^{E}:t\in\mathbb{N}\\}$ as follows.

$\displaystyle\zeta^{E}_{-}:=\inf\left\\{n\geq
1:\sum_{t=1}^{n}\xi_{t}^{E}<0\right\\}\ \qquad\text{and}\qquad\
\zeta^{E}_{+}:=\inf\left\\{n\geq 1:\sum_{t=1}^{n}\xi_{t}^{E}>0\right\\}\ .$
(41)

When $E\notin\mathcal{A}({\sf G})$, we denote by $q^{E}_{+}$ the probability
under ${\sf F}$ that this random walk never exceeds $0$, i.e.,

$\displaystyle q^{E}_{+}:={\sf F}(\zeta^{E}_{+}=\infty)\ .$ (42)

When $E\in\mathcal{A}({\sf G})$, we denote by $q^{E}_{-}({\sf G})$ the
probability under ${\sf G}$ that this random walk never falls below 0, i.e.,

$\displaystyle q^{E}_{-}({\sf G}):={\sf G}(\zeta^{E}_{-}=\infty)\ .$ (43)

We note that under assumptions (23)-(24), both these probabilities are
strictly positive (see, e.g.,[27, Corollary 8.39], and Lemma C.1 in Appendix
C).

###### Proposition 2

Suppose (22) -(24) hold. If we have

$\displaystyle\mathcal{W}^{E}_{0}({\sf G})$
$\displaystyle:=\int\left(\xi_{1}^{E}-\mathcal{J}^{E}_{0}({\sf
G})\right)^{2}d{\sf G}<\infty\qquad\text{for every}\quad E\in\mathcal{A}({\sf
G})\cap{\cal U}\ ,$ (44)

then (30) holds for every large enough $A>0$, with $o(A)$ replaced by

$\displaystyle\begin{split}&\frac{1}{1-\prod_{E\in\mathcal{A}({\sf
G})\cap{\cal U}}(1-q^{E}_{-}({\sf G}))}\,\sum_{E\in{\cal
U}\setminus\mathcal{A}({\sf
G})}\frac{1}{q^{E}_{+}}\;+\;\max_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\frac{1}{q^{E}_{-}({\sf G})}\left(1+\frac{\mathcal{W}^{E}_{0}({\sf
G})}{\mathcal{J}^{E}_{0}({\sf G})^{2}}\right)+\;C\ ,\end{split}$ (45)

where $C>0$ is a finite constant independent of $A$.

###### Proof:

See Appendix E-H.
∎

###### Remark IV.2

A further upper bound on (45) takes the form

$\text{constant}\;+\;\frac{1}{p_{+}}\cdot\frac{|{\cal
U}\setminus\mathcal{A}({\sf
G})|}{\left(1-\left(1-p_{-}\right)^{|\mathcal{A}({\sf G})\cap{\cal
U}|}\right)}\ ,$ (46)

where “constant” refers to a term that does not depend on $\gamma$, and

$\displaystyle p_{-}:=\min_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}q^{E}_{-}({\sf G})\ \qquad\text{and}\qquad\ p_{+}:=\min_{E\in{\cal
U}}q_{+}^{E}\ .$ (47)

###### Remark IV.3

As implied by Corollary IV.2, and we will see in some examples that follow,
$(\tilde{S},\tilde{T})$ may be asymptotically optimal even with a family of
units, ${\cal U}$, that is smaller than $\mathcal{K}_{m}$. The upper bounds
presented in Proposition 2 as well as in Remark IV.2, in which the second-
order term grows with the number of units, suggest that the smaller family of
units may not only be more computationally efficient but also preferable in
terms of its detection performance.

##  V Change in the Marginal Distributions of the Sources

In this section, we illustrate the model, algorithm, and theoretical results
of the previous sections in the problem of detecting a change in the marginal
distributions of the sources. Specifically, we assume that at an unknown time
$\nu$ the global distribution changes from ${\sf F}$ to some ${\sf G}$ so that
the marginal distribution of at least one source changes. Since it is possible
to detect this change even when sampling one source at a time, we focus on the
case that $m=1$. Furthermore, we do not assume any prior information regarding
the subset of sources that are affected by the change. Thus, the family of
units, ${\cal U}$, has to be selected as the family of all singletons of
$[K]$, i.e., $\mathcal{K}_{1}=\\{\\{k\\}:k\in[K]\\}$. Note also that we do not
assume independence among the sources, in fact, the dependence structure may
also change after $\nu$. To simplify the notation, we use $k$ instead of
$\\{k\\}$ as superscript in the local distributions. Hence, we have

$\displaystyle X^{k}_{n}\sim\left\\{\begin{array}[]{lll}{\sf
F}^{k}&&\text{for}\ n\leq\nu,\quad\;k\in[K]\\\ {\sf F}^{k}&&\text{for}\
n>\nu,\quad\\{k\\}\notin\mathcal{A}({\sf G})\\\ {\sf G}^{k}&&\text{for}\
n>\nu,\quad\\{k\\}\in\mathcal{A}({\sf G})\\\ \end{array}\right.\ .$ (51)

Furthermore, for every $k\in[K]$ and $n\in\mathbb{N}$ we set

$\displaystyle{\sf H}^{k}=\frac{1}{|\mathcal{G}^{k}|}\sum_{{\sf
P}\in\mathcal{G}^{k}}{\sf P}\ \ \qquad\text{and}\qquad\ \xi_{n}^{k}:=$
$\displaystyle\log\frac{d{\sf H}^{k}}{d{\sf F}^{k}}(X_{n}^{k})\ ,$ (52)

where $\mathcal{G}^{k}$ is the family of all possible post-change local
distributions of source $k$. Then, the second-moment assumption (15) is
equivalent to

$\displaystyle\int\left(\log\left(\frac{d{\sf G}^{k}}{d{\sf
F}^{k}}\right)\right)^{2}d{\sf G}^{k}<\infty\ ,\qquad\text{for
every}\quad\\{k\\}\in\mathcal{A}({\sf G})\ ,$ (53)

and assumptions (23)-(24) are equivalent to

$\displaystyle\mathcal{J}^{k}_{\infty}$
$\displaystyle=\int\log\left(\frac{d{\sf F}^{k}}{d{\sf H}^{k}}\right)d{\sf
F}^{k}\in(0,\infty)\ ,\qquad\text{for every}\quad k\in[K]\ ,$ (54)
$\displaystyle\mathcal{J}^{k}_{0}({\sf G})$
$\displaystyle=\int\log\left(\frac{d{\sf H}^{k}}{d{\sf F}^{k}}\right)d{\sf
G}^{k}\in(0,\infty)\ ,\qquad\text{for every}\quad\\{k\\}\in\mathcal{A}({\sf
G})\ .$ (55)

The following proposition specializes Theorem IV.3 to the setting of this
section.

###### Proposition 3

Suppose that (53) holds for every $k\in[K]$.

  * (i)

If ${\sf H}^{k}\neq{\sf F}^{k}$ and $\mathcal{J}^{k}_{\infty}<\infty$ for
every $k\in[K]$, and the expectation of $\xi_{1}^{k}$ is finite and has the
same value for every ${\sf P}\in\mathcal{G}^{k}$ and
$\\{k\\}\in\mathcal{A}({\sf G})$, then

$\displaystyle{\sf ARE}^{{\sf G}}(\tilde{S},\tilde{T})$
$\displaystyle\leq\frac{\max\\{\mathcal{I}^{k}_{0}({\sf
G}):\\{k\\}\in\mathcal{A}({\sf G})\\}}{\min\\{\mathcal{J}^{k}_{0}({\sf
G}):\\{k\\}\in\mathcal{A}({\sf G})\\}}\ .$ (56)

  * (ii)

If, also, there is exactly one possible post-change marginal distribution for
every affected source, i.e., $\mathcal{G}^{k}$ is a singleton for every
$k\in[K]$, and $\mathcal{I}^{k}_{0}({\sf G})$ has the same value for every
$\\{k\\}\in\mathcal{A}({\sf G})$, then $(\tilde{S},\tilde{T})$ is
asymptotically optimal under ${\sf G}$.

###### Proof:

(i) Due to (53), assumption (15) is satisfied, and under the conditions stated
above, assumptions (54)-(55), or equivalently, (23)-(24) are also satisfied by
Proposition 1. Furthermore, since ${\cal U}=\mathcal{K}_{1}$, we have
$\mathcal{A}({\sf G})\cap{\cal U}=\mathcal{A}({\sf G})$, and thus, (56)
follows from (33). (ii) It suffices to check the conditions of Corollary IV.1.
Indeed, condition (i) in Corollary IV.1 is satisfied when $\mathcal{G}^{k}$ is
a singleton for every $k\in[K]$. Moreover, when the quantities
$\\{\mathcal{I}^{k}_{0}({\sf G}):\\{k\\}\in\mathcal{A}({\sf G})\\}$ are
identical, by Remark IV.1 it follows that condition (ii) in Corollary IV.1 is
also satisfied.

∎

###### Remark V.1

The setup of Proposition 3(ii) coincides with the one in [15] with the
differences that we allow (i) the data sources to be dependent and (ii) any
number of data sources to be affected by the change. In [15], a second-order
asymptotic optimality property is established when only a single data source
can be affected by the change. Proposition 3 shows that the same scheme is
asymptotically optimal also when an arbitrary, unknown number of data sources
can be affected by the change, as long as the magnitude of the change is the
same in all affected sources. This is, in particular, the case in the context
of the following proposition, where there is a common pre-change and a common
post-change marginal distribution for all sources.

###### Proposition 4

If there are ${\sf F}^{*}$ and ${\sf G}^{*}$ such that

$\displaystyle{\sf F}^{k}$ $\displaystyle={\sf F}^{*},\quad\text{for
every}\;k\in[K]\ ,$ (57) $\displaystyle{\sf G}^{k}$ $\displaystyle={\sf
G}^{*},\quad\text{for every}\;\\{k\\}\in\mathcal{A}({\sf G}),\ {\sf
G}\in\mathcal{G}\ ,$ (58)

and (36) and (53) hold, then $(\tilde{S},\tilde{T})$ is asymptotically optimal
under every ${\sf G}\in\mathcal{G}$.

###### Proof:

It suffices to check the conditions of Corollary IV.2. Conditions (22) and
(35) are satisfied for every ${\sf G}\in\mathcal{G}$ when ${\cal
U}=\mathcal{K}_{1}$. Again, (37) holds since ${\cal U}=\mathcal{K}_{1}$, and
condition (15) is satisfied due to (53). ∎

Next, we illustrate the above results with two concrete examples that involve
a change in the mean of a Gaussian sequence. In the first one, the post-change
local distribution of each affected source is completely specified, whereas in
the second the mean of each source may either increase or decrease.

###### Example V.1

Suppose that for every $k\in[K]$ we have ${\sf F}^{k}=N(0,1)$ and
$\mathcal{G}^{k}=\\{N(\mu_{k},1)\\}$, where $\mu_{k}\in\mathbb{R}$. Then,
condition (53) clearly holds, and conditions (54)-(55) are satisfied with

$\displaystyle\mathcal{J}^{k}_{\infty}({\sf G})=\mathcal{J}^{k}_{0}({\sf
G})=\mathcal{I}^{k}_{0}({\sf G})=\frac{1}{2}\,\mu_{k}^{2}\ .$ (59)

Therefore, following Proposition 3 we have

$\displaystyle{\sf ARE}^{{\sf
G}}(\tilde{S},\tilde{T})\leq\frac{\max_{\\{k\\}\in\mathcal{A}({\sf
G})}\;\mu_{k}^{2}}{\min_{\\{k\\}\in\mathcal{A}({\sf G})}\;\mu_{k}^{2}}\ ,$
(60)

and $(\tilde{S},\tilde{T})$ is asymptotically optimal if $|\mu_{k}|$ is the
same for every $\\{k\\}\in\mathcal{A}({\sf G})$, i.e., the absolute magnitude
of the post-change mean is the same for every affected source. Clearly, this
is always the case when $\mathcal{A}({\sf G})$ is a singleton, i.e., only a
single source is affected by the change, or when $|\mu_{k}|$ is the same for
every $k\in[K]$.

###### Example V.2

Suppose that for every $k\in[K]$ we have ${\sf F}^{k}=N(0,1)$ and
$\mathcal{G}^{k}=\\{N(-\delta_{k},1),\;N(\delta_{k},1)\\}$ for some
$\delta_{k}>0$. This clearly implies that ${\sf H}^{k}\neq{\sf F}^{k}$ for
every $k\in[K]$, and that (53) holds. Furthermore, for every $k\in[K]$ we have

$\displaystyle\xi_{1}^{k}$
$\displaystyle=\log\;\bigg{\\{}\frac{1}{2}\,\exp\left(+\frac{\delta_{k}}{2}\left(2X_{1}^{k}-\delta_{k}\right)\right)+\frac{1}{2}\,\exp\left(-\frac{\delta_{k}}{2}\left(2X_{1}^{k}+\delta_{k}\right)\right)\bigg{\\}}\
.$ (61)

Since $\xi^{k}_{1}$ is symmetric with respect to $+\delta_{k}$ and
$-\delta_{k}$, it is identically distributed under $N(-\delta_{k},1)$ and
$N(\delta_{k},1)$. By Jensen’s inequality, it follows that the expectations of
$\xi_{1}^{k}$ under ${\sf F}^{k}$ and any ${\sf P}$ in $\mathcal{G}^{k}$ are
finite. Therefore, following Proposition 1, assumptions (54)-(55) hold.

##  VI Change in Correlation

In this section, we illustrate the models, algorithms, and theoretical results
of the previous sections in the problem of detecting a change in the
correlation structure of sources that follow a multivariate Gaussian
distribution. For simplicity, we assume that the sources are initially
independent, each with distribution $N(0,1)$. After $\nu$, the marginal
distributions still remain the same, i.e., $N(0,1)$, while an unknown subset
of sources become dependent. For each pair of sources that is affected by the
change, we assume that the correlation coefficient takes a value in a finite
set $\mathcal{R}\subset(0,1)$. Hence, we have

$\displaystyle X_{n}\sim\left\\{\begin{array}[]{lll}N_{K}(\boldsymbol{0},\,I)\
,&\text{for}\ n\leq\nu\\\ N_{K}(\boldsymbol{0},R)\ ,&\text{for}\
n>\nu\end{array}\right.\ ,$ (64)

where $R\in\mathbb{R}^{K\times K}$ is a correlation matrix such that

$\displaystyle\begin{split}\;&R_{ii}=1\,\quad\forall\;i\in[K]\ ,\\\
\;&R_{ij}\in\mathcal{R}\cup\\{0\\}\quad\forall\;i,j\in[K],\;i<j\ ,\;\\\ &R\neq
I\ .\end{split}$ (65)

While the global pre-change distribution is fixed to ${\sf F}\equiv
N_{K}(\boldsymbol{0},I)$, for the family of post-change distributions,
$\mathcal{G}$, we will consider different setups depending on the
specification of $\mathcal{R}$ and the available topological information
regarding where correlations are induced. In all of them, it is clear that it
is necessary to sample at least $2$ sources at each time, i.e., $m$ must be at
least $2$. First, we will consider the case that we can sample only two
sources per time instant, i.e., $m=2$, and then the general case where $m\geq
2$. In all cases, it is readily verified that condition (15) is satisfied.

###  VI-A Sampling two sources at a time ($m=2$)

In this setting, $\mathcal{K}_{m}$ is the set of all pairs of sources, i.e.,
$\\{\\{i,j\\}:1\leq i<j\leq K\\}$, and for any post-change global distribution
${\sf G}\in\mathcal{G}$, the set $\mathcal{A}({\sf G})$, defined in (10), is
the set of all pairs of sources that become correlated after the change under
${\sf G}$, i.e.,

$\displaystyle\mathcal{A}({\sf G})=\\{\\{i,j\\}\in\mathcal{K}_{2}:R_{ij}\neq
0\\}\ .$ (66)

We start with the case where every affected pair of sources becomes positively
correlated after the change with a specified correlation $\rho\in(0,1)$. We
consider two cases regarding the prior topological information under which the
policy $(\tilde{S},\tilde{T})$ achieves asymptotic optimality.

###### Proposition 5

Suppose that $\mathcal{R}=\\{\rho\\}$, where $\rho\in(0,1)$.

  * (i)

If there is no prior information regarding the correlated pairs of sources,
i.e.,

$\displaystyle\mathcal{G}=\\{N_{K}(\boldsymbol{0},R)\
:\;R\;\;\text{satisfies}~{}\eqref{eq:R}\\}\ ,$ (67)

then the policy $(\tilde{S},\tilde{T})$, with ${\cal U}=\mathcal{K}_{2}$, is
asymptotically optimal.

  * (ii)

If it is a priori known that there exists at least one pair of consecutive
sources, i.e.,

$\displaystyle\mathcal{G}=\left\\{N_{K}(\boldsymbol{0},R)\
:\;R\;\;\text{satisfies}~{}\eqref{eq:R}\;\;\text{and}\;\;R_{i(i+1)}=\rho\;\;\text{for
some}\;\;i\in[K-1]\right\\}\ ,$ (68)

then the policy $(\tilde{S},\tilde{T})$, with ${\cal U}$ either
$\mathcal{K}_{2}$ or $\\{\\{i,i+1\\}:i\in[K-1]\\}$, is asymptotically optimal.

###### Proof:

In both (i) and (ii), all conditions of Corollary IV.2 are satisfied with

$\displaystyle{\sf F}^{*}\equiv N_{2}(\boldsymbol{0},I)\ \qquad\text{and}\
\qquad{\sf G}^{*}\equiv N_{2}(\boldsymbol{0},R_{+})\ ,\quad\mbox{where}\quad
R_{+}:=\begin{bmatrix}1&\rho\\\ \rho&1\end{bmatrix}\ .$ (69)

∎

###### Remark VI.1

The previous proposition provides an example of a setup where, due to the
presence of prior topological information, asymptotic optimality is achieved
with a family of units, ${\cal U}$, that is smaller than the largest possible,
$\mathcal{K}_{2}$. Specifically, its size is only $(K-1)$ compared to
$K(K-1)/2$, i.e, the size of $\mathcal{K}_{2}$ (recall Remark IV.3).

Next, we consider the case where every affected pair of sources becomes either
positively or negatively correlated after the change.

###### Proposition 6

Suppose $\mathcal{R}=\\{+\rho,-\rho\\}$, where $\rho\in(0,1)$. If there is no
prior information regarding the correlated pairs of sources, i.e.,

$\displaystyle\mathcal{G}=\left\\{N_{K}(\boldsymbol{0},R)\
:\;R\;\;\text{satisfies}~{}\eqref{eq:R}\right\\},$ (70)

then conditions (23)-(24) hold for every ${\sf G}\in\mathcal{G}$ with ${\cal
U}=\mathcal{K}_{2}$.

###### Proof:

It suffices to verify the conditions of Proposition 1. For any pair of sources
$E\in\mathcal{K}_{2}$ that is affected by the change, the covariance matrix
changes from the identity to either $R_{+}$ or $R_{-}$, where

$\displaystyle R_{-}:=\begin{bmatrix}1&-\rho\\\
-\rho&1\end{bmatrix}\qquad\text{and}\qquad R_{+}:=\begin{bmatrix}1&+\rho\\\
+\rho&1\end{bmatrix}\ .$ (71)

Therefore, we have

$\displaystyle{\sf
F}^{E}=N_{2}(\boldsymbol{0},I)\qquad\text{and}\qquad\mathcal{G}^{E}=\\{N_{2}(\boldsymbol{0},R_{+}),\,N_{2}(\boldsymbol{0},R_{-})\\}\
.$ (72)

This yields

$\displaystyle\begin{split}\xi_{1}^{E}&=\log\;\bigg{\\{}\exp\left(-\frac{1}{2}(X_{1}^{E})^{T}(R_{-}^{-1}-I_{2})\,X_{1}^{E}\right)\;+\;\exp\left(-\frac{1}{2}(X_{1}^{E})^{T}(R_{+}^{-1}-I_{2})\,X_{1}^{E}\right)\bigg{\\}}-\log\left(2\sqrt{1-\rho^{2}}\right)\
.\end{split}$ (73)

Since $\xi_{1}^{E}$ is symmetric with respect to $+\rho$ and $-\rho$, it is
identically distributed under $N_{2}(\boldsymbol{0},R_{+})$ and
$N_{2}(\boldsymbol{0},R_{-})$. Thus, by Jensen’s inequality, the expectations
of $\xi_{1}^{E}$ under ${\sf F}^{E}$ and any ${\sf P}$ in $\mathcal{G}^{E}$
are finite.

∎

###  VI-B Sampling $m$ sources, where $m\geq 2$

In this case, for any ${\sf G}\in\mathcal{G}$, $\mathcal{A}({\sf G})$ is the
set of all subsets of sources of size $m$ that contain at least one pair of
sources that is correlated after the change when the post-change global
distribution is ${\sf G}$, i.e.,

$\displaystyle\mathcal{A}({\sf G})=\\{\\{i_{1},$
$\displaystyle,\dots,i_{m}\\}\in\mathcal{K}_{m}:\ \text{there exist}\ i\neq
j,\;\;i,j\in\\{i_{1},i_{2},\dots,i_{m}\\}\ \text{such that}\ R_{ij}\neq 0\\}\
.$ (74)

The following proposition describes a setup where the policy
$(\tilde{S},\tilde{T})$ achieves asymptotic optimality.

###### Proposition 7

Suppose that the total number of sources is a multiple of $m$, i.e., $K=Cm$
for some $C\geq 2$, and $\mathcal{R}=\\{\rho\\}$ for some $\rho\in(0,1)$.
Also, suppose that after the change at least one of the _disjoint_ $m$-tuples
of consecutive sources in

$\displaystyle\mathcal{M}_{k}:=\\{(k-1)m+1,(k-1)m+2,\dots,km-1,km\\}\ ,\quad
k\in[C]\ ,$ (75)

follows an equi-correlated multivariate Gaussian distribution with common
positive correlation $\rho\in(0,1)$ and is independent of the rest of the
sources, that is,

$\displaystyle\mathcal{G}=\Bigg{\\{}N_{K}(\boldsymbol{0},R)\ :\ $ $R$
satisfies (65) and (76) $\displaystyle\exists\;A\subseteq[C]\quad\mbox{such
that}\quad R_{ij}=\begin{cases}\rho&\text{if}\
\\{i,j\\}\in\mathcal{M}_{k}\;\;\mbox{for some }k\in A\\\
0&\text{otherwise}\end{cases}\quad\Bigg{\\}}\ .$ (77)

Then, the policy $(\tilde{S},\tilde{T})$, with ${\cal U}$ either
$\mathcal{K}_{m}$ or $\\{\mathcal{M}_{k}:k\in[C]\\}$, is asymptotically
optimal.

###### Proof:

Under ${\sf G}$, at least one element from $\\{\mathcal{M}_{k},k\in[C]\\}$ is
affected by the change, and its local distribution changes from the standard
$m$-variate Gaussian to the equi-correlated one with common positive
correlation $\rho$. Thus, it suffices to verify the conditions of Corollary
IV.2 with

$\displaystyle{\sf F}^{*}\equiv N_{m}(\boldsymbol{0},I)\qquad\text{and}\qquad\
{\sf G}^{*}\equiv N_{m}(\boldsymbol{0},R_{m})\ ,$ (78)

where, for every $k\in\mathbb{N}$, we set

$\displaystyle R_{k}:=\begin{bmatrix}1&\rho&\cdots&\rho\\\
\rho&1&\cdots&\rho\\\ \vdots&\vdots&\ddots&\vdots\\\
\rho&\rho&\cdots&1\end{bmatrix}\ \in\mathbb{R}^{k\times k}\ .$ (79)

It can be readily verified that (36) holds. Specifically, we have

$\displaystyle\int\log\left(\frac{d{\sf G}^{*}}{d{\sf F}^{*}}\right)d{\sf
G}^{*}=-\frac{1}{2}\log{\det(R_{m})}\ .$ (80)

Now, for every $E\in\mathcal{A}({\sf G})$, we have

$\mathcal{I}^{E}_{0}({\sf G})=-\frac{1}{2}\log({\det(\Sigma^{E}_{\sf G})})\ ,$
(81)

where $\Sigma_{\sf G}^{E}$ denotes the covariance matrix of $X_{1}^{E}$ under
${\sf G}$. Clearly, the above quantity varies over $E\in\mathcal{A}({\sf G})$.
Therefore, in order to prove (37), it suffices to show that

$\displaystyle\int\log\left(\frac{d{\sf G}^{*}}{d{\sf F}^{*}}\right)d{\sf
G}^{*}\geq\mathcal{I}^{E}_{0}({\sf G})\ \quad\text{for every}\quad
E\in\mathcal{A}({\sf G})\ ,$ (82)

or equivalently that

$\displaystyle-\frac{1}{2}\log{\det(R_{m})}\geq\frac{1}{2}\log({\det(\Sigma^{E}_{\sf
G})})\ \quad\text{for every}\quad E\in\mathcal{A}({\sf G})\ .$ (83)

Indeed, for every $E\in\mathcal{A}({\sf G})$ the covariance matrix
$\Sigma^{E}_{\sf G}$ takes the following block-matrix form:

$\displaystyle\Sigma^{E}_{\sf G}=\begin{bmatrix}R_{s}&0&0\\\ 0&R_{t}&0\\\
0&0&I_{m-(s+t)}\end{bmatrix},\quad\text{for some}\quad
s,t\in\mathbb{N}\quad\text{such that}\quad s+t\leq m\ .$ (84)

Hence, in order to prove (83), it is enough to show that for every
$s,t\in\mathbb{N}$ such that $s+t\leq m$ we have

$\displaystyle-\frac{1}{2}\log({{\rm det}(R_{m})})\geq-\frac{1}{2}\log({{\rm
det}(R_{s})\;{\rm det}(R_{t})})\ ,$ (85)

or, equivalently, $\det(R_{m})\leq\det(R_{s})\;\det(R_{t})$. This inequality
follows by the explicit expression for the determinant of the autocorrelation
matrix of order $k$, i.e.,

$\displaystyle\det(R_{k})=(1-\rho)^{k-1}(1+(k-1)\rho)\ ,\quad k\in\mathbb{N}\
.$ (86)

∎

##  VII Simulation Studies

###  VII-A Description of the model and settings

In this section, we present the results of various simulation studies. In all
of them, we apply the policy $(\tilde{S},\tilde{T})$, introduced in Section
IV, to the problem of detecting a change in the correlation structure of
$K=10$ Gaussian information sources (Section VI). After the change, every
affected pair of sources becomes positively correlated with correlation
coefficient $\rho\in(0,1)$, i.e., $\mathcal{R}=\\{\rho\\}$, but there is no
prior information regarding the post-change correlation structure. That is, it
is not known a priori which or even how many sources become correlated. We
denote the unknown number of affected sources by $s$, and without loss of
generality, we assume that the sources in $\\{K-s+1,K-s+2,\dots,K\\}$ are the
ones that become correlated to each other after the change. In each simulation
study, we vary $s$ in $\\{2,\dots,K\\}$, and in this way the true number of
correlated pairs varies in $\left\\{{s\choose 2}:2\leq s\leq K\right\\}$.
Given the above, we consider three simulation setups.

  1. 1.

In the first one, we set $\rho=0.7$, we are allowed to sample only $2$ sources
at each time, i.e., $m=2$, and we consider two cases for $\gamma$, $10^{2}$
and $10^{5}$.

  2. 2.

In the second, we set $\rho=0.7$, $\gamma=10^{2}$, and we consider two cases
for the number of sources we are allowed to sample at each time, $m=2$ and
$m=3$.

  3. 3.

In the third study, we consider the same setup as in the second with the only
difference that we set $\rho=0.95$.

In all studies, for the implementation of the policy $(\tilde{S},\tilde{T})$
the threshold is $A=\log\gamma$, the family of units is ${\cal
U}=\mathcal{K}_{m}$, and the permutation of elements of $\mathcal{K}_{m}$ for
$m=2$ is

$\displaystyle\\{1,2\\},\\{1,3\\},\dots,\\{1,K\\},\\{2,3\\},\dots,\\{2,K\\},\dots,\\{K-1,K\\}\
,$ (87)

and for $m=3$ it is

$\displaystyle\\{1,2,3\\},\\{1,2,4\\},\dots,\\{1,K-1,K\\},\\{2,3,4\\},\dots,\\{2,K-1,K\\},\dots,\\{K-2,K-1,K\\}\
.$ (88)

For all studies, we consider the case that the change happens at time $\nu=0$,
and we focus on the worst-case expected detection delay, in the sense that the
unaffected (less informative) subsets, either pairs or triplets, of sources
are the ones sampled first, and the affected (more informative) ones are
sampled later. Given these settings, we estimate the expected detection delay
of $(\tilde{S},\tilde{T})$ using $4,000$ Monte Carlo replications for each
$s\in\\{2,\dots,K\\}$. In all cases, the Monte Carlo standard error in the
estimation of every expectation did not exceed $5\%$ of the corresponding
estimate.

In the first study, the goal is to investigate the sharpness of the non-
asymptotic upper bound in Proposition 2. In the other two, the goal is to
explore the impact of sampling 2 or 3 sources at a time on the performance of
$(\tilde{S},\tilde{T})$. Expectedly, sampling 3 sources at a time improves the
first-order asymptotic performance of $(\tilde{S},\tilde{T})$, but there is a
considerable increase in the second-order term. Furthermore, by Proposition
5(i) it follows that $(\tilde{S},\tilde{T})$ is asymptotically optimal when
$m=2$, but this is not the case when $m=3$, as there are multiple possible
local post-change distributions for any triplet of sources.

We present the results for the first study in Figure 1, for the second in
Figure 2a, and for the third one in Figure 2b. In all figures, the horizontal
axis corresponds to the true number of correlated pairs and the vertical axis
to the expected detection delay of the implemented procedures.

Figure 1: Expected detection delay of the rules under the first study.

###  VII-B Simulation results

From Figure 1, we observe that the non-asymptotic upper bound established in
Proposition 2 is very close to the expected detection delay, especially for
the larger value of $\gamma$. Furthermore, we can see that when the true
number of correlated pairs is large enough, the detection delay decreases
linearly with it. This can be predicted by the form of upper bound described
in Remark IV.2. Indeed, the numerator in the second term of this upper bound
takes the form ${K\choose 2}-|\mathcal{A}({\sf G})|$, whereas the denominator
changes very slowly and behaves like a constant as the true number of
correlated pairs $|\mathcal{A}({\sf G})|$ increases to ${K\choose 2}$. Hence,
this upper bound overall exhibits an almost linear trend with a negative
slope. Finally, we observe that the performance of the Round Robin CUSUM rule
essentially agrees with the first-order approximation of the corresponding
lower bound (Theorem III.1) in both cases for $\gamma$ when all sources become
correlated after the change.

(a)

(b)

Figure 2: Expected detection delay of the rules under the second study (a) and
third study (b).

From Figure 2a, we observe that when $\rho=0.7$, the detection delay when
sampling $3$ sources at each time is worse than that when sampling $2$ sources
at a time. However, as shown in Figure 2b, the situation is mostly reversed
when $\rho=0.95$. This phenomenon could be explained by the possible trade-off
between the strength of correlation and the advantageousness of asymptotic
optimality, and this leads us to a potential direction for future research.

##  VIII Concluding Remarks and Future Directions

In this paper, we have considered an environment of multiple information
sources or channels generating data streams in discrete time. The generated
data are independent over time, but the observations from different sources
can be statistically dependent. At an unknown time, the underlying joint
distribution undergoes a change. The objective has been to detect the change
with minimal delay, subject to a sampling constraint, when at each time, it is
allowed to sample only a pre-fixed number of sources, of our choice. In the
class of all sequential procedures that satisfy the sampling constraint and
control the false alarm rate below a certain pre-specified level, we have
established a universal asymptotic lower bound for a modified version of
Lorden’s criterion [25], as the false alarm rate vanishes. Subsequently, we
have considered a simple, computationally efficient, and easily implementable
sequential procedure that belongs to the above-mentioned class and achieves
asymptotic optimality under certain assumptions regarding the underlying
change-point model. Furthermore, under more general conditions, we have shown
that the asymptotic relative efficiency of the proposed rule remains bounded.
In contrast with most previous studies in the literature, the results in the
present paper have not assumed independence among the data sources and have
not relied on any prior information regarding how the sources are affected by
the change. Thus, we have applied the procedures and the results to the
problems of detecting a change in (i) the marginal distributions of multiple,
not necessarily independent, data sources and (ii) the correlation structure
of multiple Gaussian data sources. In the context of the first problem, we
have generalized the results in [15, 16, 17] by relaxing the assumption that
exactly one source is affected by the change, and establishing an asymptotic
optimality property that holds for any possible number of sources affected by
the change, as long as the signal to noise ratio is the same in all affected
sources.

There are several potential open questions for further research, such as a
more precise description of the optimal worst-case detection delay, and the
consideration of more general setups that may involve temporal dependence
and/or in which the pre-change and post-change distributions belong to
parametric families. Other directions of interest include considering
alternative error and delay metrics, studying an asymptotic regime where the
number of sources also goes to infinity as the false alarm rate vanishes,
modeling the data streams using spatial models, e.g., a Markov random field,
where the special underlying dependence could be used to obtain more efficient
rules in practice. Finally, it would be of interest to design procedures that
provide guarantees for the correct isolation of the sources that are affected
by the change under such sampling constraints.

##  Appendix A Some Useful Lemmas for Lower Bound Analysis

In this section, we assume that assumption (15) holds and present some lemmas
that are critical in establishing the universal asymptotic lower bound in
Theorem III.1. We denote by $\lambda_{n}^{E}({\sf G})$ the LLR of ${\sf G}$
versus ${\sf F}$ based on the samples from the sources in $E$ at time $n$,
i.e.,

$\displaystyle\lambda_{n}^{E}({\sf G}):=\log\frac{d{\sf G}^{E}}{d{\sf
F}^{E}}\left(X_{n}^{E}\right)\ .$ (89)

Therefore, from the definition of $\mathcal{A}({\sf G})$, it is noted that

$\displaystyle\lambda_{n}^{E}({\sf G})=0\ ,\quad\text{if}\quad
E\notin\mathcal{A}({\sf G})\ .$ (90)

Note that, for every ${\sf G}\in\mathcal{G}$ and $E\in\mathcal{A}({\sf G})$,
the LLRs $\\{\lambda_{n}^{E}({\sf G}):n\in\mathbb{N}\\}$ are identically
distributed under ${\sf G}$, with mean $\mathcal{I}^{E}_{0}({\sf G})$ and
variance

$\displaystyle\mathcal{V}^{E}_{0}({\sf G}):={\sf E}_{{\sf
G}}\left[\left(\lambda_{1}^{E}({\sf G})-\mathcal{I}^{E}_{0}({\sf
G})\right)^{2}\right]<\infty\ .$ (91)

The finiteness in (91) follows from (15).

###### Lemma A.1

Suppose ${\sf G}\in\mathcal{G}$, $\nu\geq 0$, and $S$ is any sampling rule.
Then for every $n\geq\nu+1$ we have

$\displaystyle\text{(i)}\qquad\qquad\mathbb{E}_{\nu}^{{\sf
G}}\left[\left(\lambda_{n}^{S_{n}}({\sf G})-\mathcal{I}^{S_{n}}_{0}({\sf
G})\right)\;\Bigg{|}\;\mathcal{F}_{n-1}^{S}\right]=\;0\ ,$ (92)
$\displaystyle\text{(ii)}\qquad\quad\;\;\,\mathbb{E}_{\nu}^{{\sf
G}}\left[\left(\lambda_{n}^{S_{n}}({\sf G})-\mathcal{I}^{S_{n}}_{0}({\sf
G})\right)^{2}\;\Bigg{|}\;\mathcal{F}_{n-1}^{S}\right]=\;\mathcal{V}^{S_{n}}_{0}({\sf
G})\,\mathbbm{1}\\{S_{n}\in\mathcal{A}({\sf G})\\}\ .$ (93)

###### Proof:

By assumption, $X_{n}^{S_{n}}$ is conditionally independent of
$\mathcal{F}_{n-1}^{S}$ given $S_{n}$, i.e.,

$\displaystyle
X_{n}^{S_{n}}\;\Big{|}\;\mathcal{F}_{n-1}^{S}\;\overset{d}{=}\;X_{n}^{S_{n}}\
.$ (94)

Thus, for every $n\geq\nu+1$

$\displaystyle\mathbb{E}_{\nu}^{{\sf G}}\left[\left(\lambda_{n}^{S_{n}}({\sf
G})-\mathcal{I}^{S_{n}}_{0}({\sf
G})\right)\;\Bigg{|}\;\mathcal{F}_{n-1}^{S}\right]$
$\displaystyle=\sum_{E}\mathbb{E}_{\nu}^{{\sf G}}\left[\lambda_{n}^{E}({\sf
G})-\mathcal{I}^{E}_{0}({\sf G})\right]\,\mathbbm{1}\\{S_{n}=E\\}$ (95)
$\displaystyle=0\ ,$ (96)

and

$\displaystyle\mathbb{E}_{\nu}^{{\sf G}}\left[\left(\lambda_{n}^{S_{n}}({\sf
G})-\mathcal{I}^{S_{n}}_{0}({\sf
G})\right)^{2}\;\Bigg{|}\;\mathcal{F}_{n-1}^{S}\right]\ $
$\displaystyle=\sum_{E}\mathbb{E}_{\nu}^{{\sf
G}}\left[\left(\lambda_{n}^{E}({\sf G})-\mathcal{I}^{E}_{0}({\sf
G})\right)^{2}\right]\,\mathbbm{1}\\{S_{n}=E\\}$ (97)
$\displaystyle=\sum_{E}\mathcal{V}^{E}_{0}({\sf G})\,\mathbbm{1}\\{S_{n}=E\\}$
(98) $\displaystyle=\mathcal{V}^{S_{n}}_{0}({\sf
G})\,\mathbbm{1}\\{S_{n}\in\mathcal{A}({\sf G})\\}\ ,$ (99)

where the first equality is due to (94) and the second equality follows by
noting that for any $n\geq\nu+1$ and $E\in\mathcal{A}({\sf G})$ we have

$\displaystyle X_{n}^{S_{n}}\;\Big{|}\;S_{n}=E\sim{\sf G}^{E}\ ,$ (100)

which implies

$\displaystyle\mathbb{E}_{\nu}^{{\sf G}}\left[\left(\lambda_{n}^{S_{n}}({\sf
G})-\mathcal{I}^{S_{n}}_{0}({\sf
G})\right)^{2}\;\Big{|}\;S_{n}=E\right]=\mathbb{E}_{\nu}^{{\sf
G}}\left[\left(\lambda_{n}^{E}({\sf G})-\mathcal{I}^{E}_{0}({\sf
G})\right)^{2}\right]=\mathcal{V}^{E}_{0}({\sf G})\ .$ (101)

Also, for any $E\notin\mathcal{A}({\sf G})$

$\displaystyle X_{n}^{S_{n}}\;\Big{|}\;S_{n}=E\sim{\sf F}^{E}\ ,$ (102)

which implies

$\displaystyle\left[\left(\lambda_{n}^{S_{n}}({\sf
G})-\mathcal{I}^{S_{n}}_{0}({\sf G})\right)^{2}\;\Big{|}\;S_{n}=E\right]\equiv
0\ .$ (103)

This completes the proof. ∎

###### Lemma A.2

Suppose ${\sf G}\in\mathcal{G}$, $\nu\geq 0$, and $S$ is any sampling rule.
For any $n\geq 0$, let

$\displaystyle Z_{n}:=\log\frac{d\mathbb{P}_{0}^{{\sf
G}}}{d\mathbb{P}_{\infty}}(\mathcal{F}^{S}_{n})\ \qquad\text{and}\qquad\
A_{n}:=\sum_{t=1}^{n}\mathcal{I}^{S_{t}}_{0}({\sf G})\ ,$ (104)

where $Z_{0}$ and $A_{0}\equiv 0$. Then under $\mathbb{P}_{\nu}^{{\sf G}}$,
the process

$\displaystyle\\{(Z_{n}-A_{n})-(Z_{\nu}-A_{\nu}):n>\nu\\}$ (105)

is a zero-mean martingale with respect to the filtration
$\\{\mathcal{F}_{n}^{S}:n>\nu\\}$.

###### Proof:

Note that, for every $n\in\mathbb{N}$,

$\displaystyle Z_{n}-A_{n}=\sum_{t=1}^{n}\left(\lambda_{t}^{S_{t}}({\sf
G})-\mathcal{I}^{S_{t}}_{0}({\sf G})\right)\ .$ (106)

Consequently, for every $n>\nu$ we have

$\displaystyle(Z_{n}-A_{n})-(Z_{\nu}-A_{\nu})=\sum_{t=\nu+1}^{n}\left(\lambda_{t}^{S_{t}}({\sf
G})-\mathcal{I}^{S_{t}}_{0}({\sf G})\right)\ .$ (107)

Then, using (107), for every $n>\nu$, from (15) we obtain

$\displaystyle\mathbb{E}_{\nu}^{{\sf
G}}\left[|(Z_{n}-A_{n})-(Z_{\nu}-A_{\nu})|\right]$
$\displaystyle\leq\sum_{t=\nu+1}^{n}\mathbb{E}_{\nu}^{{\sf
G}}\left[|\lambda_{t}^{S_{t}}({\sf G})-\mathcal{I}^{S_{t}}_{0}({\sf
G})|\right]$ (108) $\displaystyle=\sum_{t=\nu+1}^{n}\sum_{E\in\mathcal{A}({\sf
G})}\mathbb{E}_{\nu}^{{\sf G}}\left[|\lambda_{t}^{E}({\sf
G})-\mathcal{I}^{E}_{0}({\sf G})|\mathbbm{1}\\{S_{t}=E\\}\right]$ (109)
$\displaystyle\leq\sum_{t=\nu+1}^{n}\sum_{E\in\mathcal{A}({\sf
G})}\mathbb{E}_{\nu}^{{\sf G}}\left[|\lambda_{t}^{E}({\sf
G})-\mathcal{I}^{E}_{0}({\sf G})|\right]$ (110)
$\displaystyle=(n-\nu)\sum_{E\in\mathcal{A}({\sf G})}\mathbb{E}_{\nu}^{{\sf
G}}\left[|\lambda_{\nu+1}^{E}({\sf G})-\mathcal{I}^{E}_{0}({\sf
G})|\right]<\infty\ ,$ (111)

where the last inequality follows from (91). Furthermore, we have

$\displaystyle\mathbb{E}_{\nu}^{{\sf
G}}\left[(Z_{n}-A_{n})-(Z_{\nu}-A_{\nu})\;|\;\mathcal{F}_{n-1}^{S}\right]$
$\displaystyle=\mathbb{E}_{\nu}^{{\sf
G}}\bigg{[}\sum_{t=\nu+1}^{n-1}\left(\lambda_{t}^{S_{t}}({\sf
G})-\mathcal{I}^{S_{t}}_{0}({\sf G})\right)+\left(\lambda_{n}^{S_{n}}({\sf
G})-\mathcal{I}^{S_{n}}_{0}({\sf
G})\right)\;\Bigg{|}\;\mathcal{F}_{n-1}^{S}\bigg{]}$ (112)
$\displaystyle=(Z_{n-1}-A_{n-1})-(Z_{\nu}-A_{\nu})+\mathbb{E}_{\nu}^{{\sf
G}}\left[\left(\lambda_{n}^{S_{n}}({\sf G})-\mathcal{I}^{S_{n}}_{0}({\sf
G})\right)\;\Bigg{|}\;\mathcal{F}_{n-1}^{S}\right]\ .$ (113)

Therefore, it suffices to show that the second term in (113) is $0$, which
follows from Lemma A.1. ∎

######  Lemma A.3 (Optional Stopping Theorem)

For some $\nu\geq 0$, let $\\{M_{n}:n>\nu\\}$ be a submartingale with respect
to some filtration $\\{\mathcal{G}_{n}:n>\nu\\}$, and $T$ be a stopping time
such that $T\in\\{\nu+1,\dots,N\\}$, where $N\in\mathbb{N}$. Then

$\displaystyle M_{T}\leq{\sf E}\left[M_{N}|\mathcal{G}_{T}\right]\ ,$ (114)

where ${\sf E}[\cdot]$ denotes the underlying expectation.

###### Proof:

This is a standard and fundamental result in probability theory. see, e.g.,
[12, Theorem 2.3.1]. ∎

######  Lemma A.4 (Conditional Doob’s Submartingale Inequality)

For some $\nu\geq 0$, let $\\{M_{n}:n>\nu\\}$ be a submartingale with respect
to some filtration $\\{\mathcal{G}_{n}:n>\nu\\}$. Then for every $a>0$ and
$n\geq 1$ the following holds almost surely:

$\displaystyle{\sf P}\left(\max_{\nu+1\leq k\leq\nu+n}M_{k}\geq
a\;\;\Bigg{|}\;\;\mathcal{G}_{\nu}\right)\leq\frac{{\sf
E}\left[M_{\nu+n}|\mathcal{G}_{\nu}\right]}{a}\ ,$ (115)

where ${\sf P}$ and ${\sf E}[\cdot]$ are the underlying probability measure
and its corresponding expectation, respectively.

###### Proof:

We fix $a>0$ and $n\geq 1$, and define the following stopping time

$\displaystyle T:=\inf\left\\{k\geq\nu+1:M_{k}\geq a\right\\}\wedge(\nu+n)\;,$
(116)

which clearly satisfies $\nu+1\leq T\leq\nu+n$ and

$\displaystyle\left\\{\max_{\nu+1\leq k\leq\nu+n}M_{k}\geq
a\right\\}=\left\\{M_{T}\geq a\right\\}\ .$ (117)

Then,

$\displaystyle{\sf P}\left(\max_{\nu+1\leq k\leq\nu+n}M_{k}\geq
a\;\;\Bigg{|}\;\;\mathcal{G}_{\nu}\right)$ $\displaystyle={\sf
P}\left(M_{T}\geq a\,\;\Bigg{|}\;\,\mathcal{G}_{\nu}\right)$ (118)
$\displaystyle\leq\frac{1}{a}{\sf E}\left[M_{T}\mathbbm{1}\left\\{M_{T}\geq
a\right\\}\;\Bigg{|}\;\mathcal{G}_{\nu}\right]$ (119)
$\displaystyle\leq\frac{1}{a}{\sf
E}\left[M_{\nu+n}\mathbbm{1}\left\\{M_{T}\geq
a\right\\}\;\Bigg{|}\;\mathcal{G}_{\nu}\right]$ (120)
$\displaystyle\leq\frac{1}{a}{\sf
E}\left[M_{\nu+n}\;\Bigg{|}\;\mathcal{G}_{\nu}\right]\ ,$ (121)

where the inequality in (120) holds, since for any
$A\in\mathcal{G}_{\nu}\subseteq\mathcal{G}_{T}$ we have $A\cap\\{M_{T}\geq
a\\}\in\mathcal{G}_{T}$ and, thus, by Lemma A.3 we have

$\displaystyle{\sf E}\left[M_{T}\mathbbm{1}\left\\{A\cap\left\\{M_{T}\geq
a\right\\}\right\\}\right]\leq{\sf
E}\left[M_{\nu+n}\mathbbm{1}\left\\{A\cap\left\\{M_{T}\geq
a\right\\}\right\\}\right]\ .$ (122)

The proof is complete. ∎

###### Lemma A.5

Suppose ${\sf G}\in\mathcal{G}$ and $(S,T)$ is any sequential change detection
policy. Then for any $\nu,n\in\mathbb{N}$ we have

$\displaystyle\begin{split}\mathbb{E}_{\nu}^{{\sf
G}}\left[\left\\{\sum_{t=\nu+1}^{\nu+n}\left(\lambda_{t}^{S_{t}}({\sf
G})-\mathcal{I}^{S_{t}}_{0}({\sf
G})\right)\right\\}^{2}\;\Bigg{|}\;T>\nu\right]\leq
n\;\max_{E\in\mathcal{A}({\sf G})}\mathcal{V}^{E}_{0}({\sf G})\ .\end{split}$
(123)

###### Proof:

For any $\nu+1\leq t\leq\nu+n$, we have

$\displaystyle\mathbb{E}_{\nu}^{{\sf G}}\left[\left(\lambda_{t}^{S_{t}}({\sf
G})-\mathcal{I}^{S_{t}}_{0}({\sf G})\right)^{2}\;\;\Bigg{|}\;\;T>\nu\right]$
$\displaystyle=\mathbb{E}_{\nu}^{{\sf G}}\left[\mathbb{E}_{\nu}^{{\sf
G}}\left[\left(\lambda_{t}^{S_{t}}({\sf G})-\mathcal{I}^{S_{t}}_{0}({\sf
G})\right)^{2}\;\Bigg{|}\;\mathcal{F}^{S}_{t-1}\right]\;\Bigg{|}\;\;T>\nu\right]$
(124) $\displaystyle=\mathbb{E}_{\nu}^{{\sf
G}}\left[\mathcal{V}^{S_{t}}_{0}({\sf
G})\mathbbm{1}\\{S_{t}\in\mathcal{A}({\sf G})\\}\;\Bigg{|}\;\;T>\nu\right]$
(125) $\displaystyle\leq\mathbb{E}_{\nu}^{{\sf
G}}\left[\mathbbm{1}\\{S_{t}\in\mathcal{A}({\sf
G})\\}\max_{E\in\mathcal{A}({\sf G})}\mathcal{V}^{E}_{0}({\sf
G})\;\Bigg{|}\;\;T>\nu\right]$ (126)
$\displaystyle\leq\max_{E\in\mathcal{A}({\sf G})}\mathcal{V}^{E}_{0}({\sf
G})\;\mathbb{P}_{\nu}^{{\sf G}}\left(S_{t}\in\mathcal{A}({\sf
G})\;\Bigg{|}\;\;T>\nu\right)\ ,$ (127)

where (124) follows by using the tower property of conditional expectation and
the fact that,
$\\{T>\nu\\}\in\mathcal{F}^{S}_{\nu-1}\subseteq\mathcal{F}^{S}_{t-1}$, and
(125) follows from Lemma A.1(ii). ∎

##  Appendix B Proof of Universal Asymptotic Lower Bound

Fix any arbitrary ${\sf G}\in\mathcal{G}$, $\nu\geq 0$,
$(S,T)\in\Delta(\gamma)$ and consider the sequences $\\{Z_{n},A_{n}:n\geq
0\\}$ as defined in (104). Then by using Lemma A.2, under
$\mathbb{P}_{\nu}^{\sf G}$ and with respect to the filtration
$\\{\mathcal{F}_{n}^{S}:n>\nu\\}$, the process
$\\{(Z_{n}-A_{n})-(Z_{\nu}-A_{\nu}):n>\nu\\}$ is a zero-mean martingale, which
further implies that the process

$\displaystyle\\{\\{(Z_{n}-A_{n})-(Z_{\nu}-A_{\nu})\\}^{2}:n>\nu\\}\ ,$ (128)

is a submartingale. Note that, for any $m,n\in\mathbb{N}$, such that $m<n$ we
have

$\displaystyle A_{n}-A_{m}\leq(n-m)\;\mathcal{I}_{*}\
,\qquad\text{where}\quad\mathcal{I}_{*}:=\max_{E\in\mathcal{A}({\sf
G})}\mathcal{I}^{E}_{0}({\sf G})\ .$ (129)

Now, for an arbitrary $0<\epsilon<1$ and $\gamma>1$ we define

$\displaystyle
N_{\gamma,\epsilon}:=\frac{\log\gamma}{\mathcal{I}_{*}}(1-\epsilon)\ .$ (130)

and

$\log\eta_{\gamma}:=(1-\epsilon^{2})\log\gamma=(1+\epsilon)N_{\gamma,\epsilon}\mathcal{I}_{*}\
.$ (131)

Then by the definition of $D^{{\sf G}}(S,T)$ in (11) and Markov’s inequality
it follows that, for any $\nu\geq 0$,

$\displaystyle\begin{split}D^{{\sf G}}(S,T)&\geq\mathbb{E}_{\nu}^{{\sf
G}}[T-\nu\,|\,T>\nu]\\\ &\geq N_{\gamma,\epsilon}\,\mathbb{P}_{\nu}^{{\sf
G}}\left(T-\nu>N_{\gamma,\epsilon}\,|\,T>\nu\right)\\\
&=N_{\gamma,\epsilon}\,(1-\mathbb{P}_{\nu}^{{\sf G}}\left(T-\nu\leq
N_{\gamma,\epsilon}\,|\,T>\nu\right)\\\
&=N_{\gamma,\epsilon}\,\left(1-p(\nu,T)-q(\nu,T)\right)\ ,\end{split}$ (132)

where we have defined

$\displaystyle p(\nu,T)$ $\displaystyle:=\mathbb{P}_{\nu}^{{\sf
G}}\left(T-\nu\leq
N_{\gamma,\epsilon},\;e^{Z_{T}-Z_{\nu}}>\eta_{\gamma}|T>\nu\right)\ ,$ (133)
$\displaystyle q(\nu,T)$ $\displaystyle:=\mathbb{P}_{\nu}^{{\sf
G}}\left(T-\nu\leq
N_{\gamma,\epsilon},\;e^{Z_{T}-Z_{\nu}}\leq\eta_{\gamma}|T>\nu\right)\ .$
(134)

First, we find an upper bound on $p(\nu,T)$ for any $\nu\geq 0$. To this end,
note that

$\displaystyle\left\\{T\leq\nu+N_{\gamma,\epsilon},e^{Z_{T}-Z_{\nu}}>\eta_{\gamma}\right\\}$
(135) $\displaystyle\subseteq\left\\{\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}{Z_{k}-Z_{\nu}}>\log\eta_{\gamma}\right\\}$ (136)
$\displaystyle\subseteq\left\\{\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}\big{\\{}(Z_{k}-A_{k})-(Z_{\nu}-A_{\nu})\big{\\}}+\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}(A_{k}-A_{\nu})>\log\eta_{\gamma}\right\\}$ (137)
$\displaystyle\overset{\eqref{eta_gamma}}{=}\left\\{\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}\big{\\{}(Z_{k}-A_{k})-(Z_{\nu}-A_{\nu})\big{\\}}+\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}(A_{k}-A_{\nu})>N_{\gamma,\epsilon}\mathcal{I}_{*}+\epsilon
N_{\gamma,\epsilon}\mathcal{I}_{*}\right\\}$ (138)
$\displaystyle\subseteq\left\\{\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}\big{\\{}(Z_{k}-A_{k})-(Z_{\nu}-A_{\nu})\big{\\}}>\epsilon
N_{\gamma,\epsilon}\mathcal{I}_{*}\right\\}$ (139)
$\displaystyle\subseteq\left\\{\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}\big{\\{}(Z_{k}-A_{k})-(Z_{\nu}-A_{\nu})\big{\\}}^{2}>\epsilon^{2}N_{\gamma,\epsilon}^{2}\mathcal{I}_{*}^{2}\right\\}\
.$ (140)

The relationship in (139) holds because for every $\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}$, by using (129) we have:

$\displaystyle A_{k}-A_{\nu}\leq(k-\nu)\mathcal{I}_{*}\leq
N_{\gamma,\epsilon}\mathcal{I}_{*}\ .$ (141)

Now, conditioning on the event $\\{T>\nu\\}$ and following (140), we have

$\displaystyle p(\nu,T)$ $\displaystyle=\mathbb{P}_{\nu}^{{\sf
G}}\left(T\leq\nu+N_{\gamma,\epsilon},e^{Z_{T}-Z_{\nu}}>\eta_{\gamma}|T>\nu\right)$
(142) $\displaystyle\leq\mathbb{P}_{\nu}^{{\sf G}}\bigg{(}\max_{\nu+1\leq
k\leq\nu+N_{\gamma,\epsilon}}\big{\\{}(Z_{k}-A_{k})-(Z_{\nu}-A_{\nu})\big{\\}}^{2}>\epsilon^{2}N_{\gamma,\epsilon}^{2}\mathcal{I}_{*}^{2}\;\Bigg{|}\;T>\nu\bigg{)}$
(143) $\displaystyle\leq\frac{\mathbb{E}_{\nu}^{\sf
G}\left[\left\\{\left(Z_{\nu+N_{\gamma,\epsilon}}-A_{\nu+N_{\gamma,\epsilon}}\right)-\left(Z_{\nu}-A_{\nu}\right)\right\\}^{2}\;\Bigg{|}\;T>\nu\right]}{\epsilon^{2}N_{\gamma,\epsilon}^{2}\mathcal{I}_{*}^{2}}$
(144) $\displaystyle=\frac{\mathbb{E}_{\nu}^{{\sf
G}}\left[\left\\{\sum_{t=\nu+1}^{\nu+N_{\gamma,\epsilon}}\left(\lambda_{t}^{S_{t}}({\sf
G})-\mathcal{I}^{S_{t}}_{0}({\sf
G})\right)\right\\}^{2}\;\Bigg{|}\;T>\nu\right]}{\epsilon^{2}N_{\gamma,\epsilon}^{2}\mathcal{I}_{*}^{2}}$
(145) $\displaystyle\leq\max_{E\in\mathcal{A}({\sf
G})}\mathcal{V}^{E}_{0}({\sf
G})\;\frac{N_{\gamma,\epsilon}}{\epsilon^{2}N_{\gamma,\epsilon}^{2}\mathcal{I}_{*}^{2}}$
(146) $\displaystyle=\max_{E\in\mathcal{A}({\sf G})}\mathcal{V}^{E}_{0}({\sf
G})\;\frac{1}{\epsilon^{2}N_{\gamma,\epsilon}\mathcal{I}_{*}^{2}}\equiv\xi_{\epsilon}(\gamma)\
.$ (147)

The inequality in (144) holds by using Lemma A.4 for the submartingale
process, $\\{\\{(Z_{n}-A_{n})-(Z_{\nu}-A_{\nu})\\}^{2}:n>\nu\\}$, and the
inequality in (146) follows from Lemma A.5. Now, since for any given
$\epsilon>0$, $N_{\gamma,\epsilon}\to\infty$ as $\gamma\to\infty$, we have
$\xi_{\epsilon}(\gamma)\to 0$ as $\gamma\to\infty$.

Next, we characterize an upper bound on $q(\nu,T)$. For this purpose, we
follow the approach developed in the proof of Theorem 1 in [26]. Let
$n_{\gamma}$ be the largest integer less than or equal to
$\left(\log\gamma\right)^{2}$. Then, as shown in the proof of Theorem 1 in
[26], there exists $\nu_{\gamma}\geq 1$ such that

$\displaystyle\mathbb{P}_{\infty}\left(T\geq\nu_{\gamma}\right)>0\
,\qquad\text{and}\qquad\mathbb{P}_{\infty}\left(T<\nu_{\gamma}+n_{\gamma}|T\geq\nu_{\gamma}\right)\leq\frac{n_{\gamma}}{\gamma}\
.$ (148)

Thus, for $\gamma$ large enough,

$\displaystyle q(\nu_{\gamma},T)$
$\displaystyle=\mathbb{P}_{\nu_{\gamma}}^{{\sf
G}}\left(T\leq\nu_{\gamma}+N_{\gamma,\epsilon},e^{Z_{T}-Z_{\nu_{\gamma}}}\leq\eta_{\gamma}|T>\nu_{\gamma}\right)$
(149) $\displaystyle=\frac{\mathbb{P}_{\nu_{\gamma}}^{{\sf
G}}\left(\nu_{\gamma}<T\leq\nu_{\gamma}+N_{\gamma,\epsilon},e^{Z_{T}-Z_{\nu_{\gamma}}}\leq\eta_{\gamma}\right)}{\mathbb{P}_{\infty}(T>\nu_{\gamma})}$
(150)
$\displaystyle=\frac{\mathbb{E}_{\infty}[e^{Z_{T}-Z_{\nu_{\gamma}}}\mathbbm{1}\\{\nu_{\gamma}<T\leq\nu_{\gamma}+N_{\gamma,\epsilon},e^{Z_{T}-Z_{\nu_{\gamma}}}\leq\eta_{\gamma}\\}]}{\mathbb{P}_{\infty}(T>\nu_{\gamma})}$
(151)
$\displaystyle\leq\frac{\eta_{\gamma}\,\mathbb{P}_{\infty}\left(\nu_{\gamma}<T\leq\nu_{\gamma}+N_{\gamma,\epsilon}\right)}{\mathbb{P}_{\infty}(T>\nu_{\gamma})}$
(152)
$\displaystyle=\eta_{\gamma}\,\mathbb{P}_{\infty}\left(T\leq\nu_{\gamma}+N_{\gamma,\epsilon}|T>\nu_{\gamma}\right)$
(153)
$\displaystyle\leq\eta_{\gamma}\,\mathbb{P}_{\infty}\left(T\leq\nu_{\gamma}+n_{\gamma}|T>\nu_{\gamma}\right)$
(154) $\displaystyle\leq\eta_{\gamma}\,\frac{n_{\gamma}}{\gamma}$ (155)
$\displaystyle\leq\gamma^{-\epsilon^{2}}\left(\log\gamma\right)^{2}$ (156)
$\displaystyle\equiv\xi^{\prime}_{\epsilon}(\gamma)\ .$ (157)

The equality in (150) follows from the fact that,
$\mathbb{P}_{\nu_{\gamma}}^{{\sf
G}}(T>\nu_{\gamma})=\mathbb{P}_{\infty}(T>\nu_{\gamma})$ since
$\\{T>\nu_{\gamma}\\}\in\mathcal{F}^{S}_{\nu_{\gamma}}$. The inequality in
(154) follows because for sufficiently large $\gamma$,
$N_{\gamma,\epsilon}\leq n_{\gamma}$ for every $\epsilon>0$, and the
inequality in (155) follows from (148). It is important to observe that
$\xi^{\prime}_{\epsilon}(\gamma)\to 0$ as $\gamma\to\infty$ for any given
$\epsilon>0$. Finally from (132), we have, for all large $\gamma$,

$\displaystyle D^{{\sf G}}(S,T)$ $\displaystyle\geq
N_{\gamma,\epsilon}\,\left(1-p(\nu_{\gamma},T)-q(\nu_{\gamma},T)\right)$ (158)
$\displaystyle\geq\frac{\log\gamma}{\mathcal{I}_{*}}(1-\epsilon)\;(1-\xi_{\epsilon}(\gamma)-\xi^{\prime}_{\epsilon}(\gamma))\
.$ (159)

Now, we let first $\gamma\to\infty$, and then $\epsilon\to 0$, and the proof
is complete.

##  Appendix C Some Useful Lemmas for Performance Analysis

In this appendix, we present some lemmas that are useful in proving Theorem
IV.1 and Theorem IV.2. All random variables are defined on a probability space
$(\Omega,\mathcal{F},{\sf P})$, and we denote by ${\sf E}[\cdot]$ the
corresponding expectation.

For the first two lemmas, namely Lemma C.1 and Lemma C.3, we assume that
$\\{Z_{n}:n\in\mathbb{N}\\}$ is a sequence of independent and identically
distributed (i.i.d.) random variables, and we set

$\displaystyle S_{n}:=\sum_{t=1}^{n}Z_{t},\quad n\in\mathbb{N}\ .$ (160)

Furthermore, we fix some arbitrary $A>0$, and for any $x\in[0,A)$ we set
$\pi(x):=\min\\{\pi_{-}(x),\pi_{+}(x)\\}$, where

$\displaystyle\pi_{-}(x)$ $\displaystyle:=\inf\left\\{n\geq
1:S_{n}<-x\right\\}\ ,$ (161) $\displaystyle\pi_{+}(x)$
$\displaystyle:=\inf\left\\{n\geq 1:S_{n}>A-x\right\\}\ .$ (162)

Furthermore, we assume that the first two moments of $Z_{1}$ exist, and we
denote them as follows:

$\displaystyle\mathcal{I}:={\sf E}[Z_{1}]\ \qquad\text{and}\qquad\
\mathcal{V}:={\sf E}\left[\left(Z_{1}-\mathcal{I}\right)^{2}\right]\ .$ (163)

###### Lemma C.1

If $0<\mathcal{I}<\infty$, then for any $x\in[0,A)$ we have, as $A\to\infty$,

$\displaystyle\frac{{\sf E}\left[\pi(x)\right]}{{\sf
P}\left(\pi_{+}(x)<\pi_{-}(x)\right)}\leq\frac{A-x}{\mathcal{I}}+o(A)\ .$
(164)

If, also, $\mathcal{V}<\infty$, then the inequality (164) holds for every
$A>0$ with the $o(A)$ term being replaced with

$\displaystyle\frac{1}{p}\left(1+\frac{\mathcal{V}}{\mathcal{I}^{2}}\right),\qquad\text{where}\;\;\;p:=\;{\sf
P}\left(\pi_{-}(0)=\infty\right)>0\ .$ (165)

In particular, when $x=0$, the upper bound holds even without the factor
$1/p$.

###### Proof:

For any $x\in[0,A)$ we have

$\displaystyle\mathcal{I}\,{\sf E}\left[\pi(x)\right]$ $\displaystyle={\sf
E}\left[S_{\pi(x)}\right]$ (166) $\displaystyle={\sf
E}\left[S_{\pi(x)}\mathbbm{1}\\{\pi_{+}(x)<\pi_{-}(x)\\}\right]+{\sf
E}\left[S_{\pi(x)}\;\mathbbm{1}\\{\pi_{-}(x)<\pi_{+}(x)\\}\right]$ (167)
$\displaystyle\leq{\sf
E}\left[S_{\pi(x)}\mathbbm{1}\\{\pi_{+}(x)<\pi_{-}(x)\\}\right]$ (168)
$\displaystyle=(A-x)\;{\sf P}\left(\pi_{+}(x)<\pi_{-}(x)\right)+{\sf
E}\left[(S_{\pi(x)}-(A-x))\;\mathbbm{1}\\{\pi_{+}(x)<\pi_{-}(x)\\}\right]$
(169) $\displaystyle\leq(A-x)\;{\sf
P}\left(\pi_{+}(x)<\pi_{-}(x)\right)+o(A),$ (170)

where the equality in (166) follows from Wald’s identity, the inequality in
(168) follows from the fact that

$\displaystyle
S_{\pi(x)}\mathbbm{1}\\{\pi_{-}(x)<\pi_{+}(x)\\}=S_{\pi_{-}(x)}\mathbbm{1}\\{\pi_{-}(x)<\pi_{+}(x)\\}\leq
0\ ,$ (171)

and the inequality in (170) holds from (166) along with the fact, due to the
elementary renewal theorem, that, as $(A-x)\to\infty$,

$\displaystyle{\sf E}\left[S_{\pi(x)}\right]=\mathcal{I}\,{\sf
E}\left[\pi(x)\right]\leq(A-x)+o(A-x)\ ,$ (172)

and also, $o(A-x)/A\leq o(A-x)/(A-x)\to 0$. The inequality in (170) further
leads to

$\displaystyle\frac{\mathcal{I}\;{\sf E}\left[\pi(x)\right]}{{\sf
P}\left(\pi_{+}(x)<\pi_{-}(x)\right)}$
$\displaystyle\leq(A-x)+\frac{o(A)}{{\sf
P}\left(\pi_{+}(x)<\pi_{-}(x)\right)}$ (173)
$\displaystyle\leq(A-x)+\frac{o(A)}{{\sf P}\left(\pi_{-}(x)=\infty\right)}$
(174) $\displaystyle\leq(A-x)+\frac{o(A)}{p}\ .$ (175)

The inequalities in (174) and (175) follow by using the fact that

$\displaystyle{\sf P}\left(\pi_{+}(x)<\pi_{-}(x)\right)\geq{\sf
P}\left(\pi_{-}(x)=\infty\right)\geq{\sf P}\left(\pi_{-}(0)=\infty\right)=p\
,$ (176)

where the second inequality in (176) follows from the fact that, for every
$x\geq 0$, $\pi_{-}(x)\geq\pi_{-}(0)$ as $\pi_{-}(x)$ is an increasing
function with respect to $x$. Furthermore, the positivity of $p$ follows from
the fact that, for large $A$,

$\displaystyle p={\sf P}\left(\pi_{-}(0)=\infty\right)=\frac{1}{{\sf
E}\left[\pi_{+}(A)\right]}\geq\frac{1}{{\sf
E}\left[\pi_{+}(0)\right]}\geq\left(\frac{A+o(A)}{\mathcal{I}}\right)^{-1}>0\
,$ (177)

where, in (177), the second equality follows from [27, Corollary 8.39], the
first inequality holds because $\pi_{+}(0)\geq\pi_{+}(A)$, as $\pi_{+}(x)$ is
a decreasing function with respect to $x$, and the second inequality follows
from what is shown next. Note that the quantity

$\displaystyle\frac{{\sf E}\left[\pi(0)\right]}{{\sf
P}\left(\pi_{+}(0)<\pi_{-}(0)\right)}\ ,$ (178)

represents the expected detection delay of a CUSUM process adapted to the
sequence $\\{S_{n}:n\in\mathbb{N}\\}$ [12]. Since for every $n\in\mathbb{N}$
the CUSUM process at time $n$ can always be bounded below by $S_{n}$, the
detection delay can be consequently bounded above by $\pi_{+}(0)$. Therefore,
as $A\to\infty$,

$\displaystyle\mathcal{I}\,\frac{{\sf E}\left[\pi(0)\right]}{{\sf
P}\left(\pi_{+}(0)<\pi_{-}(0)\right)}$ $\displaystyle\leq\mathcal{I}\,{\sf
E}\left[\pi_{+}(0)\right]$ (179) $\displaystyle={\sf
E}\left[S_{\pi_{+}(0)}\right]$ (180) $\displaystyle\leq A+o(A)\ ,$ (181)

where the equality in (180) follows from Wald’s identity and the inequality in
(181) follows similarly to (170) If, also, $\mathcal{V}<\infty$, then by
Theorem 1 in [28] it follows that, for every $A>0$, each of the above
relations holds with the $o(A)$ term being replaced with

$\displaystyle\frac{1}{\mathcal{I}}{\sf
E}\left[\left({S_{1}^{+}}\right)^{2}\right]\leq\frac{\mathcal{V}+\mathcal{I}^{2}}{\mathcal{I}}\
,$ (182)

where the inequality follows from the fact that $S_{1}^{+}\leq|S_{1}|$. This
completes the proof.
∎

###### Lemma C.2

For any non-negative random variable $X$ and two disjoint non-null events
$H_{1}$ and $H_{2}$, we have

$\displaystyle{\sf E}\left[X\;\Big{|}\;H_{1}\cup H_{2}\right]\leq{\sf
E}\left[X\;\Big{|}\;H_{1}\right]+{\sf E}\left[X\;\Big{|}\;H_{2}\right]\ .$
(183)

###### Proof:

The proof follows from the below that

$\displaystyle{\sf E}\left[X\;\Big{|}\;H_{1}\cup H_{2}\right]$
$\displaystyle=\frac{{\sf E}\left[X\mathbbm{1}\\{H_{1}\cup
H_{2}\\}\right]}{{\sf P}\left(H_{1}\cup H_{2}\right)}$ (184)
$\displaystyle=\frac{{\sf E}\left[X\mathbbm{1}\\{H_{1}\\}\right]+{\sf
E}\left[X\mathbbm{1}\\{H_{2}\\}\right]}{{\sf P}(H_{1})+{\sf P}(H_{2})}$ (185)
$\displaystyle\leq\frac{{\sf E}\left[X\mathbbm{1}\\{H_{1}\\}\right]}{{\sf
P}(H_{1})}+\frac{{\sf E}\left[X\mathbbm{1}\\{H_{2}\\}\right]}{{\sf
P}(H_{2})}={\sf E}\left[X\;\Big{|}\;H_{1}\right]+{\sf
E}\left[X\;\Big{|}\;H_{2}\right]\ .$ (186)

∎

###### Lemma C.3

Let $W$ be a random variable independent of $\\{Z_{n}:n\in\mathbb{N}\\}$ such
that

$\displaystyle{\sf P}(W>x)\leq e^{-x},\quad x\geq 0\ .$ (187)

If $-\infty<\mathcal{I}<0$, then for every $A>0$ large enough, we have

$\displaystyle{\sf E}\left[\pi(W)\;\Big{|}\;W\in(0,A)\right]\leq C\ ,$ (188)

where $C<\infty$ is a constant independent of $A$.

###### Proof:

Since $\\{Z_{n}:n\in\mathbb{N}\\}$ is independent of $W$, for any $x\in(0,A)$
we have, as $x\to\infty$, and hence, $A\to\infty$,

$\displaystyle{\sf E}\left[\pi(W)\;\Big{|}\;W=x\right]\leq{\sf
E}\left[\pi_{-}(x)\right]\leq-\frac{x}{\mathcal{I}}+o(x)\ ,$ (189)

where the second inequality follows from the elementary renewal theorem (also
see the derivation in the proof of Lemma C.1). Fix any arbitrary $\epsilon>0$.
Then, there exists $M>0$ such that for every $x\geq M$,

$\displaystyle\frac{1}{x}{\sf
E}\left[\pi(W)\;\Big{|}\;W=x\right]\leq\mathcal{I}_{\epsilon}:=-\frac{1}{\mathcal{I}}+\epsilon\
.$ (190)

We assume that there exists $\kappa>1$ such that ${\sf P}(W>M)>e^{-\kappa M}$.
Otherwise, we have ${\sf P}(W\in(0,M])=1$, and thus, for every $A>M$,

$\displaystyle{\sf E}\left[\pi(W)\;\Big{|}\;W\in(0,A)\right]={\sf
E}\left[\pi(W)\;\Big{|}\;W\in(0,M]\right]\leq{\sf
E}\left[\pi_{-}(W)\mathbbm{1}\\{W\in(0,M]\\}\right]\leq{\sf
E}\left[\pi_{-}(M)\right]\ ,$ (191)

and the proof is complete. Then, for every $A\geq\kappa M$, we have

$\displaystyle{\sf E}\left[\pi(W)\;\Big{|}\;W\in(0,A)\right]$ (192)
$\displaystyle\leq{\sf E}\left[\pi(W)\;\Big{|}\;W\in(0,M]\right]+{\sf
E}\left[\pi(W)\;\Big{|}\;W\in(M,A)\right]$ (193) $\displaystyle=\frac{{\sf
E}\left[\pi(W)\mathbbm{1}\\{W\in(0,M]\\}\right]}{{\sf P}(W\in(0,M])}+{\sf
E}\left[{\sf
E}\left[\pi(W)\;\Big{|}\;W,W\in(M,A)\right]\;\Big{|}\;W\in(M,A)\right]$ (194)
$\displaystyle\leq\frac{{\sf E}\left[\pi_{-}(M)\right]}{1-e^{-M}}+{\sf
E}\left[\mathcal{I}_{\epsilon}W\mathbbm{1}\\{W\in(M,A)\;\Big{|}\;W\in(M,A)\right]\
,$ (195)

where the inequality in (193) follows from Lemma C.2 and the inequality in
(195) follows from (187). Next, we bound the second term in (195) as follows.

$\displaystyle{\sf
E}\left[\mathcal{I}_{\epsilon}W\mathbbm{1}\\{W\in(M,A)\;\Big{|}\;W\in(M,A)\right]$
(196) $\displaystyle=\mathcal{I}_{\epsilon}\int_{0}^{\infty}{\sf
P}\left(W\mathbbm{1}\\{W\in(M,A)>x\;\Big{|}\;W\in(M,A)\right)dx$ (197)
$\displaystyle=\mathcal{I}_{\epsilon}\int_{0}^{A}\frac{{\sf P}\left(\\{x\vee
M\\}<W<A\right)}{{\sf P}\left(M<W<A\right)}dx$ (198)
$\displaystyle=\mathcal{I}_{\epsilon}\left\\{\int_{0}^{M}\frac{{\sf
P}\left(M<W<A\right)}{{\sf P}\left(M<W<A\right)}dx\;+\;\int_{M}^{A}\frac{{\sf
P}\left(x<W<A\right)}{{\sf P}\left(M<W<A\right)}dx\right\\}$ (199)
$\displaystyle\leq\mathcal{I}_{\epsilon}\left\\{\int_{0}^{M}dx\;+\;\int_{M}^{A}\frac{{\sf
P}\left(x<W\right)}{{\sf P}\left(M<W\right)-{\sf
P}\left(A<W\right)}dx\right\\}$ (200)
$\displaystyle\leq\mathcal{I}_{\epsilon}\left\\{M\;+\;\int_{M}^{A}\frac{e^{-x}}{{\sf
P}\left(M<W\right)-e^{-A}}dx\right\\}$ (201)
$\displaystyle=\mathcal{I}_{\epsilon}\left\\{M\;+\;\frac{e^{-M}-e^{-A}}{{\sf
P}\left(M<W\right)-e^{-A}}dx\right\\}$ (202)
$\displaystyle\leq\mathcal{I}_{\epsilon}\left\\{M\;+\;\frac{e^{-M}}{{\sf
P}\left(M<W\right)-e^{-\kappa M}}\right\\}\ ,$ (203)

where the inequality in (201) follows from (187) and the inequality in (203)
follows from the fact that $A\geq\kappa M$. The proof is complete. ∎

The following lemma is a generalization of Wald’s identity that we use
repeatedly later.

###### Lemma C.4

Let $\\{Y_{n}:n\in\mathbb{N}\\}$ be a sequence of Bernoulli random variables,
and set

$\displaystyle N:=\inf\\{n\geq 1:Y_{n}=1\\}\ .$ (204)

Furthermore, let $W$ be a random variable so that $Z_{1},Y_{1},W$ are
independent of $\\{(Z_{n},Y_{n}):n\geq 2\\}$, and set

$\displaystyle\mu_{x}\equiv{\sf E}\left[Z_{1}\,|\,W=x\right]\in\mathbb{R}\
\qquad\text{and}\ \qquad p_{x}\equiv{\sf P}(Y_{1}=1\,|\,W=x)\ .$ (205)

  * (i)

If $\\{(Z_{n},Y_{n}):n\geq 2\\}$ are i.i.d. with

$\displaystyle{\sf E}\left[Z_{n}\right]=\mu\in\mathbb{R}\
\qquad\text{and}\qquad\ {\sf P}(Y_{n}=1)=p>0\ ,$ (206)

then

$\displaystyle{\sf
E}\left[\sum_{t=1}^{N}Z_{t}\;\Bigg{|}\;W=x\right]=\mu_{x}+(1-p_{x})\left(\frac{\mu}{p}\right)\
.$ (207)

  * (ii)

If there exists an $L\in\mathbb{N}$ such that, for every
$i\in\\{2,\dots,L+1\\}$, $\\{(Z_{jL+i},Y_{jL+i}):j\geq 0\\}$ are i.i.d. with

$\displaystyle{\sf E}\left[Z_{i}\right]=\mu_{i}\in\mathbb{R}\
\qquad\text{and}\qquad{\sf P}(Y_{i}=1)=p_{i}>0\ ,$ (208)

then

$\displaystyle{\sf
E}\left[\sum_{t=1}^{N}Z_{t}\;\Bigg{|}\;W=x\right]=p_{x}\times\frac{\mu_{x}}{p_{x}}+{(1-p_{x})}\times\sum_{i=2}^{L+1}\;w_{i}\,\frac{\mu_{i}}{p_{i}}\
,$ (209)

where

$\displaystyle
w_{i}\equiv\frac{p_{i}\,\prod_{j=2}^{i-1}\,(1-p_{j})}{1-\prod_{j=2}^{L+1}\,(1-p_{j})}\
,1<i\leq L+1\ ,$ (210)

and $\prod_{j}^{i}=1$ whenever $j>i$.

###### Proof:

We first observe that if ${\sf E}[N|W=x]<\infty$, then by Wald’s identity we
have

$\displaystyle{\sf E}\left[\sum_{t=1}^{N}Z_{t}\;\Bigg{|}\;W=x\right]$
$\displaystyle={\sf E}\left[\sum_{t=1}^{N}{\sf
E}[Z_{t}\,|\,W=x]\;\Bigg{|}\;W=x\right].$ (211)

(i) By (211) we have

$\displaystyle{\sf E}\left[\sum_{t=1}^{N}Z_{t}\;\Bigg{|}\;W=x\right]$
$\displaystyle=\mu_{x}+\mu\;\left({\sf E}[N|W=x]-1\right)\ .$ (212)

To this point, it suffices to show that

$\displaystyle{\sf E}\left[N\;|\;W=x\right]=1+\frac{1-p_{x}}{p}\ .$ (213)

Indeed, the conditional distribution of $N$ can be easily found as follows.

$\displaystyle{\sf
P}\left(N=k\,|\,W=x\right)=\begin{cases}p_{x}\quad&\text{if}\quad k=1\\\
(1-p_{x})(1-p)^{k-2}p\quad&\text{if}\quad k\geq 2\end{cases}\ ,$ (214)

which further yields that

$\displaystyle{\sf E}\left[N\,|\,W=x\right]$
$\displaystyle=p_{x}+\sum_{k=2}^{\infty}k(1-p_{x})(1-p)^{k-2}p$ (215)
$\displaystyle=p_{x}+(1-p_{x})\sum_{k=1}^{\infty}(1+k)(1-p)^{k-1}p$ (216)
$\displaystyle=p_{x}+(1-p_{x})\left(\sum_{k=1}^{\infty}(1-p)^{k-1}p+\sum_{k=1}^{\infty}k(1-p)^{k-1}p\right)$
(217) $\displaystyle=p_{x}+(1-p_{x})\left(1+\frac{1}{p}\right)$ (218)
$\displaystyle=1+\frac{1-p_{x}}{p}\ .$ (219)

(ii) By (211) we have

$\displaystyle{\sf E}\left[\sum_{t=1}^{N}Z_{t}\;\Bigg{|}\;W=x\right]$
$\displaystyle={\sf E}\left[Z_{1}|W=x\right]+\sum_{t=2}^{\infty}{\sf
E}\left[Z_{t}\mathbbm{1}\;\\{N\geq t\\}\;\Bigg{|}\;W=x\right]$ (220)
$\displaystyle=\mu_{x}+\sum_{t=2}^{\infty}{\sf E}\left[Z_{t}\right]\;{\sf
P}\left(N\geq t\;\Big{|}\;W=x\right)$ (221)
$\displaystyle=\mu_{x}+\sum_{j=0}^{\infty}\sum_{t=jL+2}^{(j+1)L+1}{\sf
E}\left[Z_{t}\right]{\sf P}\left(N\geq t\;\Big{|}\;W=x\right)\ ,$ (222)

where the equality in (221) follows from the fact that, since $N$ is a
stopping time with respect to the filtrations generated by
$\\{W,Y_{n}:n\in\mathbb{N}\\}$, for every $t\geq 2$, we have

$\displaystyle\\{N\geq t\\}\in\sigma\left(W,Y_{k}:k\in[t-1]\right)\ .$ (223)

Thus, the event $\\{N\geq t\\}$ is independent of $(Z_{t},Y_{t})$, which is
also independent of $W$. To this end, also following (222), it is necessary to
derive the expressions for the conditional tail probabilities

$\displaystyle{\sf P}\left(N\geq t\;\Big{|}\;W=x\right)\ ,\qquad t\geq 2\ ,$
(224)

and we do it as follows. For every $t\geq 2$ in the form $t=j_{t}L+i_{t}$, for
some $j_{t}\geq 0$ and $i_{t}\in\\{2,\dots,L+1\\}$, we have

$\displaystyle{\sf P}\left(N\geq t\;\Big{|}\;W=x\right)$ $\displaystyle={\sf
P}\left(Y_{k}=0\;\;\text{for every}\;\;k=1,\dots,t-1\;|W=x\right)$ (225)
$\displaystyle={\sf P}(Y_{1}=0\,|\,W=x)\prod_{k=2}^{t-1}{\sf P}(Y_{k}=0)$
(226) $\displaystyle={\sf
P}(Y_{1}=0\,|\,W=x)\prod_{j=0}^{j_{t}-1}\prod_{i=2}^{L+1}{\sf
P}(Y_{jL+i}=0)\times\prod_{i=2}^{i_{t}-1}{\sf P}(Y_{j_{t}L+i}=0)$ (227)
$\displaystyle=(1-p_{x})\prod_{j=0}^{j_{t}-1}\prod_{i=2}^{L+1}(1-p_{i})\times\prod_{i=2}^{i_{t}-1}(1-p_{i})$
(228)
$\displaystyle=(1-p_{x})\left(\prod_{i=2}^{L+1}(1-p_{i})\right)^{j_{t}}\prod_{i=2}^{i_{t}-1}(1-p_{i})\
,$ (229)

where the equality in (225) follows from the definition of $N$, and the
equality in (226) holds since $\\{Y_{n}:n\geq 2\\}$ is independent of $W$.
Thus, following (222),

$\displaystyle\sum_{j=0}^{\infty}\sum_{t=jL+2}^{(j+1)L+1}{\sf
E}\left[Z_{t}\right]{\sf P}\left(N\geq t\;\Big{|}\;W=x\right)$ (230)
$\displaystyle=\sum_{j=0}^{\infty}\sum_{i=2}^{L+1}{\sf
E}\left[Z_{jL+i}\right]\;{\sf P}\left(N\geq jL+i\;\Big{|}\;W=x\right)$ (231)
$\displaystyle=\sum_{j=0}^{\infty}\sum_{i=2}^{L+1}\mu_{i}(1-p_{x})\left(\prod_{k=2}^{L+1}(1-p_{k})\right)^{j}\prod_{k=2}^{i-1}(1-p_{k})$
(232)
$\displaystyle=(1-p_{x})\sum_{j=0}^{\infty}\left(\prod_{k=2}^{L+1}(1-p_{k})\right)^{j}\sum_{i=2}^{L+1}\mu_{i}\prod_{k=2}^{i-1}(1-p_{k})$
(233)
$\displaystyle=(1-p_{x})\left\\{\sum_{i=2}^{L+1}\mu_{i}\prod_{k=2}^{i-1}(1-p_{k})\right\\}\sum_{j=0}^{\infty}\left(\prod_{k=2}^{L+1}(1-p_{k})\right)^{j}$
(234)
$\displaystyle=(1-p_{x})\sum_{i=2}^{L+1}\mu_{i}\prod_{k=2}^{i-1}(1-p_{k})\frac{1}{1-\prod_{k=2}^{L+1}(1-p_{k})}$
(235)
$\displaystyle=(1-p_{x})\,\sum_{i=2}^{L+1}\;w_{i}\,\frac{\mu_{i}}{p_{i}}\ ,$
(236)

where $w_{i},2\leq i\leq L+1$ is defined in (210). ∎

##  Appendix D Proof of False Alarm Control

In this section, we prove Theorem IV.1. For this, we need to introduce some
additional notations, which are also used later in the proof of Theorem IV.2.
Specifically, for every $E\in{\cal U}$, we recall from (41) the definition of
the first descending ladder variable of the random walk with increments
$\\{\xi_{t}^{E}:t\in\mathbb{N}\\}$,

$\displaystyle\zeta^{E}_{-}:=\inf\left\\{n\geq
1:\sum_{t=1}^{n}\xi_{t}^{E}<0\right\\}\ ,$ (237)

for every $A>0$ we denote by $\zeta^{E}_{A}$ the first time this random walk
crosses $A$ for the first time, i.e.,

$\displaystyle\zeta^{E}_{A}:=\inf\left\\{n\geq
1:\sum_{t=1}^{n}\xi_{t}^{E}>A\right\\}\ ,$ (238)

and we set

$\displaystyle\zeta^{E}:=\min\\{\zeta^{E}_{-},\zeta^{E}_{A}\\}\
\qquad\text{and}\qquad\ z^{E}:=\mathbbm{1}\\{\zeta^{E}_{A}<\zeta^{E}_{-}\\}\
.$ (239)

###  D-A Proof of Theorem IV.1

###### Proof:

For every $n\in\mathbb{N}$ we set

$\displaystyle\tau_{n}$
$\displaystyle:=\inf\\{t>\tau_{n-1}:\tilde{S}_{t+1}\neq\tilde{S}_{\tau_{n-1}+1}\\}\
,\quad\text{where}\quad\tau_{0}\equiv 0\ ,$ (240) $\displaystyle z_{n}$
$\displaystyle:=\mathbbm{1}\\{Y_{\tau_{n}}\geq A\\}\ .$ (241)

That is, $\tau_{n}$ is the time instant at which the sampling unit changes for
the $n^{th}$ time, and $z_{n}$ is equal to 1 if the alarm is raised at time
$\tau_{n}$ and 0 otherwise. Then, we have the following representation:

$\displaystyle\tilde{T}=\sum_{n=1}^{M}\zeta_{n}\ ,$ (242)

where $M$ denotes the stage at which the process is terminated, i.e.,

$\displaystyle M:=\inf\\{n\in\mathbb{N}:z_{n}=1\\}\ ,$ (243)

and, for every $n\in\mathbb{N}$, $\zeta_{n}:=\tau_{n}-\tau_{n-1}$. Due to
independence over time, $\\{(\zeta_{n},z_{n}):n\in\mathbb{N}\\}$ is a sequence
of independent random vectors under $\mathbb{P}_{\infty}$. Furthermore, since
for the sampling policy $\tilde{S}$ we consider a pre-specified permutation
$E_{1},E_{2},\dots,E_{|{\cal U}|}$ of the elements in ${\cal U}$ that remains
unchanged over time, then, clearly, for every $i\in[|{\cal U}|]$, the sequence

$\displaystyle\\{(\zeta_{j|{\cal U}|+i},z_{j|{\cal U}|+i}):j\geq 0\\}$ (244)

is i.i.d. under $\mathbb{P}_{\infty}$ with common expectation
$(\mathbb{E}_{\infty}[\zeta^{E_{i}}],\ \mathbb{P}_{\infty}(z^{E_{i}}=1))$.
Thus,

$\displaystyle\mathbb{E}_{\infty}[\tilde{T}]$
$\displaystyle=\mathbb{E}_{\infty}\left[\sum_{n=1}^{M}\zeta_{n}\right]$ (245)
$\displaystyle=\sum_{i=1}^{|{\cal
U}|}\mathbb{E}_{\infty}[\zeta^{E_{i}}]\;\frac{\prod_{j=1}^{i-1}(1-\mathbb{P}_{\infty}(z^{E_{j}}=1))}{1-\prod_{j=1}^{|{\cal
U}|}(1-\mathbb{P}_{\infty}(z^{E_{j}}=1))}$ (246)
$\displaystyle\geq\sum_{i=1}^{|{\cal
U}|}\frac{(1-e^{-A})^{i-1}}{1-(1-e^{-A})^{|{\cal
U}|}}=e^{A}\,\frac{1-(1-e^{-A})^{|{\cal U}|}}{1-(1-e^{-A})^{|{\cal U}|}}$
(247) $\displaystyle=e^{A}\ ,$ (248)

which proves that setting $A=\log\gamma$ guarantees the desired error control.
The equality in (246) holds by an application of Lemma C.4(ii), whereas the
inequality in (247) holds since $\zeta^{E_{i}}\geq 1$ for every $i\in[|{\cal
U}|]$, and also because by Wald’s likelihood ratio identity we have, for every
$E\in{\cal U}$,

$\displaystyle\mathbb{P}_{\infty}(z^{E}=1)$
$\displaystyle=\mathbb{P}_{\infty}(\zeta^{E}_{A}<\zeta^{E}_{-})$ (249)
$\displaystyle=\mathbb{P}_{\infty}(\xi_{\zeta^{E}}^{E}>A)\leq e^{-A}\ .$ (250)

∎

##  Appendix E Proof of Asymptotic Upper Bound on Detection Delay

In this appendix, we prove Theorem IV.2. For this, we need to show that, for
any $\nu\geq 0$, as $A\to\infty$ we have

$\displaystyle\text{esssup}\ \mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\mathcal{F}^{\tilde{S}}_{\nu}({\sf
G}),\tilde{T}>\nu\right]\leq\max_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\;\frac{A}{\mathcal{J}^{E}_{0}({\sf G})}+o(A)\ .$ (251)

Thus, throughout this appendix, we fix an arbitrary $\nu\geq 0$. This proof is
quite lengthy, and requires introducing some additional notation.

###  E-A Stages

First, we introduce the sequence of random times, starting from $\nu$, at
which the sampled unit changes, i.e.,

$\displaystyle\tau_{n}$
$\displaystyle:=\inf\\{t>\tau_{n-1}:\tilde{S}_{t+1}\neq\tilde{S}_{\tau_{n-1}+1}\\}\
,\quad n\in\mathbb{N}\ ,$ (252) $\displaystyle\tau_{0}$ $\displaystyle:=\nu\
.$ (253)

For every $n\in\mathbb{N}$,

  * •

we refer to the time interval $[\tau_{n-1}-\tau_{n}]$ as the $n^{\rm th}$
“stage” of the sampling procedure,

  * •

we denote by $\zeta_{n}$ the duration of the $n^{th}$ stage, i.e.,

$\displaystyle\zeta_{n}:=\tau_{n}-\tau_{n-1}\ ,$ (254)

  * •

we denote by $z_{n}$ the indicator that is equal to 1 if and only if the
process is terminated at the end of the $n^{\rm th}$ stage, i.e.,

$\displaystyle z_{n}:=\mathbbm{1}\\{Y_{\tau_{n}}\geq A\\}\ ,$ (255)

  * •

we denote by $w_{n}$ the quantity that is equal to 1 if the unit that is
sampled at the $n^{th}$ stage is actually affected by the change and $0$
otherwise, i.e.,

$\displaystyle w_{n}:=\mathbbm{1}\\{S_{\tau_{n}}\in\mathcal{A}({\sf G})\\}\ .$
(256)

We stress that since the permutation of the units is pre-specified, the
sequence $\\{w_{n}:n\in\mathbb{N}\\}$ is deterministic. Furthermore, we denote
by

  * •

$\\{(\zeta^{\prime}_{n},z^{\prime}_{n}):n\in\mathbb{N}\\}$ the subsequence of
$\\{(\zeta_{n},z_{n}):n\in\mathbb{N}\\}$ that corresponds to $w_{n}=1$,

  * •

$\\{(\zeta^{\prime\prime}_{n},z^{\prime\prime}_{n}):n\in\mathbb{N}\\}$ the
subsequence of $\\{(\zeta_{n},z_{n}):n\in\mathbb{N}\\}$ that corresponds to
$w_{n}=0$,

  * •

$M_{\sf G}$ the total number of stages until the process is terminated by a
stage at which the sampled unit is actually affected by the change, i.e.,

$\displaystyle M_{\sf G}:=\inf\\{n\in\mathbb{N}:z_{n}=1,\quad w_{n}=1\\}\ ,$
(257)

  * •

$M^{\prime}_{\sf G}$ the number of stages until the above-mentioned
termination at which the sampled units are affected by the change, i.e.,

$\displaystyle M_{\sf G}^{\prime}:=\sum_{n=1}^{M_{\sf
G}}\mathbbm{1}\\{w_{n}=1\\}=\inf\\{n\in\mathbb{N}:z^{\prime}_{n}=1\\}\ .$
(258)

We have the following representation that, given $Y_{\nu}$,

$\displaystyle\zeta_{1}$ $\displaystyle=\inf\left\\{n\geq
1:Y_{\nu}+\sum_{t=1}^{n}\xi_{\nu+t}^{\tilde{S}_{\nu}}\notin(0,A)\right\\}\ ,$
(259) $\displaystyle\zeta_{n}$ $\displaystyle=\inf\left\\{n\geq
1:\sum_{t=1}^{n}\xi_{\tau_{n-1}+t}^{\tilde{S}_{\tau_{n-1}}}\notin(0,A)\right\\}\
,\qquad\forall\;\;n\geq 2\ .$ (260)

Thus, due to the independence of the observations over time, under
$\mathbb{P}_{\nu}^{\sf G}$, $\\{(\zeta_{n},z_{n}):n\geq 2\\}$ are independent
as well as independent of $Y_{\nu}$ and $(\zeta_{1},z_{1})$.

###  E-B Cycles

For every $k\in\mathbb{N}$,

  * •

we refer to the stages from $\\{(k-1)\,|{\cal U}|+2\\}$ to $\\{k\,|{\cal
U}|+1\\}$ as the $k^{\rm th}$ “cycle” of the sampling process. To be precise,
the $1^{\rm st}$ cycle starts just after the end of $1^{\rm st}$ stage, and
afterwards, every time the process completes $|{\cal U}|$ stages, we define
its duration as a cycle.

  * •

we denote by $\sigma_{k}$ the total duration of only those stages in the
$k^{\rm th}$ cycle at which the units that are not affected by the change are
sampled, i.e.,

$\displaystyle\sigma_{k}=\sum_{n=2}^{|{\cal U}|+1}\zeta_{(k-1)|{\cal
U}|+n}\,\mathbbm{1}\\{w_{(k-1)|{\cal U}|+n}=0\\}\ ,\quad k\in\mathbb{N}\ .$
(261)

  * •

we denote by $N_{\sf G}$ the number of cycles the sampling process has
undergone before its termination, i.e.,

$\displaystyle N_{\sf G}:=\inf\left\\{k\in\mathbb{N}:((k-1)|{\cal U}|+2)\leq
M_{\sf G}\leq(k|{\cal U}|+1)\right\\}\ .$ (262)

###  E-C An upper bound on the worst-case detection delay

We next upper bound the worst-case detection delay of $\tilde{T}$ using the
previous quantities.

###### Lemma E.1

On the event $\\{\tilde{T}>\nu\\}$ we have

$\displaystyle\tilde{T}-\nu\leq\zeta_{1}\cdot\mathbbm{1}\\{\tilde{S}_{\nu}\notin\mathcal{A}({\sf
G})\\}+\sum_{n=1}^{M^{\prime}_{\sf G}}\zeta^{\prime}_{n}+\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\ ,$ (263)

and, consequently,

$\displaystyle\text{esssup}\ \mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\mathcal{F}^{\tilde{S}}_{\nu}({\sf
G}),\tilde{T}>\nu\right]$ (264)
$\displaystyle\leq\max\Bigg{\\{}\max_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\;\mathbb{E}^{{\sf G}}_{\nu}\left[\sum_{n=1}^{M^{\prime}_{\sf
G}}\zeta^{\prime}_{n}+\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\,\;\Big{|}\;\,\tilde{S}_{\nu}=E,\,Y_{\nu},\,Y_{\nu}\in(0,A)\right]\
,$ (265) $\displaystyle\qquad\qquad\,\max_{E\in{\cal
U}\setminus\mathcal{A}({\sf G})}\;\mathbb{E}^{{\sf
G}}_{\nu}\left[\zeta_{1}+\sum_{n=1}^{M^{\prime}_{\sf
G}}\zeta^{\prime}_{n}+\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\,\;\Big{|}\;\,\tilde{S}_{\nu}=E,\,Y_{\nu}\in(0,A)\right]\Bigg{\\}}\
.$ (266)

###### Proof:

By the above definitions it is clear that

$\displaystyle\tilde{T}-\nu\leq\sum_{n=1}^{M_{\sf G}}\zeta_{n}\ ,$ (267)

and

$\displaystyle\sum_{n=1}^{M_{\sf
G}}\zeta_{n}\mathbbm{1}\\{w_{n}=1\\}=\sum_{n=1}^{M^{\prime}_{\sf
G}}\zeta^{\prime}_{n}\ .$ (268)

Furthermore, we have

$\displaystyle\sum_{n=1}^{M_{\sf
G}}\zeta_{n}\mathbbm{1}\\{w_{n}=0\\}=\zeta_{1}\mathbbm{1}\\{w_{1}=0\\}+\sum_{n=2}^{M_{\sf
G}}\zeta_{n}\mathbbm{1}\\{w_{n}=0\\}\leq\zeta_{1}\mathbbm{1}\\{\tilde{S}_{\nu}\notin\mathcal{A}({\sf
G})\\}+\sum_{m=1}^{N_{\sf G}}\sigma_{m}\ ,$ (269)

where the inequality holds since by definition, cycles are counted from the
$2^{\rm nd}$ stage, and when $\tilde{S}_{\nu}\notin\mathcal{A}({\sf G})$,
i.e., at the first stage, sampling is done from a unit which is not affected
by the change, we have $w_{1}=0$. This completes the first part.

Now, we have

$\displaystyle\mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\mathcal{F}^{\tilde{S}}_{\nu}({\sf
G}),\tilde{T}>\nu\right]$ $\displaystyle=\mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\tilde{S}_{\nu}\in\mathcal{A}({\sf
G}),\,\mathcal{F}^{\tilde{S}}_{\nu}({\sf G}),\,\tilde{T}>\nu\right]$ (270)
$\displaystyle=\mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\tilde{S}_{\nu}\in\mathcal{A}({\sf
G}),\,\mathcal{F}^{\tilde{S}}_{\nu}({\sf
G}),\,\tilde{T}>\nu\right]\mathbbm{1}\\{\tilde{S}_{\nu}\in\mathcal{A}({\sf
G})\\}$ (271) $\displaystyle\quad+\mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\tilde{S}_{\nu}\notin\mathcal{A}({\sf
G}),\,\mathcal{F}^{\tilde{S}}_{\nu}({\sf
G}),\,\tilde{T}>\nu\right]\mathbbm{1}\\{\tilde{S}_{\nu}\notin\mathcal{A}({\sf
G})\\}$ (272) $\displaystyle=\mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\tilde{S}_{\nu}\in\mathcal{A}({\sf
G}),\,Y_{\nu},\,Y_{\nu}\in(0,A)\right]\mathbbm{1}\\{\tilde{S}_{\nu}\in\mathcal{A}({\sf
G})\\}$ (273) $\displaystyle\quad+\mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\tilde{S}_{\nu}\notin\mathcal{A}({\sf
G}),\,Y_{\nu}\in(0,A)\right]\mathbbm{1}\\{\tilde{S}_{\nu}\notin\mathcal{A}({\sf
G})\\}\ ,$ (274)

where the equality in (270) follows from the fact that
$\\{\tilde{S}_{\nu}\in\mathcal{A}({\sf
G})\\}\in\mathcal{F}_{\nu}^{\tilde{S}}({\sf G})$. The equality in (273) holds
because given $\tilde{S}_{\nu}\in\mathcal{A}({\sf G})$ and $\tilde{T}>\nu$,
the detection delay $\tilde{T}-\nu$ depends on the history
$\mathcal{F}_{\nu}^{\tilde{S}}({\sf G})$ only through $Y_{\nu}$, i.e., the
value of the statistic at time $\nu$. However, given
$\tilde{S}_{\nu}\notin\mathcal{A}({\sf G})$, $Y_{\nu}$ is not observed from
the history $\mathcal{F}_{\nu}^{\tilde{S}}({\sf G})$, hence, the detection
delay is independent of $\mathcal{F}_{\nu}^{\tilde{S}}({\sf G})$. The result
now follows from the first part and the following identities:

$\displaystyle\\{\tilde{S}_{\nu}\in\mathcal{A}({\sf
G})\\}=\bigcup_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\;\\{\tilde{S}_{\nu}=E\\}\ \qquad\text{and}\
\qquad\\{\tilde{S}_{\nu}\notin\mathcal{A}({\sf G})\\}=\bigcup_{E\in{\cal
U}\setminus\mathcal{A}({\sf G})}\;\\{\tilde{S}_{\nu}=E\\}\ .$ (275)

∎

In view of Lemma E.1, we need to upper bound the conditional expectation of
each of the quantities in the right-hand side of (263). This is done in Lemmas
E.3, E.4, E.5 and E.6. For some of these lemmas, we need to introduce some
additional notations and state some supporting lemmas.

###  E-D Random walk quantities

Recall the stopping times introduced in (237) and (238). Now, for every
$E\in{\cal U}$,

  * •

we denote by $q^{E}_{+}$ the probability that, while sampling from $E$,
$\xi_{n}^{E}$ never exceeds $0$ under ${\sf F}$, i.e.,

$\displaystyle q^{E}_{+}:={\sf F}(\zeta^{E}_{+}=\infty)\ ,$ (276)

  * •

when $E\in\mathcal{A}({\sf G})$, we denote by $q^{E}_{-}({\sf G})$ the
probability that, while sampling from $E$, the random walk never falls below 0
under ${\sf G}$, i.e.,

$\displaystyle q^{E}_{-}({\sf G}):={\sf G}(\zeta^{E}_{-}=\infty)\ .$ (277)

[We note that under assumptions (24)-(23), both these probabilities are
strictly positive (see, e.g.,[27, Corollary 8.39], and also Lemma C.1 in
Appendix C).]

  * •

when $E\in\mathcal{A}({\sf G})$, we denote by $\mu^{E}_{A}({\sf G})$ the
expectation of $\zeta^{E}$, and by $q^{E}_{A}({\sf G})$ the probability that,
while sampling from $E$, the corresponding LLR process crosses $A$ for the
first time before falling below $0$ under ${\sf G}$, i.e.,

$\displaystyle\mu^{E}_{A}({\sf G}):={\sf E}_{{\sf G}}[\zeta^{E}]\qquad\
\text{and}\ \qquad q^{E}_{A}({\sf G}):={\sf E}_{{\sf G}}[z^{E}]={\sf
G}(\zeta^{E}_{A}<\zeta^{E}_{-})\ .$ (278)

###  E-E Cycle quantities

Recall that we have fixed an arbitrary permutation, $(E_{1},\dots,E_{|{\cal
U}|})$, of the elements of ${\cal U}$ to start the sampling process
$\tilde{S}$. Next, for any ${\sf G}\in\mathcal{G}$, order the indices in this
particular permutation, which correspond to the elements of $\mathcal{A}({\sf
G})$, and denote them as follows.

$\displaystyle 1\leq i_{1}({\sf G})<i_{2}({\sf G})<\dots<i_{|\mathcal{A}({\sf
G})\cap{\cal U}|}({\sf G})\leq|{\cal U}|\ .$ (279)

It is important to note that the above ordering depends on what permutation we
determine at the beginning of sampling. Subsequently, we can also represent
$\mathcal{A}({\sf G})$ as

$\displaystyle\mathcal{A}({\sf G})\cap{\cal U}=\\{E_{i_{j}({\sf
G})}:j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]\\}\ .$ (280)

Next, for any $j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]$,

  * •

when $E$ is the $j^{\rm th}$ element of $\mathcal{A}({\sf G})\cap{\cal U}$ in
the the above ordering, i.e., $E=E_{i_{j}({\sf G})}\in\mathcal{A}({\sf
G})\cap{\cal U}$, we set

$\displaystyle\tilde{\zeta}^{j}:=\zeta^{E}\ $ $\displaystyle,\quad\quad\
\tilde{z}^{j}:=z^{E}\ ,$ (281) $\displaystyle\tilde{q}^{j}_{-}({\sf
G}):=q^{E}_{-}({\sf G})\ $ $\displaystyle,\quad\quad\ \tilde{q}^{j}_{A}({\sf
G}):=q^{E}_{A}({\sf G})\ ,\quad\quad\ \tilde{\mu}_{A}^{j}({\sf
G}):=\mu^{E}_{A}({\sf G})\ ,$ (282)
$\displaystyle\tilde{\mathcal{J}}^{j}_{0}({\sf G}):=\mathcal{J}^{E}_{0}({\sf
G})\ $ $\displaystyle,\quad\quad\tilde{\mathcal{W}}^{j}_{0}({\sf
G}):=\mathcal{W}^{E}_{0}({\sf G})\ ,$ (283)

  * •

for any $l\in\mathbb{N}$, we denote by $\kappa(j,l)$ the $l^{\rm th}$ element
of the following periodic sequence, which starts from $j$ and has period
$|\mathcal{A}({\sf G})\cap{\cal U}|$,

$\displaystyle\left\\{j,j+1,\dots,|\mathcal{A}({\sf G})\cap{\cal
U}|,1,2,\dots,j-1,j,j+1,\dots,|\mathcal{A}({\sf G})\cap{\cal
U}|,1,2,\dots\right\\}\ ,$ (284)

i.e., more formally,

$\displaystyle\kappa(j,l):=(j+l-1)\;\;{\rm mod}\;|\mathcal{A}({\sf
G})\cap{\cal U}|\;\in\;[|\mathcal{A}({\sf G})\cap{\cal U}|]\ ,$ (285)

  * •

we define the $j$-cycle to be the total duration in which sampling is
performed only from the elements of $\mathcal{A}({\sf G})\cap{\cal U}$
starting with the element corresponding to the $j^{\rm th}$ index in (279),
i.e., $E_{i_{j}({\sf G})}$, until the process stops or returns to start
sampling again from $E_{i_{j}({\sf G})}$,

  * •

we introduce the quantity $\tilde{\mathcal{J}}^{j}_{*}({\sf G})$, which is a
weighted harmonic mean of the information numbers corresponding to the
elements of $\mathcal{A}({\sf G})\cap{\cal U}$, i.e.

$\displaystyle\frac{1}{\tilde{\mathcal{J}}^{j}_{*}({\sf
G})}:=\sum_{l=1}^{|\mathcal{A}({\sf G})\cap{\cal
U}|}w^{j}_{l}\,\frac{1}{\tilde{\mathcal{J}}^{\kappa(j,l)}_{0}({\sf G})}\ ,$
(286)

where the weight corresponding to any element is the conditional probability
that during the $j$-cycle we stop while sampling from that particular element
given that we stop in the $j$-cycle, i.e.,

$\displaystyle w^{j}_{l}=\frac{{\tilde{q}_{A}^{\kappa(j,l)}({\sf
G})\;\prod_{s=1}^{l-1}(1-\tilde{q}_{A}^{\kappa(j,s)}({\sf
G}))}}{1-\prod_{s=1}^{|\mathcal{A}({\sf G})\cap{\cal
U}|}(1-\tilde{q}_{A}^{\kappa(j,s)}({\sf G}))}\ ,\ \qquad\text{for every}\quad
l\in[|\mathcal{A}({\sf G})\cap{\cal U}|]\ .$ (287)

Since the inverse of the information number of any unit in $\mathcal{A}({\sf
G})\cap{\cal U}$ represents the delay or difficulty of detection when sampling
only from that element after the change, $\tilde{\mathcal{J}}^{j}_{*}({\sf
G})$ represents the overall difficulty of detection averaged over all elements
in $\mathcal{A}({\sf G})\cap{\cal U}$ when $E_{i_{j}({\sf G})}$ is the first
element in $\mathcal{A}({\sf G})\cap{\cal U}$ that we sample from immediately
after the change. Hence, $\tilde{\mathcal{J}}^{j}_{*}({\sf G})$ can be
interpreted as the information number corresponding to the $j$-cycle.

###  E-F Some useful lemmas

Next, in the following lemmas, we establish upper bounds of the conditional
expectation of each of the quantities in the right-hand side of (263), and
combine them in the end to obtain the desired result.

###### Lemma E.2

Fix ${\sf G}\in\mathcal{G}$ and recall the definition of $\kappa(j,l)$ in
(285) for any $j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]$ and $l\in\mathbb{N}$.
Then

$\displaystyle\kappa(j,l+1)=\kappa(\kappa(j,2),l)\ .$ (288)

###### Proof:

We have

$\displaystyle\begin{split}\kappa(\kappa(j,2),l)&=\kappa((j+1)\;{\rm
mod}\;|\mathcal{A}({\sf G})\cap{\cal U}|,\ l)\\\ &=((j+1)\;{\rm
mod}\;|\mathcal{A}({\sf G})\cap{\cal U}|+l-1)\;{\rm mod}\;|\mathcal{A}({\sf
G})\cap{\cal U}|\\\ &=((j+1)\;{\rm mod}\;|\mathcal{A}({\sf G})\cap{\cal
U}|)\;{\rm mod}\;|\mathcal{A}({\sf G})\cap{\cal U}|+(l-1)\;{\rm
mod}\;|\mathcal{A}({\sf G})\cap{\cal U}|\\\ &=(j+1)\;{\rm
mod}\;|\mathcal{A}({\sf G})\cap{\cal U}|+(l-1)\;{\rm mod}\;|\mathcal{A}({\sf
G})\cap{\cal U}|\\\ &=(j+l)\;{\rm mod}\;|\mathcal{A}({\sf G})\cap{\cal U}|\\\
&=(j+(l+1)-1)\;{\rm mod}\;|\mathcal{A}({\sf G})\cap{\cal U}|=\kappa(j,l+1)\
,\end{split}$ (289)

which completes the proof. ∎

###### Lemma E.3

For any $j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]$,

$\displaystyle\mathbb{E}^{{\sf G}}_{\nu}\left[\sum_{n=1}^{M^{\prime}_{\sf
G}}\zeta^{\prime}_{n}\,\;\Big{|}\;\,\tilde{S}_{\nu}=E_{i_{j}({\sf
G})},Y_{\nu},Y_{\nu}\in(0,A)\right]$
$\displaystyle\leq\left(\frac{A}{\tilde{\mathcal{J}}_{0}^{j}({\sf
G})}\bigvee\frac{A}{\tilde{\mathcal{J}}_{*}^{\kappa(j,2)}({\sf
G})}\right)+o(A)\ .$ (290)

###### Proof:

First, fix any arbitrary $j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]$ and
consider conditioning on

$\displaystyle\\{\tilde{S}_{\nu}=E_{i_{j}({\sf G})},Y_{\nu},\tilde{T}>\nu\\}\
.$ (291)

Now, since $\tilde{S}_{\nu}=E_{i_{j}({\sf G})}$, clearly, at the first stage
sampling is done from a unit that belongs to $\mathcal{A}({\sf G})$, i.e.,
$w_{1}=1$ or $\zeta^{\prime}_{1}=\zeta_{1}$. Thus, we define the following
conditional expectations

$\displaystyle\mu^{j}_{Y_{\nu}}$ $\displaystyle:=\mathbb{E}_{\nu}^{\sf
G}[\zeta^{\prime}_{1}\,|\,\tilde{S}_{\nu}=E_{i_{j}({\sf
G})},Y_{\nu},Y_{\nu}\in(0,A)]\ ,$ (292) $\displaystyle p^{j}_{Y_{\nu}}$
$\displaystyle:=\mathbb{P}_{\nu}^{{\sf
G}}(z_{1}^{\prime}=1|\tilde{S}_{\nu}=E_{i_{j}({\sf
G})},Y_{\nu},Y_{\nu}\in(0,A))\ .$ (293)

Furthermore, under $\mathbb{P}_{\nu}^{\sf G}$,
$\\{(\zeta^{\prime}_{n},z^{\prime}_{n}):n\geq 2\\}$ is independent of
$\\{\tilde{S}_{\nu}=E_{i_{j}({\sf G})}\\}$, $Y_{\nu}$ and
$(\zeta^{\prime}_{1},z_{1})$, and for every $l\in\\{2,\dots,|\mathcal{A}({\sf
G})\cap{\cal U}|+1\\}$, the following sequence is i.i.d.:

$\displaystyle\\{(\zeta^{\prime}_{k|\mathcal{A}({\sf G})\cap{\cal
U}|+l},z^{\prime}_{k|\mathcal{A}({\sf G})\cap{\cal U}|+l}):\;k\geq 0\\}\ ,$
(294)

with the common expectation $(\tilde{\mu}_{A}^{\kappa(j,l)}({\sf G}),\
\tilde{q}_{A}^{\kappa(j,l)}({\sf G}))$. Also, note that, in this case,
$M^{\prime}_{\sf G}\geq 1$ is a stopping time with respect to the filtration
generated by $\\{Y_{\nu},Y_{\nu}\in(0,A),z^{\prime}_{n}:n\in\mathbb{N}\\}$.
Then,

$\displaystyle\mathbb{E}_{\nu}^{\sf G}\left[\sum_{n=1}^{M^{\prime}_{\sf
G}}\zeta^{\prime}_{n}\;\Bigg{|}\;\tilde{S}_{\nu}=E_{i_{j}({\sf
G})},Y_{\nu},Y_{\nu}\in(0,A)\right]$ (295)
$\displaystyle=p^{j}_{Y_{\nu}}\times\frac{\mu_{Y_{\nu}}^{j}}{p^{j}_{Y_{\nu}}}+(1-p^{j}_{Y_{\nu}})\times\sum_{l=2}^{|\mathcal{A}({\sf
G})\cap{\cal
U}|+1}w_{l-1}^{\kappa(j,2)}\;\frac{\tilde{\mu}_{A}^{\kappa(j,l)}({\sf
G})}{\tilde{q}_{A}^{\kappa(j,l)}({\sf G})}$ (296)
$\displaystyle=p^{j}_{Y_{\nu}}\times\frac{\mu_{Y_{\nu}}^{j}}{p^{j}_{Y_{\nu}}}+(1-p^{j}_{Y_{\nu}})\times\sum_{l=1}^{|\mathcal{A}({\sf
G})\cap{\cal
U}|}w_{l}^{\kappa(j,2)}\;\frac{\tilde{\mu}_{A}^{\kappa(j,l+1)}({\sf
G})}{\tilde{q}_{A}^{\kappa(j,l+1)}({\sf G})}$ (297)
$\displaystyle=p^{j}_{Y_{\nu}}\times\frac{\mu_{Y_{\nu}}^{j}}{p^{j}_{Y_{\nu}}}+(1-p^{j}_{Y_{\nu}})\times\sum_{l=1}^{|\mathcal{A}({\sf
G})\cap{\cal
U}|}w_{l}^{\kappa(j,2)}\;\frac{\tilde{\mu}_{A}^{\kappa(\kappa(j,2),l)}({\sf
G})}{\tilde{q}_{A}^{\kappa(\kappa(j,2),l)}({\sf G})}$ (298) $\displaystyle\leq
p^{j}_{Y_{\nu}}\left(\frac{A-Y_{\nu}}{\tilde{\mathcal{J}}_{0}^{j}({\sf
G})}\mathbbm{1}\\{Y_{\nu}\in(0,A)\\}+o(A)\right)+(1-p^{j}_{Y_{\nu}})\sum_{l=1}^{|\mathcal{A}({\sf
G})\cap{\cal
U}|}w_{l}^{\kappa(j,2)}\left(\frac{A}{\tilde{\mathcal{J}}^{\kappa(\kappa(j,2),l)}_{0}({\sf
G})}+o(A)\right)$ (299) $\displaystyle\leq
p^{j}_{Y_{\nu}}\left(\frac{A}{\tilde{\mathcal{J}}_{0}^{j}({\sf
G})}\right)+(1-p_{Y_{\nu}})\left(\frac{A}{\tilde{\mathcal{J}}_{*}^{\kappa(j,2)}({\sf
G})}\right)+o(A)$ (300)
$\displaystyle\leq\left(\frac{A}{\tilde{\mathcal{J}}_{0}^{j}({\sf
G})}\bigvee\frac{A}{\tilde{\mathcal{J}}_{*}^{\kappa(j,2)}({\sf
G})}\right)+o(A)\ ,$ (301)

where the constants $\\{w_{l}^{j}:\;j,l\in[|\mathcal{A}({\sf G})\cap{\cal
U}|]\\}$ are defined in (287). In the above, the equality in (296) follows by
a direct application of Lemma C.4(ii), the one in (298) follows by using Lemma
E.2, and the inequality in (299) follows by a direct application of Lemma
(C.1). The proof is complete.

∎

###### Lemma E.4

For every $E\in{\cal U}\setminus\mathcal{A}({\sf G})$ and $A>0$ large enough,
we have

$\displaystyle\mathbb{E}_{\nu}^{{\sf
G}}\left[\zeta_{1}\;\Big{|}\;\tilde{S}_{\nu}=E,Y_{\nu}\in(0,A)\right]$
$\displaystyle\leq C\ ,$ (302)

where $C>0$ is a finite constant independent of $A$.

###### Proof:

We have

$\displaystyle\mathbb{E}_{\nu}^{{\sf
G}}\left[\zeta_{1}\;\Big{|}\;\tilde{S}_{\nu}=E,\,Y_{\nu}\in(0,A)\right]$
$\displaystyle=\mathbb{E}_{\nu}^{{\sf
G}}\left[\zeta^{\prime\prime}_{1}\;\Big{|}\;\tilde{S}_{\nu}=E,Y_{\nu}\in(0,A)\right]$
(303) $\displaystyle\leq C\ ,$ (304)

where the equality in (303) follows from the facts that, given
$\tilde{S}_{\nu}=E$, we have $\zeta_{1}=\zeta^{\prime\prime}_{1}$, and the one
in (304) follows by a direct application of Lemma C.3 since the unit sampled
in $\zeta^{\prime\prime}_{1}$, under $\mathbb{P}_{\nu}^{\sf G}$, follows the
local distribution ${\sf F}^{E}$.
∎

###### Lemma E.5

For any $E\in{\cal U}\setminus\mathcal{A}({\sf G})$,

$\displaystyle\mathbb{E}^{{\sf G}}_{\nu}\left[\sum_{n=1}^{M^{\prime}_{\sf
G}}\zeta^{\prime}_{n}\;\Big{|}\;\tilde{S}_{\nu}=E,\tilde{T}>\nu\right]\leq\max_{j\in[|\mathcal{A}({\sf
G})\cap{\cal U}|]}\;\frac{A}{\tilde{\mathcal{J}}_{*}^{j}({\sf G})}+o(A)\ .$
(305)

###### Proof:

Suppose $j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]$ is such that $E_{i_{j}({\sf
G})}$ is the immediate next unit after $E$, from where we are supposed to
sample according to the pre-fixed permutation of the units. Then,
$\\{\zeta^{\prime}_{n}:n\in\mathbb{N}\\}$ is a sequence of positive and
independent random variables such that, under $\mathbb{P}_{\nu}^{\sf G}$, for
every $l\in\\{1,\dots,|\mathcal{A}({\sf G})\cap{\cal U}|\\}$, the following
sequence is i.i.d.:

$\displaystyle\\{(\zeta^{\prime}_{k|\mathcal{A}({\sf G})\cap{\cal
U}|+l},z^{\prime}_{k|\mathcal{A}({\sf G})\cap{\cal U}|+l}):\;k\geq 0\\}\ ,$
(306)

with the common expectation $(\tilde{\mu}_{A}^{\kappa(j,l)}({\sf G}),\
\tilde{q}_{A}^{\kappa(j,l)}({\sf G}))$, and is independent of
$\\{\tilde{T}>\nu\\}$. As a consequence, $M^{\prime}_{\sf G}$ is a stopping
time with respect to the filtration generated by
$\\{\zeta^{\prime}_{n}:n\in\mathbb{N}\\}$, and

$\displaystyle\mathbb{E}_{\nu}^{{\sf G}}\left[\sum_{n=1}^{M^{\prime}_{\sf
G}}\zeta^{\prime}_{n}\;\Bigg{|}\;\tilde{S}_{\nu}=E\right]$
$\displaystyle=\sum_{l=1}^{|\mathcal{A}({\sf G})\cap{\cal
U}|}w_{l}^{j}\;\frac{\tilde{\mu}_{A}^{\kappa(j,l)}({\sf
G})}{\tilde{q}_{A}^{\kappa(j,l)}({\sf G})}$ (307)
$\displaystyle\leq\sum_{l=1}^{|\mathcal{A}({\sf G})\cap{\cal
U}|}w_{l}^{j}\;\left(\frac{A}{\tilde{\mathcal{J}}_{0}^{\kappa(j,l)}({\sf
G})}+o(A)\right)$ (308)
$\displaystyle\leq\frac{A}{\tilde{\mathcal{J}}_{*}^{j}({\sf G})}+o(A)$ (309)
$\displaystyle\leq\max_{j\in[|\mathcal{A}({\sf G})\cap{\cal
U}|]}\;\frac{A}{\tilde{\mathcal{J}}_{*}^{j}({\sf G})}+o(A)\ ,$ (310)

where the equality in (307) follows by using Lemma C.4(ii), and the inequality
in (308) follows by a direct application of Lemma C.1.
∎

###### Lemma E.6

For any $E\in{\cal U}\setminus\mathcal{A}({\sf G})$ and
$j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]$, we have

$\displaystyle\mathbb{E}^{{\sf G}}_{\nu}\left[\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\,\;\Big{|}\;\,\tilde{S}_{\nu}=E_{i_{j}({\sf
G})},Y_{\nu},Y_{\nu}\in(0,A)\right]\;\leq\;\mathbb{E}_{\nu}^{\sf
G}\left[\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\;\Bigg{|}\;\tilde{S}_{\nu}=E,Y_{\nu}\in(0,A)\right]\leq\;\text{constant}\
,$ (311)

where

$\displaystyle\text{constant}\;=\frac{1}{1-\prod_{j=1}^{|\mathcal{A}({\sf
G})\cap{\cal U}|}(1-\tilde{q}_{-}^{j}({\sf G}))}\sum_{E\in{\cal
U}\setminus\mathcal{A}({\sf G})}\frac{1}{q^{E}_{+}}\ .$ (312)

###### Proof:

Since $\zeta_{1}=\zeta^{\prime\prime}_{1}$, we have $M_{{\sf G}}\geq 1$ and
thus, $N_{\sf G}\geq 1$ is a Geometric random variable with parameter, say
$q_{A}$. Therefore, we have

$\displaystyle\mathbb{E}_{\nu}^{\sf G}\left[\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\;\Bigg{|}\;\tilde{S}_{\nu}=E,Y_{\nu}\in(0,A)\right]\;=\;\mathbb{E}_{\nu}^{\sf
G}\left[\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\;\Bigg{|}\;\tilde{S}_{\nu}=E\right]\;=\;\frac{\mathbb{E}_{\nu}^{\sf
G}[\sigma_{1}]}{q_{A}}\ ,$ (313)

where the first equality in (313) follows from the fact that the distributions
of the cycles are independent of $\\{Y_{\nu}\in(0,A)\\}$, and the second one
follows by an application of Wald’s identity, where $q_{A}$ is the probability
that the process is terminated in the first cycle, i.e.,

$\displaystyle q_{A}:=\mathbb{P}_{\nu}^{\sf G}(z_{n}=1\;\;\text{for
some}\;\;2\leq n\leq|{\cal U}|+1\;\;\text{with}\;\;w_{n}=1)\ .$ (314)

Since we stop only while sampling a unit in $\mathcal{A}({\sf G})$, when
$\tilde{S}_{\nu}\in\mathcal{A}({\sf G})$, we have

$\displaystyle N_{\sf G}=0\quad\text{if and only if}\quad z^{\prime}_{1}=1\ .$
(315)

Otherwise, since the cycles are i.i.d., the probability of termination of the
process at any of the cycles is $q_{A}$. Therefore, under
$\mathbb{P}_{\nu}^{\sf G}$, the conditional distribution of $N_{\sf G}$ is

$\displaystyle\mathbb{P}_{\nu}^{\sf G}\left(N_{\sf
G}=k\;\Big{|}\;\tilde{S}_{\nu}=E_{i_{j}({\sf
G})},Y_{\nu},Y_{\nu}\in(0,A)\right)=\begin{cases}p^{j}_{Y_{\nu}}\qquad&\text{if}\quad
k=0\\\ (1-p^{j}_{Y_{\nu}})(1-q_{A})^{k-1}q_{A}\qquad&\text{if}\quad k\geq
1\end{cases}\ ,$ (316)

where $p^{j}_{Y_{\nu}}$ is defined in (293). Therefore, we have

$\displaystyle\mathbb{E}_{\nu}^{\sf G}\left[\sum_{m=1}^{N_{\sf
G}}\sigma_{m}\;\Bigg{|}\;\tilde{S}_{\nu}=E_{i_{j}({\sf
G})},Y_{\nu},Y_{\nu}\in(0,A)\right]$
$\displaystyle=(1-p^{j}_{Y_{\nu}})\,\frac{\mathbb{E}_{\nu}^{\sf
G}[\sigma_{1}]}{q_{A}}\leq\frac{\mathbb{E}_{\nu}^{\sf G}[\sigma_{1}]}{q_{A}}\
,$ (317)

where the equality in (317) follows from Lemma C.4(ii). Finally, since every
unit in ${\cal U}\setminus\mathcal{A}({\sf G})$ has exactly one corresponding
stage that appears in every cycle, we have

$\displaystyle\mathbb{E}_{\nu}^{{\sf G}}[\sigma_{1}]=\sum_{E\in{\cal
U}\setminus\mathcal{A}({\sf G})}{\sf E}_{{\sf F}}[\zeta^{E}]\ .$ (318)

Furthermore, for any $E\in{\cal U}\setminus\mathcal{A}({\sf G})$, we have

$\displaystyle{\sf E}_{{\sf F}}[\zeta^{E}]\leq{\sf E}_{{\sf
F}}[\zeta^{E}_{-}]=\frac{1}{{\sf
F}(\zeta^{E}_{+}=\infty)}=\frac{1}{q^{E}_{+}}\ ,$ (319)

where the first equality follows from [27, Corollary 8.39].
Furthermore, we have

$\displaystyle 1-q_{A}$ $\displaystyle=\mathbb{P}_{\nu}^{\sf
G}(z_{n}=0\;\;\text{for every}\;\;2\leq n\leq|{\cal
U}|+1\;\;\text{with}\;\;w_{n}=1)$ (320)
$\displaystyle=\prod_{\begin{subarray}{c}2\leq n\leq|{\cal U}|+1,\\\
w_{n}=1\end{subarray}}{\sf G}(z_{n}=0)$ (321)
$\displaystyle=\prod_{j=1}^{|\mathcal{A}({\sf G})\cap{\cal U}|}{\sf
G}(\tilde{z}^{j}=0)=\prod_{j=1}^{|\mathcal{A}({\sf G})\cap{\cal
U}|}(1-\tilde{q}_{A}^{j}({\sf G}))$ (322)
$\displaystyle\leq\prod_{j=1}^{|\mathcal{A}({\sf G})\cap{\cal
U}|}(1-\tilde{q}_{-}^{j}({\sf G}))\ ,$ (323)

where the equality in (320) follows from the fact that,
$\\{z^{\prime}_{n}:n\geq 2\\}$ is a sequence of independent random variables
under $\mathbb{P}_{\nu}^{{\sf G}}$, the one in (322) holds because every unit
in $\mathcal{A}({\sf G})\cap{\cal U}$ has exactly one corresponding stage that
appears in every cycle, which implies that

$\displaystyle\prod_{\begin{subarray}{c}2\leq n\leq|{\cal U}|+1,\\\
w_{n}=1\end{subarray}}\;\mathbbm{1}\\{z_{n}=0\\}\;\overset{d}{=}\;\prod_{j=1}^{|\mathcal{A}({\sf
G})|}\;\mathbbm{1}\\{\tilde{z}^{j}=0\\}\ .$ (324)

The inequality in (323) holds because, by the definitions of
$\tilde{q}_{A}^{j}({\sf G})$ and $\tilde{q}^{j}_{-}({\sf G})$, for
$E=E_{i_{j}({\sf G})}$ we have

$\displaystyle\tilde{q}_{A}^{j}({\sf G})={\sf
G}(\zeta^{E}_{-}>\zeta^{E}_{A})\geq{\sf
G}(\zeta^{E}_{-}=\infty)=\tilde{q}^{j}_{-}({\sf G})\ .$ (325)

The proof is complete.
∎

Finally, we combine every result in this appendix to prove Theorem IV.2.

###  E-G Proof of Theorem IV.2

###### Proof:

Following Lemma E.1, Lemma E.3, Lemma E.4, Lemma E.5 and Lemma E.6, we have

$\displaystyle\text{esssup}\ \mathbb{E}^{{\sf
G}}_{\nu}\left[\tilde{T}-\nu\;\Big{|}\;\mathcal{F}^{\tilde{S}}_{\nu}({\sf
G}),\tilde{T}>\nu\right]$ (326) $\displaystyle\leq\max_{j\in[|\mathcal{A}({\sf
G})\cap{\cal U}|]}\left(\frac{A}{\tilde{\mathcal{J}}_{0}^{j}({\sf
G})}\bigvee\frac{A}{\tilde{\mathcal{J}}_{*}^{\kappa(j,2)}({\sf
G})}\bigvee\frac{A}{\tilde{\mathcal{J}}_{*}^{j}({\sf
G})}\right)+o(A)+\;\text{constant}$ (327)
$\displaystyle=\max_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\left(\frac{A}{\mathcal{J}_{0}^{E}({\sf G})}\right)+o(A)+\;\text{constant}\
.$ (328)

The last equality holds due to the following. For every
$j\in[|\mathcal{A}({\sf G})\cap{\cal U}|]$, note that,

$\displaystyle\min_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\mathcal{J}^{E}_{0}({\sf G})=\min_{l\in[|\mathcal{A}({\sf G})\cap{\cal
U}|]}\tilde{\mathcal{J}}_{0}^{l}({\sf G})\leq\tilde{\mathcal{J}}^{j}_{*}({\sf
G})\ ,$ (329)

where the inequality follows by the definition of
$\tilde{\mathcal{J}}^{j}_{*}({\sf G})$. Consequently, we have

$\displaystyle\min_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\mathcal{J}^{E}_{0}({\sf G})=\min_{l\in[|\mathcal{A}({\sf G})\cap{\cal
U}|]}(\tilde{\mathcal{J}}_{0}^{l}({\sf
G})\wedge\tilde{\mathcal{J}}^{\kappa(l,2)}_{*}({\sf
G})\wedge\tilde{\mathcal{J}}^{l}_{*}({\sf G}))\ .$ (330)

∎

###  E-H Proof of Proposition 2

###### Proof:

By using Lemma C.1 if in the proof of Theorem IV.2 we appropriately replace
the $o(A)$ terms with the following constant

$\displaystyle\max_{E\in\mathcal{A}({\sf G})\cap{\cal
U}}\;\frac{1}{q^{E}_{-}({\sf G})}\left(1+\frac{\mathcal{W}^{E}_{0}({\sf
G})}{\mathcal{J}^{E}_{0}({\sf G})^{2}}\right)\ ,$ (331)

then the non-asymptotic upper bound is obtained. ∎

##  Appendix F An Improvement of The Non-asymptotic Upper Bound

In this appendix, we further improve the non-asymptotic upper bound
established in Proposition 2 under an additional distributional assumption. In
the following, first, we present some lemmas that are useful later.

###  F-A Some useful lemmas

###### Lemma F.1

Suppose $A>0$, $\mathcal{I}_{1}\geq\mathcal{I}_{2}>0$ and $\omega<0$. Let

$\displaystyle f(x):=\frac{A-x}{\mathcal{I}_{1}}+Ae^{\omega
x}\left(\frac{1}{\mathcal{I}_{2}}-\frac{1}{\mathcal{I}_{1}}\right)\
,\quad\text{for}\;\;x\in(0,A)\ .$ (332)

Then