# Quickest Change Detection with Post-Change Density Estimation

Yuchen Liang, and Venugopal V. Veeravalli, Y. Liang was with the ECE
Department and Coordinated Science Laboratory, University of Illinois at
Urbana-Champaign; he is now with the ECE Department, The Ohio State
University; email<EMAIL_ADDRESS>V. Veeravalli is with the ECE
Department and Coordinated Science Laboratory, University of Illinois at
Urbana-Champaign; email<EMAIL_ADDRESS>work was supported in part by
the US National Science Foundation under grant ECCS-2033900. This work is
based in part on the paper presented at the 2023 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP) [1]

###### Abstract

The problem of quickest change detection in a sequence of independent
observations is considered. The pre-change distribution is assumed to be
known, while the post-change distribution is unknown. Two tests based on post-
change density estimation are developed for this problem, the window-limited
non-parametric generalized likelihood ratio (NGLR) CuSum test and the non-
parametric window-limited adaptive (NWLA) CuSum test. Both tests do not assume
any knowledge of the post-change distribution, except that the post-change
density satisfies certain smoothness conditions that allows for efficient non-
parametric estimation. Also, they do not require any pre-collected post-change
training samples. Under certain convergence conditions on the density
estimator, it is shown that both tests are first-order asymptotically optimal,
as the false alarm rate goes to zero. The analysis is validated through
numerical results, where both tests are compared with baseline tests that have
distributional knowledge.

###### Index Terms:

Quickest change detection (QCD), non-parametric statistics, (kernel) density
estimation, sequential methods.

##  I Introduction

The problem of quickest change detection (QCD) is of fundamental importance in
mathematical statistics (see, e.g., [2, 3] for an overview). Given a sequence
of observations whose distribution changes at some unknown change-point, the
goal is to detect the change in distribution as quickly as possible after it
occurs, while controlling the false alarm rate. In classical formulations of
the QCD problem, it is assumed that the pre- and post-change distributions are
known, and that the observations are independent and identically distributed
(i.i.d.) in the pre- and post-change regimes. However, in many practical
situations, while it is reasonable to assume that we can accurately estimate
the pre-change distribution, the post-change distribution is rarely completely
known.

There have been extensive efforts to address pre- and/or post-change
distributional uncertainty in QCD problems. In the case where both
distributions are not fully known, one approach is to assume that the
distributions are parametrized by a (low-dimensional) parameter that comes
from a pre-defined parameter set, and to employ a generalized likelihood ratio
(GLR) approach for detection. This approach was first introduced in [4] and
later analyzed in more detail in [5]. In particular, in [5], it is assumed
that the pre-change distribution is known and that the post-change
distribution comes from a parametric family, with the parameter being finite-
dimensional. A window-limited GLR test is proposed, which is shown to be
asymptotically optimal under certain smoothness conditions. This work has
recently been extended to non-stationary post-change settings [6]. For the
setting considered in [5], a window-limited adaptive approach to constructing
a QCD test was developed in recent work [7]. This adaptive test is also shown
to achieve first-order asymptotic optimality [7]. In this paper, one of the
test constructions for the case where the post-change is completely unknown is
based on extending techniques introduced in [7].

We assume complete knowledge of the pre-change distribution, while not making
any parametric assumptions about the post-change distribution. There has been
prior work along these lines. One approach is to replace the log-likelihood
ratio by some other useful statistic for distinguishing between distributions
in constructing tests. Examples of this approach include the use of kernel
M-statistics [8, 9], one-class SVMs [10], nearest neighbors [11, 12], and
Geometric Entropy Minimization [13, 14]. In [8], a test is proposed that
compares the kernel maximum mean discrepancy (MMD) within a window to a given
threshold. A way to set the threshold is also proposed that meets the false
alarm rate asymptotically [8]. Another approach is to estimate the log-
likelihood ratio and thus the CuSum test statistic through a pre-collected
training dataset. This include direct kernel estimation [15] and, more
recently, neural network estimation [16]. However, the tests proposed in
[8]–[16] lack explicit performance guarantees on the detection delay.

Our contributions are as follows:

  1. 1.

We propose a window-limited non-parametric generalized likelihood ratio (NGLR)
CuSum test and a non-parametric window-limited adaptive (NWLA) CuSum test,
both of which do not assume any knowledge of the post-change distribution
(except that the post-change density satisfies certain smoothness conditions
that allows for efficient non-parametric estimation), and do not require any
post-change training data.

  2. 2.

We characterize a generic class of density estimators that enable detection.

  3. 3.

For both tests, we provide a way to set the test threshold to meet false alarm
constraints (asymptotically).

  4. 4.

We show that both proposed tests are first-order asymptotically optimal with
the selected thresholds, as the false alarm rate goes to zero.

  5. 5.

We validate our analysis through numerical results, in which we compare both
tests with baseline tests that have distributional knowledge.

The rest of the paper is structured as follows. In Section II, we describe
some properties required of the density estimators for asymptotically optimal
QCD. In Section III, we propose the NGLR-CuSum test and analyze its
theoretical performance. In Section IV, we study the performance of the NWLA-
CuSum test. Both tests are analyzed under the assumption that the post-change
distribution is completely unknown. In Section V, we present numerical results
that validate the theoretical analysis. In Section VI, we provide some
concluding remarks.

A preliminary version of the results in this paper for the NGLR-CuSum test
appeared in [1].

##  II Density Estimators for Quickest Detection

Let $X_{1},X_{2},\dots\in\mathbb{R}^{d}$ be i.i.d. observations drawn from an
unknown distribution, with probability density function (or _density_) $p$
with respect to some dominating measure $\mu$, and let $\mathrm{supp}(p)$ be
the support of $p$. Let $\mathrm{E}_{p}$ and $\mathrm{V}_{p}$ denote,
respectively, the expectation and variance operator on the sequence of
observations, when the density corresponding to each observation is $p$. For
two densities $p$ and $q$ on $\mathbb{R}^{d}$ with respect to $\mu$, the
Kullback-Leibler (KL) divergence is defined as:

$D(p||q):=\int_{\mathrm{supp}(p)}\log(p(x)/q(x))p(x)d\mu(x).$

Define $X^{[k,n]}:=X_{k},\dots,X_{n}$. Let $\widehat{p}^{n,k}_{-i}$ be a
density on $\mathbb{R}^{d}$ with respect to $\mu$ that is estimated using
$X^{[k,n]}_{-i}:=X_{k},\dots,X_{i-1},X_{i+1},\dots,X_{n}$, where the subscript
$-i$ represents that $X_{i}$, with $k\leq i\leq n$, is the observation that is
left out from $X^{[k,n]}$. We refer to $\widehat{p}^{n,k}_{-i}$ as a leave-
one-out (LOO) estimator. Note that $\widehat{p}^{n,k}_{-i}$ and $X_{i}$ are
independent for each $1\leq k\leq i\leq n$.

With some possible abuse of notation, we also define

$\widehat{p}^{w}_{n}:=\widehat{p}^{n,n-w}_{-n}$

to be the LOO estimate of $p$ obtained from the past $w$ i.i.d. samples from
$p$.

Suppose that, for large enough $w$, there exist constants
$0<\beta_{1},C_{1},C_{2}<\infty$ and $0<\beta_{2}<2$ (that depend only on the
density $p$ and the estimation procedure) such that the KL loss [17] of the
density estimator satisfies

$\text{KL-
loss}(\widehat{p}^{w}_{n}):=\mathrm{E}_{p}\left[D(p||\widehat{p}^{w}_{n})\right]\leq\frac{C_{1}}{w^{\beta_{1}}}$
(1)

where the KL divergence and the expectation operator $\mathrm{E}_{p}$ are
taken over the randomness of $X_{n}$ and $\widehat{p}^{w}_{n}$, respectively.
Also, the second moment satisfies

$\mathrm{E}_{p}\left[\left(\log\frac{p(X_{n})}{\widehat{p}^{w}_{n}(X_{n})}\right)^{2}\right]\leq\frac{C_{2}}{w^{\beta_{2}}}.$
(2)

Here the expectation operator $\mathrm{E}_{p}$ is taken over the randomness of
both $X_{n}$ and $\widehat{p}^{w}_{n}$. Recall that $X_{n}$ is independent of
$\widehat{p}^{w}_{n}$.

Similar assumptions to (1) and (2) are imposed for general
$\widehat{p}^{n,k}_{-i}$ as follows. When $n-k$ is large enough, for each
$k\leq i\leq n$,

$\text{KL-
loss}(\widehat{p}^{n,k}_{-i})=\mathrm{E}_{p}\left[D(p||\widehat{p}^{n,k}_{-i})\right]\leq\frac{C_{1}}{(n-k)^{\beta_{1}}}$
(3)

and

$\mathrm{E}_{p}\left[\left(\frac{1}{(n-k+1)}\sum_{i=k}^{n}\log\frac{p(X_{i})}{\widehat{p}^{n,k}_{-i}(X_{i})}\right)^{2}\right]\leq\frac{C_{2}}{(n-k+1)^{\beta_{2}}}.$
(4)

A typical loss measure for a density estimator is the mean-integrated squared
error (MISE), defined as (see, e.g., [18, Chap. 2])

$\displaystyle\mathrm{MISE}(p,\widehat{p}^{w}_{n})$
$\displaystyle=\mathrm{E}_{p}\left[\int(\widehat{p}^{w}_{n}(x_{n})-p(x_{n}))^{2}d\mu(x_{n})\right]=\mathrm{E}_{p}\left[\left\lVert\widehat{p}^{w}_{n}-p\right\rVert_{2}^{2}\right].$
(5)

The following lemma connects the MISE measure with the bounds in (1)–(4). The
proof is given in the Appendix.

######  Lemma II.1.

Suppose that there exist $\overline{\zeta},\underline{\zeta}$ such that

$0<\underline{\zeta}\leq
p(x),\widehat{p}^{w}_{n}(x)\leq\overline{\zeta}<\infty,~{}\forall
x\in\mathrm{supp}(p).$ (6)

If the estimator achieves

$\mathrm{MISE}(p,\widehat{p}^{w}_{n})\leq\frac{C_{3}}{w^{\beta_{3}}},$ (7)

for all $w$ large enough and for some constants $0<\beta_{3},C_{3}<\infty$,
then (1)-(4) are satisfied with

$C_{1}=\frac{C_{3}}{\underline{\zeta}},\quad
C_{2}=\frac{\overline{\zeta}rC_{3}}{\underline{\zeta}^{2}},\quad\beta_{1}=\beta_{2}=\beta_{3}$

where

$r:=\left(\frac{\log(\underline{\zeta}/\overline{\zeta})}{(\underline{\zeta}/\overline{\zeta})-1}\right)^{2}.$
(8)

In the following, for any positive functions $g(w),h(w)$, the notation
$h(w)=O(g(w))$ means that $\frac{h(w)}{g(w)}\xrightarrow{w\to\infty}L<\infty$,
and $h(w)=\Omega(g(w))$ means that
$\frac{h(w)}{g(w)}\xrightarrow{w\to\infty}L>0$.

######  Corollary II.1.1.

Suppose that (6) is satisfied with

$\overline{\zeta}=\overline{\zeta}_{w}=O(w^{\overline{\beta}}),\quad\underline{\zeta}=\underline{\zeta}_{w}=\Omega(w^{-\underline{\beta}})$

such that

$\underline{\beta}<\beta_{3}/2,\quad\overline{\beta}<\beta_{3}-2\underline{\beta}.$

Suppose that the estimator still achieves (7). Then, (1)–(4) are still
satisfied, with

$\beta_{1}=\beta_{3}-\underline{\beta},\quad\beta_{2}=\beta_{3}-2\underline{\beta}-\overline{\beta}-\varrho$

where $\varrho>0$ is a small constant such that $\beta_{2}$ is still positive.

The proof of this corollary is given in the Appendix.

An example of a density estimator that satisfies (1)–(4) (under condition (6)
and when the density satisfies some smoothness condition) is the _kernel_
density estimator (KDE).

######  Example II.1 (Kernel Density Estimator (KDE)).

Suppose $d=1$ and the dominating measure $\mu$ is the Lebesgue measure on
$\mathbb{R}$. Given observations $X_{1},\dots,X_{w}$, the kernel density
estimator (KDE) is defined as

$\widehat{p}^{w}_{n}(x_{n})=\frac{1}{wh}\sum_{j=n-w}^{n-1}K\left(\frac{x_{n}-X_{j}}{h}\right)$
(9)

where $K(\cdot)\geq 0$ is a kernel function and $h>0$ is a smoothing
parameter. Define the $\gamma$-Hölder density class as

${\cal H}_{\gamma}:=\left\\{p:\int p(x)dx=1,\exists
L>0,\left|p^{(\ell)}(x_{1})-p^{(\ell)}(x_{2})\right|\leq
L\left|x_{1}-x_{2}\right|^{\gamma-\ell},~{}\forall
x_{1},x_{2}\in\mathrm{supp}(p)\right\\}.$

Here $\gamma>0$ and $\ell=\left\lfloor\gamma\right\rfloor$. Further, if the
kernel function $K(\cdot)$ satisfies

$\int K(u)du=1,\quad\int u^{j}K(u)du=0,~{}j=1,\ldots,\ell.$ (10)

Then, as shown in [19], with a properly chosen $h=h^{w}$, the KDE satisfies

$\sup_{p\in{\cal
H}_{\gamma}}\mathrm{MISE}(p,\widehat{p}^{w}_{n})=O(w^{-\frac{2\gamma}{2\gamma+1}}).$

Therefore, if the condition (6) is further satisfied, from Lemma II.1,
conditions (1)–(4) are satisfied with

$\beta_{1}=\beta_{2}=\frac{2\gamma}{2\gamma+1}.$ (11)

For the case where $\mu$ is the Lebesgue measure on $\mathbb{R}^{d}$, a
product kernel can be used to estimate the density, and the corresponding KDE
is

$\widehat{p}^{w}_{n}(\bm{x}_{n})=\frac{1}{w\prod_{i=1}^{d}h^{(i)}}\sum_{j=n-w}^{n-1}\prod_{i=1}^{d}K\left(\frac{x_{n}^{(i)}-X_{j}^{(i)}}{h^{(i)}}\right)$

where $x^{(i)},~{}i=1,\dots,d$ is the $i$-th element of a vector
$\bm{x}\in\mathbb{R}^{d}$, and $\bm{h}$ is a vector for smoothing parameter.
With a properly chosen $\bm{h}$, it can be shown that [20]:

$\sup_{p\in{\cal
H}_{\gamma}}\mathrm{MISE}(p,\widehat{p}^{w}_{n})=O(w^{-\frac{2\gamma}{2\gamma+d}}).$

Therefore, if the condition (6) is further satisfied, we have

$\beta_{1}=\beta_{2}=\frac{2\gamma}{2\gamma+d}.$ (12)

We note that the actual choices of $\beta_{1}$ and $\beta_{2}$ do not affect
the first-order asymptotic optimality results given in Thm III.3 and Thm IV.6.

##  III QCD with NGLR-CuSum Test

Let $X_{1},X_{2},\dots,X_{n},\dots\in\mathbb{R}^{d}$ be a sequence of
independent random variables (or vectors), and let $\nu$ be a change-point.
Assume that $X_{1},\dots,X_{\nu-1}$ all have density $p_{0}$ with respect to
some dominating measure $\mu$. Furthermore, assume that
$X_{\nu},X_{\nu+1},\dots$ have densities $p_{1}$ also with respect to $\mu$.
Here $p_{0}$ is assumed to be completely known. Regarding $p_{1}$, we only
assume that (3) and (4) are satisfied. Let $({\cal F}_{n})_{n\geq 0}$ be the
filtration, with ${\cal F}_{0}=\\{\Omega,\varnothing\\}$ and ${\cal
F}_{n}=\sigma\left\\{X_{\ell},1\leq\ell\leq n\right\\}$ being the sigma-
algebra generated by the set of $n$ observations $X_{1},\dots,X_{n}$.
Furthermore, let ${\cal F}_{\infty}=\sigma(X_{1},X_{2},\dots)$.

Let $\mathbb{P}_{\nu}$ denote the probability measure on the entire sequence
of observations when the change-point is $\nu$, and let $\mathbb{E}_{\nu}$
denote the corresponding expectation. The change-time $\nu$ is assumed to be
unknown but deterministic. The problem is to detect the change quickly, while
controlling the false alarm rate. Let $\tau$ be a stopping time [21] defined
on the observation sequence associated with the detection rule, i.e. $\tau$ is
the time at which we stop taking observations and declare that the change has
occurred.

We employ standard notations as follows:

$\displaystyle o(x)~{}\text{as}~{}x\to x_{0}~{}\text{for a function $h(x)\geq
0$ such that}~{}\limsup_{x\to x_{0}}\left|\frac{h(x)}{x}\right|=0$
$\displaystyle\omega(x)~{}\text{as}~{}x\to x_{0}~{}\text{for a function
$h(x)\geq 0$ such that}~{}\liminf_{x\to
x_{0}}\left|\frac{h(x)}{x}\right|=\infty$ $\displaystyle
O(x)~{}\text{as}~{}x\to x_{0}~{}\text{for a function $h(x)\geq 0$ such
that}~{}\limsup_{x\to x_{0}}\left|\frac{h(x)}{x}\right|<\infty$
$\displaystyle\Theta(x)~{}\text{as}~{}x\to x_{0}~{}\text{for a function
$h(x)\geq 0$ such that}~{}\lim_{x\to
x_{0}}\left|\frac{h(x)}{x}\right|=L\in(0,\infty)$

and $A_{\alpha}\sim B_{\alpha}$ is equivalent to
$A_{\alpha}=B_{\alpha}(1+o(1))$. If not explicitly specified, $x\to x_{0}$
refers to $\alpha\to 0$ or $b\to\infty$.

###  III-A QCD Problem Formulation and Classical Results

When $p_{1}$ is known, Lorden [4] proposed solving the following optimization
problem to find the best stopping time $\tau$:

$\inf_{\tau\in\mathcal{C}_{\alpha}}\mathrm{WADD}\left(\tau\right)$ (13)

where

$\mathrm{WADD}\left(\tau\right):=\sup_{\nu\geq
1}\operatorname*{ess\,sup}\mathbb{E}_{\nu}\left[\left(\tau-\nu+1\right)^{+}|{\cal
F}_{\nu-1}\right]$ (14)

characterizes the worst-case delay, and the constraint set is

$\mathcal{C}_{\alpha}:=\left\\{\tau:\mathrm{FAR}\left(\tau\right)\leq\alpha\right\\}$
(15)

with
$\mathrm{FAR}\left(\tau\right):=\frac{1}{\mathbb{E}_{\infty}\left[\tau\right]}$,
which guarantees that the false alarm rate of the algorithm does not exceed
$\alpha$. Here, $\mathbb{E}_{\infty}\left[\cdot\right]$ is the expectation
operator when the change never happens, and $(\cdot)^{+}:=\max\\{0,\cdot\\}$.

Lorden also showed that Page’s Cumulative Sum (CuSum) algorithm [22] whose
test statistic is given by:

$W(n)=\max_{1\leq k\leq
n}\sum_{i=k}^{n}\log\frac{p_{1}(X_{i})}{p_{0}(X_{i})}=\left(W(n-1)\right)^{+}+\log\frac{p_{1}(X_{n})}{p_{0}(X_{n})}$

solves the problem in (13) asymptotically as $\alpha\to 0$. The CuSum stopping
rule is given by:

$\tau_{\text{Page}}\left(b\right):=\inf\\{n:W(n)\geq b\\}.$ (16)

It was shown by Moustakides [23] that the CuSum test is exactly optimal for
the problem in (13) with some threshold $b_{\alpha}$ that meets the false
alarm constraint exactly, where $b_{\alpha}\sim\left|\log\alpha\right|$. Thus,
we have the first-order asymptotic approximation as:

$\inf_{\tau\in\mathcal{C}_{\alpha}}\mathrm{WADD}\left(\tau\right)=\mathrm{WADD}\left(\tau_{\text{Page}}\left(b_{\alpha}\right)\right)\sim\frac{\left|\log\alpha\right|}{I}$
(17)

as $\alpha\to 0$. Here we define

$I:=D(p_{1}||p_{0}).$

When the post-change distribution has parametric uncertainties, Lai [5]
generalized this performance guarantee with the following assumptions. Let
$\theta\in\Theta$ be the post-change parameter, and denote the post-change
density as $p_{1}^{\theta}$. Define $\mathbb{P}^{\theta}_{\nu}$ and
$\mathbb{E}^{\theta}_{\nu}$ to be the probability and expectation operator on
the sequence, respectively, when the true post-change density is
$p_{1}^{\theta}$. For fixed $\theta\in\Theta$, define the worst-case average
detection delay as:

$\mathrm{WADD}^{\theta}\left(\tau\right):=\sup_{\nu\geq
1}\operatorname*{ess\,sup}\mathbb{E}_{\nu}^{\theta}\left[\left(\tau-\nu+1\right)^{+}|{\cal
F}_{\nu-1}\right].$ (18)

Under parametric uncertainty, the goal is to find a test that belongs to
$\mathcal{C}_{\alpha}$ (see (15) and achieves

$\inf_{\tau\in\mathcal{C}_{\alpha}}\mathrm{WADD}^{\theta}\left(\tau\right)$
(19)

for every $\theta\in\Theta$.

Define $I^{\theta}:=D(p_{1}^{\theta}||p_{0})$. Suppose that $p_{0}$ and
$p_{1}^{\theta}$ satisfy

$\sup_{\nu\geq 1}\mathbb{P}_{\nu}^{\theta}\left\\{\max_{t\leq
n}\sum_{i=\nu}^{\nu+t}\log\frac{p_{1}^{\theta}(X_{i})}{p_{0}(X_{i})}\geq(1+\delta)nI^{\theta}\right\\}\xrightarrow{n\to\infty}0$
(20)

for any $\delta>0$, and

$\sup_{t\geq\nu}\mathbb{P}_{\nu}^{\theta}\left\\{\sum_{i=t}^{t+n}\log\frac{p_{1}^{\theta}(X_{i})}{p_{0}(X_{i})}\leq(1-\delta)nI^{\theta}\right\\}\xrightarrow{n\to\infty}0$
(21)

for any $\delta\in(0,1)$. Also, suppose that the window size $m_{\alpha}$
satisfies

$\liminf m_{\alpha}/\left|\log\alpha\right|>\frac{1}{I^{\theta}}\quad\text{
and }\log m_{\alpha}=o(\left|\log\alpha\right|).$

Then, under some smoothness conditions [5], the window-limited GLR-CuSum test:

$\tilde{\tau}_{\text{GLR}}\left(b\right):=\inf\left\\{n\geq
1:\max_{(n-m_{\alpha})^{+}<k\leq{n}}\sup_{\theta\in\Theta}\sum_{i=k}^{n}\log\frac{p_{1}^{\theta}(X_{i})}{p_{0}(X_{i})}\geq
b\right\\}$ (22)

with test threshold $b_{\alpha}=\left|\log\alpha\right|(1+o(1))$ solves the
problem in (19) asymptotically as $\alpha\to 0$, for every $\theta\in\Theta$.
The asymptotic performance is

$\inf_{\tau\in\mathcal{C}_{\alpha}}\mathrm{WADD}^{\theta}\left(\tau\right)\sim\mathrm{WADD}^{\theta}\left(\tilde{\tau}_{\text{GLR}}\left(b_{\alpha}\right)\right)\sim\frac{\left|\log\alpha\right|}{I^{\theta}}.$
(23)

###  III-B Non-parametric GLR CuSum Test

For the case when $p_{1}$ is unknown, we define the non-parametric GLR
statistic as

$\widehat{Z}^{n,k}_{i}=\log\frac{\widehat{p}^{n,k}_{-i}(X_{i})}{p_{0}(X_{i})},\
\forall k\leq i\leq n.$ (24)

We remind readers of the definition of $\widehat{p}^{n,k}_{-i}$ from Section
II. The non-parametric generalized likelihood ratio (NGLR) CuSum stopping rule
is defined as

$\widehat{\tau}(b):=\inf\left\\{n>1:\max_{(n-m_{b})^{+}<k\leq
n-1}\sum_{i=k}^{n}\widehat{Z}^{n,k}_{i}\geq b\right\\}.$ (25)

Here the window size $m_{b}$ is designed to satisfy

$\liminf m_{b}/b\geq\frac{\eta}{I}$ (26)

where $\eta>1$ is an arbitrary constant.

In Lemma III.1, we show that $\widehat{\tau}$ with a properly chosen density
estimator and threshold $b=b_{\alpha}$ satisfies the false alarm constraint
asymptotically in (15). In Lemma III.2, we establish an asymptotic upper bound
on $\mathrm{WADD}\left(\widehat{\tau}(b)\right)$. The proofs of the lemmas are
given in the Appendix. Finally, in Theorem III.3, we combine the lemmas and
establish the first-order asymptotic optimality of the NGLR-CuSum test.

######  Lemma III.1.

Suppose that the estimator is chosen such that $\exists~{}\varsigma>0$,

$\mathbb{E}_{\infty}\left[\max_{(k,n):k\leq n\leq
k+m_{b}}\prod_{i=k}^{n}\frac{\widehat{p}^{n,k}_{-i}(X_{i})}{p_{0}(X_{i})}\right]\leq
b^{\varsigma}$ (27)

for any large enough $b$. Let $b_{\alpha}$ satisfy

$b_{\alpha}-\varsigma\log b_{\alpha}=\left|\log\alpha\right|+\log 8.$ (28)

Then,

$\mathbb{E}_{\infty}\left[\widehat{\tau}(b_{\alpha})\right]\geq\alpha^{-1}(1+o(1)).$

We will elaborate on condition (27) in Section V-A. Intuitively, this
condition is satisfied when the density estimator converges to the true
density fast enough ($\mathbb{P}_{\infty}$-almost surely). Since the pre-
change distribution is known, we can numerically verify condition (27) with
the chosen window size and density estimator.

######  Lemma III.2.

Suppose $b$ is large enough such that condition (26) holds. Suppose that (3)
and (4) hold. Further, suppose (21) holds for the true log-likelihood ratio.
Then,

$\mathrm{WADD}\left(\widehat{\tau}(b)\right)\leq\frac{b}{I}(1+o(1)),~{}\text{as
}b\to\infty.$

######  Theorem III.3.

Suppose that conditions (20) and (21) hold for the true log-likelihood ratio,
and suppose that the window size satisfies (26). Suppose that (27) is
satisfied for the chosen estimator. Let $b_{\alpha}$ be so selected according
to equation (28) such that
$\mathrm{FAR}\left(\widehat{\tau}(b_{\alpha})\right)\leq\alpha(1+o(1))$, where
also $b_{\alpha}=\left|\log\alpha\right|(1+o(1))$. Then
$\widehat{\tau}(b_{\alpha})$ solves the problem in (13) asymptotically as
$\alpha\to 0$, and

$\inf_{\tau\in\mathcal{C}_{\alpha}}\mathrm{WADD}\left(\tau\right)\sim\mathrm{WADD}\left(\widehat{\tau}\left(b_{\alpha}\right)\right)\sim\frac{\left|\log\alpha\right|}{I}.$

###### Proof of Theorem III.3.

The asymptotic lower bound on the delay follows from (21) using [5, Thm. 1].
The asymptotic optimality of $\widehat{\tau}(b_{\alpha})$ follows from Lemma
III.1 and Lemma III.2. ∎

##  IV QCD with NWLA CuSum Test

Define the non-parametric window-limited adaptively-estimated log-likelihood
ratio as

$\widehat{Z}^{w}_{n}=\log\frac{\widehat{p}_{n}^{w}(X_{n})}{p_{0}(X_{n})},\
\forall n>w$ (29)

where $\widehat{p}_{n}^{w}$ is the output of the density estimator given input
$X^{[n-w,n-1]}$. Note that $\widehat{Z}^{w}_{n}$ is independent of ${\cal
F}_{n-w-1}$. Define the non-parametric window-limited adaptive (NWLA) CuSum
statistic as:

$\overline{W}^{w}(n)=\left(\overline{W}^{w}(n-1)\right)^{+}+\widehat{Z}^{w}_{n},\quad
n>w$ (30)

and $\overline{W}^{w}(1)=\dots=\overline{W}^{w}(w)=0$. The corresponding
stopping rule is

$\overline{\tau}(b):=\inf\left\\{n>w:\overline{W}^{w}(n)\geq b\right\\}.$ (31)

Here $b=b_{\alpha}>0$ is a threshold depending on the false alarm rate
$\alpha$. We omit the dependency of $\overline{W}$ on $w$ for brevity.

The following observations regarding condition (1) are useful for the analysis
in this section. If the estimated density $p=p_{1}$, equation (1) is
equivalent to

$\widehat{I}:=\mathbb{E}_{1}\left[\widehat{Z}^{w}_{n}\right]\geq
I-\frac{C_{1}}{w^{\beta_{1}}},\quad n>w$ (32)

when $w$ is large. This guarantees that $\widehat{I}>0$ for all sufficiently
large $w$’s.

In Lemma IV.1, we show that $\overline{\tau}$ with a properly chosen threshold
$b_{\alpha}$ satisfies the false alarm constraint in (15). In Lemma IV.5, we
establish an asymptotic upper bound on
$\mathrm{WADD}\left(\overline{\tau}(b_{\alpha})\right)$. Finally, in Theorem
IV.6, we combine the lemmas and establish the first-order asymptotic
optimality of the NWLA-CuSum test. It should be mentioned that the results in
this section are similar to those in [7], in which a window-limited adaptive
CuSum test is studied for the case where there is parametric uncertainty in
the post-change regime. However, the results in [7] are clearly not applicable
to the non-parametric setting studied here.

The proofs of Lemmas IV.1, IV.2, and IV.5 are given in the Appendix.

######  Lemma IV.1.

For any $w>0$,

$\mathbb{E}_{\infty}\left[\overline{\tau}(b)\right]\geq e^{b}.$

Thus, $\overline{\tau}(\overline{b}_{\alpha})\in\mathcal{C}_{\alpha}$ if
$\overline{b}_{\alpha}=\left|\log\alpha\right|$.

Before introducing the main lemma on the delay, we first introduce three
helping lemmas below.

######  Lemma IV.2.

For any change-point $\nu\geq 1$ and $b>0$,

$\operatorname*{ess\,sup}\mathbb{E}_{\nu}\left[(\overline{\tau}(b)-\nu+1)^{+}|{\cal
F}_{\nu-1}\right]\leq\mathbb{E}_{1}\left[\overline{\tau}(b)\right].$

######  Lemma IV.3.

Define

$U_{n}=U_{n-1}+\widehat{Z}^{w}_{n},\quad\forall n>w$

with $U_{1}=\dots=U_{w}=0$. Also define the stopping time

$\tau_{u}(b):=\inf\\{n>w:U_{n}\geq b\\}.$ (33)

Then, $\tau_{u}(b)\geq\overline{\tau}(b)$ on
$\left\\{\tau_{u}(b)<\infty\right\\}$ for any $b>0$.

###### Proof of Lemma IV.3.

The proof is similar to [7, Lemma 5]. Note that $U_{w}=0=\overline{W}(w)$. For
any $k\geq w$, if $U_{k}\leq\overline{W}(k)$, then

$U_{k+1}=U_{k}+\widehat{Z}^{w}_{k}\leq\overline{W}(k)+\widehat{Z}^{w}_{k}\leq\left(\overline{W}(k)\right)^{+}+\widehat{Z}^{w}_{k}=\overline{W}(k+1)\quad
a.s.$

Thus by induction, $\tau_{u}(b)\geq\overline{\tau}(b)$ on
$\left\\{\tau_{u}(b)<\infty\right\\}$. ∎

######  Lemma IV.4.

If $\widehat{I}>0$, then the $\tau_{u}$ defined in (33) satisfies
$\tau_{u}<\infty$ almost surely under $\mathbb{P}_{1}$.

###### Proof of Lemma IV.4.

First, for any $k>0$,

$\sum_{i=w+1}^{w+wk}\widehat{Z}^{w}_{i}=\sum_{j=1}^{w}\sum_{\ell=1}^{k}\widehat{Z}^{w}_{w\ell+j}$

and given $j$, $\sum_{\ell=1}^{k}\widehat{Z}^{w}_{w\ell+j}$ is a sum of i.i.d.
random variables under $\mathbb{P}_{1}$. Define

$\tau_{u,j}:=w\cdot\inf\left\\{k\geq
1:\sum_{\ell=1}^{k}\widehat{Z}^{w}_{w\ell+j}\geq b/w\right\\}+j.$

Note that $\tau_{u,j}$ is the boundary crossing time of a sum of i.i.d. random
variables with mean $\widehat{I}$. Now, if
$\widehat{I}=\mathbb{E}_{1}\left[\widehat{Z}^{w}_{i}\right]>0,~{}\forall i>w$,
then by [24, Prop. 8.21],
$\mathbb{E}_{1}\left[\tau_{u,j}\right]<\infty,~{}\forall j=1,\dots,w$.
Finally, since

$\forall j,~{}\sum_{\ell=1}^{k}\widehat{Z}^{w}_{w\ell+j}\geq
b/w\implies\sum_{i=w+1}^{w+wk}\widehat{Z}^{w}_{i}\geq b,$

we have that $\tau_{u}\leq\max_{j=1,\dots,w}\tau_{u,j}$ almost surely under
$\mathbb{P}_{1}$, and thus $\mathbb{E}_{1}\left[\tau_{u}\right]<\infty$. ∎

Now, using the lemmas above, we can upper bound the delay of the NWLA-CuSum
test.

######  Lemma IV.5.

Suppose that $w$ is sufficiently large such that $\widehat{I}>0$. Suppose
further that (2) holds for the estimator. Then,

$\mathbb{E}_{1}\left[\overline{\tau}(b)\right]\leq\mathbb{E}_{1}\left[\tau_{u}(b)\right]\leq\widehat{I}^{-1}\left(b+w\widehat{I}+I+\sqrt{2}\frac{C_{2}}{\widehat{I}w^{\beta_{2}}}+\left(\frac{4C_{2}}{\widehat{I}w^{\beta_{2}}}(b+I)\right)^{\frac{1}{2}}\right)$
(34)

where $\tau_{u}(b)$ is defined in (33).

######  Theorem IV.6.

Suppose that $\overline{b}_{\alpha}=\left|\log\alpha\right|$ and the window
size $w_{\alpha}=\left|\log\alpha\right|^{\kappa}$ for some $0<\kappa<1$.
Then, $\overline{\tau}(\overline{b}_{\alpha})$ solves the problem in (13)
asymptotically as $\alpha\to 0$, and the delay is upper-bounded as

$\mathrm{WADD}\left(\overline{\tau}\left(\overline{b}_{\alpha}\right)\right)\leq\frac{\left|\log\alpha\right|}{I}\left(1+\Theta(\left|\log\alpha\right|^{-\rho_{\kappa}})\right),$

where

$\rho_{\kappa}=\min\left\\{\kappa\beta_{1},1-\kappa\right\\}.$ (35)

###### Proof of Theorem IV.6.

From (1) it follows that,

$\displaystyle\frac{I}{\widehat{I}}=1+\frac{I-\widehat{I}}{\widehat{I}}$
$\displaystyle\leq 1+\frac{C_{1}}{\widehat{I}w^{\beta_{1}}}$
$\displaystyle\leq
1+\frac{C_{1}}{\left(I-\frac{C_{1}}{w^{\beta_{1}}}\right)w^{\beta_{1}}}$
$\displaystyle=1+\frac{C_{1}}{Iw^{\beta_{1}}-C_{1}}.$

Given the selected $w=w_{\alpha}$, $\widehat{I}>0$ for a sufficiently small
$\alpha$. Define $r_{\alpha}:=\frac{\left|\log\alpha\right|}{I}$. From (34),
if we select $\overline{b}_{\alpha}=\left|\log\alpha\right|$ and
$w=\left|\log\alpha\right|^{\kappa}$, the scaled average delay (when $\nu=1$)
can be upper bounded as:

$\displaystyle
r_{\alpha}^{-1}\mathbb{E}_{1}\left[\overline{\tau}(\overline{b}_{\alpha})\right]\leq
r_{\alpha}^{-1}\mathbb{E}_{1}\left[\tau_{u}(\overline{b}_{\alpha})\right]$
$\displaystyle\leq\frac{I}{\widehat{I}}\left(1+\frac{\widehat{I}}{\left|\log\alpha\right|^{1-\kappa}}+\frac{I}{\left|\log\alpha\right|}+\sqrt{2}\frac{C_{2}}{\widehat{I}\left|\log\alpha\right|^{1+\kappa\beta_{2}}}+\frac{1}{\left|\log\alpha\right|}\left(\frac{4C_{2}}{\widehat{I}\left|\log\alpha\right|^{\kappa\beta_{2}}}(\left|\log\alpha\right|+I)\right)^{\frac{1}{2}}\right)$
$\displaystyle\leq
1+\frac{C_{1}}{I\left|\log\alpha\right|^{\kappa\beta_{1}}-C_{1}}+\frac{I}{\left|\log\alpha\right|^{1-\kappa}}+o\left(\frac{1}{\left|\log\alpha\right|^{1-\kappa}}\right)$
$\displaystyle=1+\Theta\left(\frac{1}{\left|\log\alpha\right|^{\rho_{\kappa}}}\right)$

Together with Lemmas IV.1–IV.4, the result on the asymptotic delay at $\nu=1$
establishes the asymptotic optimality. ∎

######  Remark.

Since $\beta_{1}<1$, we have $\rho_{\kappa}<\frac{1}{2}$ if $\kappa\in(0,1)$.
Also, from (35), to maximize $\rho_{\kappa}$, one can choose

$\rho^{*}=\max_{\kappa\in(0,1)}\rho_{\kappa},\quad\kappa^{*}=\arg\max_{\kappa\in(0,1)}\rho_{\kappa}.$

######  Example IV.1.

Let the dominating measure $\mu$ be the Lebesgue measure on $\mathbb{R}^{d}$.
Recall the definition of ${\cal H}_{\gamma}$ in Example II.1. Consider
$p_{0},p_{1}\in{\cal H}_{\gamma}$ with bounded support and non-zero density.
Consider using KDE as the estimator with some kernel that satisfies (10).
Previously we showed in (12) and Lemma II.1 that with a properly chosen
$\bm{h}$, the optimal $\beta_{1}$ and $\beta_{2}$ are
$\beta_{1}=\beta_{2}=\frac{2\gamma}{2\gamma+d}$. Therefore, in this case
$\kappa^{*}$ and $\rho^{*}$ are

$\kappa^{*}=\arg\max_{\kappa\in(0,1)}\min\left\\{\frac{2\gamma}{2\gamma+d}\kappa,1-\kappa\right\\}=\frac{2\gamma+d}{4\gamma+d},$

and

$\rho^{*}=\frac{2\gamma}{4\gamma+d}.$

##  V Numerical Results

In this section, we present some numerical results for the proposed tests.
Before presenting the main results, we first investigate from a numerical
perspective the feasibility of condition (27), which is key to Lemma III.1.

###  V-A Discussion of Condition (27)

The quantity of interest is

$Q(m):=\mathbb{E}_{\infty}\left[\max_{n=2,\dots,m}\prod_{i=1}^{n}\frac{\widehat{p}^{n,1}_{-i}(X_{i})}{p_{0}(X_{i})}\right].$
(36)

In Fig. 1, we study the numerical properties of $Q(m)$ for KDE with Gaussian
kernels. The difference $\log(Q(m))-3\log m$ is plotted against $m$ for each
$m=5,10,\dots,100$. In the plot, it is observed that

$\log(Q(m))-3\log m<0\implies Q(m)\leq m^{3}$

Therefore, with the chosen density estimator, if further the window size is
chosen such that $m_{b}\leq b^{\vartheta}(1+o(1))$ with some $\vartheta>1$,
then condition (27) is satisfied with $\varsigma=3\vartheta$.

Figure 1: $\log(Q(m))-3\log m$ versus $m$ with $Q(m)$ defined in (36). For
each value of $m$, 100000 Monte Carlo runs are performed for each
$n=2,\dots,m$, and the maximum product of likelihood ratios is averaged. The
selected pre-change distributions are $\mathcal{N}(0,1)$ (solid lines) and
$\frac{1}{3}(\mathcal{N}(-2,\frac{1}{4})+\mathcal{N}(0,\frac{1}{4})+\mathcal{N}(2,1))$
(dashed lines), with $\mathcal{N}(\mu,\sigma^{2})$ denote a Gaussian with mean
$\mu$ and $\sigma^{2}$. The KDE with Gaussian kernel is used for density
estimation, with bandwidth $h=n^{-r}$ where $r$ chosen as 0.05 (red), 0.2
(blue), and 0.4 (cyan). In both plots, it is observed that the difference
trends lower as $m$ increases, and that all simulated values are below zero.

###  V-B Performance of NGLR-CuSum Test

In Fig. 2, we study the performance of the proposed NGLR-CuSum test (defined
in (25)) through Monte Carlo (MC) simulations when the pre-change distribution
is ${\cal N}(0,1)$. The KDE (defined in (9)) with a Gaussian kernel is used to
estimate the density. The actual post-change distribution is ${\cal
N}(0.5,1)$, but this knowledge is not used in the NGLR-CuSum test. The
performance of the NGLR-CuSum test is compared against that of the following
tests:

  1. 1.

the CuSum test (in (16)), which has full knowledge of the post-change
distribution;

  2. 2.

the parametric window-limited GLR-CuSum test (in (22)), in which it is assumed
that the post-change distribution belongs to $\\{{\cal
N}(\theta,1)\\}_{\theta\neq 0}$.

The change-point is taken to be $\nu=1$.111Note that $\nu=1$ may not
necessarily be the worst-case value for the change-point for the NGLR-CuSum
test in general. However, extensive experimentation on this Gaussian mean-
change problem with different values of $\nu$ ranging from 1 to 100, with a
window-size of 100, shows that $\nu=1$ results in the largest expected delay
among all $\nu$’s considered. Different window sizes are considered, among
which the window size of 100 is sufficiently large to cover the full range of
delay. It is seen that the expected delay of the NGLR-CuSum test is close to
that of the GLR-CuSum test for all window sizes considered.

Figure 2: Comparison of operating characteristics of the NGLR-CuSum test
(solid lines) with the CuSum test (in red) and the parametric window-limited
GLR-CuSum test (dashed lines) in detecting a shift in the mean of a Gaussian.
The pre- and post-change distributions are ${\cal N}(0,1)$ and ${\cal
N}(0.5,1)$. The change-point $\nu=1$. The kernel width parameter
$h=10^{-1/5}$.

###  V-C Performance of NWLA-CuSum Test

In Fig. 3, we study the performance of the proposed NWLA-CuSum test (defined
in (31)) through Monte Carlo (MC) simulations when the pre-change distribution
is ${\cal N}(0,1)$. The KDE (defined in (9)) is used to estimate the density.
The actual post-change distribution is ${\cal N}(0.5,1)$. This knowledge is
not used in the NWLA-CuSum test. The performance of the NWLA-CuSum test is
compared against that of the following tests:

  1. 1.

the CuSum test (in (16)), which assumes full knowledge of the post-change
distribution;

  2. 2.

the parametric window-limited GLR-CuSum test (in (22)), in which it is assumed
that the post-change distribution belongs to $\\{{\cal
N}(\theta,1)\\}_{\theta\neq 0}$.;

  3. 3.

the parallel-NWLA-CuSum test, defined as

$\overline{\tau}_{\text{parallel}}(b,W_{\text{max}}):=\inf\left\\{n>1:\max_{1\leq
w\leq W_{\text{max}}}\overline{W}^{w}(n)\geq b\right\\}.$

Using a similar analysis as in Section IV, it can be shown that the parallel-
NWLA-CuSum test is also asymptotically optimal with the threshold chosen as
$b_{\alpha}=\left|\log\alpha\right|+\log W_{\text{max}}$. The change-point is
taken to be $\nu=1$, which corresponds to the worst-case expected delay for
the NWLA-CuSum test (shown in Lemma IV.2), the parallel NWLA-CuSum test, and
the CuSum test, but not necessarily for the parametric window-limited GLR-
CuSum test. Different window sizes are also considered. We note that there is
a trade-off to consider in the design of the window size for the NWLA-CuSum
test. If the window size is too small, the post-change density might not be
accurately estimated. On the other hand, if the window size is too large, the
test might wait too long before its statistic starts to grow in the post-
change regime. To address this trade-off, the parallel-NWLA-CuSum test could
be employed without specifying a pre-defined window size, albeit at the
expense of having to run more tests in parallel.

Figure 3: Comparison of operating characteristics of the NWLA-CuSum test
(solid lines) and the parallel-NWLA-CuSum test (dashed line) with the CuSum
test (in red) and the parametric window-limited GLR-CuSum test (dotted line)
in detecting a shift in the mean of a Gaussian. The pre- and post-change
distributions are ${\cal N}(0,1)$ and ${\cal N}(0.5,1)$. The change-point
$\nu=1$. The kernel width parameter $h=w^{-1/5}$, where $w$ is the window
size.

###  V-D Comparison between NGLR-CuSum Test and NWLA-CuSum Test

We now compare the performance between the NGLR-CuSum test and the parallel-
NWLA-CuSum test. First, we compare the computational complexity of both tests
if the KDE is used for density estimation. For the NGLR-CuSum test, at each
input observation $X_{n}$, for all hypothesized change-points
$k\in((n-m)^{+},n-1]$ (where $m$ is the window size), the pair-wise kernel
value $K(X_{i},X_{j})$ for each pair of $i,j\in[k,n]$ with $i\neq j$ is
calculated and a LOO kernel estimate is evaluated at each point
$X_{k},\dots,X_{n}$. Then, the LOO-estimated log-likelihood ratios at these
points are summed up and the maximum sum (over $k$) is compared to the given
threshold. Thus, the computation complexity of the NGLR-CuSum test at each
time is $\Theta((n\wedge m)^{3})$. For the parallel-NWLA-CuSum test, at each
given $X_{n}$, $K(X_{i},X_{n})$ is first calculated for each
$i\in[(n-W_{\text{max}})\vee 1,n-1]$. Then, with each possible window size
$w=1,\dots,W_{\text{max}}\wedge(n-1)$, a WLA kernel estimate is evaluated to
update the corresponding NWLA-CuSum statistic in an efficient manner. Finally,
the maximum NWLA-CuSum statistic (over $w$) is compared to the given
threshold. Therefore, the computation complexity of the parallel-NWLA-CuSum
test is $\Theta((n\wedge W_{\text{max}})^{2})$. Also note that in practice,
$W_{\text{max}}$ is usually chosen to be smaller than $m$, by comparing the
requirement of $m_{b}$ in (26) with the window condition in Thm IV.6.

In Fig. 4, we compare the numerical performance of the NGLR-CuSum test and the
parallel-NWLA-CuSum test in detecting a shift in the mean of a Gaussian. When
the window size is large enough, both tests achieve similar performance at
$\nu=1$, which corresponds to the worst-case $\nu$ for the parallel-NWLA-CuSum
test, but not necessarily for the NGLR-CuSum test.

Figure 4: Comparison of operating characteristics of the NGLR-CuSum test
(solid lines) and the parallel-NWLA-CuSum test (dashed lines) with the CuSum
test (in red) in detecting a shift in the mean of a Gaussian. The pre- and
post-change distributions are ${\cal N}(0,1)$ and ${\cal N}(0.5,1)$. The
change-point $\nu=1$. The kernel width parameters are $h=10^{-1/5}$ for the
NGLR-CuSum test, and $h=w^{-1/5}$ for the parallel-NWLA-CuSum test, where $w$
is the window size.

##  VI Conclusion

We studied a window-limited non-parametric generalized likelihood ratio (NGLR)
CuSum test and a non-parametric window-limited adaptive (NWLA) CuSum test for
QCD. Both tests do not assume any explicit knowledge of the post-change
distribution, and do not require post-change training samples ahead of time.
We characterized a generic class of density estimators that enable detection.
For both tests, we provided a way to set the test thresholds to meet false
alarm constraints, and we showed that the tests are first-order asymptotically
optimal with the selected thresholds, as the false alarm rate goes to zero. We
validated our analysis through Monte-Carlo simulations, in which we compared
both tests with baseline tests that have distributional knowledge.

## Acknowledgements

The authors would like to thank George Moustakides for helpful discussions
regarding the NWLA-CuSum test.

## References

  * [1] Y. Liang and V. V. Veeravalli, “Quickest change detection with leave-one-out density estimation,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , Rhodes Island, Greece, June 2023, pp. 1–5.
  * [2] V. V. Veeravalli and T. Banerjee, “Quickest change detection,” in _Academic press library in signal processing: Array and statistical signal processing_. Cambridge, MA: Academic Press, 2013.
  * [3] L. Xie, S. Zou, Y. Xie, and V. V. Veeravalli, “Sequential (quickest) change detection: Classical results and new directions,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 2, pp. 494–514, 2021.
  * [4] G. Lorden, “Procedures for reacting to a change in distribution,” _The Annals of Mathematical Statistics_ , vol. 42, no. 6, pp. 1897–1908, Dec. 1971\.
  * [5] T. L. Lai, “Information bounds and quick detection of parameter changes in stochastic systems,” _IEEE Transactions on Information Theory_ , vol. 44, no. 7, pp. 2917–2929, November 1998.
  * [6] Y. Liang, A. G. Tartakovsky, and V. V. Veeravalli, “Quickest change detection with non-stationary post-change observations,” _IEEE Transactions on Information Theory_ , vol. 69, no. 5, pp. 3400–3414, December 2022.
  * [7] L. Xie, G. V. Moustakides, and Y. Xie, “Window-limited cusum for sequential change detection,” _IEEE Transactions on Information Theory_ , vol. 69, no. 9, pp. 5990–6005, May 2023.
  * [8] S. Li, Y. Xie, H. Dai, and L. Song, “M-statistic for kernel change-point detection,” in _Advances in Neural Information Processing Systems_ , C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, Eds., vol. 28. Curran Associates, Inc., 2015, pp. 3366–3374.
  * [9] T. Flynn and S. Yoo, “Change detection with the kernel cumulative sum algorithm,” in _IEEE 58th Conference on Decision and Control (CDC)_ , Nice, France, 2019, pp. 6092–6099.
  * [10] F. Desobry, M. Davy, and C. Doncarli, “An online kernel change detection algorithm,” _IEEE Transactions on Signal Processing_ , vol. 53, no. 8, pp. 2961–2974, Aug 2005.
  * [11] L. Chu and H. Chen, “Sequential change-point detection for high-dimensional and non-euclidean data,” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 4498–4511, 2022.
  * [12] H. Chen, “Sequential change-point detection based on nearest neighbors,” _The Annals of Statistics_ , vol. 47, no. 3, pp. 1381–1407, June 2019.
  * [13] Y. Yilmaz, “Online nonparametric anomaly detection based on geometric entropy minimization,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 3010–3014.
  * [14] M. N. Kurt, Y. Yılmaz, and X. Wang, “Real-time nonparametric anomaly detection in high-dimensional settings,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 43, no. 7, pp. 2463–2479, 2021.
  * [15] Y. Kawahara and M. Sugiyama, “Sequential change-point detection based on direct density-ratio estimation,” _Statistical Analysis and Data Mining: The ASA Data Science Journal_ , vol. 5, no. 2, pp. 114–127, 2012. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/sam.10124
  * [16] G. V. Moustakides and K. Basioti, “Training neural networks for likelihood/density ratio estimation,” 2019. [Online]. Available: https://arxiv.org/abs/1911.00405
  * [17] P. Hall, “On Kullback-Leibler loss and density estimation,” _The Annals of Statistics_ , vol. 15, no. 4, pp. 1491–1519, 1987.
  * [18] D. W. Scott, _Multivariate Density Estimation: Theory, Practice, and Visualization_ , 2nd ed. Hoboken, NJ: John Wiley & Sons, Inc., 2015.
  * [19] A. B. Tsybakov, _Introduction to Nonparametric Estimation_. New York, NY: Springer, 2009.
  * [20] L. Wasserman, _All of Nonparametric Statistics_. New York, NY: Springer, 2006.
  * [21] P. Moulin and V. V. Veeravalli, _Statistical Inference for Engineers and Data Scientists_. Cambridge, UK: Cambridge University Press, 2018.
  * [22] E. S. Page, “Continuous inspection schemes,” _Biometrika_ , vol. 41, no. 1/2, pp. 100–115, Jun. 1954.
  * [23] G. V. Moustakides, “Optimal stopping times for detecting changes in distributions,” _Annals of Statistics_ , vol. 14, no. 4, pp. 1379–1387, Dec. 1986.
  * [24] D. Siegmund, _Sequential analysis: Tests and confidence intervals_. New York, NY: Springer, 1985.
  * [25] A. G. Tartakovsky, _Sequential Change Detection and Hypothesis Testing: General Non-i.i.d. Stochastic Models and Asymptotically Optimal Rules_ , ser. Monographs on Statistics and Applied Probability 165. Boca Raton, London, New York: Chapman & Hall/CRC Press, Taylor & Francis Group, 2020.
  * [26] S. Janson, “Renewal Theory for $M$-Dependent Variables,” _The Annals of Probability_ , vol. 11, no. 3, pp. 558–568, 1983.

###### Proof of Lemma II.1.

For brevity we write $\widehat{p}(X)=\widehat{p}^{w}_{n}(X_{n})$, and note
that $X$ is independent of $\widehat{p}$. We use the fact that
$\log{s}\leq(s-1)$ to establish an upper bound on the first moment. In
particular,

$\displaystyle\mathrm{E}_{p}\left[\log\frac{p(X)}{\widehat{p}(X)}\right]$
$\displaystyle\leq\mathrm{E}_{p}\left[\frac{p(X)}{\widehat{p}(X)}-1\right]$
$\displaystyle=\mathrm{E}_{p}\left[\int\frac{p^{2}(x)-p(x)\widehat{p}(x)}{\widehat{p}(x)}d\mu(x)\right]$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{=}}\mathrm{E}_{p}\left[\int\frac{p^{2}(x)-2p(x)\widehat{p}(x)+\widehat{p}^{2}(x)}{\widehat{p}(x)}d\mu(x)\right]$
$\displaystyle\leq\frac{1}{\underline{\zeta}}\mathrm{MISE}(p,\widehat{p})$
(37)

where $(*)$ follows by the independence between $\widehat{p}$ and $X$ and
because both $p$ and $\widehat{p}$ are densities. This establishes (1) with
$\beta_{1}=\beta_{3}$. The proof for (3) is similar, noting the independence
between $\widehat{p}^{n,k}_{-i}$ and $X_{i}$. For the second moment, note that
$(\log{s})^{2}\leq r(s-1)^{2}$ on $s\geq\underline{\zeta}/\overline{\zeta}$
with $r$ as defined in (8). Thus,

$\displaystyle\mathrm{E}_{p}\left[\left(\log\frac{p(X)}{\widehat{p}(X)}\right)^{2}\right]$
$\displaystyle\leq\mathrm{E}_{p}\left[r\left(\frac{p(X)}{\widehat{p}(X)}-1\right)^{2}\right]$
$\displaystyle=r\mathrm{E}_{p}\left[\int\frac{\left(p(x)-\widehat{p}(x)\right)^{2}}{\widehat{p}^{2}(x)}p(x)d\mu(x)\right]$
$\displaystyle\leq\frac{\overline{\zeta}r}{\underline{\zeta}^{2}}\mathrm{MISE}(p,\widehat{p})$
(38)

which shows (2) with $\beta_{2}=\beta_{3}$. Furthermore, for (4),

$\displaystyle\mathrm{E}_{p}\left[\left(\frac{1}{n-k+1}\sum_{i=k}^{n}\log\frac{p(X_{i})}{\widehat{p}^{n,k}_{-i}(X_{i})}\right)^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathrm{E}_{p}\left[\frac{1}{n-k+1}\sum_{i=k}^{n}\left(\log\frac{p(X_{i})}{\widehat{p}^{n,k}_{-i}(X_{i})}\right)^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathrm{E}_{p}\left[\left(\log\frac{p(X_{n})}{\widehat{p}^{n,k}_{-n}(X_{n})}\right)^{2}\right]$
$\displaystyle\leq\frac{\overline{\zeta}rC_{3}}{\underline{\zeta}^{2}(n-k+1)^{\beta_{3}}}.$
(39)

Here $(a)$ follows by Jensen’s inequality, and $(b)$ follows because
$\log\frac{p(X_{i})}{\widehat{p}^{n,k}_{-i}(X_{i})}$ has the same distribution
for all $i\in[k,n]$. The proof is now complete. ∎

###### Proof of Corollary II.1.1.

Following the argument in (Proof of Lemma II.1.), we have

$\mathrm{E}_{p}\left[\log\frac{p(X)}{\widehat{p}(X)}\right]=O\left(\frac{1}{\underline{\zeta}}\mathrm{MISE}(p,\widehat{p})\right)=O(w^{-(\beta_{3}-\underline{\beta})}),$

and thus the first moment results (i.e., that of $\beta_{1}$) follow
immediately for (1) and (3).

Now we turn to the second moment. From the definition of $r$,

$r=\left(\frac{\log(\overline{\zeta}/\underline{\zeta})}{1-(\underline{\zeta}/\overline{\zeta})}\right)^{2}\leq(\log(\overline{\zeta}/\underline{\zeta}))^{2}=(\overline{\beta}-\underline{\beta})^{2}(\log
w)^{2}$

Therefore, following the argument in (Proof of Lemma II.1.), we get

$\displaystyle\mathrm{E}_{p}\left[\left(\log\frac{p(X)}{\widehat{p}(X)}\right)^{2}\right]$
$\displaystyle=O\left(\frac{\overline{\zeta}r}{\underline{\zeta}^{2}}\mathrm{MISE}(p,\widehat{p})\right)$
$\displaystyle=O\left(\frac{w^{\overline{\beta}}}{w^{-2\underline{\beta}}w^{\beta_{3}}}(\log
w)^{2}\right)$
$\displaystyle=O\left(w^{-(\beta_{3}-2\underline{\beta}-\overline{\beta}-\varrho)}\right)$

where $\varrho>0$ is an arbitrarily small constant. This shows the second
moment result for (2). The second moment result for (4) is similar if we
follow the argument in (Proof of Lemma II.1.). ∎

###### Proof of Lemma III.1.

Fix $\ell>1$. For all thresholds $b>0$,

$\displaystyle\mathbb{P}_{\infty}\left\\{\ell\leq\widehat{\tau}(b)<\ell+m_{b}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\mathbb{P}_{\infty}\left\\{\exists(k,n)\text{
with }\ell\leq n<\ell+m_{b},(n-m_{b})^{+}<k\leq
n-1:\sum_{i=k}^{n}\widehat{Z}^{n,k}_{i}\geq b\right\\}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\mathbb{P}_{\infty}\left\\{\exists(k,n)\text{
with }(\ell-m_{b})^{+}<k<\ell+m_{b},k+1\leq n\leq
k+m_{b}:\sum_{i=k}^{n}\widehat{Z}^{n,k}_{i}\geq b\right\\}$
$\displaystyle=\mathbb{P}_{\infty}\left(\bigcup_{k=(\ell-
m_{b})^{+}+1}^{\ell+m_{b}-1}\left\\{\exists n\text{ with }k+1\leq n\leq
k+m_{b}:\sum_{i=k}^{n}\widehat{Z}^{n,k}_{i}\geq b\right\\}\right)$
$\displaystyle\leq\sum_{k=(\ell-
m_{b})^{+}+1}^{\ell+m_{b}-1}\mathbb{P}_{\infty}\left\\{\exists n\text{ with
}k+1\leq n\leq k+m_{b}:\sum_{i=k}^{n}\widehat{Z}^{n,k}_{i}\geq b\right\\}$
$\displaystyle\leq\sum_{k=(\ell-
m_{b})^{+}+1}^{\ell+m_{b}-1}\mathbb{P}_{\infty}\left\\{\tau_{k}(b)\leq
k+m_{b}\right\\}$ (40)

where $(i)$ follows from the definition of $\widehat{\tau}(b)$, and $(ii)$
follows because

$\ell\leq n<\ell+m_{b},~{}~{}(n-m_{b})^{+}<k\leq n-1$

implies that

$(\ell-m_{b})^{+}<k<\ell+m_{b},~{}~{}k+1\leq n\leq k+m_{b}.$

Here we define the auxiliary stopping time $\tau_{k}(b)$ for $k\geq 1$ as

$\tau_{k}(b):=\inf\left\\{n\in[k+1,k+m_{b}]:\sum_{i=k}^{n}\widehat{Z}^{n,k}_{i}\geq
b\right\\}$ (41)

and we define $\inf\emptyset:=\infty$. Now, for each $k\in[(\ell-
m_{b})^{+},\ell+m_{b})$, we have

$\displaystyle\mathbb{P}_{\infty}\left\\{k+1\leq\tau_{k}(b)\leq
k+m_{b}\right\\}$ $\displaystyle=\int\mathds{1}\\{k+1\leq\tau_{k}(b)\leq
k+m_{b}\\}d\mathbb{P}_{\infty}$
$\displaystyle=\int\mathds{1}\\{k+1\leq\tau_{k}(b)\leq
k+m_{b}\\}\prod_{i=k}^{\tau_{k}(b)}\frac{\widehat{p}^{\tau_{k}(b),k}_{-i}(x_{i})}{p_{0}(x_{i})}\prod_{i=k}^{\tau_{k}(b)}\frac{p_{0}(x_{i})}{\widehat{p}^{\tau_{k}(b),k}_{-i}(x_{i})}d\mathbb{P}_{\infty}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}e^{-b}\int\mathds{1}\\{k+1\leq\tau_{k}(b)\leq
k+m_{b}\\}\prod_{i=k}^{\tau_{k}(b)}\frac{\widehat{p}^{\tau_{k}(b),k}_{-i}(x_{i})}{p_{0}(x_{i})}d\mathbb{P}_{\infty}$
(42)

where $(iii)$ follows from the definition of $\tau_{k}(b)$.

Now,

$\displaystyle\int\mathds{1}\\{k+1\leq\tau_{k}(b)\leq
k+m_{b}\\}\prod_{i=k}^{\tau_{k}(b)}\frac{\widehat{p}^{\tau_{k}(b),k}_{-i}(x_{i})}{p_{0}(x_{i})}d\mathbb{P}_{\infty}$
$\displaystyle\leq\int\max_{n\in[k,k+m_{b}]}\prod_{i=k}^{n}\frac{\widehat{p}^{n,k}_{-i}(x_{i})}{p_{0}(x_{i})}d\mathbb{P}_{\infty}$
$\displaystyle\stackrel{{\scriptstyle(iv)}}{{\leq}}b^{\varsigma}(1+o(1))$

where $(iv)$ follows from condition (27). Combining with (Proof of Lemma
III.1.) and (Proof of Lemma III.1.), we have

$\sup_{\ell>1}\mathbb{P}_{\infty}\left\\{\ell\leq\widehat{\tau}(b)<\ell+m_{b}\right\\}\leq
2m_{b}e^{-b}b^{\varsigma}(1+o(1)),$

and by [25, Lemma 2.2(ii)],

$\mathbb{E}_{\infty}\left[\widehat{\tau}(b)\right]\geq\frac{1}{8}e^{b}b^{-\varsigma}(1+o(1)).$

Choosing $b=b_{\alpha}$ then satisfies the false alarm constraint
asymptotically. ∎

###### Proof of Lemma III.2.

Recall that $I=D(p_{1}||p_{0})$. Define a function $\delta_{b}$ such that
$\delta_{0}:=1-\eta^{-1}<1$, that $\delta_{b}\in(0,\delta_{0})$ is decreasing
in $b$, and that $\delta_{b}\searrow 0$ as $b\to\infty$. Define

$n_{b}:=\left\lfloor\frac{b}{I(1-\delta_{b})}\right\rfloor$ (43)

and thus

$n_{b}<\frac{b}{I(1-\delta_{0})}=\frac{\eta b}{I}\leq m_{b}$

when $b$ is large enough. If for now that we can get a large enough $b$ to
satisfy

$\mathbb{P}_{\nu}\left\\{\sum_{i=n}^{n+n_{b}-1}\widehat{Z}^{n+n_{b}-1,n}_{i}<b\right\\}<2\delta_{b}^{2},~{}\forall(\nu,n):n\geq\nu\geq
1.$ (44)

Then in the following, we will show by induction that

$\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell)n_{b},{\cal
F}_{\nu-1}\right\\}\leq(2\delta_{b}^{2})^{\ell},~{}\forall\nu\geq 1,k\geq\ell$
(45)

when $b$ is large enough.

We will induct on the variable $\ell$. The base case is where $\ell=1$, and we
get, $\forall k\geq 1$,

$\displaystyle\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|\widehat{\tau}(b)-\nu+1>(k-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\left.\widehat{\tau}(b)-\nu+1>kn_{b}\right|{\cal
F}_{\nu+(k-1)n_{b}-1}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\left.\sum_{i=\nu+(k-1)n_{b}}^{\nu+kn_{b}-1}\widehat{Z}^{\nu+kn_{b}-1,\nu+(k-1)n_{b}}_{i}<b\right|{\cal
F}_{\nu+(k-1)n_{b}-1}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{=}}\mathbb{P}_{\nu}\left\\{\sum_{i=\nu+(k-1)n_{b}}^{\nu+kn_{b}-1}\widehat{Z}^{\nu+kn_{b}-1,\nu+(k-1)n_{b}}_{i}<b\right\\}$
$\displaystyle\stackrel{{\scriptstyle(iv)}}{{\leq}}2\delta_{b}^{2}.$ (46)

In the series of inequalities above, $(i)$ is by definition of essential
supremum and $\widehat{\tau}(b)$, $(iii)$ follows from independence between
the event
$\Big{\\{}\sum_{i=\nu+(k-1)n_{b}}^{\nu+kn_{b}-1}\widehat{Z}^{\nu+kn_{b}-1,\nu+(k-1)n_{b}}_{i}<b\Big{\\}}$
and ${\cal F}_{\nu+(k-1)n_{b}-1}$, and $(iv)$ follows from (44). The reason
for $(ii)$ is as follows. The event $\\{\widehat{\tau}(b)-\nu+1>kn_{b}\\}$
implies that no change has been detected until time $n=kn_{b}+\nu-1$. In
particular, this means that at time $n=kn_{b}+\nu-1$,

$\max_{(\nu+kn_{b}-1-m_{b})^{+}<\kappa\leq\nu+kn_{b}-2}\sum_{i=\kappa}^{\nu+kn_{b}-1}\widehat{Z}^{\nu+kn_{b}-1,\kappa}_{i}<b.$

Now, since $n_{b}\leq m_{b}$,

$\sum_{i=\nu+(k-1)n_{b}}^{\nu+kn_{b}-1}\widehat{Z}^{\nu+kn_{b}-1,\nu+(k-1)n_{b}}_{i}\leq\max_{(\nu+kn_{b}-1-m_{b})^{+}<\kappa\leq\nu+kn_{b}-2}\sum_{i=\kappa}^{\nu+kn_{b}-1}\widehat{Z}^{\nu+kn_{b}-1,\kappa}_{i}<b.$

The induction base is thus established.

We now turn to the induction step. Suppose we have proved that

$\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell)n_{b},{\cal
F}_{\nu-1}\right\\}\leq(2\delta_{b}^{2})^{\ell},~{}\forall k\geq l.$

Then, for $k\geq\ell+1$,

$\displaystyle\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(v)}}{{=}}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b},\widehat{\tau}(b)-\nu+1>(k-1)n_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle=\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>(k-1)n_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\quad\times\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|\widehat{\tau}(b)-\nu+1>(k-1)n_{b},\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$

where $(v)$ holds because
$\\{\widehat{\tau}(b)-\nu+1>kn_{b}\\}\subseteq\\{\widehat{\tau}(b)-\nu+1>(k-1)n_{b}\\}$.
Thus,

$\displaystyle\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\leq\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>(k-1)n_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\quad\times\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|\widehat{\tau}(b)-\nu+1>(k-1)n_{b},\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(vi)}}{{\leq}}\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>(k-1)n_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\quad\times\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|{\cal
F}_{\nu+(k-1)n_{b}-1}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(vii)}}{{\leq}}\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>(k-1)n_{b}|\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\right\\}\times(2\delta_{b}^{2})$
$\displaystyle\leq(2\delta_{b}^{2})^{\ell+1}$

where $(vi)$ follows by definition of essential supremum and the fact that

$\\{\widehat{\tau}(b)-\nu+1>(k-1)n_{b},\widehat{\tau}(b)-\nu+1>(k-\ell-1)n_{b},{\cal
F}_{\nu-1}\\}\subset\\{{\cal F}_{\nu+(k-1)n_{b}-1}\\}$

and $(vii)$ follows by (Proof of Lemma III.2.). Therefore, by induction, we
get (45). In particular, letting $\ell=k$, we get

$\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|{\cal
F}_{\nu-1}\right\\}\leq(2\delta_{b}^{2})^{k},~{}\forall\nu\geq 1$

for all sufficiently large $b$’s.

Therefore, for all sufficiently large $b$’s,

$\displaystyle\sup_{\nu\geq
1}\operatorname*{ess\,sup}\mathbb{E}_{\nu}\left[n_{b}^{-1}(\widehat{\tau}(b)-\nu+1)^{+}|{\cal
F}_{\nu-1}\right]$
$\displaystyle\leq\sum_{k=1}^{\infty}\operatorname*{ess\,sup}\mathbb{P}_{\nu}\left\\{\widehat{\tau}(b)-\nu+1>kn_{b}|{\cal
F}_{\nu-1}\right\\}$
$\displaystyle\leq\sum_{k=0}^{\infty}(2\delta_{b}^{2})^{k}=\frac{1}{1-2\delta_{b}^{2}}.$

Recall the definition of WADD in (14). As $b\to\infty$, this implies that

$\mathrm{WADD}\left(\widehat{\tau}(b)\right)\leq\frac{n_{b}}{1-2\delta_{b}^{2}}\leq\frac{b}{I(1-\delta_{b})(1-2\delta_{b}^{2})}=\frac{b}{I}(1+o(1)).$

It remains to show (44). Write

$Z_{i}:=\log\frac{p_{1}(X_{i})}{p_{0}(X_{i})}.$

For any $n\geq\nu\geq 1$ and $\epsilon>0$,

$\displaystyle\mathbb{P}_{\nu}\left\\{\sum_{i=n}^{n+n_{b}-1}\widehat{Z}^{n+n_{b}-1,n}_{i}<b\right\\}$
$\displaystyle=\mathbb{P}_{\nu}\left\\{\sum_{i=n}^{n+n_{b}-1}\widehat{Z}^{n+n_{b}-1,n}_{i}<b,\sum_{i=n}^{n+n_{b}-1}Z_{i}-\widehat{Z}^{n+n_{b}-1,n}_{i}\leq\epsilon\right\\}+$
$\displaystyle\qquad\mathbb{P}_{\nu}\left\\{\sum_{i=n}^{n+n_{b}-1}\widehat{Z}^{n+n_{b}-1,t}_{i}<b,\sum_{i=n}^{n+n_{b}-1}Z_{i}-\widehat{Z}^{n+n_{b}-1,t}_{i}\geq\epsilon\right\\}$
$\displaystyle\leq\mathbb{P}_{\nu}\left\\{\sum_{i=n}^{n+n_{b}-1}Z_{i}\leq
b+\epsilon\right\\}+\mathbb{P}_{\nu}\left\\{\frac{1}{n_{b}}\sum_{i=n}^{n+n_{b}-1}\left(Z_{i}-\widehat{Z}^{n+n_{b}-1,t}_{i}\right)\geq\frac{\epsilon}{n_{b}}\right\\}$
$\displaystyle=\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}\leq
b+\epsilon\right\\}+\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}^{n_{b},1}_{i}\right)\geq\frac{\epsilon}{n_{b}}\right\\}$
(47)

where $Z_{i}$ is the true log-likelihood ratio at time $i$. Observe that the
first term increases with $\epsilon$, while the second term decreases. It is
important to choose a proper $\epsilon=\epsilon_{b}$ in order to keep both
terms small. The idea in the following is that we first choose a proper
$\epsilon=\epsilon_{b}$ by controlling the second term, and then verify that
it is small enough for the first term when $b$ becomes large.

Below, the goal is to choose $\epsilon=\epsilon_{b}$ and $\delta_{b}$ such
that

$\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}\leq\delta_{b}^{2}\quad\text{and}\quad\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}^{n_{b},1}_{i}\right)\geq\frac{\epsilon_{b}}{n_{b}}\right\\}\leq\delta_{b}^{2}$

hold simultaneously. In the following, write $\widehat{p}_{i}$ and
$\widehat{Z}_{i}$ as short-hand notations for $\widehat{p}^{n_{b},1}_{-i}$ and
$\widehat{Z}^{n_{b},1}_{-i}$, respectively. Note that
$\mathbb{E}_{1}\left[Z_{i}-\widehat{Z}_{i}\right]=\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]$.
Under the conditions for the estimator in (3) and (4), the mean and variance
of $n_{b}^{-1}\sum_{i=1}^{n_{b}}(Z_{i}-\widehat{Z}_{i})$ can be bounded as

$\displaystyle\mathbb{E}_{1}\left[\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}(Z_{i}-\widehat{Z}_{i})\right]=\mathbb{E}_{1}\left[\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\log\frac{p_{1}(X_{i})}{\widehat{p}_{i}(X_{i})}\right]\leq\frac{C_{1}}{n_{b}^{\beta_{1}}}$
$\displaystyle\mathrm{Var}_{1}\left(\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}(Z_{i}-\widehat{Z}_{i})\right)=\mathrm{Var}_{1}\left(\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\log\frac{p_{1}(X_{i})}{\widehat{p}_{i}(X_{i})}\right)\leq\frac{C_{2}}{n_{b}^{\beta_{2}}}.$
(48)

Now,

$\displaystyle\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}_{i}\right)\geq\frac{\epsilon_{b}}{n_{b}}\right\\}$
$\displaystyle\leq\mathbb{P}_{1}\left\\{\left|\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}_{i}\right)-\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]\right|\geq\frac{\epsilon_{b}}{n_{b}}-\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]\right\\}$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\mathrm{Var}_{1}\left(\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\log\frac{p_{1}(X_{i})}{\widehat{p}_{i}(X_{i})}\right)\left(\frac{\epsilon_{b}}{n_{b}}-\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]\right)^{-2}$
$\displaystyle\leq\frac{C_{2}}{n_{b}^{\beta_{2}}}\left(\frac{\epsilon_{b}}{n_{b}}-\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]\right)^{-2}$
(49)

for any
$\epsilon_{b}>n_{b}\times\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]$.
Here $(*)$ follows from Chebyshev’s inequality. Now, (Proof of Lemma III.2.)
is less than or equal to $\delta_{b}^{2}$ if

$\frac{\epsilon_{b}}{n_{b}}-\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]\geq\frac{\sqrt{C_{2}}}{\delta_{b}n_{b}^{\frac{\beta_{2}}{2}}}$

which is equivalent to

$\epsilon_{b}\geq\frac{\sqrt{C_{2}}n_{b}^{1-\beta_{2}/2}}{\delta_{b}}+n_{b}\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right].$
(50)

Consider the two terms on the right-hand-side of (50). Since
$\mathbb{E}_{1}\left[D(p_{1}||\widehat{p}_{i})\right]\leq
C_{1}n_{b}^{-\beta_{1}}$ (from (Proof of Lemma III.2.)), the second term in
(50) is no larger than $C_{1}n_{b}^{1-\beta_{1}}$. In order to choose a proper
$\epsilon_{b}$, there are three cases depending on the rate of the first term
in (50).

  * •

Case 1: $4\beta_{1}>\beta_{2}$. Let

$\epsilon_{b}=\frac{2\sqrt{C_{2}}n_{b}^{1-\beta_{2}/2}}{\delta_{b}},$ (51)

with $\delta_{b}$ as chosen below. With this $\epsilon_{b}$, the first term in
(Proof of Lemma III.2.) becomes

$\displaystyle\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}$
$\displaystyle=\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b})n_{b}I+\frac{2\sqrt{C_{2}}n_{b}^{1-\beta_{2}/2}}{\delta_{b}}\right\\}$
$\displaystyle=\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b})n_{b}I\left(1+\frac{2\sqrt{C_{2}}}{(1-\delta_{b})\delta_{b}n_{b}^{\beta_{2}/2}I}\right)\right\\}$
$\displaystyle\leq\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b})n_{b}I\left(1+\frac{2\eta\sqrt{C_{2}}}{\delta_{b}n_{b}^{\beta_{2}/2}I}\right)\right\\}$

where in the last inequality we have used the fact that
$1-\delta_{b}>\eta^{-1}$. Let

$\delta_{b}=\frac{(4\eta^{2}C_{2})^{\frac{1}{4}}}{n_{b}^{\beta_{2}/4}\sqrt{I}}\iff\frac{2\eta\sqrt{C_{2}}}{\delta_{b}n_{b}^{\beta_{2}/2}I}=\delta_{b}.$
(52)

With this chosen $\delta_{b}$,

$\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}\leq\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b}^{2})n_{b}I\right\\}.$

Assuming that (21) is true for $Z_{i}$’s, we have [5, Appendix B]

$\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b}^{2})n_{b}I\right\\}\leq\delta_{b}^{2},$

and thus

$\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}\leq\delta_{b}^{2}.$
(53)

Now, we verify that (50) holds for all large enough $b$’s. With the chosen
$\delta_{b}$ (in (52)), the first term in (50) satisfies

$\sqrt{C_{2}}\delta_{b}^{-1}n_{b}^{1-\beta_{2}/2}=\Theta(n_{b}^{1-\beta_{2}/4})=\omega(n_{b}^{1-\beta_{1}}).$

Therefore, the chosen $\epsilon_{b}$ (in (51)) satisfies (50) for all $b$’s
large enough. As a result, from (Proof of Lemma III.2.), we get

$\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}_{i}\right)\geq\frac{\epsilon_{b}}{n_{b}}\right\\}\leq\delta_{b}^{2}.$

  * •

Case 2: $4\beta_{1}<\beta_{2}$. Let

$\displaystyle\epsilon_{b}=2C_{1}n_{b}^{1-\beta_{1}},$
$\displaystyle\delta_{b}=\frac{2\eta
C_{1}}{I}n_{b}^{-\beta_{1}}\iff\frac{\eta\epsilon_{b}}{n_{b}I}=\delta_{b}.$
(54)

With this choice,

$\displaystyle\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}$
$\displaystyle=\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b})n_{b}I+2C_{1}n_{b}^{1-\beta_{1}}\right\\}$
$\displaystyle=\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b})n_{b}I\left(1+\frac{2C_{1}}{(1-\delta_{b})n_{b}^{\beta_{1}}I}\right)\right\\}$
$\displaystyle\leq\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b})n_{b}I\left(1+\frac{2\eta
C_{1}}{n_{b}^{\beta_{1}}I}\right)\right\\}$
$\displaystyle=\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b}^{2})n_{b}I\right\\}$
(55)

and thus, assuming (21) holds, we have

$\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}\leq\delta_{b}^{2}.$

Also, since

$\sqrt{C_{2}}\delta_{b}^{-1}n_{b}^{1-\beta_{2}/2}=\Theta\left(n_{b}^{1-\beta_{2}/2+\beta_{1}}\right)=o(n_{b}^{1-\beta_{1}}),$

the chosen $\epsilon_{b}$ (in (• ‣ Proof of Lemma III.2.)) satisfies (50) for
all $b$’s large enough. As a result, from (Proof of Lemma III.2.), we get

$\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}_{i}\right)\geq\frac{\epsilon_{b}}{n_{b}}\right\\}\leq\delta_{b}^{2}.$

  * •

Case 3: $4\beta_{1}=\beta_{2}$. Let $C_{3}$ be a large enough constant such
that

$C_{3}\geq\frac{I\sqrt{C_{2}}}{\eta C_{3}}+C_{1}.$ (56)

Choose

$\displaystyle\epsilon_{b}=C_{3}n_{b}^{1-\beta_{1}},$
$\displaystyle\delta_{b}=\frac{\eta
C_{3}}{I}n_{b}^{-\beta_{1}}\iff\frac{\eta\epsilon_{b}}{n_{b}I}=\delta_{b}.$
(57)

Following the same line of argument as in (• ‣ Proof of Lemma III.2.), we get

$\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}=\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<(1-\delta_{b})n_{b}I+2C_{1}n_{b}^{1-\beta_{1}}\right\\}\leq\delta_{b}^{2}.$

Also, from (56),

$\epsilon_{b}=C_{3}n_{b}^{1-\beta_{1}}\geq\frac{I\sqrt{C_{2}}}{\eta
C_{3}}n_{b}^{1-\beta_{2}/2+\beta_{1}}+C_{1}n_{b}^{1-\beta_{1}}=\frac{\sqrt{C_{2}}n_{b}^{1-\beta_{2}/2}}{\delta_{b}}+C_{1}n_{b}^{1-\beta_{1}}.$

Therefore, (50) is satisfied for the chosen $\epsilon_{b}$ (in (• ‣ Proof of
Lemma III.2.)), and from (Proof of Lemma III.2.) we get

$\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}_{i}\right)\geq\frac{\epsilon_{b}}{n_{b}}\right\\}\leq\delta_{b}^{2}.$

To sum up, in all cases, we have shown the existence of $\epsilon_{b}$ and
$\delta_{b}$ (that depend on $\beta_{1}$ and $\beta_{2}$) such that

$\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}<b+\epsilon_{b}\right\\}\leq\delta_{b}^{2}\quad\text{and}\quad\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}^{n_{b},1}_{i}\right)\geq\frac{\epsilon_{b}}{n_{b}}\right\\}\leq\delta_{b}^{2}$

hold simultaneously. Continuing (Proof of Lemma III.2.), we can write, for any
$(n,\nu)$ such that $n\geq\nu\geq 1$,

$\displaystyle\mathbb{P}_{\nu}\left\\{\sum_{i=n}^{n+n_{b}-1}\widehat{Z}^{n+n_{b}-1,n}_{i}<b\right\\}$
$\displaystyle\leq\mathbb{P}_{1}\left\\{\sum_{i=1}^{n_{b}}Z_{i}\leq
b+\epsilon_{b}\right\\}+\mathbb{P}_{1}\left\\{\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}\left(Z_{i}-\widehat{Z}^{n_{b},1}_{i}\right)\geq\frac{\epsilon_{b}}{n_{b}}\right\\}$
$\displaystyle\leq 2\delta_{b}^{2}.$

This is exactly what was required to be shown in (44). The proof is now
complete. ∎

###### Proof of Lemma IV.1.

Define the SR-like statistic

$R_{n}=(1+R_{n-1})e^{\widehat{Z}^{w}_{n}},~{}\forall n>w$

with $R_{1}=\dots=R_{w}=0$. Also define the corresponding test:

$\overline{\tau}_{R}(b):=\inf\left\\{n>w:R_{n}\geq e^{b}\right\\}.$

Note that the NWLA-CuSum statistic in (30) can be written equivalently as

$e^{\overline{W}(n)}=\max\left\\{1,e^{\overline{W}(n-1)}\right\\}e^{\widehat{Z}^{w}_{n}},\quad
n>w.$

Therefore, for $n>w$, $R_{n}>e^{\overline{W}(n)}$ and thus
$\overline{\tau}(b)\geq\overline{\tau}_{R}(b)$ on
$\\{\overline{\tau}(b)<\infty\\}$.

Now, without loss of generality assume
$\mathbb{E}_{\infty}\left[\overline{\tau}(b)\right]<\infty$; otherwise the
statement of the lemma holds trivially. This implies that
$\mathbb{E}_{\infty}\left[\overline{\tau}_{R}(b)\right]<\infty$. Observe that
$R_{n}\in{\cal F}_{n}$ and

$\mathbb{E}_{\infty}\left[R_{n}-n|{\cal
F}_{n-1}\right]=(1+R_{n-1})\mathbb{E}_{\infty}\left[e^{\widehat{Z}^{w}_{n}}|{\cal
F}_{n-1}\right]-n=R_{n-1}-(n-1),~{}\forall n>w.$

The last equality follows because $\widehat{p}^{w}_{n}$ is a density given
${\cal F}_{n-1}$. Hence $\\{R_{n}-n\\}_{n>w}$ is a $(\mathbb{P}_{\infty},{\cal
F}_{n})$-martingale. Also, for any $n>w$, since $R_{n}\in(0,e^{b})$ almost
surely on the event $\\{\overline{\tau}_{R}(b)>n\\}$, we have, for any $n>w$,

$\displaystyle\mathbb{E}_{\infty}\left[\left|(R_{n+1}-(n+1))-(R_{n}-n)\right|\Big{|}{\cal
F}_{n}\right]$
$\displaystyle=\mathbb{E}_{\infty}\left[\left|R_{n+1}-R_{n}-1\right|\Big{|}{\cal
F}_{n}\right]$ $\displaystyle\leq\mathbb{E}_{\infty}\left[R_{n+1}|{\cal
F}_{n}\right]+(R_{n}+1)$ $\displaystyle=2(R_{n}+1)$ $\displaystyle\leq
2(e^{b}+1)$

almost surely on the event $\\{\overline{\tau}_{R}(b)>n\\}$. Therefore, we can
apply the optional sampling theorem and obtain

$\mathbb{E}_{\infty}\left[R_{\overline{\tau}_{R}(b)}-\overline{\tau}_{R}(b)\right]=\mathbb{E}_{\infty}\left[R_{w+1}-(w+1)\right]=\mathbb{E}_{\infty}\left[e^{\widehat{Z}^{w}_{w+1}}\right]-(w+1)=-w,$

where $\mathbb{E}_{\infty}\left[e^{\widehat{Z}^{w}_{w+1}}\right]=1$ because
$\widehat{p}^{w}_{w+1}$ is a density given ${\cal F}_{w}$. Finally, we arrive
at

$\mathbb{E}_{\infty}\left[\overline{\tau}(b)\right]\geq\mathbb{E}_{\infty}\left[\overline{\tau}_{R}(b)\right]=w+\mathbb{E}_{\infty}\left[R_{\overline{\tau}_{R}(b)}\right]\geq
e^{b}.\qed$

###### Proof of Lemma IV.2.

The proof is similar to [7, Lemma 4]. Define a helping stopping time

$\overline{\tau}_{\nu}(b):=\inf\\{n\geq\nu+w:\overline{W}_{\nu}(n)\geq b\\}$

where

$\overline{W}_{\nu}(n)=\left(\overline{W}_{\nu}(n-1)\right)^{+}+\widehat{Z}^{w}_{n},\quad
n\geq\nu+w$

with $\overline{W}_{\nu}(n)=0,\forall n<\nu+w$. Note that
$\overline{W}(\nu+w)\geq\overline{W}_{\nu}(\nu+w)$. Now, if
$\overline{W}(k)\geq\overline{W}_{\nu}(k)$, we have

$\overline{W}(k+1)=\left(\overline{W}(k)\right)^{+}+\widehat{Z}^{w}_{k+1}\geq\left(\overline{W}_{\nu}(k)\right)^{+}+\widehat{Z}^{w}_{k+1}=\overline{W}_{\nu}(k+1)$

as long as $\overline{W}(k)<b$. Thus, by induction,

$\overline{W}(n)\geq\overline{W}_{\nu}(n),~{}\forall n\geq\nu+w$

on the event $\left\\{\overline{W}(n)<b\right\\}$, which implies that
$\overline{\tau}(b)\leq\overline{\tau}_{\nu}(b)$ almost surely under
$\mathbb{P}_{\nu}$. In the remainder of the proof, we omit “$(b)$” in the
descriptions of the stopping times for notational brevity.

Since $\overline{\tau}-\nu+1=w+\left(\overline{\tau}-\nu-w+1\right)\leq
w+(\overline{\tau}-\nu-w+1)^{+}$, we have

$(\overline{\tau}-\nu+1)^{+}\leq
w+(\overline{\tau}-\nu-w+1)^{+}\quad\mathbb{P}_{\nu}\text{--}a.s.$

Thus,

$\displaystyle\mathbb{E}_{\nu}\left[(\overline{\tau}-\nu+1)^{+}|{\cal
F}_{\nu-1}\right]$ $\displaystyle\leq
w+\mathbb{E}_{\nu}\left[(\overline{\tau}-\nu-w+1)^{+}|{\cal F}_{\nu-1}\right]$
$\displaystyle=w+\mathbb{E}_{\nu}\left[\mathbb{E}_{\nu}\left[(\overline{\tau}-\nu-w+1)^{+}|X_{\nu},\dots,X_{\nu+w-1},{\cal
F}_{\nu-1}\right]|{\cal F}_{\nu-1}\right]$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}w+\mathbb{E}_{\nu}\left[\mathbb{E}_{\nu}\left[(\overline{\tau}_{\nu}-\nu-w+1)^{+}|X_{\nu},\dots,X_{\nu+w-1},{\cal
F}_{\nu-1}\right]|{\cal F}_{\nu-1}\right]$
$\displaystyle\stackrel{{\scriptstyle(**)}}{{=}}w+\mathbb{E}_{\nu}\left[\mathbb{E}_{\nu}\left[\overline{\tau}_{\nu}-\nu-w+1|X_{\nu},\dots,X_{\nu+w-1},{\cal
F}_{\nu-1}\right]|{\cal F}_{\nu-1}\right]$

where $(*)$ holds because $\overline{\tau}\leq\overline{\tau}_{\nu}$ almost
surely (under $\mathbb{P}_{\nu}$), and $(**)$ holds because
$\overline{\tau}_{\nu}\geq\nu+w-1\geq 0$ almost surely (under
$\mathbb{P}_{\nu}$).

Now, $\forall\nu\geq 1$, given the information of $X_{\nu},\dots,X_{\nu+w-1}$,
the event $\left\\{\overline{\tau}_{\nu}\geq\nu+w\right\\}$ is independent of
${\cal F}_{\nu-1}$. Thus,

$\displaystyle\operatorname*{ess\,sup}\mathbb{E}_{\nu}\left[\mathbb{E}_{\nu}\left[\overline{\tau}_{\nu}-\nu-w+1|X_{\nu},\dots,X_{\nu+w-1},{\cal
F}_{\nu-1}\right]|{\cal F}_{\nu-1}\right]$
$\displaystyle=\mathbb{E}_{\nu}\left[\mathbb{E}_{\nu}\left[\overline{\tau}_{\nu}-\nu-w+1|X_{\nu},\dots,X_{\nu+w-1}\right]\right]$
$\displaystyle=\mathbb{E}_{1}\left[\mathbb{E}_{1}\left[\overline{\tau}_{1}-w|X_{1},\dots,X_{w}\right]\right]$
$\displaystyle=\mathbb{E}_{1}\left[\overline{\tau}-w\right]$

The last line holds because $\overline{\tau}_{1}=\overline{\tau}$ almost
surely (under $\mathbb{P}_{1}$). The proof is now complete. ∎

###### Proof of Lemma IV.5.

The proof consists of two parts. In the first part, we use a similar technique
as in [26, Thm 1.1] to obtain an extension of Wald’s identity to the case
where the samples are $w$-dependent. In the second part, we upper bound the
overshoot using results from renewal theory. For notational brevity, we omit
the dependence on $w$ and write $\widehat{Z}^{w}_{i}=\widehat{Z}_{i}$.

Define

$Y_{i}:=\mathbb{E}_{1}\left[U_{i}-(i-w)\widehat{I}|{\cal
F}_{i-w}\right],~{}\forall i\geq w$

and note that $Y_{w}=0$. Now,

$\displaystyle\mathbb{E}_{1}\left[Y_{i+1}|{\cal F}_{i-w}\right]$
$\displaystyle=\mathbb{E}_{1}\left[\mathbb{E}_{1}\left[U_{i+1}-(i+1-w)\widehat{I}|{\cal
F}_{i+1-w}\right]|{\cal F}_{i-w}\right]$
$\displaystyle=\mathbb{E}_{1}\left[U_{i}+\widehat{Z}_{i+1}-(i-w)\widehat{I}-\widehat{I}|{\cal
F}_{i-w}\right]$
$\displaystyle=Y_{i}+\mathbb{E}_{1}\left[\widehat{Z}_{i+1}-\widehat{I}|{\cal
F}_{i-w}\right]$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{=}}Y_{i}+\mathbb{E}_{1}\left[\widehat{Z}_{i+1}-\widehat{I}\right]$
$\displaystyle=Y_{i},~{}\forall i>w,~{}\mathbb{P}_{1}\text{--}a.s.$

where $(*)$ follows from independence between $\widehat{Z}^{w}_{i+1}$ and
${\cal F}_{i-w}$. This implies that $\left\\{(Y_{i},{\cal
F}_{i-w})\right\\}_{i\geq w}$ is a martingale. Therefore, for any finite
$k>w$, $\min\left\\{\tau_{u},k\right\\}\leq k<\infty$, and thus

$\displaystyle\mathbb{E}_{1}\left[U_{\min\left\\{\tau_{u},k\right\\}}-\widehat{I}(\min\left\\{\tau_{u},k\right\\}-w)\right]$
$\displaystyle=\sum_{m=1}^{\infty}\mathbb{P}_{1}\left\\{\tau_{u}=m\right\\}\mathbb{E}_{1}\left[\mathbb{E}_{1}\left[U_{\min\left\\{m,k\right\\}}-\widehat{I}(\min\left\\{m,k\right\\}-w)|{\cal
F}_{\min\left\\{m,k\right\\}-w}\right]\big{|}\tau_{u}=m\right]$
$\displaystyle=\sum_{m=1}^{\infty}\mathbb{P}_{1}\left\\{\tau_{u}=m\right\\}\mathbb{E}_{1}\left[Y_{\min\left\\{m,k\right\\}}|\tau_{u}=m\right]$
$\displaystyle=\mathbb{E}_{1}\left[Y_{\min\left\\{\tau_{u},k\right\\}}\right]\stackrel{{\scriptstyle(*)}}{{=}}\mathbb{E}_{1}\left[Y_{w}\right]=0$

where $(*)$ follows from optional sampling theorem. This implies that

$\mathbb{E}_{1}\left[U_{\min\left\\{\tau_{u},k\right\\}}\right]=\widehat{I}(\mathbb{E}_{1}\left[\min\left\\{\tau_{u},k\right\\}\right]-w).$
(58)

Note that $\tau_{u}<\infty$ with probability 1 under $\mathbb{P}_{1}$ by Lemma
IV.4. For $i>w$, let $\widehat{Z}_{i}^{+}:=\max\\{0,\widehat{Z}_{i}\\}$ and
$\widehat{Z}_{i}^{-}:=-\min\\{0,\widehat{Z}_{i}\\}$. Note that
$\widehat{Z}_{i}^{+},\widehat{Z}_{i}^{-}\geq 0$,
$\widehat{Z}_{i}=\widehat{Z}_{i}^{+}-\widehat{Z}_{i}^{-}$, and
$U_{n}=\sum_{i=w+1}^{n}\left(\widehat{Z}_{i}^{+}-\widehat{Z}_{i}^{-}\right),\forall
n>w$. Thus, we have

$\displaystyle\lim_{k\to\infty}\mathbb{E}_{1}\left[U_{\min\left\\{\tau_{u},k\right\\}}\right]$
$\displaystyle=\lim_{k\to\infty}\mathbb{E}_{1}\left[\sum_{i=w+1}^{\min\left\\{\tau_{u},k\right\\}}\widehat{Z}_{i}^{+}\right]-\lim_{k\to\infty}\mathbb{E}_{1}\left[\sum_{i=w+1}^{\min\left\\{\tau_{u},k\right\\}}\widehat{Z}_{i}^{-}\right]$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\mathbb{E}_{1}\left[\lim_{k\to\infty}\sum_{i=w+1}^{\min\left\\{\tau_{u},k\right\\}}\widehat{Z}_{i}^{+}\right]-\mathbb{E}_{1}\left[\lim_{k\to\infty}\sum_{i=w+1}^{\min\left\\{\tau_{u},k\right\\}}\widehat{Z}_{i}^{-}\right]$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}\mathbb{E}_{1}\left[\sum_{i=w+1}^{\tau_{u}}\widehat{Z}_{i}^{+}\right]-\mathbb{E}_{1}\left[\sum_{i=w+1}^{\tau_{u}}\widehat{Z}_{i}^{-}\right]$
$\displaystyle=\mathbb{E}_{1}\left[U_{\tau_{u}}\right]$

where $(i)$ follows from the monotone convergence theorem, and $(ii)$ is due
to the fact that $\tau_{u}<\infty$ with probability 1. Also by the monotone
convergence theorem,

$\lim_{k\to\infty}\mathbb{E}_{1}\left[\min\left\\{\tau_{u},k\right\\}\right]=\mathbb{E}_{1}\left[\lim_{k\to\infty}\min\left\\{\tau_{u},k\right\\}\right]=\mathbb{E}_{1}\left[\tau_{u}\right].$

Thus, taking the limit of $k$ on both sides of (58),

$\mathbb{E}_{1}\left[U_{\tau_{u}}\right]=\lim_{k\to\infty}\mathbb{E}_{1}\left[U_{\min\left\\{\tau_{u},k\right\\}}\right]=\lim_{k\to\infty}\widehat{I}(\mathbb{E}_{1}\left[\min\left\\{\tau_{u},k\right\\}\right]-w)=\widehat{I}(\mathbb{E}_{1}\left[\tau_{u}\right]-w).$
(59)

Now, denote

$L_{i}:=\log\frac{\widehat{p}_{i}^{w}(X_{i})}{p_{1}(X_{i})},\quad\forall i>w.$

By definition we have
$\mathbb{E}_{1}\left[\widehat{Z}_{i}-L_{i}\right]=I,\forall i>w$. The proof of
(59) is also applicable to $L^{2}_{\tau_{u}}$, which gives us

$\mathbb{E}_{1}\left[\sum_{i=w+1}^{\tau_{u}}L^{2}_{i}\right]=\mathbb{E}_{1}\left[L^{2}_{w+1}\right](\mathbb{E}_{1}\left[\tau_{u}\right]-w).$
(60)

Thus,

$\displaystyle\mathbb{E}_{1}\left[U_{\tau_{u}}-b\right]$
$\displaystyle=\mathbb{E}_{1}\left[U_{\tau_{u}-1}-b+\widehat{Z}_{\tau_{u}}\right]<\mathbb{E}_{1}\left[\widehat{Z}_{\tau_{u}}\right]=I+\mathbb{E}_{1}\left[L_{\tau_{u}}\right]$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}I+\sqrt{\mathbb{E}_{1}\left[L_{\tau_{u}}^{2}\right]}\leq
I+\sqrt{\mathbb{E}_{1}\left[\sum_{i=w+1}^{\tau_{u}}L_{i}^{2}\right]}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}I+\sqrt{\left(\mathbb{E}_{1}\left[\tau_{u}\right]-w\right)\mathbb{E}_{1}\left[L_{w+1}^{2}\right]}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}I+\sqrt{\frac{C_{2}}{w^{\beta_{2}}}\left(\mathbb{E}_{1}\left[\tau_{u}\right]-w\right)}$
(61)

for sufficiently large $w$. Here $(i)$ follows from Jensen’s inequality,
$(ii)$ follows from (60), and $(iii)$ follows from assumption (2). Denote
$c_{w}:=C_{2}w^{-\beta_{2}}$ and $x:=\mathbb{E}_{1}\left[\tau_{u}\right]-w$.
The goal below is to get an upper bound for $x$. Combining (Proof of Lemma
IV.5.) with (59), we obtain

$\sqrt{c_{w}x}+I\geq\widehat{I}x-b$

which implies that

$\displaystyle x$
$\displaystyle\leq\frac{(2(b+I)\widehat{I}+c_{w})+\sqrt{(2(b+I)\widehat{I}+c_{w})^{2}-4\widehat{I}^{2}(b+I)^{2}}}{2\widehat{I}^{2}}$
$\displaystyle\leq\frac{2(b+I)\widehat{I}+c_{w}}{\widehat{I}^{2}}.$

Plugging this bound into (Proof of Lemma IV.5.) gives us

$\displaystyle\mathbb{E}_{1}\left[U_{\tau_{u}}-b\right]$ $\displaystyle\leq
I+\sqrt{\frac{2(b+I)c_{w}\widehat{I}+c_{w}^{2}}{\widehat{I}^{2}}}$
$\displaystyle\leq
I+\frac{2\sqrt{(b+I)c_{w}\widehat{I}}+\sqrt{2}c_{w}}{\widehat{I}}$

where in the last inequality we use the fact that
$\sqrt{u+v}\leq\sqrt{2u}+\sqrt{2v}$ for any $u,v>0$. Therefore, combining with
(59), we obtain

$\displaystyle\mathbb{E}_{1}\left[\tau_{u}\right]$
$\displaystyle=w+\widehat{I}^{-1}\left(b+\mathbb{E}_{1}\left[U_{\tau_{u}}-b\right]\right)$
$\displaystyle\leq
w+\widehat{I}^{-1}(b+I)+\left(4C_{2}(b+I)w^{-\beta_{2}}\widehat{I}^{-3}\right)^{\frac{1}{2}}+\sqrt{2}\widehat{I}^{-2}C_{2}w^{-\beta_{2}}.$

The proof is now complete since
$\mathbb{E}_{1}\left[\overline{\tau}(b)\right]\leq\mathbb{E}_{1}\left[\tau_{u}(b)\right]$
by Lemma IV.3. ∎