# Quickest Change Detection in Statistically Periodic Processes with Unknown
Post-change Distribution

Taposh Banerjee

Department of Industrial Engineering, University of Pittsburgh

000Address correspondence to Taposh Banerjee, Dept. of Industrial Engineering,
University. of Pittsburgh, 1004 Benedum Hall, Pittsburgh, PA 15261 ; E-mail:
<EMAIL_ADDRESS>
Abstract:

Keywords:

Subject Classifications: 62L05; 62L10; 62L15; 62F05; 62F15; 60G40.

## 1\. INTRODUCTION

In the classical problem of quickest change detection (see Poor and
Hadjiliadis  (2009), Tartakovsky et al.  (2014), Veeravalli and Banerjee
(2013)), a decision maker observes a stochastic process with a given
distribution. At some point in time, the distribution of the process changes.
The problem objective is to detect this change in distribution as quickly as
possible, with minimum possible delay, subject to a constraint on the rate of
false alarms. This problem has applications in statistical process control
(Tagaras  (1998)), sensor networks (Banerjee and Veeravalli  (2015)), cyber-
physical system monitoring (Chen et al.  (2015)), regime changes in neural
data (Banerjee et al.  (2019a)), traffic monitoring (Banerjee et al.
(2018a)), and in general, anomaly detection (Banerjee et al.  (2018a, b)).

In many applications of anomaly detection, the observed process has
statistically periodic behavior. Some examples are as follows:

  1. 1.

Arrhythmia detection in ECG Data: The electrocardiography (ECG) data has an
almost periodic waveform pattern with a series of P waves, QRS complexes, and
ST segments. An arrhythmia can cause a change in this regular pattern
(Goldberger et al.  (2000)).

  2. 2.

Detecting changes in neural spike data: In certain brain-computer interface
(BCI) studies (Zhang et al.  (2003)), an identical experiment is performed on
an animal in a series of trials leading to similar firing patterns. An event
or a trigger (which is part of the experiment) can change the firing pattern
after a certain trial.

  3. 3.

Anomaly detection in city traffic data: Vehicle counts at a street
intersection in New York City (NYC) have been found to show regular patterns
of busy and quiet periods (Banerjee et al.  (2018a, b, 2019b, 2019c, 2019d)).
A congestion or an accident can cause a drop or increase in these vehicle
counts.

  4. 4.

Social network data: The count of the number of Instagram messages posted near
a CCTV camera in NYC has also been found to show approximately periodic
behavior (Banerjee et al.  (2018a, b, 2019b, 2019c, 2019d)).

  5. 5.

Congestion mode detection on highways: In traffic density estimation problems,
it is of interest to detect the mode (congested or uncongested) of the traffic
first before deciding on a model to be used for estimation (Vishnoi et al.
(2020)). Motivated by the NYC data behavior, the traffic intensity in this
application can also be modeled as statistically periodic.

In Banerjee et al. (2021), a new class of stochastic processes, called
independent and periodically identically distributed (i.p.i.d.) processes, has
been introduced to model statistically periodic data . In this process, the
sequence of random variables are independent and the distribution of the
variables are periodic with a given period $T$. Statistically periodic
processes can also be modeled using cyclostationary processes (Gardner et al.
(2006)). However, modeling using i.p.i.d. processes allow for sample-level
detection and the development of strong optimality theory.

In Banerjee et al. (2021), a Bayesian theory is developed for quickest change
detection in i.p.i.d. processes. It is shown that, similar to the i.i.d.
setting, it is optimal to use the Shiryaev statistic, i.e., the a-posteriori
probability that the change has already occured given the data, for change
detection. However, in the i.p.i.d. setting, a change is declared when the
sequence of Shiryaev statistics crosses a sequence of time-varying but
periodic thresholds. It is also shown that a single-threshold test is
asymptotically optimal, as the constraint on the probability of false alarm
goes to zero. The proposed algorithm can also be implemented recursively and
using finite memory. Thus, the set-up of i.p.i.d. processes gives an example
of a non-i.i.d. setting in which exactly optimal algorithm can be implemented
efficiently. The results in Banerjee et al. (2021) are valid when both pre-
and post-change distributions are known.

In this paper, we consider the problem of quickest change detection in
i.p.i.d. processes when the post-change law is unknown. We consider three
different formulations of the problem.

In Section 2, we first consider the problem of robust quickest change
detection in i.p.i.d. processes. In this problem, we assume that the post-
change family of distributions is not known but belongs to an uncertainity
class. We further assume that the post-change family has a distribution that
is least favorable. We then show that the algorithm designed using the least
favorable distribution is minimax robust for the Bayesian delay metric.

In Section 3, we consider the problem in which the post-change distribution is
unknown but belongs to a finite class of distributions. For this setup, we
solve the problem of joint quickest change detection and isolation in i.p.i.d.
processes.

In Section 4, we consider the problem of multislot quickest change detection
in i.p.i.d. processes. In this problem, the exact time slots in a given period
where the change can occur is unknown. We show that a mixture-based test is
asymptotically optimal.

## 2\. Robust Quickest Change Detection

### 2.1. Model and Problem Formulation

We first define the process that we will use to model statistically periodic
random processes.

######  Definition 2.1 (Banerjee et al. (2021)).

A random process $\\{X_{n}\\}$ is called independent and periodically
identically distributed (i.p.i.d) if

  1. 1.

The random variables $\\{X_{n}\\}$ are independent.

  2. 2.

If $X_{n}$ has density $f_{n}$, for $n\geq 1$, then there is a positive
integer $T$ such that the sequence of densities $\\{f_{n}\\}$ is periodic with
period $T$:

$f_{n+T}=f_{n},\quad\forall n\geq 1.$

The law of an i.p.i.d. process is completely characterized by the finite-
dimensional product distribution of $(X_{1},\dots,X_{T})$ or the set of
densities $(f_{1},\cdots,f_{T})$, and we say that the process is i.p.i.d. with
the law $(f_{1},\cdots,f_{T})$. The change point problem of interest is the
following. In the normal regime, the data is modeled as an i.p.i.d. process
with law $(f_{1},\cdots,f_{T})$. At some point in time, due to an event, the
distribution of the i.p.i.d. process deviates from $(f_{1},\cdots,f_{T})$.
Specifically, consider another periodic sequence of densities $\\{g_{n}\\}$
such that

$g_{n+T}=g_{n},\quad\forall n\geq 1.$

It is assumed that at the change point $\nu$, the law of the i.p.i.d. process
switches from $(f_{1},\cdots,f_{T})$ to $(g_{1},\cdots,g_{T})$:

$X_{n}\sim\begin{cases}f_{n},&\quad\forall n<\nu,\\\ g_{n}&\quad\forall
n\geq\nu.\end{cases}$ (2.1)

The densities $(g_{1},\cdots,g_{T})$ need not be all different from the set of
densities $(f_{1},\cdots,f_{T})$, but we assume that there exists at least an
$i$ such that they are different:

$g_{i}\neq f_{i},\quad\text{for some }i=1,2,\cdots,T.$ (2.2)

In this paper, we assume that the post-change law $(g_{1},\cdots,g_{T})$ is
unknown. Further, there are $T$ families of distributions
$\\{\mathcal{P}_{i}\\}_{i=1}^{T}$ such that

$g_{i}\in\mathcal{P}_{i},\quad i=1,2,\dots,T.$

The families $\\{\mathcal{P}_{i}\\}_{i=1}^{T}$ are known to the decision
maker. Below, we use the notation

$G=(g_{1},g_{2},\dots,g_{T})$

to denote the post-change i.p.i.d. law.

Let $\tau$ be a stopping time for the process $\\{X_{n}\\}$, i.e., a positive
integer-valued random variable such that the event $\\{\tau\leq n\\}$ belongs
to the $\sigma$-algebra generated by $X_{1},\cdots,X_{n}$. In other words,
whether or not $\tau\leq n$ is completely determined by the first $n$
observations. We declare that a change has occurred at the stopping time
$\tau$. To find the best stopping rule to detect the change in distribution,
we need a performance criterion. Towards this end, we model the change point
$\nu$ as a random variable with a prior distribution given by

$\pi_{n}=\mathbb{P}(\nu=n),\quad\text{ for }n=1,2,\cdots.$

For each $n\in\mathbb{N}$, we use $\mathbb{P}_{n}^{G}$ to denote the law of
the observation process $\\{X_{n}\\}$ when the change occurs at $\nu=n$ and
the post-change law is $G$. We use $\mathbb{E}_{n}^{G}$ to denote the
corresponding expectation. Using this notation, we define the average
probability measure

$\mathbb{P}^{\pi,G}=\sum_{n=1}^{\infty}\pi_{n}\;\mathbb{P}_{n}^{G}.$

To capture a penalty on the false alarms, in the event that the stopping time
occurs before the change, we use the probability of false alarm defined as

$\mathbb{P}^{\pi,G}(\tau<\nu).$

Note that the probability of false alarm $\mathbb{P}^{\pi,G}(\tau<\nu)$ is not
a function of the post-change law $G$. Hence, in the following, we suppress
the mention of $G$ and refer to the probability of false alarm only by

$\mathbb{P}^{\pi}(\tau<\nu).$

To penalize the detection delay, we use the average detection delay given by

$\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right],$

where $x^{+}=\max\\{x,0\\}$.

The optimization problem we are interested in solving is

$\inf_{\tau\in\mathbf{C}_{\alpha}}\;\;\sup_{G:g_{i}\in\mathcal{P}_{i},i\leq
T}\;\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right],$ (2.3)

where

$\mathbf{C}_{\alpha}=\left\\{\tau:\mathbb{P}^{\pi}(\tau<\nu)\leq\alpha\right\\},$

and $\alpha$ is a given constraint on the probability of false alarm.

In the case when the family of distributions $\\{\mathcal{P}_{i}\\}_{i=1}^{T}$
are singleton sets, i.e. when the post-change law is known and fixed $G$, a
Lagrangian relaxation of this problem was investigated in bane-TIT-2021.
Understanding the solution reported in bane-TIT-2021 is fundamental to solving
the robust problem in (2.3). In the next section, we discuss the solution
provided in bane-TIT-2021 and also its implication for the constrained version
in (2.3).

### 2.2. Exactly and Asymptotically Optimal Solutions for Known Post-Change
Law

For known post-change law $G=(g_{1},\dots,g_{T})$ and geometrically
distributed change point, it is shown in bane-TIT-2021 that the exactly
optimal solution to a relaxed version of (2.3) is a stopping rule based on a
periodic sequence of thresholds. It is also shown that it is sufficient to use
only one threshold in the asymptotic regime of false alarm constraint
$\alpha\to 0$. Furthermore, the assumption of geometrically distributed change
point can be relaxed in the asymptotic regime. In the rest of this section, we
assume that $G$ is known and fixed.

#### 2.2.1. Exactly Optimal Algorithm

Let the change point $\nu$ be a geometric random variable:

$\mathbb{P}(\nu=n)=(1-\rho)^{n-1}\rho,\quad\text{ for }n=1,2,\cdots.$

The relaxed version of (2.3) (for known $G$) is

$\inf_{\tau}\;\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right]+\lambda_{f}\;\mathbb{P}^{\pi}(\tau<\nu),$
(2.4)

where $\lambda_{f}>0$ is a penalty on the cost of false alarms. Now, define
$p_{0}=0$ and

$p_{n}=\mathbb{P}^{\pi,G}(\nu\leq n|X_{1},\cdots,X_{n}),\text{ for }n\geq 1.$
(2.5)

Then, (2.4) is equivalent to solving

$\inf_{\tau}\;\mathbb{E}^{\pi,G}\left[\sum_{n=0}^{\tau-1}p_{n}+\lambda_{f}(1-p_{\tau})\right].$
(2.6)

The belief updated $p_{n}$ can be computed recursively using the following
equations: $p_{0}=0$ and for $n\geq 1$,

$p_{n}=\frac{\tilde{p}_{n-1}\;g_{n}(X_{n})}{\tilde{p}_{n-1}\;g_{n}(X_{n})+(1-\tilde{p}_{n-1})f_{n}(X_{n})},$
(2.7)

where

$\tilde{p}_{n-1}=p_{n-1}+(1-p_{n-1})\rho.$

Since these updates are not stationary, the problem cannot be solved using
classical optimal stopping theory shir-opt-stop-book-1978 or dynamic
programming bert-dyn-prog-book-2017. However, the structure in (5.12) repeats
after every fixed time $T$. Motivated from this, in bane-TIT-2021, a control
theory is developed for Markov decision processes with periodic transition and
cost structures. This new control theory is then used to solve the problem in
(2.6).

######  Theorem 2.1 (bane-TIT-2021).

There exists thresholds $A_{1}$, $A_{2}$, $\dots$, $A_{T}$, $A_{i}\geq
0,\forall i$, such that the stopping rule

$\tau^{*}=\inf\\{n\geq 1:p_{n}\geq A_{(n\bmod T)}\\},$ (2.8)

where $(n\bmod T)$ represents $n$ modulo $T$, is optimal for problem in (2.6).
These thresholds depend on the choice of $\lambda_{f}$.

In fact, the solution given in bane-TIT-2021 is valid for a more general
change point problem in which separate delay and false alarm penalty is used
for each time slot. We do not discuss it here.

#### 2.2.2. Asymptotically Optimal Algorithm

Let there exist $d\geq 0$ such that

$\lim_{n\to\infty}\frac{\log\mathbb{P}(\nu>n)}{n}=-d.$ (2.9)

If $\pi=\text{Geom}(\rho)$, then $d=|\log(1-\rho)|$. Further, let

$I=\frac{1}{T}\sum_{i=1}^{T}D(g_{i}\;\|\;f_{i}),$ (2.10)

where $D(g_{i}\;\|\;f_{i})$ is the Kullback-Leibler divergence between the
densities $g_{i}$ and $f_{i}$.

######  Theorem 2.2 (bane-TIT-2021).

Let the information number $I$ be as defined in (5.17) and satisfy
$0<I<\infty$. Also, let $d$ be as in (4.9). Then, with

$A_{1}=A_{2}=\dots=A_{T}=1-\alpha,$

$\tau^{*}\in\mathbf{C}_{\alpha}$, and

$\begin{split}\mathbb{E}^{\pi,G}\left[(\tau^{*}-\nu)^{+}\right]&=\inf_{\tau\in\mathbf{C}_{\alpha}}\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right](1+o(1))\\\
&=\frac{|\log\alpha|}{I+d}(1+o(1)),\quad\text{ as }\alpha\to 0.\end{split}$
(2.11)

Here $o(1)\to 0$ as $\alpha\to 0$.

#### 2.2.3. Solution to the Constraint Version of the Problem

We now argue that, just as in the classical case, the relaxed version of the
problem (2.6) can be used to provide a solution to the constraint version of
the problem (2.3). We provide the proofs for completeness.

######  Lemma 2.1.

If $\alpha$ is a value of probability of false alarm achievable by the optimal
stoping rule $\tau^{*}$ in (2.6), then $\tau^{*}$ is also optimal for the
constraint problem (2.3) for this $\alpha$.

###### Proof..

By Theorem 2.1, we have

$\begin{split}\mathbb{E}^{\pi,G}\left[(\tau^{*}-\nu)^{+}\right]&+\lambda_{f}\;\mathbb{P}^{\pi}(\tau^{*}<\nu)\\\
&\leq\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right]+\lambda_{f}\;\mathbb{P}^{\pi}(\tau<\nu).\end{split}$
(2.12)

If $\mathbb{P}^{\pi}(\tau^{*}<\nu)=\alpha$ and
$\mathbb{P}^{\pi}(\tau<\nu)\leq\alpha$, then

$\begin{split}\mathbb{E}^{\pi,G}&\left[(\tau^{*}-\nu)^{+}\right]+\lambda_{f}\;\mathbb{P}^{\pi}(\tau^{*}<\nu)\\\
&=\mathbb{E}^{\pi,G}\left[(\tau^{*}-\nu)^{+}\right]+\lambda_{f}\;\alpha\\\
&\leq\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right]+\lambda_{f}\;\mathbb{P}^{\pi}(\tau<\nu)\\\
&\leq\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right]+\lambda_{f}\;\alpha.\end{split}$
(2.13)

Canceling $\lambda_{f}\;\alpha$ from both sides we get

$\mathbb{E}^{\pi,G}\left[(\tau^{*}-\nu)^{+}\right]\leq\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right].$

∎

The following lemma guarantees that a wide range of probability of false alarm
$\alpha$ is achievable by the optimal stopping rule $\tau^{*}$.

######  Lemma 2.2.

As we increase $\lambda_{f}\to\infty$ in (2.6), the probability of false alarm
achieved by the optimal stopping rule $\tau^{*}$ goes to zero.

###### Proof..

As $\lambda_{f}\to\infty$, if the probability of false alarm for $\tau^{*}$
stays bounded away from zero, then the Bayesian risk

$\mathbb{E}^{\pi,G}\left[(\tau^{*}-\nu)^{+}\right]+\lambda_{f}\;\mathbb{P}^{\pi}(\tau^{*}<\nu)$

would diverge to infinity. This will contradict the fact that $\tau^{*}$ is
optimal because we can get a smaller risk at large enough $\lambda_{f}$ by
stopping at a large enough deterministic time. ∎

### 2.3. Optimal Robust Algorithm for Unknown Post-Change Law

We now assume that the post-change law $G$ is unknown and provide the optimal
solution to (2.3) under assumptions on the families of post-change laws
$\\{\mathcal{P}_{i}\\}_{i=1}^{T}$. Specifically, we extend the results in
unni-etal-ieeeit-2011 for i.i.d. processes to i.p.i.d. processes. We assume in
the rest of this section that all densities involved are equivalent to each
other (absolutely continuous with respect to each other). Also, we assume that
the change point $\nu$ is a geometrically distributed random variable.

To state the assumptions on $\\{\mathcal{P}_{i}\\}_{i=1}^{T}$, we need some
defintions. We say that a random variable $Z_{2}$ is stochastically larger
than another random variable $Z_{1}$ if

$\mathbb{P}(Z_{2}\geq t)\geq\mathbb{P}(Z_{1}\geq t),\quad\text{for all
}t\in\mathbb{R}.$

We use the notation

$Z_{2}\succ Z_{1}.$

If $\mathcal{L}_{Z_{2}}$ and $\mathcal{L}_{Z_{1}}$ are the probability laws of
$Z_{2}$ and $Z_{1}$, then we also use the notation

$\mathcal{L}_{Z_{2}}\succ\mathcal{L}_{Z_{1}}.$

We now introduce the notion of stochastic boundedness in i.p.i.d. processes.
In the following, we use

$\mathcal{L}(\phi(X),g)$

to denote the law of some function $\phi(X)$ of the random variable $X$, when
the variable $X$ has density $g$.

######  Definition 2.2 (Stochastic Boundedness in i.p.i.d. Processes; Least
Favorable Law).

We say that the family $\\{\mathcal{P}_{i}\\}_{i=1}^{T}$ is stochastically
bounded by the i.p.i.d. law

$\bar{G}=(\bar{g}_{1},\bar{g}_{2},\dots,\bar{g}_{T}),$

and call $\bar{G}$ the least favorable law (LFL), if

$\bar{g}_{i}\in\mathcal{P}_{i},\quad i=1,2,\dots,T,$

and

$\begin{split}\hskip
11.38092pt\mathcal{L}\left(\log\frac{\bar{g}_{i}(X_{i})}{f_{i}(X_{i})},g_{i}\right)&\succ\mathcal{L}\left(\log\frac{\bar{g}_{i}(X_{i})}{f_{i}(X_{i})},\bar{g}_{i}\right),\\\
\text{for all }&\;g_{i}\in\mathcal{P}_{i},\quad i=1,2,\dots,T.\end{split}$
(2.14)

Consider the stopping rule $\tau^{*}$ designed using the LFL
$\bar{G}=(\bar{g}_{1},\bar{g}_{2},\dots,\bar{g}_{T})$:

$\bar{\tau}^{*}=\inf\\{n\geq 1:\bar{p}_{n}\geq A_{(n\bmod T)}\\},$ (2.15)

where $\bar{p}_{0}=0$, and

$\bar{p}_{n}=\frac{\tilde{p}_{n-1}\;\bar{g}_{n}(X_{n})}{\tilde{p}_{n-1}\;\bar{g}_{n}(X_{n})+(1-\tilde{p}_{n-1})f_{n}(X_{n})},$
(2.16)

where

$\tilde{p}_{n-1}=\bar{p}_{n-1}+(1-\bar{p}_{n-1})\rho.$

We now state the main result of this paper.

######  Theorem 2.3.

Suppose the following conditions hold:

  1. 1.

The family $\\{\mathcal{P}_{i}\\}_{i=1}^{T}$ be stochastically bounded by the
i.p.i.d. law

$\bar{G}=(\bar{g}_{1},\bar{g}_{2},\dots,\bar{g}_{T}).$

  2. 2.

Let $\alpha\in[0,1]$ be a constraint such that

$\mathbb{P}^{\pi}(\bar{\tau}^{*}<\nu)=\alpha,$

where $\bar{\tau}^{*}$ is the optimal rule designed using the LFL (2.15).

  3. 3.

All likelihood ratio functions involved are continuous.

  4. 4.

The change point $\nu$ is geometrically distributed.

Then, the stopping rule $\bar{\tau}^{*}$ in (2.15) designed using the LFL is
optimal for the robust constraint problem in (2.3).

###### Proof..

The key step in the proof is to show that for each $k\in\mathbb{N}$,

$\begin{split}\mathbb{E}_{k}^{\bar{G}}&\left[(\bar{\tau}^{*}-k)^{+}|\mathcal{F}_{k-1}\right]\succ\mathbb{E}_{k}^{G}\left[(\bar{\tau}^{*}-k)^{+}|\mathcal{F}_{k-1}\right],\\\
&\;\text{ for all }G=(g_{1},\dots g_{T}):g_{i}\in\mathcal{P}_{i},\;i\leq
T,\end{split}$ (2.17)

where $\mathcal{F}_{k-1}$ is the sigma algebra generated by observations
$X_{1},\dots,X_{k-1}$. If (2.17) is true then we have for each
$k\in\mathbb{N}$,

$\begin{split}\mathbb{E}_{k}^{\bar{G}}&\left[(\bar{\tau}^{*}-k)^{+}\right]\geq\mathbb{E}_{k}^{G}\left[(\bar{\tau}^{*}-k)^{+}\right]\\\
&\;\text{ for all }G=(g_{1},\dots g_{T}):g_{i}\in\mathcal{P}_{i},\;i\leq
T.\end{split}$ (2.18)

Averaging over the prior on the change point, we get

$\begin{split}&\mathbb{E}^{\pi,\bar{G}}\left[(\bar{\tau}^{*}-\nu)^{+}\right]=\sum_{k}\pi_{k}\mathbb{E}_{k}^{\bar{G}}\left[(\bar{\tau}^{*}-k)^{+}\right]\\\
&\geq\sum_{k}\pi_{k}\mathbb{E}_{k}^{G}\left[(\bar{\tau}^{*}-k)^{+}\right]=\mathbb{E}^{\pi,G}\left[(\bar{\tau}^{*}-\nu)^{+}\right],\\\
&\;\text{ for all }G=(g_{1},\dots g_{T}):g_{i}\in\mathcal{P}_{i},\;i\leq
T.\end{split}$ (2.19)

The last equation is

$\begin{split}\mathbb{E}^{\pi,\bar{G}}&\left[(\bar{\tau}^{*}-\nu)^{+}\right]\geq\mathbb{E}^{\pi,G}\left[(\bar{\tau}^{*}-\nu)^{+}\right],\\\
&\;\text{ for all }G=(g_{1},\dots g_{T}):g_{i}\in\mathcal{P}_{i},\;i\leq
T.\end{split}$ (2.20)

This implies that

$\begin{split}\mathbb{E}^{\pi,\bar{G}}&\left[(\bar{\tau}^{*}-\nu)^{+}\right]=\sup_{G:g_{i}\in\mathcal{P}_{i},i\leq
T}\mathbb{E}^{\pi,G}\left[(\bar{\tau}^{*}-\nu)^{+}\right].\end{split}$ (2.21)

Now, if $\tau$ is any stopping rule satisfying the probability of false alarm
constraint of $\alpha$, then since $\bar{\tau}^{*}$ is the optimal test for
the LFL $\bar{G}$ (see Theorem 2.1), we have

$\begin{split}\sup_{G:g_{i}\in\mathcal{P}_{i},i\leq
T}\mathbb{E}^{\pi,G}\left[(\tau-\nu)^{+}\right]&\geq\mathbb{E}^{\pi,\bar{G}}\left[(\tau-\nu)^{+}\right]\\\
&\geq\mathbb{E}^{\pi,\bar{G}}\left[(\bar{\tau}^{*}-\nu)^{+}\right]\\\
&=\sup_{G:g_{i}\in\mathcal{P}_{i},i\leq
T}\mathbb{E}^{\pi,G}\left[(\bar{\tau}^{*}-\nu)^{+}\right].\end{split}$ (2.22)

The last equation proves the robust optimality of the stopping rule
$\bar{\tau}^{*}$ for the problem in (2.3).

We now prove the key step (2.17). Towards this end, we prove that for every
integer $N\geq 0$,

$\begin{split}\mathbb{P}_{k}^{\bar{G}}&\left[(\bar{\tau}^{*}-k)^{+}>N|\mathcal{F}_{k-1}\right]\geq\mathbb{P}_{k}^{G}\left[(\bar{\tau}^{*}-k)^{+}>N|\mathcal{F}_{k-1}\right],\\\
&\;\text{ for all }G=(g_{1},\dots g_{T}):g_{i}\in\mathcal{P}_{i},\;i\leq
T,\end{split}$ (2.23)

This is trivially true for $N=0$, so we only prove it for $N\geq 1$. For a
fixed $G=(g_{1},\dots g_{T}):g_{i}\in\mathcal{P}_{i},\;i\leq T$, we have

$\begin{split}\mathbb{P}_{k}^{\bar{G}}&\left[(\bar{\tau}^{*}-k)^{+}\leq
N|\mathcal{F}_{k-1}\right]\\\
&\quad=\mathbb{P}_{k}^{\bar{G}}\left[\bar{\tau}^{*}\leq
k+N|\mathcal{F}_{k-1}\right]\\\
&\quad=\mathbb{P}_{k}^{\bar{G}}\left[f(X_{1},X_{2},\dots,X_{k+N})\;\geq\;0\;|\;\mathcal{F}_{k-1}\right],\end{split}$
(2.24)

where the function $f(z_{1},z_{2},\dots,z_{N})$ is given by

$\begin{split}f&(z_{1},z_{2},\dots,z_{N})\\\ &=\max_{1\leq n\leq
N}\left(\sum_{i=1}^{n}\pi_{k}\exp\left(\sum_{i=k}^{n}h_{i}(z_{i})\right)-B_{n}\right).\end{split}$
(2.25)

Here $\\{h_{i}\\}$ are the log likelihood ratio functions (assumed continuous)
and $\\{B_{n}\\}$ are appropriate transformation of the periodic thresholds
$\\{A_{n}\\}$. Since this function $f$ is continuous (being maximum of
continuous functions) and nondecreasing, Lemma III.1 in unni-etal-ieeeit-2011
implies that

$\begin{split}\mathbb{P}_{k}^{\bar{G}}&\left[f(X_{1},X_{2},\dots,X_{k+N})\;\geq\;0\;|\;\mathcal{F}_{k-1}\right]\\\
&\leq\mathbb{P}_{k}^{G}\left[f(X_{1},X_{2},\dots,X_{k+N})\;\geq\;0\;|\;\mathcal{F}_{k-1}\right].\end{split}$
(2.26)

The above equation is a direct consequence of the stochastic boundedness
assumption. Equations (2.24) and (2.26) combined gives

$\begin{split}\mathbb{P}_{k}^{\bar{G}}&\left[(\bar{\tau}^{*}-k)^{+}\leq
N\;|\;\mathcal{F}_{k-1}\right]\\\
&=\mathbb{P}_{k}^{\bar{G}}\left[\bar{\tau}^{*}\leq
k+N\;|\;\mathcal{F}_{k-1}\right]\\\
&=\mathbb{P}_{k}^{\bar{G}}\left[f(X_{1},X_{2},\dots,X_{k+N})\geq
0\;|\;\mathcal{F}_{k-1}\right]\\\
&\leq\mathbb{P}_{k}^{G}\left[f(X_{1},X_{2},\dots,X_{k+N})\geq
0\;|\;\mathcal{F}_{k-1}\right]\\\
&=\mathbb{P}_{k}^{{G}}\left[(\bar{\tau}^{*}-k)^{+}\leq
N\;|\;\mathcal{F}_{k-1}\right].\end{split}$ (2.27)

This proves (2.23) and hence (2.17). ∎

## 3\. Quickest Joint Detection and Classification

### 3.1. Joint Detection and Classification Formulation

We assume that in a normal regime, the data can be modeled as an i.p.i.d.
process with the law $(g_{1}^{(0)},\cdots,g_{T}^{(0)})$. At some point in time
$\nu$, called the change point in the following, the law of the i.p.i.d.
process is governed not by the densities $(g_{1}^{(0)},\cdots,g_{T}^{(0)})$,
but by one of the densities $(g_{1}^{(\ell)},\cdots,g_{T}^{(\ell)})$,
$\ell=1,2,\dots,M$, with

$g_{n+T}^{(\ell)}=g_{n}^{(\ell)},\quad\forall n\geq 1,\quad\ell=1,2,\dots,M.$

Specifically, at the time point $\nu$, the distribution of the random
variables change from $\\{g_{n}^{(0)}\\}$ to $\\{g_{n}^{(\ell)}\\}$:

$X_{n}\sim\begin{cases}g_{n}^{(0)},&\quad\forall n<\nu,\\\
g_{n}^{(\ell)}&\quad\forall n\geq\nu,\text{ for some
}\;\ell=1,2,\dots,M.\end{cases}$ (3.1)

We want to detect the change described in (3.1) as quickly as possible,
subject to a constraints on the rate of false alarms and on the probability of
misclassification. Mathematically, we are looking for a pair $(\tau,\delta)$,
where $\tau$ is stopping time, i.e.,

$\\{\tau\leq n\\}\in\sigma(X_{1},X_{2},\dots,X_{n}),$

and $\delta$ is a decision rule, i.e., a map such that

$\delta(X_{1},X_{2},\dots,X_{\tau})\in\\{1,2,\dots,M\\}.$

Let $\mathbb{P}_{\nu}^{(\ell)}$ denote the probability law of the process
$\\{X_{n}\\}$ when the change occurs at time $\nu$ and the post-change law is
$(g_{1}^{(\ell)},\cdots,g_{T}^{(\ell)})$. We let $\mathbb{E}_{\nu}^{(\ell)}$
denote the corresponding expectation. When there is no change, we use the
notation $\mathbb{E}_{\infty}$. The problem of interest is as follows
lai2000faultiso:

$\begin{split}\min_{\tau,\delta}&\;\;\max_{1\leq\ell\leq M}\sup_{\nu\geq
1}\;\text{ess}\sup\mathbb{E}_{\nu}^{(\ell)}[(\tau-\nu+1)^{+}|X_{1},\cdots,X_{\nu-1}],\\\
\text{subj. to}&\;\;\;\mathbb{E}_{\infty}[\tau]\geq\beta,\\\ \text{and
}&\;\;\;\mathbb{P}_{1}^{(\ell)}[\tau<\infty,\delta\neq\ell]\leq
a_{\beta}\;\mathbb{E}_{1}^{(\ell)}[\tau],\;\quad\ell=1,2,\dots,M,\\\
&\quad\quad\text{where }\log a_{\beta}^{-1}\sim\log\beta,\;\text{ as
}\beta\to\infty.\end{split}$ (3.2)

Here $\text{ess}\sup$ is used to denote the supremum of the random variable
$\mathbb{E}_{\nu}^{(\ell)}[(\tau-\nu+1)^{+}|X_{1},\cdots,X_{\nu-1}]$ outside a
set of measure zero. Here and below, for two functions $h(\beta)$ and
$f(\beta)$ of $\beta$, we use $f(\beta)\sim h(\beta)$, as $\beta\to\infty$, to
denote that the ratio of the two functions goes to $1$ in the limit. Further
motivation of this and other problem formulations for change point detection
and isolation can be found in the literature Tartakovsky et al.  (2014),
lai2000faultiso, niki-ieeetit-2003.

### 3.2. Algorithm for Detection when $M=1$

When $M=1$, i.e., when there is only one post-change i.p.i.d. law, then an
algorithm that is asymptotically optimal for detecting a change in the
distribution is the periodic-CUSUM algorithm proposed in Banerjee et al.
(2019b). In this algorithm, we compute the sequence of statistics

$W_{n+1}=W_{n}^{+}+\log\frac{g_{n+1}^{(1)}(X_{n+1})}{g_{n+1}^{(0)}(X_{n+1})}$
(3.3)

and raise an alarm as soon as the statistic is above a threshold $A$:

$\tau_{c}=\inf\\{n\geq 1:W_{n}\geq A\\}.$ (3.4)

Define

$I_{10}=\frac{1}{T}\sum_{i=1}^{T}D(g_{i}^{(1)}\;\|\;g_{i}^{(0)}),$ (3.5)

where $D(g_{i}^{(1)}\;\|\;g_{i}^{(0)})$ is the Kullback-Leibler divergence
between the densities $g_{i}^{(1)}$ and $g_{i}^{(0)}$. Then, the following
result is proved in Banerjee et al.  (2019b).

######  Theorem 3.1 (Banerjee et al.  (2019b)).

Let the information number $I_{10}$ as defined in (5.17) satisfy
$0<I_{10}<\infty$. Then, with $A=\log\beta$,

$\mathbb{E}_{\infty}[\tau_{c}]\geq\beta,$

and as $\beta\to\infty$,

$\begin{split}&\sup_{\nu\geq
1}\;\text{ess}\sup\mathbb{E}_{\nu}[(\tau_{c}-\nu+1^{+}|X_{1},\cdots,X_{\nu-1}]\\\
&\sim\inf_{\tau:\mathbb{E}_{\infty}[\tau]\geq\beta}\;\sup_{\nu\geq
1}\;\text{ess}\sup\mathbb{E}_{\nu}[(\tau-\nu+1)^{+}|X_{1},\cdots,X_{\nu-1}]\\\
&\sim\frac{\log\beta}{I_{10}}.\end{split}$ (3.6)

Thus, the periodic-CUSUM algorithm is asymptotically optimal for detecting a
change in the distribtion, as the false alarm constraint $\beta\to 0$.
Further, since the set of pre- and post-change densities
$(g_{1}^{(0)},\cdots,g_{T}^{(0)})$ and $(g_{1}^{(1)},\cdots,g_{T}^{(1)})$ are
finite, the recursion in (3.3) can be computed using finite memory needed to
store these $2T$ densities.

### 3.3. Algorithm for Joint Detection and Classification

When the possible number of post-change distributions $M>1$ and when we are
also interested in accurately classifying the true post-change law, the
periodic-CUSUM algorithm is not sufficient. We now propose an algorithm that
can perform joint detection and classification.

For $\ell=1,\dots,M$, define the stopping times

$\begin{split}\tau_{\ell}&=\inf\left\\{n\geq 1:\max_{1\leq k\leq
n}\;\min_{0\leq m\leq
M,m\neq\ell}\;\sum_{i=k}^{n}\log\frac{g_{i}^{(\ell)}(X_{i})}{g_{i}^{(m)}(X_{i})}\geq
A\right\\}.\end{split}$ (3.7)

The stopping time and decision rule for our detection-classification problem
is defined as follows:

$\begin{split}\tau_{dc}&=\min_{1\leq\ell\leq M}\;\tau_{\ell},\\\
\delta_{dc}&=\arg\min_{1\leq\ell\leq M}\tau_{\ell}.\end{split}$ (3.8)

A window-limited version of the above algorithm is obtained by replacing each
$\tau_{\ell}$ in (3.7) by

$\begin{split}\tilde{\tau}_{\ell}&=\inf\left\\{n:\max_{n-L_{\beta}\leq k\leq
n}\;\min_{0\leq m\leq
M,m\neq\ell}\;\sum_{i=k}^{n}\log\frac{g_{i}^{(\ell)}(X_{i})}{g_{i}^{(m)}(X_{i})}\geq
A\right\\}.\end{split}$ (3.9)

For $1\leq\ell\leq M$ and $0\leq m\leq M,\;m\neq\ell$, define

$I_{\ell m}=\frac{1}{T}\sum_{i=1}^{T}D(g_{i}^{(\ell)}\;\|\;g_{i}^{(m)}),$
(3.10)

and

$I^{*}=\min_{1\leq\ell\leq M}\;\min_{0\leq m\leq M,m\neq\ell}\;I_{\ell m}.$
(3.11)

Recall that we are looking for $(\tau,\delta)$ such that

$\begin{split}\mathbb{E}_{\infty}[\tau]\geq\beta(1+o(1)),\text{ as
}\beta\to\infty,\end{split}$ (3.12)

and

$\begin{split}\mathbb{P}_{1}^{(\ell)}&[\tau<\infty,\delta\neq\ell]\leq
a_{\beta}\;\mathbb{E}_{1}^{(\ell)}[\tau],\;\quad\ell=1,2,\dots,M,\\\
&\quad\quad\text{where }\log a_{\beta}^{-1}\sim\log\beta,\;\text{ as
}\beta\to\infty.\end{split}$ (3.13)

Let

$C_{\beta}=\\{(\tau,\delta):\text{conditions in \eqref{eq:MFA}}\text{ and
}\eqref{eq:faultIsolProb}\text{ hold}\\}.$ (3.14)

######  Theorem 3.2.

Let the information number $I^{*}$ be as defined in (3.11) and satisfy
$0<I^{*}<\infty$. Then, with $A=\log 4M\beta$,

$(\tau_{dc},\delta_{dc})\in C_{\beta}.$

Also,

$\begin{split}&\max_{1\leq\ell\leq M}\sup_{\nu\geq
1}\;\text{ess}\sup\mathbb{E}_{\nu}^{(\ell)}[(\tau_{dc}-\nu+1)^{+}|X_{1},\cdots,X_{\nu-1}]\\\
&\sim\inf_{(\tau,\delta)\in C_{\beta}}\max_{1\leq\ell\leq M}\sup_{\nu\geq
1}\;\text{ess}\sup\mathbb{E}_{\nu}^{(\ell)}[(\tau-\nu+1)^{+}|X_{1},\cdots,X_{\nu-1}]\\\
&\sim\frac{\log\beta}{I^{*}},\;\text{ as }\beta\to\infty.\end{split}$ (3.15)

Finally, the window-limited version of the test (3.9) also satisfies the same
asymptotic optimality property as long as

$\lim\inf_{\beta\to\infty}\frac{L_{\beta}}{\log\beta}>\frac{1}{I^{*}}.$

###### Proof..

For $1\leq\ell\leq M$ and $0\leq m\leq M,\;m\neq\ell$, define

$Z_{i}(\ell,m)=\log\frac{g_{i}^{(\ell)}(X_{i})}{g_{i}^{(m)}(X_{i})}$

to be the log likelihood ratio at time $i$ between the measures
$\mathbb{P}_{1}^{(\ell)}$ and $\mathbb{P}_{1}^{(m)}$. In the rest of the
proof, to write compact equations, we use $X_{1}^{\nu-1}$ to denote the vector

$X_{1}^{\nu-1}=(X_{1},X_{2},\dots,X_{\nu-1}).$

For each $1\leq\ell\leq M$ and $0\leq m\leq M,\;m\neq\ell$, we first show that
the sequence $\\{Z_{i}(\ell,m)\\}$ satisfies the following statement:

$\begin{split}\sup_{\nu\geq
1}\operatorname*{ess\,sup}\mathbb{P}_{\nu}^{(\ell)}&\left(\max_{t\leq
n}\sum_{i=\nu}^{\nu+t}Z_{i}(\ell,m)\geq I_{\ell
m}(1+\delta)n\;\bigg{|}\;X_{1}^{\nu-1}\right)\\\ &\to 0,\text{ as
}n\to\infty,\quad\forall\delta>0,\end{split}$ (3.16)

where $I_{\ell m}$ is as defined in (3.10).

Towards proving (5.19), note that as $n\to\infty$

$\begin{split}\frac{1}{n}\sum_{i=\nu}^{\nu+n}Z_{i}(\ell,m)\to I_{\ell
m},\quad\text{a.s.}\;\mathbb{P}_{\nu}^{(\ell)},\;\;\forall\nu\geq
1.\end{split}$ (3.17)

The above display is true because of the i.p.i.d. nature of the observation
process. This implies that as $n\to\infty$

$\begin{split}\max_{t\leq n}\frac{1}{n}\sum_{i=\nu}^{\nu+t}Z_{i}(\ell,m)\to
I_{\ell m},\quad\text{a.s.}\;\mathbb{P}_{\nu}^{(\ell)},\;\;\forall\nu\geq
1.\end{split}$ (3.18)

To show this, note that

$\begin{split}\max_{t\leq n}&\frac{1}{n}\sum_{i=\nu}^{\nu+t}Z_{i}(\ell,m)\\\
&=\max\left\\{\max_{t\leq
n-1}\frac{1}{n}\sum_{i=\nu}^{\nu+t}Z_{i}(\ell,m),\;\;\frac{1}{n}\sum_{i=\nu}^{\nu+n}Z_{i}(\ell,m)\right\\}.\end{split}$
(3.19)

For a fixed $\epsilon>0$, because of (3.17), the LHS in (3.18) is greater than
$I_{\ell m}(1-\epsilon)$ for $n$ large enough. Also, let the maximum on the
LHS be achieved at a point $k_{n}$, then

$\max_{t\leq
n}\frac{1}{n}\sum_{i=\nu}^{\nu+t}Z_{i}(\ell,m)=\frac{1}{n}\sum_{i=\nu}^{\nu+k_{n}}Z_{i}(\ell,m)=\frac{k_{n}}{n}\frac{1}{k_{n}}\sum_{i=\nu}^{\nu+k_{n}}Z_{i}(\ell,m).$

Now $k_{n}$ cannot be bounded because of the presence of $n$ in the
denominator. This implies $k_{n}>i$, for any fixed $i$, and $k_{n}\to\infty$.
Thus, $\frac{1}{k_{n}}\sum_{i=\nu}^{\nu+k_{n}}Z_{i}(\ell,m)\to I_{\ell m}$.
Since $k_{n}/n\leq 1$, we have that the LHS in (3.18) is less than $I_{\ell
m}(1+\epsilon)$, for $n$ large enough. This proves (3.18). To prove (5.19),
note that due to the i.p.i.d. nature of the process

$\begin{split}\sup_{\nu\geq
1}\operatorname*{ess\,sup}\mathbb{P}_{\nu}^{(\ell)}&\left(\max_{t\leq
n}\sum_{i=\nu}^{\nu+t}Z_{i}(\ell,m)\geq I_{\ell
m}(1+\delta)n\;\bigg{|}\;X_{1}^{\nu-1}\right)\\\ =\sup_{1\leq\nu\leq
T}\mathbb{P}_{\nu}^{(\ell)}&\left(\max_{t\leq
n}\sum_{i=\nu}^{\nu+t}Z_{i}(\ell,m)\geq I_{\ell
m}(1+\delta)n\right).\end{split}$ (3.20)

The right hand side goes to zero because of (3.18) and because the maximum on
the right hand side in (3.20) is over only finitely many terms.

Next, we show that the sequence $\\{Z_{i}(\ell,m)\\}$, for each $1\leq\ell\leq
M$ and $0\leq m\leq M,\;m\neq\ell$, satisfies the following statement:

$\begin{split}\lim_{n\to\infty}\sup_{k\geq\nu\geq
1}\operatorname*{ess\,sup}\;\mathbb{P}_{\nu}^{(\ell)}&\left(\frac{1}{n}\sum_{i=k}^{k+n}Z_{i}(\ell,m)\leq
I_{\ell m}-\delta\;\bigg{|}\;X_{1}^{\nu-1}\right)\\\
&=0,\quad\forall\delta>0.\end{split}$ (3.21)

To prove (3.21), note that due to the i.p.i.d nature of the process we have

$\begin{split}&\sup_{k\geq\nu\geq
1}\operatorname*{ess\,sup}\;\mathbb{P}_{\nu}^{(\ell)}\left(\frac{1}{n}\sum_{i=k}^{k+n}Z_{i}(\ell,m)\leq
I_{\ell m}-\delta\;\bigg{|}\;X_{1}^{\nu-1}\right)\\\ &=\sup_{\nu+T\geq
k\geq\nu\geq
1}\mathbb{P}_{\nu}^{(\ell)}\left(\frac{1}{n}\sum_{i=k}^{k+n}Z_{i}(\ell,m)\leq
I_{\ell m}-\delta\right)\\\ &=\max_{1\leq\nu\leq T}\max_{\nu\leq
k\leq\nu+T}\mathbb{P}_{\nu}^{(\ell)}\left(\frac{1}{n}\sum_{i=k}^{k+n}Z_{i}(\ell,m)\leq
I_{\ell m}-\delta\right).\end{split}$ (3.22)

The right hand side of the above equation goes to zero for any $\delta$
because of (3.17) and also because of the finite number of maximizations. The
theorem now follows from Theorem 4 of lai2000faultiso. ∎

######  Remark 3.1.

The algorithm and optimality are valid for multistream data as well. We only
need to treat the observation process as a sequence of random vectors.

## 4\. Multislot and Multistream Quickest Change Detection

In this paper, we extend this result in the following two directions:

  1. 1.

Multislot change detection: In the problem stated above, the density $g_{i}$
is allowed to be the same as $f_{i}$ for some values of $i$. But, the exact
time slots where they differ are assumed to be known. We develop algorithms
for multislot change detection where the exact slots out of
$\\{1,2,\dots,T\\}$ where change occurs in each period is not known. See
Section 4 below.

  2. 2.

Multistream change detection: In this problem, we assume that there are
multiple streams of data, each modeled using an i.p.i.d. process. At the
change point, the i.p.i.d. law of an unknown subset of the streams changes.
See Section 4.4 below.

The ideas used to solve the above two problems can be used to also solve the
more general multistream problem where the post-change slots in each of the
streams are also unknown. For a general background in sequential analysis and
quickest change detection, we refer the readers to Veeravalli and Banerjee
(2013); Poor and Hadjiliadis  (2009); Tartakovsky et al.  (2014); Siegmund
(1985); Woodroofe (1982); shir-opt-stop-book-1978; tartakovsky2019sequential;
wald_book_1947.

Let $(f_{1},\cdots,f_{T})$ and $(g_{1},\cdots,g_{T})$ represent the laws of
two i.p.i.d processes with $f_{i}\neq g_{i}$, $\forall i$. We assume that the
second-order moments of log likelihood ratios are finite and positive:

$\vspace{-0.2cm}\begin{split}\text{(M1)}\quad&0<\mathbb{E}_{1}\left(\left|\log\frac{g_{i}(X_{i})}{f_{i}(X_{i})}\right|\right)<\infty,\;i=1,2,\cdots,T\\\
\text{(V1)}\quad&0<\mathbb{E}_{1}\left(\log\frac{g_{i}(X_{i})}{f_{i}(X_{i})}\right)^{2}<\infty,\;i=1,2,\cdots,T.\quad\end{split}$
(4.1)

Here $\mathbb{E}_{1}$ denotes the expectation when the change occurs at time
$\nu=1$.

In the multislot change detection problem, the change occurs in only a subset
of the $T$ time slots in each period. To capture this we now introduce a new
notation for the post-change law emphasizing the slots where the density
changes. For a subset $S\subset\\{1,2,\dots,T\\}$, define a possible post-
change i.p.i.d. law as

$\begin{split}g_{S}&=(g_{S,1},g_{S,2},\dots,g_{S,T}),\end{split}$ (4.2)

with

$g_{S,i}=\begin{cases}g_{i},\text{ if }\;i\in S\\\ f_{i},\text{ if }\;i\not\in
S.\end{cases}$ (4.3)

Note that

$g_{S}=(g_{1},\cdots,g_{T}),\;\text{ if }S=\\{1,\dots,T\\}.$

Thus, the set $S$ denotes the slots in which the change occurs:

$X_{n}\sim\begin{cases}f_{n},&\quad\forall n<\nu\\\ g_{S,n}&\quad\forall
n\geq\nu,\end{cases}$ (4.4)

with the understanding that $g_{S,n+T}=g_{S,n}$, $\forall n$. This set is not
known to the decision maker. However, it is known that

$S\in\mathcal{S}\subset 2^{\\{1,\dots,T\\}},$

i.e., $S$ belongs to a family of the subsets of the power set of
$\\{1,\dots,T\\}$. For example,

$\mathcal{S}=\\{S:|S|\leq m\\},$

where $|S|$ denotes the size of set $S$. The algorithms that we will propose
for change detection will be especially useful when $m\ll T$.

Let $\tau$ be a stopping time for the process $\\{X_{n}\\}$, i.e., a positive
integer-valued random variable such that the event $\\{\tau\leq n\\}$ belongs
to the $\sigma$-algebra generated by $\\{X_{1},\cdots,X_{n}\\}$. We model the
change point $\nu$ as a random variable with a prior $\pi$:

$\pi_{n}=\mathbb{P}(\nu=n),\quad\text{ for }n=1,2,\cdots.$

Let $\mathbb{P}^{S}_{n}$ denotes the law of the observation process
$\\{X_{n}\\}$ when the change occurs in slots $S$ at time $\nu=n$ and define

$\mathbb{P}^{S}_{\pi}=\sum_{n=1}^{\infty}\pi_{n}\;\mathbb{P}^{S}_{n}.$

We use $\mathbb{E}^{S}_{n}$ and $\mathbb{E}^{S}_{\pi}$ to denote the
corresponding expectations. For each $S\in\mathcal{S}$, we seek a solution to

$\min_{\tau\in\mathbf{C}_{\alpha}}\mathbb{E}^{S}_{\pi}\left[\tau-\nu|\tau\geq\nu\right],$
(4.5)

where

$\mathbf{C}_{\alpha}=\\{\tau:\mathbb{P}^{S}_{\pi}(\tau<\nu)\leq\alpha\\},$
(4.6)

and $\alpha$ is a given constraint on the probability of false alarm. In fact,
we seek an algorithm that solves the above problem uniformly over every $S$.

### 4.1. Algorithm for Multislot Change Detection

Consider a mixing distribution or a probability mass function on the set
$\mathcal{S}$:

$p_{S}\geq 0,\;\forall S\in\mathcal{S},\quad\text{ and
}\quad\sum_{S\in\mathcal{S}}p_{S}=1.$

Define the mixture statistic

$R_{n}=\frac{1}{\Pi_{n}}\sum_{k=1}^{n}\pi_{k}\sum_{S\in\mathcal{S}}p_{S}\prod_{i=k}^{n}\frac{g_{S,i}(X_{i})}{f_{i}(X_{i})},$
(4.7)

where $\Pi_{n}=\mathbb{P}(\nu>n)$, and the stopping rule

$\tau_{mps}=\inf\\{n\geq 1:R_{n}>A\\}.$ (4.8)

In the following, we call this algorithm the mixture periodic Shiryaev or the
MPS algorithm. Note that

$R_{n}=\sum_{S\in\mathcal{S}}p_{S}\frac{1}{\Pi_{n}}\sum_{k=1}^{n}\pi_{k}\prod_{i=k}^{n}\frac{g_{S,i}(X_{i})}{f_{i}(X_{i})}.$

Thus, the statistic $R_{n}$ is a mixture of $|\mathcal{S}|$ periodic Shiryaev
statistics (see banerjee2019bayesian), one for each $S\in\mathcal{S}$. Thus,
the statistic $R_{n}$ can be computed recursively and using finite memory for
geometric prior $\pi=\text{Geom}(\rho)$ (see Lemma 5.1 in
banerjee2019bayesian).

### 4.2. Lower Bound on Detection Delay

In this section, we obtain a lower bound on the average detection delay for
any stopping time that satisfies the constraint on the probability of false
alarm (4.6). We make the following assumptions.

  * (A1)

Let there exist $d\geq 0$ such that

$\lim_{n\to\infty}\frac{\log\mathbb{P}(\nu>n)}{n}=-d.$ (4.9)

  * (A2)

Also, let

$\sum_{n=1}^{\infty}\pi_{n}|\log\pi_{n}|<\infty.$ (4.10)

If $\pi=\text{Geom}(\rho)$, then

$\frac{\log\mathbb{P}(\nu>n)}{n}=\frac{\log(1-\rho)^{n}}{n}=\frac{n\log(1-\rho)}{n}=\log(1-\rho).$

Thus, $d=|\log(1-\rho)|$. In addition,

$\sum_{n=1}^{\infty}\pi_{n}|\log\pi_{n}|=\frac{1-\rho}{\rho}\log\frac{1}{\rho(1-\rho)}<\infty.$

Thus, conditions (A1) and (A2) above are satisfied by the geometric prior.

We first start with a lemma whose proof is elementary. Define

$Z_{i}=\log\frac{g_{S,i}(X_{i})}{f_{i}(X_{i})},$ (4.11)

and

$I_{S}=\frac{1}{T}\sum_{i\in S}D(g_{S,i}\;\|\;f_{i}).$ (4.12)

######  Lemma 4.1.

For $Z_{i}$ defined in (4.11) and $I_{S}$ defined in (4.12), for each
$S\in\mathcal{S}$ and as $n\to\infty$, we have

$\frac{1}{n}\sum_{i=k}^{k+n-1}Z_{i}\;\;\to\;\;I_{S},\quad\mathbb{P}^{S}_{k}\;\text{
a.s.},\;\forall k\geq 1.$ (4.13)

The lower bound is supplied by the following theorem.

######  Theorem 4.1.

Let the information number $I_{S}$ be as defined in (4.12). Also, let the
prior $\pi$ satisfy the condition (A1) in (4.9). Then, for any stopping time
$\tau\in\mathbf{C}_{\alpha}$, we have

$\mathbb{E}^{S}_{\pi}\left[\tau-\nu|\tau\geq\nu\right]\geq\frac{|\log\alpha|}{I_{S}+d}(1+o(1)),\quad\text{
as }\alpha\to 0.$ (4.14)

Here $o(1)\to 0$ as $\alpha\to 0$.

###### Proof..

The result follows from Lemma 4.1 above and Theorem 5.1 in
banerjee2019bayesian. ∎

### 4.3. Optimality of the MPS Algorithm

We now show that the MPS algorithm (4.8) is asymptotically optimal for problem
(4.5) for each post-change slots $S\in\mathcal{S}$, as the false alarm
constraint $\alpha\to 0$. We first prove an important lemma.

Define

$\gamma_{k}(\epsilon)=\sum_{n=1}^{\infty}\mathbb{P}^{S}_{k}\left(\bigg{|}\frac{1}{n}\sum_{i=k}^{k+n-1}Z_{i}-I_{S}\bigg{|}>\epsilon\right),$
(4.15)

where $Z_{i}$ is as defined in (4.11).

######  Lemma 4.2.

For every $\epsilon>0$,

$\sum_{k=1}^{\infty}\pi_{k}\gamma_{k}(\epsilon)<\infty,$ (4.16)

where $\gamma_{k}(\epsilon)$ is defined in (4.15).

###### Proof..

The proof is provided in the appendix. ∎

In words, the above lemma states that i.p.i.d. processes satisfy the complete
convergence condition Tartakovsky et al.  (2014), tartakovsky2019sequential.

######  Theorem 4.2.

Let the prior satisfy the conditions (A1) and (A2). With
$A=\frac{1-\alpha}{\alpha}$ in (4.8), we have for each $S\in\mathcal{S}$,

$\mathbb{P}^{S}_{\pi}(\tau_{mps}<\nu)\leq\alpha$

and

$\mathbb{E}^{S}_{\pi}\left[\tau_{mps}-\nu|\tau_{mps}\geq\nu\right]\leq\frac{|\log\alpha|}{I_{S}+d}(1+o(1)),\quad\text{
as }\alpha\to 0.$ (4.17)

###### Proof..

The proof is provided in the appendix. ∎

Thus, the MPS algorithm achieves the asymptotic lower bound given in Theorem
4.1 and is asymptotically optimal uniformly over $S$.

### 4.4. Multistream Change Detection

In the multistream problem, we assume that there are $L$ independent streams
of observations $\\{X_{n,\ell}\\}$, $n\geq 1$, $\ell=1,\dots,L$. For each
$\ell$, the observation sequence $\\{X_{n,\ell}\\}_{n\geq 1}$ is an i.p.i.d.
process with law $(f_{1,\ell},\dotsc,f_{T,\ell})$. Let
$B\subset\\{1,2,\dots,L\\}$. At the change point $\nu$, the law of the
i.p.i.d. process in the $\ell$th stream, if $\ell\in B$, changes from
$(f_{1,\ell},\dotsc,f_{T,\ell})$ to $(g_{1,\ell},\dotsc,g_{T,\ell})$, i.e.,

$X_{n,\ell}\sim\begin{cases}f_{n,\ell},&\quad\forall n\text{ if }\ell\not\in
B\\\ f_{n,\ell},&\quad\text{ for }n<\nu\text{ if }\ell\in B\\\
g_{n,\ell}&\quad\text{ for }n\geq\nu\text{ if }\ell\in B.\end{cases}$ (4.18)

Similar to the multislot case, the set $B$ is not known to the decision maker.
However, it is known that $B\in\mathcal{B}\subset 2^{\\{1,\dots,L\\}}.$

The objective is to detect this change in distribution and to solve

$\min_{\tau\in\mathbf{C}_{\alpha}}\mathbb{E}^{B}_{\pi}\left[\tau-\nu|\tau\geq\nu\right],$
(4.19)

where $\mathbb{E}^{B}_{\pi}$ is the expectation with respect to the
probability measure under which change occurs in the streams $B$, and

$\mathbf{C}_{\alpha}=\\{\tau:\mathbb{P}^{B}_{\pi}(\tau<\nu)\leq\alpha\\}.$

As before, we show that a mixture based test is uniformly asymptotically
optimal for each choice of the post-change subset $B$.

Define the mixing distribution

$p_{B}\geq 0,\;\forall B\in\mathcal{B},\quad\text{ and
}\quad\sum_{B\in\mathcal{B}}p_{B}=1.$

Also, define the mixture statistic

$M_{n}=\frac{1}{\Pi_{n}}\sum_{k=1}^{n}\pi_{k}\sum_{B\in\mathcal{B}}p_{B}\prod_{\ell\in
B}\prod_{i=k}^{n}\frac{g_{i,\ell}(X_{i,\ell})}{f_{i,\ell}(X_{i,\ell})},$
(4.20)

where $\Pi_{n}=\mathbb{P}(\nu>n)$, and the stopping rule

$\tau_{msps}=\inf\\{n\geq 1:M_{n}>A\\}.$ (4.21)

Furthermore, define the information numbers

$\begin{split}I^{(\ell)}&=\frac{1}{T}\sum_{i=1}^{T}D(g_{i}^{(\ell)}\;\|\;f_{i}^{(\ell)})\\\
I_{B}&=\sum_{\ell\in B}I^{(\ell)}.\end{split}$ (4.22)

Then, we have the following optimality result for the mixture rule in (4.21).

######  Theorem 4.3.

Let the prior satisfy the conditions (A1) and (A2). With
$A=\frac{1-\alpha}{\alpha}$ in (4.21), we have for each $B\in\mathcal{B}$:
$\mathbb{P}^{B}_{\pi}(\tau_{msps}<\nu)\leq\alpha,$ and

$\begin{split}\mathbb{E}^{B}_{\pi}\left[\tau_{msps}-\nu|\tau_{msps}\geq\nu\right]&=\inf_{\tau\in
C_{\alpha}}\mathbb{E}^{B}_{\pi}\left[\tau-\nu|\tau\geq\nu\right]\\\
&=\frac{|\log\alpha|}{I_{B}+d}(1+o(1)),\quad\text{ as }\alpha\to
0.\end{split}$ (4.23)

###### Proof..

The proof uses essentially the same arguments used in the proof of Theorem
4.1, Theorem 4.2, and Lemma 4.2, and is skipped. ∎

###### Proof of Lemma 4.2.

The sequence

$\left\\{\gamma_{k}(\epsilon)\right\\}_{k=1}^{\infty}$

in (4.15) is periodic with period $T$, and as a result, there are at most $T$
distinct values in the above sequence:

$\gamma_{1}(\epsilon),\;\cdots,\gamma_{T}(\epsilon).$

Thus, if we show that these $T$ numbers are finite for any $\epsilon>0$, then
we automatically have

$\sum_{k=1}^{\infty}\pi_{k}\gamma_{k}(\epsilon)<\infty,\quad\forall\epsilon>0.$

Furthermore, since we do not make any explicit assumptions on the actual
values taken by the densities $(f_{1},\cdots,f_{T})$ and
$(g_{1},\cdots,g_{T})$, we can exploit the i.p.i.d. nature of the processes to
just show that

$\gamma_{1}(\epsilon)<\infty,\quad\forall\epsilon>0.$

Recall the definition of $\gamma_{1}(\epsilon)$:

$\gamma_{1}(\epsilon)=\sum_{n=1}^{\infty}\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}Z_{i}-I_{S}\bigg{|}>\epsilon\right).$

For $\ell=1,2,\cdots,T$, define

$Z_{i}^{(\ell)}=\begin{cases}Z_{i}\quad\text{ if }i=mT+\ell\;\text{ for
}m=0,1,2,\cdots\\\ 0\quad\text{ otherwise }.\end{cases}$

Note that

$Z_{i}^{(\ell)}=0,\;\text{ if }\ell\not\in S.$

Also recall that

$I_{S}=\frac{1}{T}\sum_{\ell\in S}I_{\ell},$

where

$I_{\ell}=D(g_{\ell}\;\|\;f_{\ell}).$

Using these definitions, we can write

$\begin{split}\frac{1}{n}\sum_{i=1}^{n}Z_{i}-I_{S}&=\frac{1}{n}\sum_{i=1}^{n}\sum_{\ell\in
S}Z^{(\ell)}_{i}-\frac{1}{T}\sum_{\ell\in S}I_{\ell}\\\ &=\sum_{\ell\in
S}\left(\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{(\ell)}-\frac{I_{\ell}}{T}\right).\end{split}$

This implies

$\begin{split}\mathbb{P}^{S}_{1}&\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}Z_{i}-I_{S}\bigg{|}>\epsilon\right)\\\
&\leq\sum_{\ell\in
S}\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{(\ell)}-\frac{I_{\ell}}{T}\bigg{|}>\frac{\epsilon}{|S|}\right).\end{split}$

Thus, to show the summability of the LHS in the above equation, we need to
show the summability of each of the $|S|$ terms on the RHS. Again, due to the
i.p.i.d. nature of the process, and because we have made no explicit
assumptions about the densities $(f_{1},\cdots,f_{T})$ and
$(g_{1},\cdots,g_{T})$, it is enough to establish the summability of any one
of terms on the right. That is, for $\ell\in S$, we want to show that

$\sum_{n=1}^{\infty}\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{(\ell)}-\frac{I_{\ell}}{T}\bigg{|}>\frac{\epsilon}{|S|}\right)<\infty.$

Define for $\ell=1,2,\cdots,T$,

$I_{i}^{(\ell)}=\begin{cases}I_{\ell}\quad\text{ if }i=mT+\ell\;\text{ for
}m=0,1,2,\cdots,\ell\in S\\\ 0\quad\text{ otherwise.}\end{cases}.$

Using this definition we write for $\ell\in S$,

$\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{(\ell)}-\frac{I_{\ell}}{T}=\frac{1}{n}\sum_{i=1}^{n}(Z_{i}^{(\ell)}-I_{i}^{(\ell)})+\frac{1}{n}\sum_{i=1}^{n}I_{i}^{(1)}-\frac{I_{\ell}}{T}.$

Thus, with $\tilde{Z}_{i}^{(\ell)}=Z_{i}^{(\ell)}-I_{i}^{(\ell)}$, we have

$\begin{split}\mathbb{P}^{S}_{1}&\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{(\ell)}-\frac{I_{\ell}}{T}\bigg{|}>\frac{\epsilon}{|S|}\right)\\\
&\leq\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\tilde{Z}_{i}^{(\ell)}\bigg{|}>\frac{\epsilon}{2|S|}\right)\\\
&\quad+\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}I_{i}^{(\ell)}-\frac{I_{\ell}}{T}\bigg{|}>\frac{\epsilon}{2|S|}\right).\end{split}$
(4.24)

Now,
$\frac{1}{n}\sum_{i=1}^{n}I_{i}^{(\ell)}=\frac{1}{n}I_{\ell}\lfloor\frac{n}{T}\rfloor\to\frac{I_{\ell}}{T},\quad\text{
as }k\to\infty$. Thus, for $n$ large enough, the second term on the right in
(4.24) is identically zero. Thus, we only need to show that

$\sum_{n=1}^{\infty}\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\tilde{Z}_{i}^{(\ell)}\bigg{|}>\frac{\epsilon}{2|S|}\right)<\infty,\quad\ell\in
S.$

Towards this end, note that the probability
$\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\tilde{Z}_{i}^{(\ell)}\bigg{|}>\frac{\epsilon}{2|S|}\right)$
is decreasing with increasing $n$. Using this fact, we can write

$\begin{split}\sum_{n=1}^{\infty}&\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\tilde{Z}_{i}^{(\ell)}\bigg{|}>\frac{\epsilon}{2|S|}\right)\\\
&\leq
T+T\sum_{j=1}^{\infty}\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{jT+\ell}\sum_{i=1}^{jT+\ell}\tilde{Z}_{i}^{(\ell)}\bigg{|}>\frac{\epsilon}{2|S|}\right)\\\
&\leq
T+T\sum_{j=1}^{\infty}\mathbb{P}^{S}_{1}\left(\bigg{|}\frac{1}{j}\sum_{i=1}^{jT+\ell}\tilde{Z}_{i}^{(\ell)}\bigg{|}>\frac{\epsilon}{2|S|}\right).\end{split}$

The rightmost summation is finite because the sum inside is a sum of $j$
i.i.d. random variables with distribution of $Z_{\ell}$ under $\mathbb{P}_{1}$
Tartakovsky et al.  (2014). The summation is finite for i.i.d. random
variables with finite variance. See also tartakovsky2019sequential. ∎

###### Proof of Theorem 4.2.

The results follows directly from Lemma 4.2 and arguments provided in
tartakovsky2019sequential. But, we provide the complete proof for
completeness. We first note that for any discrete integer-valued random
variable such as a stopping time $\tau$,

$\mathbb{E}[\tau]=\sum_{n=0}^{\infty}\mathbb{P}(\tau>n)\leq
N+\sum_{n=N}^{\infty}\mathbb{P}(\tau>n),$

where $N$ is any positive integer. The theorem follows by carefully choosing
the value $N$ above and obtaining an upper bound on $\mathbb{P}(\tau>n)$.

For $0<\epsilon<I_{S}+d$, set

$N=N_{\alpha}=1+\Bigl{\lfloor}\frac{\log(A_{\alpha}/\pi_{k})}{I_{S}+d-\epsilon}\Bigr{\rfloor},$

where

$A_{\alpha}=\frac{1-\alpha}{\alpha}.$

Using this value of $N$ for $(\tau_{mps}-k)^{+}$ we get

$\begin{split}\mathbb{E}^{S}_{k}[(\tau_{mps}-k)^{+}]&\leq
N_{\alpha}+\sum_{n\geq N_{\alpha}}\mathbb{P}^{S}_{k}(\tau_{mps}>k+n)\\\ &\leq
N_{\alpha}+\sum_{n\geq N_{\alpha}}\mathbb{P}^{S}_{k}(R_{k+n}<A_{\alpha})\\\
&=N_{\alpha}+\sum_{n\geq N_{\alpha}}\mathbb{P}^{S}_{k}(\log R_{k+n}<\log
A_{\alpha}).\end{split}$ (4.25)

Now, recall the MPS statistic

$R_{k+n}=\frac{1}{\Pi_{k+n}}\sum_{t=1}^{k+n}\pi_{t}\sum_{S\in\mathcal{S}}p_{S}\prod_{i=t}^{k+n}\frac{g_{S,i}(X_{i})}{f_{i}(X_{i})}.$

The MPS statistic is lower bounded by

$R_{k+n}\geq\frac{1}{\Pi_{k+n}}\pi_{k}\;p_{S}\prod_{i=k}^{k+n}\frac{g_{S,i}(X_{i})}{f_{i}(X_{i})}.$

Taking logarithm on both sides we get

$\begin{split}\log(R_{k+n})&\geq|\log\Pi_{k+n}|+\log(\pi_{k})+\log(p_{S})+\sum_{i=k}^{n}Z_{i}.\end{split}$
(4.26)

Using (4.26) we can bound the probability in (4.25) for $n\geq N_{\alpha}$,

$\begin{split}\mathbb{P}^{S}_{k}&(\log R_{k+n}<\log A_{\alpha})\\\
\leq&\;\mathbb{P}^{S}_{k}\left(|\log\Pi_{k+n}|+\log(p_{S})+\sum_{i=k}^{n}Z_{i}<\log(A_{\alpha}/\pi_{k})\right)\\\
=&\;\mathbb{P}^{S}_{k}\left(\frac{1}{n}\sum_{i=k}^{n}Z_{i}+\frac{|\log\Pi_{k+n}|}{n}+\frac{\log(p_{S})}{n}<\frac{\log(A_{\alpha}/\pi_{k})}{n}\right)\\\
\leq&\;\mathbb{P}^{S}_{k}\left(\frac{1}{n}\sum_{i=k}^{n}Z_{i}+\frac{|\log\Pi_{k+n}|}{n}+\frac{\log(p_{S})}{n}<I_{S}+d-\epsilon\right)\\\
=&\;\mathbb{P}^{S}_{k}\left(\frac{1}{n}\sum_{i=k}^{n}Z_{i}<I_{S}+d-\frac{|\log\Pi_{k+n}|}{n}-\frac{\log(p_{S})}{n}-\epsilon\right).\end{split}$
(4.27)

Now select $\alpha$ small enough so that for every $n\geq N_{\alpha}$

$\begin{split}\Big{|}d-\frac{|\log\Pi_{k+n}|}{n}\Big{|}&<\frac{\epsilon}{4},\\\
\Big{|}\frac{\log(\pi_{k}p_{S})}{n}\Big{|}&<\frac{\epsilon}{4}.\end{split}$

Specifically, select $\alpha$ small enough such that the statements in the
above display are true for all $n$ satisfying

$n\geq
1+\Bigl{\lfloor}\frac{\log(A_{\alpha})}{I_{S}+d-\epsilon}\Bigr{\rfloor}.$

This ensures that the chosen large $\alpha$ is not a function of the index
$k$. This gives us

$\begin{split}\mathbb{P}^{S}_{k}&(\log R_{k+n}<\log A_{\alpha})\\\
&\leq\;\mathbb{P}^{S}_{k}\left(\frac{1}{n}\sum_{i=k}^{n}Z_{i}<I_{S}+d-\frac{|\log\Pi_{k+n}|}{n}-\frac{\log(\pi_{k}p_{S})}{n}-\epsilon\right)\\\
&\leq\;\mathbb{P}^{S}_{k}\left(\frac{1}{n}\sum_{i=k}^{n}Z_{i}<I_{S}-\frac{\epsilon}{2}\right).\end{split}$
(4.28)

Substituting this in (4.25) we get for $\alpha$ small enough, uniformly over
$k$,

$\begin{split}\mathbb{E}^{S}_{k}[(\tau_{mps}-k)^{+}]&\leq
N_{\alpha}+\sum_{n\geq N_{\alpha}}\mathbb{P}^{S}_{k}(\log R_{k+n}<\log
A_{\alpha})\\\ &\leq N_{\alpha}+\sum_{n\geq
N_{\alpha}}\mathbb{P}^{S}_{k}\left(\frac{1}{n}\sum_{i=k}^{n}Z_{i}<I_{S}-\frac{\epsilon}{2}\right)\\\
&\leq
N_{\alpha}+\sum_{n=1}^{\infty}\mathbb{P}^{S}_{k}\left(\Big{|}\frac{1}{n}\sum_{i=k}^{n}Z_{i}-I_{S}\Big{|}>\frac{\epsilon}{2}\right)\\\
&=N_{\alpha}+\gamma_{k}(\epsilon/2).\end{split}$ (4.29)

This give us

$\begin{split}\mathbb{E}^{S}_{\pi}&[(\tau_{mps}-\nu)^{+}]=\sum_{k=1}^{\infty}\pi_{k}\mathbb{E}^{S}_{k}[(\tau_{mps}-k)^{+}]\\\
&\leq\sum_{k=1}^{\infty}\pi_{k}N_{\alpha}+\sum_{k=1}^{\infty}\pi_{k}\gamma_{k}(\epsilon/2)\\\
&\leq\sum_{k=1}^{\infty}\pi_{k}\left(1+\frac{\log(A_{\alpha}/\pi_{k})}{I_{S}+d-\epsilon}\right)+\sum_{k=1}^{\infty}\pi_{k}\gamma_{k}(\epsilon/2)\\\
&=\frac{\log(A_{\alpha})}{I_{S}+d-\epsilon}+\text{ constant}.\end{split}$
(4.30)

The remaining term is a constant because of the assumptions made in the
theorem statement and due to Lemma 4.2. Finally,

$\begin{split}\mathbb{E}^{S}_{\pi}&[\tau_{mps}-\nu|\tau_{mps}\geq\nu]=\frac{\mathbb{E}^{S}_{\pi}[(\tau_{mps}-\nu)^{+}]}{\mathbb{P}^{S}_{\pi}(\tau_{mps}\geq\nu)}\\\
&\leq\frac{\frac{\log(A_{\alpha})}{I_{S}+d-\epsilon}+\text{
constant}}{1-\alpha}\\\
&=\frac{|\log\alpha|}{I_{S}+d-\epsilon}(1+o(1)),\quad\text{ as }\alpha\to
0.\end{split}$ (4.31)

The result now follows because $\epsilon$ can be made arbitrarily small.

The fact that setting $A=A_{\alpha}$ guarantees that the false alarm
constraint is satisfied follows from tartakovsky2019sequential.

∎

## 5\. Quickest Change Detection in Episodic Processes

In this paper, we develop models, algorithms, and theory for detecting a
change in statistically periodic processes where the period is random.
Specifically, we define a new class of stochastic processes called episodic
processes to model this dynamic behavior of periods. The class of episodic
processes is strictly larger than the class of independent and periodically
identically distributed (i.p.i.d.) processes studied in
banerjee2019minimaxoptimal and banerjee2019bayesian. We then propose
algorithms to detect a change in episodic processes and show that the
algorithms can be computed efficiently. We then show that the algorithms are
asymptotically optimal for well-defined problem formulations. We investigate
both Bayesian and minimax problem formulations. Finally, we discuss how the
developed algorithms can be applied to detect a change in waveform patterns.
All the results in the paper are formulated within the framework of quickest
change detection. We refer the readers to Veeravalli and Banerjee  (2013);
Poor and Hadjiliadis  (2009); Tartakovsky et al.  (2014) for a review of the
existing literature.

### 5.1. Model for Statistical Regularity

An episodic process is characterized through a discrete integer-valued random
variable $T$ with a mass function $p_{T}$, and a family of multivariate
densities $\\{f_{e,t}\\}$, $e,t\in\mathbb{N}$, called an episodic family of
densities.

######  Definition 5.1.

An episodic family of densities $\\{f_{e,t}\\}$ is indexed by an episode index
$e$ and episode length index $t$, with $e,t\in\mathbb{N}$. It is a collection
of multivariate densities such that for each $e\in\mathbb{N}$, the density
$f_{e,t}$ is a density of $t$ variables:

$f_{e,t}(x_{1},x_{2},\dots,x_{t}).$

We now define the concept of an episodic process.

######  Definition 5.2.

An episodic process is a stochastic process $\\{X_{n}\\}$ with segments
(called episodes)

$\begin{split}(X_{1},\dots,X_{T_{1}}),&\quad\text{episode $1$ of length
}T_{1},\\\ (X_{T_{1}+1},\dots,X_{T_{1}+T_{2}}),&\quad\text{episode $2$ of
length }T_{2},\\\ \small\vdots&\\\
(X_{\sum_{i=1}^{k-1}T_{i}+1},\dots,X_{\sum_{i=1}^{k}T_{i}}),&\quad\text{episode
$k$ of length }T_{k},\\\ \small\vdots\end{split}$ (5.1)

generated as follows. The sequence $\\{T_{k}\\}$ is generated as an i.i.d.
sequence with the mass function $p_{T}$, and each episode is generated
independently using an episodic family of densities:

$(X_{\sum_{i=1}^{k-1}T_{i}+1},\dots,X_{\sum_{i=1}^{k}T_{i}})\sim
f_{k,T_{k}},\quad k=1,2,\dots.$

Here $f_{k,T_{k}}$ is the episodic density with $e=k$ and $t=T_{k}$. We say
that we have a $\left(p_{T},\\{f_{e,t}\\}\right)$-episodic process.

When the random variable $T$ is identically equal to a constant, $T\equiv t$,
the episodic densities satisfy

$f_{i,t}=f_{j,t},\quad\forall i,j\in\mathbb{N},$

and each episodic density $f_{e,t}$ is a product density, then an episodic
process reduces to an i.p.i.d. process studied in banerjee2019minimaxoptimal
and banerjee2019bayesian. For $T\equiv 1$, we get an i.i.d. process.

######  Definition 5.3.

An episodic process is called regular if episodes of equal lengths are
identically distributed: for any fixed $t\in\mathbb{N}$,

$f_{i,t}=f_{j,t}=f_{t},\quad\forall i,j\in\mathbb{N}.$

A regular episodic process is called strongly regular if the episodic
densities are product densities:

$f_{t}(x_{1},x_{2},\dots,x_{t})=\prod_{i=1}^{t}f_{t}^{(i)}(x_{i}).$

Thus, an i.p.i.d. process is a strongly regular episodic process in which the
episode lengths are constant. More generally, conditioned on the realizations
of the episode lengths $\\{T_{k}\\}$, a strongly regular episodic process is a
sequence of independent random variables.

Example Let $\theta(s)$ be a function defined on $[0,1]$ and $\\{V_{k}\\}$ be
a sequence of i.i.d. random variables. For each positive integer $T$, define

$X_{k}=\theta\left(\frac{k}{T}\right)+V_{k},\quad\text{for }k=1,2,\dots,T.$
(5.2)

Let $f_{t}$ be the density of $(X_{1},\dots,X_{T})$ when $T=t$ in (5.2) and
let $T$ be randomly generated with a mass function $p_{T}$. Then, the pair
$(p_{T},\\{f_{t}\\})$ defines a strongly regular episodic process. We call an
episodic process of this type as a waveform process. In the ECG application,
the function $\theta(s)$ can be interpreted as the average normal ECG waveform
normalized to the interval $[0,1]$, and $(X_{1},\dots,X_{T})$ can be seen as
the measured noisy ECG signal of length $T$ during a single heartbeat. The
problem of arrhythmia detection can be posed as the problem of detecting a
change in the waveform $\theta(s)$.

### 5.2. Conditional Change Point Model For Episodic Processes

In this section, we propose a conditional change point model for strongly
regular episodic processes. Change point models and algorithms for more
general episodic processes can be developed following the development here. In
the rest of the paper, for simplicity, we refer to a strongly regular episodic
process as simply an episodic process.

We recall that a (strongly regular) episodic process is completely
charaterized by the episode length law $p_{T}$ and the multivariate episodic
densities $\\{f_{t}\\}$, $t\in\mathbb{N}$, where $f_{t}$ is the joint
(product) density of variables in an episode of length $t$:

$f_{t}(x_{1},x_{2},\dots,x_{t})=\prod_{i=1}^{t}f_{t}^{(i)}(x_{i}).$ (5.3)

We assume that in the normal regime, the data is modeled as a
$(p_{T},\\{f_{t}\\})$–episodic process. At some point in time $\nu$, due to
some event or an anomaly, the distribution of the process changes and the new
law becomes $(p_{T},\\{g_{t}\\})$, where $\\{g_{t}\\},t\in\mathbb{N}$, is
another family of episodic joint product densities:

$g_{t}(x_{1},x_{2},\dots,x_{t})=\prod_{i=1}^{t}g_{t}^{(i)}(x_{i}).$ (5.4)

To be precise, let

$\mathcal{T}=(T_{1},T_{2},\cdots)$ (5.5)

collect the realizations of the episode lengths. Let $f(x|n,\mathcal{T})$ be
the density of the random variable $X_{n}$ given the realizations
$\mathcal{T}$ when the law of the process is $(p_{T},\\{f_{t}\\})$. Also, let
$g(x|n,\mathcal{T})$ be the density of the random variable $X_{n}$ given the
realizations $\mathcal{T}$ when the law of the process is
$(p_{T},\\{g_{t}\\})$. Then, the change point model we assume is given $\nu$
and $\mathcal{T}$,

$X_{n}\;\sim\;\begin{cases}f(x|n,\mathcal{T}),\quad\quad\text{for }n<\nu\\\
g(x|n,\mathcal{T}),\quad\quad\text{for }n\geq\nu.\end{cases}$ (5.6)

The objective is to detect this change in distribution as quickly as possible,
subject to a constraint on the rate of false alarms.

### 5.3. Stochastic Optimization Problem Formulations for Change Detection

Let $\mathbb{P}_{\nu,\mathcal{T}}$ denote the probability measure under which
the change point occurs at time $\nu$ and the realizations of episode lengths
are $\mathcal{T}$, and let $\mathbb{E}_{\nu,\mathcal{T}}$ be the corresponding
expectation. We use $\mathbb{E}_{\infty,\mathcal{T}}$ to denote the
expectation when there is no change point. To detect the change, we seek a
stopping time $N$ for the process $\\{X_{n}\\}$ to minimizes the detection
delay $N-\nu$ while avoiding frequent false alarms. We investigate two
different classes of problem formulations: Bayesian and Minimax.

### 5.4. Bayesian Formulation

For a Bayesian analysis, we assume that the change point is a random variable
with prior distribution

$\pi_{k}=\mathbb{P}(\nu=k).$

We also define the average probability measure

$\mathbb{P}_{\pi,\mathcal{T}}=\sum_{k=1}^{\infty}\pi_{k}\mathbb{P}_{k,\mathcal{T}},$

with $\mathbb{E}_{\pi,\mathcal{T}}$ being the corresponding expectation. We
seek a stopping time for the process $\\{X_{n}\\}$ to solve the following
modification of Shiryaev’s problem for every $m$ Shiryaev  (1963):

$\begin{split}\inf_{N}&\;\;\;\mathbb{E}_{\pi,\mathcal{T}}[(N-\nu)^{m}|N\geq\nu]\\\
\text{subj.
to}&\;\;\;\;\mathbb{P}_{\pi,\mathcal{T}}(N<\nu)\leq\alpha.\end{split}$ (5.7)

Here $\alpha\in[0,1]$ is a constraint on the probability of a false alarm. We
refer to (5.7) as a modification because of the extra conditioning on the
realizations of the episode lengths $\mathcal{T}$. Also, note that we are
seeking a time $N$ so that all the moments of the detection delay are
optimized. We emphasize that while the lengths of the episodes are random and
are realizations of a random variable $T$ with the mass function $p_{T}$, in
the optimization problems above, we seek a solution that is optimal for every
realization $\mathcal{T}$. For the same reason, the stopping time $N$ is
adapted to the knowledge of these realizations. In practice, this can be
achieved by acquiring the lengths of the episodes (or estimating them) just
before the episodes start. We will revisit this issue in the numerical results
section.

#### 5.4.1. Minimax Formulations

In the minimax settings, we assume that the change point is an unknown
constant $\nu$ and seek a stopping time $N$ so as to solve the following
problem which is a modified version of the formulation of Pollak Pollak
(1985):

$\begin{split}\inf_{N}&\;\;\;\sup_{\nu\geq
1}\;\mathbb{E}_{\nu,\mathcal{T}}[N-\nu|N\geq\nu]\\\ \text{subj.
to}&\;\;\;\;\mathbb{E}_{\infty,\mathcal{T}}[N]\geq\beta,\end{split}$ (5.8)

where $\beta$ is a given constraint on the mean time to a false alarm. We
follow the classical approach of seeking at the same time a solution to the
related problem of Lorden Lorden  (1971):

$\begin{split}\inf_{N}&\;\;\;\;\sup_{\nu\geq
1}\;\text{ess}\sup\mathbb{E}_{\nu,\mathcal{T}}[(N-\nu)^{+}|X_{1},\cdots,X_{\nu-1}]\\\
\text{subj.
to}&\;\;\;\;\mathbb{E}_{\infty,\mathcal{T}}[N]\geq\beta,\end{split}$ (5.9)

where $\text{ess}\sup$ is used to denote the supremum of the random variable
$\mathbb{E}_{\nu,\mathcal{T}}[N-\nu|X_{1},\cdots,X_{\nu-1}]$ outside a set of
measure zero.

### 5.5. Algorithms for Change Detection in Episodic Processes

We now discuss algorithms for detecting a change in an episodic process. We
discuss three algorithms: one Bayesian and two non-Bayesian.

#### 5.5.1. A Bayesian Algorithm

Define the a posteriori probability that the change has already occurred given
all the available observations:

$p_{n}=\mathbb{P}_{\pi,\mathcal{T}}(\nu\leq n|X_{1},\cdots,X_{n}),\text{ for
}n\geq 1.$ (5.10)

Our Bayesian algorithm or stopping rule is to stop the first time this
probability is above a pre-designed threshold $A$:

$N_{s}=\min\\{n\geq 1:p_{n}>A\\}.$ (5.11)

It is customary in the literature to refer to an a posteriori probability-
based change detection rule as the Shiryaev stopping rule Tartakovsky and
Veeravalli (2005); tartakovsky2017asymptotic. To emphasize the fact that we
are computing the statistic for a new class of stochastic processes, we call
the statistic the episodic-Shiryaev statistic and the stopping rule the
episodic-Shiryaev algorithm.

In the following lemma, it is proved that the episodic-Shiryaev statistic
$p_{n}$ for episodic processes can be computed recursively for geometric
priors. Furthermore, we only need a finite amount of memory when the episode
length variable $T$ is bounded. Note that without the boundedness assumption
on $T$, we need potentially infinite amounts of memory to compute the
statistic.

######  Lemma 5.1.

Let the prior be geometrically distributed with parameter $\rho$:

$\pi_{k}=\mathbb{P}(\nu=k)=(1-\rho)^{k-1}\rho.$

The episodic-Shiryaev statistic $p_{n}$ in (5.10) can be recursively computed
using the following equations: $p_{0}=0$ and for $n\geq 1$, we have

$p_{n}=\frac{\tilde{p}_{n-1}\;g(X_{n}|n,\mathcal{T})}{\tilde{p}_{n-1}\;g(X_{n}|n,\mathcal{T})+(1-\tilde{p}_{n-1})f(X_{n}|n,\mathcal{T})},$
(5.12)

where $\tilde{p}_{n-1}=p_{n-1}+(1-p_{n-1})\rho$. Furthermore, if $T$ is a
bounded random variable, then the statistic can be computed using a finite
amount of memory.

#### 5.5.2. Non-Bayesian Algorithms

We now propose a maximum likelihood test statistic to detect the change. We
compute the sequence of statistics

$W_{n}=\max_{1\leq k\leq
n}\sum_{i=k}^{n}\log\frac{g(X_{i}|i,\mathcal{T})}{f(X_{i}|i,\mathcal{T})}$
(5.13)

and raise an alarm as soon as the statistic is above a threshold:

$N_{c}=\inf\\{n\geq 1:W_{n}>A\\}.$ (5.14)

We call this algorithm the episodic-cumulative sum (CUSUM) algorithm. In the
next lemma, it is proved that the episodic-CUSUM statistic $W_{n}$ can also be
computed recursively. Again, we only need a finite amount of memory when the
episode length variable $T$ is bounded.

######  Lemma 5.2.

The statistic sequence $\\{W_{n}\\}$ can be recursively computed as

$W_{n}=W_{n-1}^{+}+\log\frac{g(X_{n}|n,\mathcal{T})}{f(X_{n}|n,\mathcal{T})},$
(5.15)

where $(x)^{+}=\max\\{x,0\\}$. Further, if $T$ is a bounded random variable,
then the above statistic can be computed using a finite amount of memory.

In a non-Bayesian setting, we can also use the episodic-Shiryaev-Roberts (SR)
statistic:

$R_{n}=(1+R_{n-1})\frac{g(X_{n}|n,\mathcal{T})}{f(X_{n}|n,\mathcal{T})}$

which can be obtained from the Shiryaev statistic by setting the geometric
parameter $\rho=0$.

### 5.6. Asymptotic Optimality of the Proposed Algorithms

Define for $t\in\mathbb{N}$,

$I_{t}=\frac{1}{t}\sum_{i=1}^{t}D(g_{t}^{(i)}\;\|\;f_{t}^{(i)}),$ (5.16)

where $D(g_{t}^{(i)}\;\|\;f_{t}^{(i)})$ is the Kullback-Leibler divergence
between the densities $g_{t}^{(i)}$ and $f_{t}^{(i)}$ appearing in (5.4) and
(5.3). Also, define

$I_{avg}=\sum_{t}I_{t}\;p_{T}(t).$ (5.17)

We first prove that the episodic-Shiryaev algorithm is asymptotically optimal
for the Bayesian formulation, under geometric prior and for each integer
$m>0$, as $\alpha\to 0$.

######  Theorem 5.1.

Let the information number $I_{avg}$ as defined in (5.17) satisfy
$0<I_{avg}<\infty$. Setting $A=1-\alpha$ in (5.11) ensures that

$\mathbb{P}_{\pi,\mathcal{T}}(N_{s}<\nu)\leq\alpha.$

Furthermore, for every $m>0$, as $\alpha\to 0$,

$\begin{split}\mathbb{E}_{\pi,\mathcal{T}}\left[(N_{s}-\nu)^{m}|N_{s}\geq\nu\right]&\sim\left(\frac{|\log\alpha|}{I_{avg}+|\log(1-\rho)|}\right)^{m}\\\
&\sim\inf_{N\in\mathbf{C}_{\alpha}}\mathbb{E}_{\pi,\mathcal{T}}\left[(N-\nu)^{m}|N\geq\nu\right],\end{split}$
(5.18)

where
$\mathbf{C}_{\alpha}=\\{N:\mathbb{P}_{\pi,\mathcal{T}}(N<\nu)\leq\alpha\\}$
and we use $a(\alpha)\sim b(\alpha)$ as $\alpha\to 0$ to denote that
$\frac{a(\alpha)}{b(\alpha)}\to 1$ as $\alpha\to 0$.

In the minimax settings, we have the following optimality result.

######  Theorem 5.2.

Let $Z_{i}=\log\frac{g(X_{i}|i,\mathcal{T})}{f(X_{i}|i,\mathcal{T})}$ be the
log likelihood ratio at time $i$. Let the information number $I_{avg}$ as
defined in (5.17) satisfy $0<I_{avg}<\infty$. If

$\begin{split}\lim_{n\to\infty}\sup_{\nu\geq
1}\;\mathbb{P}_{\nu,\mathcal{T}}\left(\max_{t\leq
n}\sum_{i=\nu}^{\nu+t}Z_{i}\geq
I_{avg}(1+\delta)n\right)&=0,\quad\forall\delta>0,\\\
\lim_{n\to\infty}\sup_{k\geq\nu\geq
1}\mathbb{P}_{\nu,\mathcal{T}}\left(\frac{1}{n}\sum_{i=k}^{k+n}Z_{i}\leq
I_{avg}-\delta\right)&=0,\quad\forall\delta>0.\end{split}$ (5.19)

Then, with $A=\log\beta$ in (5.14) we have
$\mathbb{E}_{\infty,\mathcal{T}}[N_{c}]\geq\beta,$ and as $\beta\to\infty$,

$\begin{split}\sup_{\nu\geq
1}\mathbb{E}_{\nu,\mathcal{T}}\left[(N_{c}-\nu)|N_{c}\geq\nu\right]&\sim\frac{\log\beta}{I_{avg}}\\\
&\sim\inf_{N\in\mathbf{D}_{\beta}}\sup_{\nu\geq
1}\mathbb{E}_{\nu,\mathcal{T}}\left[(N-\nu)|N\geq\nu\right],\end{split}$
(5.20)

where
$\mathbf{D}_{\beta}=\\{N:\mathbb{E}_{\infty,\mathcal{T}}[N]\geq\beta\\}$.
Furthermore, the above statement remains valid if we use the modified Lorden’s
delay metric (5.9) in place of the Pollak’s metric (5.8).

The conditions in (5.19) are satisfied, for example, when the processes are
i.p.i.d. banerjee2019bayesian, banerjee2019minimaxoptimal .

## ACKNOWLEDGEMENTS

We thank the Editor, the Associate Editor and the referees for their
constructive suggestions and comments. The work of Taposh Banerjee was
supported in part by the CCDC Army Research Laboratory under W911NF1820295, in
part by the Cloud Technology Endowed Professorship IV, and in part by the
National Science Foundation under grant 1917164.

## References

  * Banerjee et al. (2011) Banerjee, T., Sharma, V., Kavitha, V., and Jayaprakasam, A. (2011). Generalized Analysis of a Distributed Energy Efficient Algorithm for Change Detection, IEEE Transactions on Wireless Communication 10: 91–101.
  * Banerjee and Veeravalli (2012a) Banerjee, T. and Veeravalli, V. V. (2012a). Data-Efficient Quickest Change Detection with On-Off Observation Control, Sequential Analysis 31: 40–77.
  * Banerjee and Veeravalli (2012b) Banerjee, T. and Veeravalli, V. V. (2012b). Energy-Efficient Quickest Change Detection in Sensor Networks, in Proceedings of IEEE Statistical Signal Processing Workshop (SSP), AUG 5–8, Ann Arbor, MI, USA.
  * Banerjee and Veeravalli (2013a) Banerjee, T. and Veeravalli, V. V. (2013a). Data-Efficient Quickest Change Detection in Minimax Settings, IEEE Transactions on Information Theory 59: 6917–6931.
  * Banerjee and Veeravalli (2013b) Banerjee, T. and Veeravalli, V. V. (2013b). Data-Efficient Quickest Change Detection in Distributed and Multichannel Systems, in Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP) , MAY 26–31, Vancouver, Canada.
  * Banerjee and Veeravalli (2014a) Banerjee, T. and Veeravalli, V. V. (2014a). Data-Efficient Quickest Change Detection, in Modern Statistical Methodologies in the Cutting Edge of Science, N. Mukhopadhyay, eds., Sri Lankan Journal of Applied Statistics, pp. 183–208.
  * Banerjee and Veeravalli (2014b) Banerjee, T. and Veeravalli, V. V. (2014b). Data-Efficient Quickest Change Detection with Unknown Post-Change Distribution, in Proceedings of IEEE International Symposium on Information Theory (ISIT), JUN 29–JUL 4, Honolulu, USA.
  * Banerjee and Veeravalli (2015) Banerjee, T. and Veeravalli, V. V. (2015). Data-efficient quickest change detection in sensor networks.” IEEE Transactions on Signal Processing 63: 3727-3735
  * Banerjee et al. (2018a) Banerjee, T., Whipps, G., Gurram, P., and Tarokh, V. (2018a) Sequential event detection using multimodal data in nonstationary environments. In 2018 21st International Conference on Information Fusion (FUSION) (pp. 1940-1947).
  * Banerjee et al. (2018b) . Banerjee, T., Whipps, G., Gurram, P. and Tarokh, V., (2018b), Cyclostationary statistical models and algorithms for anomaly detection using multi-modal data. In 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP) (pp. 126-130).
  * Banerjee et al. (2019a) Banerjee, T, Stephen A., Kay M. T., Ba, D., and Tarokh, V. Sequential detection of regime changes in neural data. in Processings of International IEEE/EMBS Conference on Neural Engineering (NER), pp. 139-142. IEEE, 2019.
  * Banerjee et al. (2019b) Banerjee, T., Gurram, P. and Whipps, G., 2019, Quickest detection of deviations from periodic statistical behavior. In Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 5351-5355).
  * Banerjee et al. (2019c) Banerjee, T., Gurram, P. and Whipps, G., 2019, Bayesian quickest detection of changes in statistically periodic processes. In 2019 IEEE International Symposium on Information Theory (ISIT) (pp. 2204-2208). .
  * Banerjee et al. (2019d) Banerjee, T., Gurram, P. and Whipps, G., (2019) A sequential detection theory for statistically periodic random processes. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (pp. 290-297).
  * Banerjee et al. (2021) Banerjee, T., Gurram, P. and Whipps, G.T., (2021). A Bayesian theory of change detection in statistically periodic random processes. IEEE Transactions on Information Theory, 67(4), pp.2562-2580.
  * Chen et al. (2015) Chen, Y. C., Banerjee, T., Dominguez-Garcia, A. D., and Veeravalli, V. V. (2015). Quickest line outage detection and identification. IEEE Transactions on Power Systems, 31(1): 749-758.
  * Gardner et al. (2006) Gardner, W.A., Napolitano, A. and Paura, L., (2006). Cyclostationarity: Half a century of research. Signal processing, 86(4), pp.639-697.
  * Goldberger et al. (2000) Goldberger, A.L., Amaral, L.A., Glass, L., Hausdorff, J.M., Ivanov, P.C., Mark, R.G., Mietus, J.E., Moody, G.B., Peng, C.K. and Stanley, H.E., (2000). PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals. Circulation, 101(23), pp.e215-e220.
  * Lai (1998) Lai, T. L. (1998). Information Bounds and Quick Detection of Parameter Changes in Stochastic Systems, IEEE Transactions on Information Theory 44: 2917–2929.
  * Lorden (1971) Lorden, G. (1971). Procedures for Reacting to a Change in Distribution, Annals of Mathematical Statistics 42: 1897–1908.
  * Mei (2005) Mei, Y. (2005). Information Bounds and Quickest Change Detection in Decentralized Decision Systems, IEEE Transactions on Information Theory 51: 2669–2681.
  * Mei (2010) Mei, Y. (2010). Efficient Scalable Schemes for Monitoring a Large Number of Data Streams, Biometrika 97: 419–433.
  * Mei (2011) Mei, Y. (2011). Quickest Detection in Censoring Sensor Networks, in Proceedings of IEEE International Symposium on Information Theory (ISIT), JUL 31–AUG 5, Saint-Petersburg, Russia.
  * Moustakides (1986) Moustakides, G. V. (1986). Optimal Stopping Times for Detecting Changes in Distributions, Annals of Statistics 14: 1379–1387.
  * Page (1954) Page, E. S. (1954). Continuous Inspection Schemes, Biometrika 41: 100–115.
  * Pollak (1985) Pollak, M. (1985). Optimal Detection of a Change in Distribution, Annals of Statistics 13: 206–227.
  * Poor and Hadjiliadis (2009) Poor, H. V. and Hadjiliadis, O. (2009). Quickest Detection, Cambridge: Cambridge University Press.
  * Premkumar and Kumar (2008) Premkumar, K. and Kumar, A. (2008). Optimal Sleep/Wake Scheduling for Quickest Intrusion Detection using Sensor Networks, in Proceedings of IEEE Conference on Computer Communications (INFOCOM), APR 15–17, Phoenix, AZ, USA.
  * Shiryaev (1963) Shiryaev, A. N. (1963). On Optimal Methods in Quickest Detection Problems, Theory of Probability and Its Applications 8: 22–46.
  * Siegmund (1985) Siegmund, D. (1985). Sequential Analysis: Tests and Confidence Intervals, New York: Springer.
  * Tagaras (1998) Tagaras, G.. (1998). A Survey of Recent Developments in the Design of Adaptive Control Charts, Journal of quality technology 30: 212–231.
  * Tartakovsky et al. (2014) Tartakovsky, A. G., Nikiforov, I. V., and Basseville, M. (2014). Sequential Analysis: Hypothesis Testing and Change-Point Detection, Statistics, Boca Raton: CRC.
  * Tartakovsky and Veeravalli (2002) Tartakovsky, A. G. and Veeravalli, V. V. (2002). An Efficient Sequential Procedure for Detecting Changes in Multichannel and Distributed systems, in Proceedings of IEEE International Conference on Information Fusion (ICIF), JUL 8–11, Annapolis, MD, USA.
  * Tartakovsky and Veeravalli (2005) Tartakovsky, A. G. and Veeravalli, V. V. (2005). General Asymptotic Bayesian Theory of Quickest Change Detection, Theory of Probability and Its Applications 49: 458–497.
  * Tartakovsky and Veeravalli (2008) Tartakovsky, A. G. and Veeravalli, V. V. (2008). Asymptotically Optimal Quickest Change Detection in Distributed Sensor Systems, Sequential Analysis 27: 441–475.
  * Veeravalli (2001) Veeravalli, V. V. (2001). Decentralized Quickest Change Detection, IEEE Transactions on Information Theory 47: 1657–1665.
  * Veeravalli and Banerjee (2013) Veeravalli, V. V. and Banerjee, T. (2013). Quickest Change Detection, Elsevier: E-reference Signal Processing http://arxiv.org/abs/1210.5552.
  * Vishnoi et al. (2020) Vishnoi, S.C., Nugroho, S.A., Taha, A.F., Claudel, C. and Banerjee, T., (2020), Asymmetric cell transmission model-based, ramp-connected robust traffic density estimation under bounded disturbances. In 2020 American Control Conference (ACC) (pp. 1197-1202).
  * Wald and Wolfowitz (1948) Wald, A. and Wolfowitz, J. (1948). Optimum Character of the Sequential Probability Ratio Test, Annals of Mathematical Statistics 19: 326–339.
  * Woodroofe (1982) Woodroofe, M. (1982). Nonlinear Renewal Theory in Sequential Analysis, Philadelphia: SIAM.
  * Zacharias and Sundaresan (2007) Zacharias, L. and Sundaresan, R. (2007). Decentralized Sequential Change Detection using Physical Layer Fusion, in Proceedings of IEEE International Symposium on Information Theory (ISIT), June 24–29, Nice, France.
  * Zhang et al. (2003) Zhang, Y., Shinitski, N.M., Allsop, S., Tye, K. and Ba, D., 2003. A two-dimensional seperable random field model of within and cross-trial neural spiking dynamics. Neural Computation, 15(5), pp.965-991.