# Asymptotic Optimality of Mixture Rules for Detecting Changes in General
Stochastic Models ††thanks: The work was supported in part by the Russian
Federation 5-100 program, the Russian Federation Ministry of Science and
Education Arctic program and the grant 18-19-00452 from the Russian Science
Foundation at the Moscow Institute of Physics and Technology.

Alexander G. Tartakovsky  A.G. Tartakovsky is a Head of the Space informatics
Laboratory at the Moscow Institute of Physics and Technology, Russia and Vice
President of AGT StatConsult, Los Angeles, California, USA; e-mail:
<EMAIL_ADDRESS>received October 31, 2017; revised May 22, 2018;
accepted May 26, 2018.Copyright (c) 2017 IEEE. Personal use of this material
is permitted. However, permission to use this material for any other purposes
must be obtained from the IEEE by sending a request to pubs-
<EMAIL_ADDRESS>
###### Abstract

The paper addresses a sequential changepoint detection problem for a general
stochastic model, assuming that the observed data may be non-i.i.d. (i.e.,
dependent and non-identically distributed) and the prior distribution of the
change point is arbitrary. Tartakovsky and Veeravalli (2005), Baron and
Tartakovsky (2006), and, more recently, Tartakovsky (2017) developed a general
asymptotic theory of changepoint detection for non-i.i.d. stochastic models,
assuming the certain stability of the log-likelihood ratio process, in the
case of simple hypotheses when both pre-change and post-change models are
completely specified. However, in most applications, the post-change
distribution is not completely known. In the present paper, we generalize
previous results to the case of parametric uncertainty, assuming the parameter
of the post-change distribution is unknown. We introduce two detection rules
based on mixtures – the Mixture Shiryaev rule and the Mixture Shiryaev–Roberts
rule – and study their asymptotic properties in the Bayesian context. In
particular, we provide sufficient conditions under which these rules are
first-order asymptotically optimal, minimizing moments of the delay to
detection as the probability of false alarm approaches zero.

###### Index Terms:

Asymptotic Optimality; Changepoint Problems; Expected Detection Delay; General
Stochastic Models; Hidden Markov Models; Moments of the Delay to Detection;
$r$-Complete Convergence.

##  I Introduction

Suppose $X_{1},X_{2},\dots$ are random variables observed sequentially, which
may change statistical properties at an unknown point in time
$\nu\in\\{0,1,2,\dots\\}$, so that $X_{1},\dots,X_{\nu}$ are generated by one
stochastic model and $X_{\nu+1},X_{\nu+2},\dots$ by another model. The value
of the change point $\nu$ is unknown and the fact of change must be detected
as soon as possible controlling for a risk associated with false detections.

More specifically, let ${\mathbf{X}}^{n}=(X_{1},\dots,X_{n})$ denote a sample
of size $n$ and let $\\{f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})\\}_{n\geqslant
1}$ be a sequence of conditional densities of $X_{n}$ given
${\mathbf{X}}^{n-1}$. If $\nu=\infty$, i.e., there is no change, then the
parameter $\theta$ is equal to $\theta_{0}$, so that
$f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})=f_{\theta_{0},n}(X_{n}|{\mathbf{X}}^{n-1})$
for all $n\geqslant 1$. If $\nu=k<\infty$, then
$\theta=\theta_{1}\neq\theta_{0}$, so that
$f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})=f_{\theta_{0},n}(X_{n}|{\mathbf{X}}^{n-1})$
for $n\leqslant k$ and
$f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})=f_{\theta_{1},n}(X_{n}|{\mathbf{X}}^{n-1})$
for $n>k$.

A sequential detection rule is a stopping time $T$ with respect to an observed
sequence $\\{X_{n}\\}_{n\geqslant 1}$. That is, $T$ is an integer-valued
random variable, such that the event $\\{T=n\\}$, which denotes stopping and
taking an action after observing the sample ${\mathbf{X}}^{n}$, belongs to the
sigma-algebra ${\mathcal{F}}_{n}=\sigma({\mathbf{X}}^{n})$ generated by
observations $X_{1},\dots,X_{n}$. A false alarm is raised when the detection
is declared before the change occurs, $T\leqslant\nu$. The goal of the
quickest changepoint detection problem is to develop a detection rule that
stops as soon as possible after the real change occurs under a given risk of
false alarms.

In early stages, the work focused on the i.i.d. case where
$f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})=f_{\theta}(X_{n})$, i.e., when the
observations are independent and identically distributed (i.i.d.) according to
a distribution with density $f_{\theta_{0}}(X_{n})$ in the pre-change mode and
with density $f_{\theta_{1}}(X_{n})$ in the post-change mode. In the early
1960s, Shiryaev [1] developed a Bayesian sequential changepoint detection
theory when $\theta_{1}$ is known. This theory implies that the detection
procedure based on thresholding the posterior probability of the change being
active before the current time is strictly optimal, minimizing the expected
delay to detection in the class of procedures with a given weighted
probability of false alarm if the prior distribution of the change point is
geometric. At the beginning of the 1970s, Lorden [2] showed that Page’s CUSUM
procedure [3] is first-order asymptotically optimal in a minimax sense,
minimizing the maximal expected delay to detection in the class of procedures
with the prescribed average run length to false alarm (ARL2FA) as ARL2FA
approaches infinity. In the mid-1980s, Moustakides [4] established exact
minimaxity of the CUSUM procedure for any value of the ARL2FA. Pollak [5]
suggested modifying the conventional Shiryaev–Roberts statistic (see [6, 1,
7]) by randomizing the initial condition to make it an equalizer. His version
of the Shiryaev–Roberts statistic starts from a random point sampled from the
quasi-stationary distribution of the Shiryaev–Roberts statistic. He proved
that, for a large ARL2FA, this randomized procedure is asymptotically third-
order minimax within an additive vanishing term. The articles [8, 9] indicate
that the Shiryaev–Roberts–Pollak procedure is not exactly minimax for all
values of the ARL2FA by showing that a generalized Shiryaev–Roberts procedure
that starts from a specially designed deterministic point performs slightly
better. Shiryaev [6, 1] was the first who established exact optimality of the
Shiryaev–Roberts detection procedure in the problem of detecting changes
occurring at a far time horizon after many re-runs among multi-cyclic
procedures with the prescribed mean time between false alarms for detecting a
change in the drift of the Brownian motion. Pollak and Tartakovsky [10]
extended Shiryaev’s result to the discrete-time i.i.d. (not necessarily
Gaussian) case. Third-order asymptotic optimality of generalized
Shiryaev–Roberts procedures with random and deterministic head-starts was
established in [11]. Another trend related to evaluation of performance of
CUSUM and EWMA detection procedures was initiated by the SPC (statistical
process control) community (see, e.g., [12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22]).

In many practical applications, the i.i.d. assumption is too restrictive. The
observations may be either non-identically distributed or correlated or both,
i.e., non-i.i.d. Lai [23] generalized Lorden’s asymptotic theory [2] for the
general non-i.i.d. case establishing asymptotic optimality of the CUSUM
procedure under very general conditions in the point-wise, minimax, and
Bayesian settings. He also suggested a window-limited version of the CUSUM
procedure, which is computationally less demanding than a conventional CUSUM,
but still preserves asymptotic optimality properties. Tartakovsky and
Veeravalli [24], Baron and Tartakovsky [25], and Tartakovsky [26] generalized
Shiryaev’s Bayesian theory for the general non-i.i.d. case and for a wide
class of prior distributions. In particular, it was proved that the Shiryaev
detection rule is asymptotically optimal – it minimizes not only the expected
delay to detection but also higher moments of the detection delay as the
weighted probability of a false alarm vanishes. Fuh and Tartakovsky [27]
specified the results in [24, 26] for finite-state hidden Markov models (HMM),
finding sufficient conditions under which the Shiryaev and Shiryaev–Roberts
rules are first-order asymptotically optimal, assuming that both pre-change
and post-change distributions are completely specified, i.e., the post-change
parameter $\theta_{1}$ is known. Fuh [28] proved first-order asymptotic
minimaxity of the CUSUM procedure as the ARL2FA goes to infinity.
Pergamenchtchikov and Tartakovsky [29] established point-wise and minimax
asymptotic optimality properties of the Shiryaev–Roberts rule for the general
non-i.i.d. stochastic model in the class of rules with the prescribed local
conditional probability of false alarm (in the given time interval) as well as
presented sufficient conditions for ergodic Markov processes.

In a variety of applications, however, a pre-change distribution is known but
the post-change distribution is rarely known completely. A more realistic
situation is parametric uncertainty when the parameter $\theta$ of the post-
change distribution is unknown since a putative value of $\theta$ is rarely
representative. When the post-change parameter is unknown, so that the post-
change hypothesis “${\mathsf{H}}_{k}^{\vartheta}:\nu=k,\theta=\vartheta$”,
$\vartheta\in\Theta$ is composite, and it is desirable to detect quickly a
change in a broad range of possible values, the natural modification of the
CUSUM, Shiryaev and Shiryaev–Roberts procedures is based either on maximizing
over $\vartheta$ or weighting over a mixing measure $W(\vartheta)$ the
corresponding statistics tuned to $\theta=\vartheta$. The maximization leads
to the generalized likelihood ratio (GLR)-based procedures and weighting to
mixtures. Lorden [2] was the first established first-order asymptotic
minimaxity of the GLR-CUSUM procedure for the i.i.d. exponential families as
the ARL2FA goes to infinity (see also Dragalin [30] for refined results).
Siegmund and Yakir [31] established third-order asymptotic minimaxity of the
randomized mixture Shiryaev–Roberts–Pollak procedure for the exponential
family with respect to the maximal Kullback–Leibler information. Lai [23]
established point-wise and minimax asymptotic optimality of the window-limited
mixture CUSUM and GLR-CUSUM procedures for general non-i.i.d. models. Further
detailed overview and references can be found in the monographs [32, 33].

A variety of applications where sequential changepoint detection is important
are discussed, e.g., in [34, 35, 32, 36, 37, 38, 39, 17, 40, 41, 42, 43, 44,
45, 46, 47, 48, 33, 49].

In this paper, we generalize the asymptotic Bayesian theory, developed in [24,
26] for a simple post-change hypothesis, to the more important and typical
case of the composite post-change hypothesis where the post-change parameter
is unknown. We assume that the observations can have a very general structure,
i.e., can be dependent and non-identically distributed. The key assumption in
the general asymptotic theory is a stability property of the log-likelihood
ratio process between the “change” and “no-change” hypotheses, which can be
formulated in terms of a Law of Large Numbers and rates of convergence, e.g.,
as the $r$-complete convergence of the properly normalized log-likelihood
ratio and its adaptive version in the vicinity of the true parameter value.

The rest of the paper is organized as follows. In Section II, we introduce the
mixture Shiryaev and the mixture Shiryaev–Roberts rules. In Section III, we
formulate the asymptotic optimization problems in the class of changepoint
detection procedures with the constraint imposed on the weighted probability
of false alarm, which we address in the following sections. In Section IV, we
establish the first-order asymptotic optimality of the mixture Shiryaev rule
and, in Section V, we study the performance of the mixture Shiryaev–Roberts
rule as the weighted probability of false alarm goes to zero. In Section VI,
we prove asymptotic optimality of the mixture Shiryaev and mixture
Shiryaev–Roberts rules in a purely Bayesian setup when the cost of delay in
change detection approaches zero. In Section VII, we use several examples to
illustrate general results. Section VIII concludes.

##  II The Shiryaev and Shiryaev–Roberts Mixture Rules

Let ${\mathsf{P}}_{\infty}$ denote the probability measure corresponding to
the sequence of observations $\\{X_{n}\\}_{n\geqslant 1}$ when there is never
a change ($\nu=\infty$) and, for $k=0,1,\dots$ and $\vartheta\in\Theta$, let
${\mathsf{P}}_{k,\vartheta}$ denote the measure corresponding to the sequence
$\\{X_{n}\\}_{n\geqslant 1}$ when $\nu=k<\infty$ and $\theta=\vartheta$ (i.e.,
$X_{\nu+1}$ is the first post-change observation), where $\theta\in\Theta$ is
a parameter (possibly multidimensional). Further, let
$p_{k,\vartheta}({\mathbf{X}}^{n})=p({\mathbf{X}}^{n}|\nu=k,\theta=\vartheta)$
denote a joint density of the sample ${\mathbf{X}}^{n}=(X_{1},\dots,X_{n})$,
i.e., density of the restriction ${\mathsf{P}}_{k,\vartheta}^{(n)}$ of the
measure ${\mathsf{P}}_{k,\vartheta}$ to the sigma-algebra
${\mathcal{F}}_{n}=\sigma({\mathbf{X}}^{n})$ with respect to a non-degenerate
sigma-finite measure. Let $\\{g_{n}(X_{n}|{\mathbf{X}}^{n-1})\\}_{n\geqslant
1}$ and $\\{f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})\\}_{n\geqslant 1}$ be two
sequences of conditional densities of $X_{n}$ given ${\mathbf{X}}^{n-1}$. With
this notation, the general non-i.i.d. changepoint model, which we are
interested in, can be written as

$\begin{split}p_{\nu,\theta}({\mathbf{X}}^{n})&=p_{\infty}({\mathbf{X}}^{n})=\prod_{i=1}^{n}g_{i}(X_{i}|{\mathbf{X}}^{i-1})~{}~{}\text{for}~{}~{}\nu\geqslant
n,\\\
p_{\nu,\theta}({\mathbf{X}}^{n})&=\prod_{i=1}^{\nu}g_{i}(X_{i}|{\mathbf{X}}^{i-1})\times\prod_{i=\nu+1}^{n}f_{\theta,i}(X_{i}|{\mathbf{X}}^{i-1})\\\
&~{}~{}\text{for}~{}~{}\nu<n.\end{split}$ (1)

Therefore, $g_{n}(X_{n}|{\mathbf{X}}^{n-1})$ and
$f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})$ are the pre-change and post-change
conditional densities. Note that the post-change densities may depend on the
change point $\nu$, i.e.,
$f_{\theta,n}(X_{n}|{\mathbf{X}}^{n-1})=f_{\theta,n}^{(\nu)}(X_{n}|{\mathbf{X}}^{n-1})$
for $n>\nu$. We omit the superscript $\nu$ for brevity. While often the pre-
change density $g_{n}$ belongs to the same parametric family as the post-
change one $f_{\theta,n}$, i.e., $g_{n}=f_{\theta_{0},n}$ for some known value
$\theta_{0}$, this is not necessarily the case, so that we consider a more
general scenario.

Let ${\mathsf{E}}_{k,\vartheta}$ and ${\mathsf{E}}_{\infty}$ denote
expectations under ${\mathsf{P}}_{k,\vartheta}$ and ${\mathsf{P}}_{\infty}$,
respectively.

The likelihood ratio (LR) of the hypothesis
“${\mathsf{H}}_{k}^{\vartheta}:\nu=k,\theta=\vartheta$” that the change occurs
at $\nu=k$ with the post-change parameter $\theta=\vartheta$ against the no-
change hypothesis “${\mathsf{H}}_{\infty}:\nu=\infty$” based on the sample
${\mathbf{X}}^{n}=(X_{1},\dots,X_{n})$ is given by the product

$LR_{k,n}(\vartheta)=\prod_{i=k+1}^{n}\frac{f_{\vartheta,i}(X_{i}|{\mathbf{X}}^{i-1})}{g_{i}(X_{i}|{\mathbf{X}}^{i-1})},\quad
n>k$

and we set $LR_{k,n}(\vartheta)=1$ for $n\leqslant k$.

Assume that the change point $\nu$ is a random variable independent of the
observations with prior distribution $\pi_{k}={\mathsf{P}}(\nu=k)$,
$k=0,1,2,\dots$ with $\pi_{k}>0$ for $k\in\\{0,1,2,\dots\\}=\mathbb{Z}_{+}$.
We will also assume that a change point may take negative values, which means
that the change has occurred by the time the observations became available.
However, the detailed structure of the distribution ${\mathsf{P}}(\nu=k)$ for
$k=-1,-2,\dots$ is not important. The only value which matters is the total
probability $q={\mathsf{P}}(\nu\leqslant-1)$ of the change being in effect
before the observations become available.

Let
${\mathcal{L}}_{n}(\vartheta)=f_{\vartheta,n}(X_{n}|{\mathbf{X}}^{n-1})/g_{n}(X_{i}|{\mathbf{X}}^{n-1})$.
In [24, 26] for detecting a change from
$\\{g_{n}(X_{n}|{\mathbf{X}}^{n-1})\\}$ to
$\\{f_{\vartheta,n}(X_{n}|{\mathbf{X}}^{n-1})\\}$ it was proposed to use the
Shiryaev statistic

$\begin{split}S_{n}(\vartheta)&=\frac{1}{{\mathsf{P}}(\nu\geqslant
n)}\left(q\prod_{i=1}^{n}{\mathcal{L}}_{i}(\vartheta)+\sum_{k=0}^{n-1}\pi_{k}\prod_{i=k+1}^{n}{\mathcal{L}}_{i}(\vartheta)\right),\\\
&\quad n\geqslant 1,\quad S_{0}(\vartheta)=q/(1-q),\end{split}$ (2)

where $\prod_{i=j}^{s}{\mathcal{L}}_{i}=1$ for $s<j$.

When the value of the parameter is unknown there are two conventional
approaches to overcome uncertainty – either to maximize or average over
$\vartheta$. The second approach is usually referred to as Mixtures. To be
more specific, introduce a mixing measure $W(\theta)$,
$\int_{\Theta}\rm{d}W(\theta)=1$, which can be interpreted as a prior
distribution if needed. Define the average (mixed) LR

$\Lambda_{k,n}^{W}=\int_{\Theta}LR_{k,n}(\vartheta)\,\mathrm{d}W(\vartheta),\quad
k<n$ (3)

and the statistic

$\begin{split}S_{n}^{W}&=\int_{\Theta}S_{n}(\vartheta)\,\mathrm{d}W(\vartheta)\\\
&=\frac{1}{{\mathsf{P}}(\nu\geqslant
n)}\left(q\Lambda_{0,n}^{W}+\sum_{k=0}^{n-1}\pi_{k}\Lambda_{k,n}^{W}\right),\\\
&\quad n\geqslant 1,~{}~{}S_{0}^{W}=q/(1-q),\end{split}$ (4)

where $S_{n}(\vartheta)$ is the Shiryaev statistic tuned to the parameter
$\theta=\vartheta$ defined in (2). We will call this statistic the Mixture
Shiryaev (MS) statistic.

In the sequel, we study the MS detection rule that stops and raises an alarm
as soon as the statistic $S_{n}^{W}$ reaches a positive level $A$, i.e., the
MS rule is nothing but the stopping time

$T_{A}=\inf\left\\{n\geqslant 1:S_{n}^{W}\geqslant A\right\\},$ (5)

where $A>0$ is a threshold controlling for the false alarm risk. In
definitions of stopping times we always set
$\inf\\{\mathchoice{\mbox{\msbmx\char 63\relax}}{\mbox{\msbmx\char
63\relax}}{\mbox{\msbmvii\char 63\relax}}{\mbox{\msbmv\char
63\relax}}\\}=\infty$.

Another popular statistic for detecting a change from
$\\{g_{n}(X_{n}|{\mathbf{X}}^{n-1})\\}$ to
$\\{f_{\vartheta,n}(X_{n}|{\mathbf{X}}^{n-1})\\}$, which has certain
optimality properties [10, 11, 9, 33], is the generalized Shiryaev–Roberts
(SR) statistic

$\begin{split}R_{n}(\vartheta)&=\omega
LR_{0,n}(\vartheta)+\sum_{k=0}^{n-1}LR_{k,n}(\vartheta)\\\
&=\omega\prod_{i=1}^{n}{\mathcal{L}}_{i}(\vartheta)+\sum_{k=1}^{n}\prod_{i=k}^{n}{\mathcal{L}}_{i}(\vartheta),\quad
n\geqslant 1\end{split}$ (6)

with a non-negative head-start $R_{0}(\vartheta)=\omega$, $\omega\geqslant 0$.
The mixture counterpart, which we will refer to as the Mixture
Shiryaev–Roberts (MSR) statistic, is

$\begin{split}R_{n}^{W}&=\int_{\Theta}R_{n}(\vartheta)\,\mathrm{d}W(\vartheta),\\\
&=\omega\Lambda_{0,n}^{W}+\sum_{k=0}^{n-1}\Lambda_{k,n}^{W},\quad n\geqslant
1,~{}~{}R_{0}^{W}=\omega,\end{split}$ (7)

and the corresponding MSR detection rule is given by the stopping time

$\widetilde{T}_{A}=\inf\left\\{n\geqslant 1:R_{n}^{W}\geqslant A\right\\},$
(8)

where $A>0$ is a threshold controlling for the false alarm risk.

In Section IV, we show that the MS detection rule $T_{A}$ is first-order
asymptotically optimal, minimizing moments of the stopping time distribution
for the low risk of false alarms under very general conditions. In Section V,
we establish asymptotic properties of the MSR rule, showing that it is also
asymptotically optimal when the prior distribution becomes asymptotically
flat, but not in general.

##  III Asymptotic Problems

Let
${\mathsf{P}}^{\pi}_{\theta}({\mathcal{A}}\times\mathcal{K})=\sum_{k\in\mathcal{K}}\,\pi_{k}{\mathsf{P}}_{k,\theta}\left({\mathcal{A}}\right)$
denote the “weighted” probability measure and ${\mathsf{E}}^{\pi}_{\theta}$
the corresponding expectation.

For $r\geqslant 1$, $\nu=k\in\mathbb{Z}_{+}$, and $\theta\in\Theta$, introduce
the risk associated with the conditional $r$-th moment of the detection delay

${\mathcal{R}}^{r}_{k,\theta}(T)={\mathsf{E}}_{k,\theta}\left[(T-k)^{r}\,|\,T>k\right].$
(9)

In a Bayesian setting, the average risk associated with the moments of delay
to detection is

$\begin{split}{\bar{\mathcal{R}}}^{r}_{\pi,\theta}(T)&:={\mathsf{E}}^{\pi}_{\theta}[(T-\nu)^{r}|T>\nu]\\\
&=\frac{{\displaystyle\sum_{k=0}^{\infty}}\pi_{k}{\mathcal{R}}^{r}_{k,\theta}(T){\mathsf{P}}_{\infty}(T>k)}{1-\mathsf{PFA}(T)},\end{split}$
(10)

where

$\mathsf{PFA}(T)={\mathsf{P}}^{\pi}_{\theta}(T\leqslant\nu)=\sum_{k=0}^{\infty}\pi_{k}{\mathsf{P}}_{\infty}(T\leqslant
k)$ (11)

is the weighted probability of false alarm (PFA) that corresponds to the risk
associated with a false alarm. Note that in (10) and (11) we used the fact
that ${\mathsf{P}}_{k,\theta}(T\leqslant k)={\mathsf{P}}_{\infty}(T\leqslant
k)$ since the event $\\{T\leqslant k\\}$ depends on the observations
$X_{1},\dots X_{k}$ generated by the pre-change probability measure
${\mathsf{P}}_{\infty}$ since by our convention $X_{k}$ is the last pre-change
observation if $\nu=k$.

In Section IV, we are interested in the Bayesian optimization problem

$\inf_{\\{T:\mathsf{PFA}(T)\leqslant\alpha\\}}\,{\bar{\mathcal{R}}}_{\pi,\theta}^{r}(T)\quad\text{for
all}~{}\theta\in\Theta.$ (12)

However, in general this problem is not manageable for every value of the PFA
$\alpha\in(0,1)$. So we will focus on the asymptotic problem assuming that the
PFA $\alpha$ approaches zero. Specifically, we will be interested in proving
that the MS rule is first-order asymptotically optimal, i.e.,

$\lim_{\alpha\to
0}\frac{\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\bar{\mathcal{R}}}_{\pi,\theta}^{r}(T)}{{\bar{\mathcal{R}}}_{\pi,\theta}^{r}(T_{A})}=1\quad\text{for
all}~{}\theta\in\Theta,$ (13)

where ${\mathbb{C}}(\alpha,\pi)=\\{T:\mathsf{PFA}(T)\leqslant\alpha\\}$ is the
class of detection rules for which the PFA does not exceed a prescribed number
$\alpha\in(0,1)$. In addition, we will prove that the MS rule is uniformly
first-order asymptotically optimal in a sense of minimizing the conditional
risk (9) for all change point values $\nu=k\in\mathbb{Z}_{+}$, i.e.,

$\begin{split}&\lim_{\alpha\to
0}\frac{\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathcal{R}}_{k,\theta}^{r}(T)}{{\mathcal{R}}_{k,\theta}^{r}(T_{A})}=1\\\
&\quad\text{for all}~{}\theta\in\Theta~{}\text{and
all}~{}k\in\mathbb{Z}_{+}.\end{split}$ (14)

In Section VI, we consider a “purely” Bayes problem with the average
(integrated) risk, which is the sum of the PFA and the cost of delay
proportional to the $r$-th moment of the detection delay and prove that the MS
rule is asymptotically optimal when the cost of delay to detection approaches
$0$.

Asymptotic properties of the MSR rule $\widetilde{T}_{A}$ will be also
established.

For a fixed $\theta\in\Theta$, introduce the log-likelihood ratio (LLR)
process $\\{\lambda_{k,n}(\theta)\\}_{n\geqslant k+1}$ between the hypotheses
${\mathsf{H}}_{k,\theta}$ ($k=0,1,\dots$) and ${\mathsf{H}}_{\infty}$:

$\lambda_{k,n}(\theta)=\sum_{j=k+1}^{n}\,\log\frac{f_{\theta,j}(X_{j}|{\mathbf{X}}^{j-1})}{g_{j}(X_{j}|{\mathbf{X}}^{j-1})},\quad
n>k$

($\lambda_{k,n}(\theta)=0$ for $n\leqslant k$).

Let $k\in\mathbb{Z}_{+}$ and $r>0$. We say that a sequence of the normalized
LLRs $\\{n^{-1}\lambda_{k,n}(\theta)\\}_{n\geqslant 1}$ converges
$r-$completely to a number $I_{\theta}$ under the probability measure
${\mathsf{P}}_{k,\theta}$ as $n\to\infty$ if

$\begin{split}&\sum_{n=1}^{\infty}n^{r-1}{\mathsf{P}}_{k,\theta}\left\\{\left|n^{-1}\lambda_{k,n}(\theta)-I_{\theta}\right|>\varepsilon\right\\}<\infty\\\
&\quad\text{for all}~{}~{}\varepsilon>0,\end{split}$ (15)

and we say that $\\{n^{-1}\lambda_{k,n}(\theta)\\}_{n\geqslant 1}$ converges
to $I_{\theta}$ uniformly $r-$completely as $n\to\infty$ if

$\begin{split}&\sum_{n=1}^{\infty}n^{r-1}\sup_{0\leqslant
k<\infty}{\mathsf{P}}_{k,\theta}\left\\{\left|n^{-1}\lambda_{k,n}(\theta)-I_{\theta}\right|>\varepsilon\right\\}<\infty\\\
&\quad\text{for all}~{}~{}\varepsilon>0.\end{split}$ (16)

Assume that there exists a positive and finite number $I_{\theta}$ such that
the normalized LLR $n^{-1}\lambda_{k,n+k}(\theta)$ converges to $I_{\theta}$
$r-$completely. Then it follows from [26] that when the parameter $\theta$ is
known the Shiryaev detection rule that raises an alarm at the first time such
that the Shiryaev statistic $S_{n}(\theta)$ exceeds threshold
$(1-\alpha)/\alpha$ is asymptotically (as $\alpha\to 0$) optimal in class
${\mathbb{C}}(\alpha,\pi)$.

Below we extend this result to the case where $\theta$ is unknown.
Specifically, we will show that the MS rule (5) is asymptotically optimal in
problems (13) and (14) under condition (15) and some other conditions for a
large class of priors and all parameter values $\theta\in\Theta$.

##  IV Asymptotic Optimality of the Mixture Shiryaev Rule

To study asymptotic optimality we need certain constraints imposed on the
prior distribution $\\{\pi_{k}\\}$ and on the asymptotic behavior of the
decision statistics as the sample size increases (i.e., on the general
stochastic model (1)).

The following two conditions are imposed on the prior distribution:

$\mathbf{CP}\mathbf{1}$. For some $0\leqslant\mu<\infty$,

$\lim_{n\to\infty}\frac{1}{n}\left|\log\sum_{k=n+1}^{\infty}\pi_{k}\right|=\mu.$
(17)

$\mathbf{CP}{\mathbf{2}}$. If $\mu=0$, then in addition

$\sum_{k=0}^{\infty}\pi_{k}|\log\pi_{k}|^{r}<\infty\quad\text{for
some}~{}r\geqslant 1.$ (18)

The class of prior distributions satisfying conditions $\mathbf{CP}\mathbf{1}$
and $\mathbf{CP}\mathbf{2}$ will be denoted by ${\mathbf{C}}(\mu)$.

Note that if $\mu>0$, then the prior distribution has an exponential right
tail, in which case, condition (18) holds automatically. If $\mu=0$, the
distribution has a heavy tail, i.e., belongs to the model with a vanishing
hazard rate. However, we cannot allow this distribution to have a too heavy
tail, which will generate very large time intervals between change points.
This is guaranteed by condition $\mathbf{CP}{\mathbf{2}}$. Note that condition
$\mathbf{CP}{\mathbf{1}}$ excludes light-tail distributions with unbounded
hazard rates (e.g., Gaussian-type or Weibull-type with the shape parameter
$\kappa>1$) for which the time-intervals with a change point are very short.
In this case, prior information dominates information obtained from the
observations, the change can be easily detected at early stages, and the
asymptotic analysis is impractical. Note also that constraint (18) is often
guaranteed by finiteness of the $r$-th moment,
$\sum_{k=0}^{\infty}k^{r}\pi_{k}<\infty$.

For $\delta>0$ define
$\Gamma_{\delta,\theta}=\\{\vartheta\in\Theta\,:\,|\vartheta-\theta|<\delta\\}$.
Regarding the general model for the observations (1), we assume that the
following two conditions are satisfied:
${\mathbf{C}}_{1}$. There exists a positive and finite number $I_{\theta}$
such that $n^{-1}\lambda_{k,k+n}(\theta)$ converges to $I_{\theta}$ in
${\mathsf{P}}_{k,\theta}$-probability and for any $k\in\mathbb{Z}_{+}$ and
$\varepsilon>0$

$\begin{split}&\lim_{N\to\infty}{\mathsf{P}}_{k,\theta}\left\\{\frac{1}{N}\max_{1\leqslant
n\leqslant
N}\lambda_{k,k+n}(\theta)\geqslant(1+\varepsilon)I_{\theta}\right\\}=0\\\
&\quad\text{for all}~{}\theta\in\Theta;\end{split}$ (19)

${\mathbf{C}}_{2}$. For any $\varepsilon>0$ there exists
$\delta=\delta_{\varepsilon}>0$ such that $W(\Gamma_{\delta,\theta})>0$ and
for every $\theta\in\Theta$, for any $k\in\mathbb{Z}_{+}$, any
$\varepsilon>0$, and for some $r\geqslant 1$

$\begin{split}&\Upsilon_{k,r}(\varepsilon,\theta):=\\\
&\sum_{n=1}^{\infty}n^{r-1}{\mathsf{P}}_{k,\theta}\left(\frac{1}{n}\inf_{\vartheta\in\Gamma_{\delta,\theta}}\lambda_{k,k+n}(\vartheta)<I_{\theta}-\varepsilon\right)<\infty.\end{split}$
(20)

Note that condition ${\mathbf{C}}_{1}$ holds whenever
$\lambda_{k,k+n}(\theta)/n$ converges almost surely to $I_{\theta}$ under
${\mathsf{P}}_{\theta,k}$,

$\frac{1}{n}\lambda_{k,k+n}(\theta)\xrightarrow[n\to\infty]{{\mathsf{P}}_{k,\theta}-\text{a.s.}}I_{\theta}\quad\text{for
all}~{}\theta\in\Theta.$ (21)

In order to establish asymptotic optimality we first obtain, under condition
${\mathbf{C}}_{1}$, an asymptotic lower bound for moments of the detection
delay
${\bar{\mathcal{R}}}^{r}_{\pi,\theta}(T)={\mathsf{E}}^{\pi}_{\theta}\left[\left(T-\nu\right)^{r}|T>\nu\right]$
and
${\mathcal{R}}^{r}_{k,\theta}={\mathsf{E}}_{k,\theta}\left[\left(T-k\right)^{r}|T>k\right]$
of any detection rule $T$ from class ${\mathbb{C}}(\alpha,\pi)$, and then we
show that under condition ${\mathbf{C}}_{2}$ this bound is attained for the MS
rule $T_{A}$ when $A=A_{\alpha}$ is properly selected.

Asymptotic lower bounds for all positive moments of the detection delay are
specified in the following lemma. Condition (19) (and hence, the a.s.
convergence condition (21)) is sufficient for this purpose.

######  Lemma 1.

Let, for some $\mu\geqslant 0$, the prior distribution belong to class
${\mathbf{C}}(\mu)$. Assume that for some positive and finite function
$I(\theta)=I_{\theta}$, $\theta\in\Theta$ condition ${\mathbf{C}}_{1}$ holds.
Then, for all $r>0$ and all $\theta\in\Theta$

$\liminf_{\alpha\to
0}\frac{{\displaystyle\inf_{T\in{\mathbb{C}}(\alpha,\pi)}}{\bar{\mathcal{R}}}^{r}_{\pi,\theta}(T)}{|\log\alpha|^{r}}\geqslant\frac{1}{(I_{\theta}+\mu)^{r}}$
(22)

and for every $k\in\mathbb{Z}_{+}$, all $r>0$, and all $\theta\in\Theta$

$\liminf_{\alpha\to
0}\frac{{\displaystyle\inf_{T\in{\mathbb{C}}(\alpha,\pi)}}{\mathcal{R}}^{r}_{k,\theta}(T)}{|\log\alpha|^{r}}\geqslant\frac{1}{(I_{\theta}+\mu)^{r}}.$
(23)

###### Proof:

The lower bound (22) follows from Lemma 1 in Tartakovsky [26]. The proof of
(23) is a modification and generalization of the argument in the proof of
Theorem 1 in [29] provided in the Appendix. ∎

The following lemma provides the upper bound for the PFA of the MS rule.

######  Lemma 2.

For all $A>q/(1-q)$ and any prior distribution of $\nu$, the PFA of the MS
rule $T_{A}$ satisfies the inequality

$\mathsf{PFA}(T_{A})\leqslant 1/(1+A),$ (24)

so that for $\alpha<1-q$

$A=A_{\alpha}=(1-\alpha)/\alpha\quad\text{implies}\quad\mathsf{PFA}(T_{A_{\alpha}})\leqslant\alpha.$
(25)

###### Proof:

Clearly,

$\mathsf{PFA}(T_{A})={\mathsf{E}}^{\pi}[{\mathsf{P}}(T_{A}\leqslant\nu|{\mathcal{F}}_{T_{A}});T_{A}<\infty].$

Using the Bayes rule and the fact that
$\prod_{i=j+1}^{n}{\mathcal{L}}_{i}(\theta)=1$ for $j\geqslant n$, we obtain

$\displaystyle{\mathsf{P}}(\nu=k|{\mathcal{F}}_{n})=\frac{\pi_{k}\Lambda_{k,n}^{W}}{q\Lambda_{0,n}^{W}+\sum_{j=0}^{n-1}\pi_{j}\Lambda_{j,n}^{W}+{\mathsf{P}}(\nu\geqslant
n)},$

so that

$\displaystyle{\mathsf{P}}(\nu\geqslant n|{\mathcal{F}}_{n})$
$\displaystyle=\sum_{k=n}^{\infty}{\mathsf{P}}(\nu=k|{\mathcal{F}}_{n})$
$\displaystyle=\frac{{\mathsf{P}}(\nu\geqslant
n)}{q\Lambda_{0,n}^{W}+\sum_{j=0}^{n-1}\pi_{j}\Lambda_{j,n}^{W}+{\mathsf{P}}(\nu\geqslant
n)}$ $\displaystyle=\frac{1}{S_{n}^{W}+1}.$

Therefore, taking into account that $S_{T_{A}}^{W}\geqslant A$ on
$\\{T_{A}<\infty\\}$, we have

$\mathsf{PFA}(T_{A})={\mathsf{E}}^{\pi}[1/(1+S_{T_{A}}^{W});T_{A}<\infty]\leqslant
1/(1+A)$

and the inequality (24) follows. Implication (25) is obvious. ∎

The following theorem is the main result in the general non-i.i.d. case, which
shows that the MS detection rule is asymptotically optimal to the first order
under mild conditions for the observations and prior distributions. Its proof
is given in the Appendix.

######  Theorem 1.

Let $r\geqslant 1$ and let the prior distribution of the change point belong
to class ${\mathbf{C}}(\mu)$. Assume that for some $0<I_{\theta}<\infty$,
$\theta\in\Theta$, right-tail and left-tail conditions ${\mathbf{C}}_{1}$ and
${\mathbf{C}}_{2}$ are satisfied.

(i) Then, for all $0<m\leqslant r$ and all $\theta\in\Theta$ as $A\to\infty$

${\mathcal{R}}^{m}_{k,\theta}(T_{A})\sim\left(\frac{\log
A}{I_{\theta}+\mu}\right)^{m}\quad\text{for all}~{}k\in\mathbb{Z}_{+}$ (26)

and

${\bar{\mathcal{R}}}^{m}_{\pi,\theta}(T_{A})\sim\left(\frac{\log
A}{I_{\theta}+\mu}\right)^{m}.$ (27)

(ii) If $A=A_{\alpha}$ is so selected that
$\mathsf{PFA}(T_{A_{\alpha}})\leqslant\alpha$ and $\log
A_{\alpha}\sim|\log\alpha|$ as $\alpha\to 0$, in particular
$A=A_{\alpha}=(1-\alpha)/\alpha$, where $0<\alpha<1-q$, then $T_{A_{\alpha}}$
is first-order asymptotically optimal as $\alpha\to 0$ in class
${\mathbb{C}}(\alpha,\pi)$, minimizing moments of the detection delay up to
order $r$, i.e., for all $0<m\leqslant r$ and all $\theta\in\Theta$ as
$\alpha\to 0$

$\begin{split}\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathcal{R}}^{m}_{k,\theta}(T)&\sim\left(\frac{|\log\alpha|}{I_{\theta}+\mu}\right)^{m}\sim{\mathcal{R}}^{m}_{k,\theta}(T_{A_{\alpha}})\\\
&\quad\text{for all}~{}k\in\mathbb{Z}_{+}\end{split}$ (28)

and

$\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\bar{\mathcal{R}}}^{m}_{\pi,\theta}(T)\sim\left(\frac{|\log\alpha|}{I_{\theta}+\mu}\right)^{m}\sim{\bar{\mathcal{R}}}^{m}_{\pi,\theta}(T_{A_{\alpha}}).$
(29)

Theorem 1 covers a very wide class of non-i.i.d. models for the observations
as well as a large class of prior distributions. However, condition (17) does
not include the case where $\mu$ is strictly positive, but may go to zero,
$\mu\to 0$. Indeed, as discussed in detail in [26] the distributions with an
exponential right tail that satisfy condition (17) with $\mu>0$ do not
converge as $\mu\to 0$ to heavy-tailed distributions for which $\mu=0$. As a
result, the assertions of Theorem 1 do not hold with $\mu=0$ if $\mu$
approaches $0$ with an arbitrary rate. The rate has to be matched somehow with
$\alpha$. For this reason, we now consider the case where the prior
distribution $\pi^{\alpha}=\\{\pi_{k}^{\alpha}\\}$ of the change point depends
on the PFA constraint $\alpha$ and becomes “flat” when $\alpha$ vanishes.

In the next lemma, which is analogous to Lemma 1, we provide asymptotic lower
bounds for moments of the detection delay in class
${\mathbb{C}}(\alpha)=\mathbb{C}(\alpha,\pi^{\alpha})$ when the prior
distribution $\pi^{\alpha}=\\{\pi_{k}^{\alpha}\\}$ depends on $\alpha$ and
$\mu=\mu_{\alpha}\to 0$ as $\alpha\to 0$.

######  Lemma 3.

Let the prior distribution $\pi^{\alpha}=\\{\pi_{k}^{\alpha}\\}$ of the change
point satisfy condition (17) with $\mu>0$ such that $\mu=\mu_{\alpha}\to 0$ as
$\alpha\to 0$. Assume that for some $0<I_{\theta}<\infty$, $\theta\in\Theta$,
condition ${\mathbf{C}}_{1}$ holds. Then, for all $r>0$ and $\theta\in\Theta$

$\liminf_{\alpha\to
0}\frac{{\displaystyle\inf_{T\in{\mathbb{C}}(\alpha)}}{\bar{\mathcal{R}}}^{r}_{\pi^{\alpha},\theta}(T)}{|\log\alpha|^{r}}\geqslant\frac{1}{I_{\theta}^{r}}$
(30)

and

$\liminf_{\alpha\to
0}\frac{{\displaystyle\inf_{T\in{\mathbb{C}}(\alpha)}}{\mathcal{R}}^{r}_{k,\theta}(T)}{|\log\alpha|^{r}}\geqslant\frac{1}{I_{\theta}^{r}}\quad\text{for
all}~{}k\in\mathbb{Z}_{+}.$ (31)

###### Proof:

The lower bound (30) follows from Lemma 3 in [26]. A proof of the lower bound
(31) is given in the Appendix. ∎

Using this lemma, we now establish first-order asymptotic optimality of the MS
rule when $\mu=\mu_{\alpha}$ approaches zero as $\alpha\to 0$. To simplify the
proof, we strengthen condition ${\mathbf{C}}_{2}$ in the following uniform
version:
${\mathbf{C}}_{3}$. For any $\varepsilon>0$ there exists
$\delta=\delta_{\varepsilon}>0$ such that $W(\Gamma_{\delta,\theta})>0$ and
for every $\theta\in\Theta$, for any $\varepsilon>0$, and for some $r\geqslant
1$

$\begin{split}&\Upsilon_{r}(\varepsilon,\theta):=\\\
&\sum_{n=1}^{\infty}\,n^{r-1}\,\sup_{k\in\mathbb{Z}_{+}}{\mathsf{P}}_{k,\theta}\Big{(}\frac{1}{n}\inf_{\vartheta\in\Gamma_{\delta,\theta}}\lambda_{k,k+n}(\vartheta)\\\
&<I_{\theta}-\varepsilon\Big{)}<\infty.\end{split}$ (32)

######  Theorem 2.

Let $r\geqslant 1$. Assume that the prior distribution
$\pi^{\alpha}=\\{\pi_{k}^{\alpha}\\}$ of the change point $\nu$ satisfies
condition (17) with $\mu=\mu_{\alpha}\to 0$ as $\alpha\to 0$ and that
$\mu_{\alpha}$ approaches zero at such rate that

$\lim_{\alpha\to
0}\frac{{\sum_{k=0}^{\infty}\pi_{k}^{\alpha}|\log\pi_{k}^{\alpha}|^{r}}}{|\log\alpha|^{r}}=0.$
(33)

Assume that for some $0<I_{\theta}<\infty$, $\theta\in\Theta$, the right-tail
condition ${\mathbf{C}}_{1}$ and the uniform left-tail condition
${\mathbf{C}}_{3}$ are satisfied. If $A=A_{\alpha}$ is so selected that
$\mathsf{PFA}(T_{A_{\alpha}})\leqslant\alpha$ and $\log
A_{\alpha}\sim|\log\alpha|$ as $\alpha\to 0$, in particular
$A_{\alpha}=(1-\alpha)/\alpha$, then the MS rule $T_{A_{\alpha}}$ is
asymptotically optimal as $\alpha\to 0$ in class ${\mathbb{C}}(\alpha)$,
minimizing moments of the detection delay up to order $r$: for all
$0<m\leqslant r$ and all $\theta\in\Theta$ as $\alpha\to 0$

$\begin{split}\inf_{T\in{\mathbb{C}}(\alpha)}{\bar{\mathcal{R}}}^{m}_{\pi^{\alpha},\theta}(T)\sim\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{m}\sim{\bar{\mathcal{R}}}^{m}_{\pi^{\alpha},\theta}(T_{A_{\alpha}})\end{split}$
(34)

and for all $k\in\mathbb{Z}_{+}$

$\begin{split}\inf_{T\in{\mathbb{C}}(\alpha)}{\mathcal{R}}^{m}_{k,\theta}(T)\sim\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{m}\sim{\mathcal{R}}^{m}_{k,\theta}(T_{A_{\alpha}}).\end{split}$
(35)

The proof of this theorem is given in the Appendix.

##  V Asymptotic Performance of the Mixture Shiryaev–Roberts Rule

Consider now the MSR detection rule $\widetilde{T}_{A}$ defined in (7) and
(8).

The following lemma shows how to select threshold $A=A_{\alpha}$ in the MSR
rule to embed it in class ${\mathbb{C}}(\alpha,\pi)$. Write

$\displaystyle\bar{\nu}=\sum_{k=0}^{\infty}k\,\pi_{k}$
$\displaystyle=(1-q)\sum_{k=1}^{\infty}k\,{\mathsf{P}}(\nu=k|\nu\geqslant 0)$
$\displaystyle=(1-q){\mathsf{E}}[\nu|\nu\geqslant 0].$

Since we are not interested in negative values of $\nu$ we will refer to
$\bar{\nu}$ as the mean of the prior distribution. Recall that $\omega$
($\omega\geqslant 0$) is a head-start of the MSR statistic $R_{n}^{W}$ (see
(7)).

######  Lemma 4.

For all $A>0$ and any prior distribution of $\nu$ with finite mean
$\bar{\nu}$, the PFA of the MSR rule $\widetilde{T}_{A}$ satisfies the
inequality

$\mathsf{PFA}(\widetilde{T}_{A})\leqslant\frac{\omega b+\bar{\nu}}{A},$ (36)

where $b=\sum_{k=1}^{\infty}\pi_{k}$, so that if

$A=A_{\alpha}=(\omega b+\bar{\nu})/\alpha$

then $\mathsf{PFA}(\widetilde{T}_{A_{\alpha}})\leqslant\alpha$, i.e.,
$\widetilde{T}_{A_{\alpha}}\in{\mathbb{C}}(\alpha,\pi)$.

###### Proof:

Evidently,
${\mathsf{E}}_{\infty}[R_{n}(\vartheta)|{\mathcal{F}}_{n-1}]=1+R_{n-1}(\vartheta)$
and hence

$\displaystyle{\mathsf{E}}_{\infty}[R_{n}^{W}|{\mathcal{F}}_{n-1}]$
$\displaystyle=\int_{\Theta}\mathrm{d}W(\vartheta)+\int_{\Theta}R_{n-1}(\vartheta)\,\mathrm{d}W(\vartheta)$
$\displaystyle=1+R_{n-1}^{W}.$

So $\\{R_{n}^{W}-\omega-n\\}_{n\geqslant 1}$ is a zero-mean
$({\mathsf{P}}_{\infty},{\mathcal{F}}_{n})-$martingale and the MSR statistic
$R_{n}^{W}$ is a $({\mathsf{P}}_{\infty},{\mathcal{F}}_{n})-$submartingale
with mean ${\mathsf{E}}_{\infty}[R_{n}^{W}]=\omega+n$. Applying Doob’s
submartingale inequality, we obtain that for $j=1,2,\dots$

${\mathsf{P}}_{\infty}(\widetilde{T}_{A}\leqslant
j)={\mathsf{P}}_{\infty}\left(\max_{1\leqslant i\leqslant j}R_{i}^{W}\geqslant
A\right)\leqslant(\omega+j)/A$

and ${\mathsf{P}}_{\infty}(\widetilde{T}_{A}\leqslant 0)=0$. Thus,

$\displaystyle\mathsf{PFA}(\widetilde{T}_{A})$
$\displaystyle=\sum_{j=1}^{\infty}\pi_{j}{\mathsf{P}}_{\infty}(\widetilde{T}_{A}\leqslant
j)$
$\displaystyle\leqslant\frac{\omega\sum_{j=1}^{\infty}\pi_{j}+\sum_{j=1}^{\infty}j\pi_{j}}{A},$

which proves inequality (36). Therefore, assuming $\bar{\nu}<\infty$, we
obtain that setting $A=A_{\alpha}=(\omega b+\bar{\nu})/\alpha$ implies
$\widetilde{T}_{A_{\alpha}}\in{\mathbb{C}}(\alpha,\pi)$ and the proof is
complete. ∎

The following theorem, whose proof is postponed to the Appendix, establishes
asymptotic operating characteristics of the MSR rule $\widetilde{T}_{A}$.

######  Theorem 3.

Let $\bar{\nu}<\infty$ and $0\leqslant\omega<\infty$. Let $r\geqslant 1$.
Assume that for some function $0<I_{\theta}<\infty$, $\theta\in\Theta$,
conditions ${\mathbf{C}}_{1}$ and ${\mathbf{C}}_{2}$ are satisfied.

(i) Then, for all $0<m\leqslant r$ and $\theta\in\Theta$

$\lim_{A\to\infty}\frac{{\mathcal{R}}^{m}_{k,\theta}(\widetilde{T}_{A})}{(\log
A)^{m}}=\frac{1}{I_{\theta}^{m}}\quad\text{for all}~{}k\in\mathbb{Z}_{+}$ (37)

and

$\lim_{A\to\infty}\frac{{\bar{\mathcal{R}}}^{m}_{\pi,\theta}(\widetilde{T}_{A})}{(\log
A)^{m}}=\frac{1}{I_{\theta}^{m}}.$ (38)

(ii) If $A=A_{\alpha}$ is so selected that
$\widetilde{T}_{A_{\alpha}}\in{\mathbb{C}}(\alpha,\pi)$ and $\log
A_{\alpha}\sim|\log\alpha|$ as $\alpha\to 0$, in particular
$A_{\alpha}=(\omega b+\bar{\nu})/\alpha$, then for all $0<m\leqslant r$ and
$\theta\in\Theta$

$\lim_{\alpha\to
0}\frac{{\mathcal{R}}^{m}_{k,\theta}(\widetilde{T}_{A_{\alpha}})}{|\log\alpha|^{m}}=\frac{1}{I_{\theta}^{m}}\quad\text{for
all}~{}k\in\mathbb{Z}_{+}$ (39)

and

$\lim_{\alpha\to
0}\frac{{\bar{\mathcal{R}}}^{m}_{\pi,\theta}(\widetilde{T}_{A_{\alpha}})}{|\log\alpha|^{m}}=\frac{1}{I_{\theta}^{m}}.$
(40)

The next theorem addresses the case where the head-start
$\omega=\omega_{\alpha}$ of the MSR statistic and the mean value
$\bar{\nu}=\bar{\nu}_{\alpha}$ of the prior distribution approach infinity as
$\alpha\to 0$ with a certain rate. The proof is given in the Appendix.

######  Theorem 4.

Assume that $\omega_{\alpha}\to\infty$ and $\bar{\nu}_{\alpha}\to\infty$ with
such rate that the following condition holds:

$\lim_{\alpha\to
0}\frac{{\log(\omega_{\alpha}+\bar{\nu}_{\alpha})}}{|\log\alpha|}=0.$ (41)

Assume further that for some $0<I_{\theta}<\infty$ and $r\geqslant 1$
conditions ${\mathbf{C}}_{1}$ and ${\mathbf{C}}_{3}$ are satisfied. If
threshold $A_{\alpha}$ is so selected that
$\mathsf{PFA}(T_{A_{\alpha}})\leqslant\alpha$ and $\log
A_{\alpha}\sim|\log\alpha|$ as $\alpha\to 0$, in particular
$A_{\alpha}=(\omega_{\alpha}b_{\alpha}+\bar{\nu}_{\alpha})/\alpha$, then for
all $0<m\leqslant r$ and $\theta\in\Theta$, as $\alpha\to 0$

$\begin{split}{\bar{\mathcal{R}}}^{m}_{\pi^{\alpha},\theta}(\widetilde{T}_{A_{\alpha}})\sim\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{m}\sim\inf_{T\in{\mathbb{C}}(\alpha)}{\bar{\mathcal{R}}}^{m}_{\pi^{\alpha},\theta},\end{split}$
(42)

and for all $k\in\mathbb{Z}_{+}$

$\begin{split}{\mathcal{R}}^{m}_{k,\theta}(\widetilde{T}_{A_{\alpha}})\sim\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{m}\sim\inf_{T\in{\mathbb{C}}(\alpha)}{\mathcal{R}}^{m}_{k,\theta}(T).\end{split}$
(43)

Therefore, the MSR rule $\widetilde{T}_{A_{\alpha}}$ is asymptotically optimal
as $\alpha\to 0$ in class ${\mathbb{C}}(\alpha)$, minimizing moments of the
detection delay up to order $r$.

##  VI Asymptotic Optimality with Respect to the Integrated Risk

Instead of the constrained optimization problem (12) consider now the
unconstrained, “purely” Bayes problem with the loss function

$L_{r}(T,\nu)={\mathchoice{\rm 1\mskip-4.2mul}{\rm 1\mskip-4.2mul}{\rm
1\mskip-4.6mul}{\rm
1\mskip-5.2mul}_{\\{T\leqslant\nu\\}}}+c\,(T-\nu)^{r}{\mathchoice{\rm
1\mskip-4.2mul}{\rm 1\mskip-4.2mul}{\rm 1\mskip-4.6mul}{\rm
1\mskip-5.2mul}_{\\{T>\nu\\}}},$

where $c>0$ is the cost of delay per unit of time and $r\geqslant 1$. The
unknown parameter $\theta$ is now assumed random and the weight function
$W(\vartheta)$ is interpreted as the prior distribution of $\theta$. The
expected loss (integrated risk) associated with the detection rule $T$ is
given by

$\rho_{\pi,W}^{c,r}(T)={\mathsf{P}}^{\pi}(T\leqslant\nu)+c\,\int_{\Theta}{\mathsf{E}}_{\vartheta}^{\pi}[(T-\nu)^{+}]^{r}\,{\mathrm{d}}W(\vartheta).$

Below we show that the MS rule $T_{A}$ with a certain threshold $A=A_{c,r}$
that depends on the cost $c$ is asymptotically optimal, minimizing the
integrated risk $\rho_{\pi,W}^{c,r}(T)$ over all stopping times as the cost
vanishes, $c\to 0$.

Define

${\mathcal{R}}_{\pi,W}^{r}(T)=\int_{\Theta}{\bar{\mathcal{R}}}_{\pi,\vartheta}^{r}(T)\,{\mathrm{d}}W(\vartheta).$

Observe that, if we ignore the overshoot, then $\mathsf{PFA}(T_{A})\approx
1/(1+A)$ and that using approximation (27) we may expect that for a large $A$

${\mathcal{R}}_{\pi,W}^{r}(T_{A})\approx\int_{\Theta}\left(\frac{\log
A}{I_{\vartheta}+\mu}\right)^{r}\,{\mathrm{d}}W(\vartheta)=(\log
A)^{r}D_{\mu,r}$

where

$D_{\mu,r}=\int_{\Theta}\left(\frac{1}{I_{\vartheta}+\mu}\right)^{r}\,{\mathrm{d}}W(\vartheta).$

So for large $A$ the integrated risk of the MS rule is approximately equal to

$\displaystyle\rho_{\pi,W}^{c,r}(T_{A})$
$\displaystyle=\mathsf{PFA}(T_{A})+c\,[1-\mathsf{PFA}(T_{A})]{\mathcal{R}}_{\pi,W}^{r}(T_{A})$
$\displaystyle\approx 1/A+c\,D_{\mu,r}(\log A)^{r}:=G_{c,r}(A).$

The threshold value $A=A_{c,r}$ that minimizes $G_{c,r}(A)$, $A>0$, is a
solution of the equation

$rD_{\mu,r}A(\log A)^{r-1}=1/c.$ (44)

In particular, for $r=1$ we obtain $A_{c,1}=1/(cD_{\mu,1})$. Thus, it is
reasonable to conjecture that threshold $A_{c,r}$ optimizes the performance of
the MS rule for a small $c$, and hence, makes this rule asymptotically optimal
as $c\to 0$.

In the next theorem, whose proof is given in the Appendix, we establish that
the MS rule $T_{A_{c,r}}$ with threshold $A_{c,r}$ that satisfies (44) is
indeed asymptotically optimal as $c\to 0$ under conditions ${\mathbf{C}}_{1}$
and ${\mathbf{C}}_{2}$ when the set $\Theta$ is compact.

######  Theorem 5.

Let the prior distribution of the change point belong to class
${\mathbf{C}}(\mu)$. Assume that for some $0<I_{\theta}<\infty$,
$\theta\in\Theta$, right-tail and left-tail conditions ${\mathbf{C}}_{1}$ and
${\mathbf{C}}_{2}$ are satisfied and that $\Theta$ is a compact set. Let
$A=A_{c,r}$ be the solution of the equation (44). Then, as $c\to 0$,

$\inf_{T\geqslant 0}\rho_{\pi,W}^{c,r}(T)\sim D_{\mu,r}\,c\,|\log
c|^{r}\sim\rho_{\pi,W}^{c,r}(T_{A_{c,r}}).$ (45)

Finally, the results analogous to Theorems 2 and 4 in the case where the prior
distribution has an exponential tail, i.e., $\mu>0$, but $\mu=\mu_{c}\to 0$ as
$c\to 0$ also hold for the integrated risk. Specifically, let
$D_{r}=D_{\mu=0,r}$, i.e.,

$D_{r}=\int_{\Theta}\left(\frac{1}{I_{\vartheta}^{r}}\right)\,{\mathrm{d}}W(\vartheta).$

Note that the values of the mean of the prior distribution of the change point
$\bar{\nu}=\sum_{j=1}^{\infty}j\pi_{j}^{c}=\bar{\nu}_{c}$, the head-start of
the MSR statistic $\omega=\omega_{c}$, and the value of
$b=\sum_{j=1}^{\infty}\pi_{j}^{c}=b_{c}$ are the functions of the cost $c$.
The following theorem spells out details. The proof is given in the Appendix.

######  Theorem 6.

Assume that for some $0<I_{\theta}<\infty$, $\theta\in\Theta$, right-tail and
left-tail conditions ${\mathbf{C}}_{1}$ and ${\mathbf{C}}_{3}$ are satisfied
and that $\Theta$ is compact.

(i) If the prior distribution $\pi^{c}=\\{\pi_{k}^{c}\\}$ satisfies condition
(17) with $\mu=\mu_{c}\to 0$ as $c\to 0$ at such rate that

$\lim_{c\to
0}\frac{{\sum_{k=0}^{\infty}\pi_{k}^{c}|\log\pi_{k}^{c}|^{r}}}{|\log
c|^{r}}=0$ (46)

and threshold $A=A_{c,r}$ of the MS rule $T_{A}$ is the solution of the
equation

$rD_{r}A(\log A)^{r-1}=1/c,$ (47)

then, as $c\to 0$,

$\begin{split}\inf_{T\geqslant 0}\rho_{\pi^{c},W}^{c,r}(T)\sim D_{r}\,c\,|\log
c|^{r}\sim\rho_{\pi^{c},W}^{c,r}(T_{A_{c,r}}).\end{split}$ (48)

Therefore, the MS rule $T_{A_{c,r}}$ is asymptotically optimal as $c\to 0$.

(ii) If the head-start $\omega_{c}$ and the mean of the prior distribution
$\bar{\nu}_{c}$ approach infinity at such rate that

$\lim_{c\to 0}\frac{{\log(\omega_{c}+\bar{\nu}_{c})}}{|\log c|}=0$ (49)

and if $A=A_{c,r}$ of the MSR rule $\widetilde{T}_{A}$ is the solution of the
equation

$rD_{r}A(\log A)^{r-1}=(\omega_{c}b_{c}+\bar{\nu}_{c})/c,$ (50)

then, as $c\to 0$,

$\begin{split}\inf_{T\geqslant 0}\rho_{\pi^{c},W}^{c,r}(T)\sim D_{r}\,c\,|\log
c|^{r}\sim\rho_{\pi^{c},W}^{c,r}(\widetilde{T}_{A_{c,r}}).\end{split}$ (51)

Therefore, the MSR rule $\widetilde{T}_{A_{c,r}}$ is asymptotically optimal as
$c\to 0$.

##  VII Examples

######  Remark 1.

Obviously, the following condition implies conditions ${\mathbf{C}}_{2}$ and
${\mathbf{C}}_{3}$:
${\mathbf{C}}_{4}$. For any $\varepsilon>0$ there exists
$\delta=\delta_{\varepsilon}>0$ such that $W(\Gamma_{\delta,\theta})>0$. Let
the $\Theta\to{\mathbb{R}}_{+}$ function $I(\theta)=I_{\theta}$ be continuous
and assume that for every compact set $\Theta_{c}\subseteq\Theta$, every
$\varepsilon>0$, and for some $r\geqslant 1$

$\begin{split}&\Upsilon^{*}_{r}(\varepsilon,\Theta_{c}):=\sup_{\theta\in\Theta_{c}}\Upsilon_{r}(\varepsilon,\theta)=\\\
&\sum_{n=1}^{\infty}\,n^{r-1}\,\sup_{\theta\in\Theta_{c}}\sup_{k\in\mathbb{Z}_{+}}{\mathsf{P}}_{k,\theta}\Big{(}\frac{1}{n}\inf_{\vartheta\in\Gamma_{\delta,\theta}}\lambda_{k,k+n}(\vartheta)\\\
&<I_{\theta}-\varepsilon\Big{)}<\infty.\end{split}$ (52)

Hence, it is sufficient for asymptotic optimality of the MS rule as well as
for asymptotic results related to the MSR rule. Note also that if there exists
a continuous $\Theta\times\Theta\to{\mathbb{R}}_{+}$ function
$I(\vartheta,\theta)$ such that for any $\varepsilon>0$, any compact
$\Theta_{c}\subseteq\Theta$ and for some $r\geqslant 1$

$\begin{split}&\Upsilon^{**}_{r}(\varepsilon,\Theta_{c}):=\\\
&\sum_{n=1}^{\infty}\,n^{r-1}\,\sup_{k\in\mathbb{Z}_{+}}\,\sup_{\theta\in\Theta_{c}}{\mathsf{P}}_{k,\theta}\Big{(}\sup_{\vartheta\in\Theta_{c}}\Big{|}\frac{1}{n}\lambda_{k,k+n}(\vartheta)\\\
&-I(\vartheta,\theta)\Big{|}>\varepsilon\Big{)}<\infty,\end{split}$ (53)

then condition ${\mathbf{C}}_{4}$, and hence, conditions ${\mathbf{C}}_{2}$
and ${\mathbf{C}}_{3}$ are satisfied with $I_{\theta}=I(\theta,\theta)$ since

$\displaystyle{\mathsf{P}}_{k,\theta}\left(\frac{1}{n}\inf_{|\vartheta-\theta|<\delta}\lambda_{k,k+n}(\vartheta)<I_{\theta}-\varepsilon\right)$
$\displaystyle\leqslant{\mathsf{P}}_{k,\theta}\left(\sup_{\vartheta\in\Theta_{c}}\left|\frac{1}{n}\lambda_{k,k+n}(\vartheta)-I(\vartheta,\theta)\right|>\varepsilon\right).$

As we will see, conditions ${\mathbf{C}}_{4}$ and (53) are useful in checking
of applicability of theorems in particular examples.

######  Example 1 (Detection of Signals with Unknown Amplitudes in a
Multichannel System).

Assume there is a multichannel system with $N$ channels (or alternatively an
$N$-sensor system) and one is able to observe the output vector
$X_{n}=(X_{n}^{1},\dots,X_{n}^{N})$, $n=1,2,\dots$, where the observations in
the $i$th channel are of the form

$X_{n}^{i}=\theta_{i}S_{n}^{i}{\mathchoice{\rm 1\mskip-4.2mul}{\rm
1\mskip-4.2mul}{\rm 1\mskip-4.6mul}{\rm
1\mskip-5.2mul}_{\\{n>\nu\\}}}+\xi_{n}^{i},\quad n\geqslant 1.$

Here $\theta_{i}S_{n}^{i}$ is a deterministic signal with an unknown amplitude
$\theta_{i}>0$ that may appear at an unknown time $\nu$ in additive noise
$\xi_{n}^{i}$. For the sake of simplicity, suppose that all signals appear at
the same unknown time $\nu$. Assume that noises
$\\{\xi_{n}^{i}\\}_{n\in\mathbb{Z}_{+}}$, $i=1,\dots,N$, are mutually
independent $p^{i}$-th order Gaussian autoregressive processes AR$(p^{i})$,
i.e.,

$\xi_{n}^{i}=\sum_{j=1}^{p^{i}}\beta_{j}^{i}\xi_{n-j}^{i}+w_{n}^{i},\quad
n\geqslant 1,$ (54)

where $\\{w_{n}^{i}\\}_{n\geqslant 1}$ are mutually independent i.i.d. normal
${\mathcal{N}}(0,1)$ sequences and the initial values $\xi_{1-p^{i}}^{i}$,
$\xi_{2-p^{i}}^{i}$, $\dots,\xi_{0}^{i}$ are arbitrary random or deterministic
numbers, in particular we may set zero initial conditions
$\xi_{1-p^{i}}^{i}=\xi_{2-p^{i}}^{i}=\cdots=\xi_{0}^{i}=0$. The coefficients
$\beta_{1}^{i},\dots,\beta_{p^{i}}^{i}$ are known and all roots of the
equations $z^{p^{i}}-\beta_{1}^{i}z^{p^{i}-1}-\cdots-\beta_{p^{i}}^{i}=0$ are
in the interior of the unit circle, so that the AR($p^{i}$) processes are
stable. Let $\varphi(x)=(2\pi)^{-1/2}\,e^{-x^{2}/2}$ denote density of the
standard normal distribution. Define the $p_{n}^{i}$-th order residual

$\widetilde{X}_{n}^{i}=X_{n}^{i}-\sum_{j=1}^{p_{n}^{i}}\beta_{j}^{i}X_{n-j}^{i},\quad
n\geqslant 1,$

where $p_{n}^{i}=p^{i}$ if $n>p^{i}$ and $p_{n}^{i}=n$ if $n\leqslant p^{i}$.
Write $\theta=(\theta_{1},\dots,\theta_{N})$ and
$\Theta=(0,\infty)\times\cdots\times(0,\infty)$ ($N$ times). It is easy to see
that the conditional pre-change density is

$g(X_{n}|{\mathbf{X}}^{n-1})=\prod_{i=1}^{N}\varphi(\widetilde{X}_{n}^{i})$

and the post-change density is

$f_{\theta}(X_{n}|{\mathbf{X}}^{n-1})=\prod_{i=1}^{N}\varphi(\widetilde{X}_{n}^{i}-\theta_{i}\widetilde{S}_{n}^{i}),\quad\theta\in\Theta,$

where
$\widetilde{S}_{n}^{i}=S_{n}^{i}-\sum_{j=1}^{p_{n}^{i}}\beta_{j}^{i}S_{n-j}^{i}$.
Obviously, due to the independence of the data across channels for all
$k\in\mathbb{Z}_{+}$ and $n\geqslant 1$ the LLR has the form

$\lambda_{k,k+n}(\vartheta)=\sum_{i=1}^{N}\left[\vartheta_{i}\sum_{j=k+1}^{k+n}\widetilde{S}_{j}^{i}\widetilde{X}_{j}^{i}-\frac{\vartheta_{i}^{2}\sum_{j=k+1}^{k+n}(\widetilde{S}_{j}^{i})^{2}}{2}\right].$

Under measure ${\mathsf{P}}_{k,\theta}$ the random variables
$\\{\widetilde{X}_{n}^{i}\\}_{n\geqslant k+1}$ are independent Gaussian random
variables with mean
${\mathsf{E}}_{k,\theta}[\widetilde{X}_{n}^{i}]=\theta_{i}\widetilde{S}_{n}^{i}$
and unit variance, and hence, under ${\mathsf{P}}_{k,\theta}$ the normalized
LLR can be written as

$\begin{split}\frac{1}{n}\lambda_{k,k+n}(\vartheta,\theta)&=\sum_{i=1}^{N}\frac{\vartheta_{i}\theta_{i}-\vartheta_{i}^{2}/2}{n}\sum_{j=k+1}^{k+n}(\widetilde{S}_{j}^{i})^{2}\\\
&\quad+\frac{1}{n}\vartheta_{i}\sum_{j=k+1}^{k+n}\widetilde{S}_{j}^{i}\eta_{j}^{i},\end{split}$
(55)

where $\\{\eta_{j}^{i}\\}_{j\geqslant k+1}$, $i=1,\dots,N$, are mutually
independent sequences of i.i.d. standard normal random variables.

Assume that

$\lim_{n\to\infty}\frac{1}{n}\sup_{k\in\mathbb{Z}_{+}}\sum_{j=k+1}^{k+n}|\widetilde{S}_{j}^{i}|^{2}=Q_{i},$
(56)

where $0<Q_{i}<\infty$. This is typically the case in most signal processing
applications, e.g., for harmonic signals
$S_{n}^{i}=\sin(\omega_{i}n+\phi_{n}^{i})$. Then for all $k\in\mathbb{Z}_{+}$
and $\theta\in\Theta$

$\frac{1}{n}\lambda_{k,k+n}(\theta)\xrightarrow[n\to\infty]{{\mathsf{P}}_{k,\theta}-\text{a.s.}}\sum_{i=1}^{N}\frac{\theta_{i}^{2}Q_{i}}{2}=I_{\theta},$

so that condition ${\mathbf{C}}_{1}$ holds. Furthermore, since all moments of
the LLR are finite it is straightforward to show that conditions (52) and
(53), and hence, conditions ${\mathbf{C}}_{2}$ and ${\mathbf{C}}_{3}$ hold for
all $r\geqslant 1$. Indeed, using (55), we obtain that
$I(\vartheta,\theta)=\sum_{i=1}^{N}(\vartheta_{i}\theta_{i}-\vartheta_{i}^{2}/2)Q_{i}$
and for any $\delta>0$

$\displaystyle{\mathsf{P}}_{k,\theta}\left(\sup_{\vartheta\in[\theta-\delta,\theta+\delta]}\left|\frac{1}{n}\lambda_{k,k+n}(\vartheta)-I(\vartheta,\theta)\right|>\varepsilon\right)$
$\displaystyle={\mathsf{P}}_{k,\theta}\left(|Y_{k,n}(\theta)|>\varepsilon\sqrt{n}\right),$

where

$Y_{k,n}(\theta)=\sum_{i=1}^{N}\frac{\theta_{i}}{\sqrt{n}}\sum_{j=k+1}^{k+n}\widetilde{S}_{j}^{i}\eta_{j}^{i},\quad
n\geqslant 1$

is the sequence of normal random variables with mean zero and variance
$\sigma_{n}^{2}=n^{-1}\sum_{i=1}^{N}\theta_{i}^{2}\sum_{j=k+1}^{k+n}(\widetilde{S}_{j}^{i})^{2}$,
which by (56) is asymptotic to $\sum_{i=1}^{N}\theta_{i}^{2}Q_{i}$. Thus, for
a sufficiently large $n$ there exists $\delta_{0}>0$ such that
$\sigma^{2}_{n}\leqslant\delta_{0}+\sum_{i=1}^{N}\theta_{i}^{2}Q_{i}$ and we
obtain that for all large $n$

$\displaystyle{\mathsf{P}}_{k,\theta}\left(\sup_{\vartheta\in[\theta-\delta,\theta+\delta]}\left|\frac{1}{n}\lambda_{k,k+n}(\vartheta)-I(\vartheta,\theta)\right|>\varepsilon\right)$
$\displaystyle\leqslant{\mathsf{P}}\left(|\hat{\eta}|>\frac{\delta_{0}+\sum_{i=1}^{N}\theta_{i}^{2}Q_{i}}{\sigma_{n}^{2}}\frac{\varepsilon\sqrt{n}}{\delta_{0}+\sum_{i=1}^{N}\theta_{i}^{2}Q_{i}}\right),$
$\displaystyle\leqslant{\mathsf{P}}\left(|\hat{\eta}|>\frac{\varepsilon\sqrt{n}}{\delta_{0}+\sum_{i=1}^{N}\theta_{i}^{2}Q_{i}}\right),$

where $\hat{\eta}\sim{\mathcal{N}}(0,1)$ is a standard normal random variable.
Hence, for all $r\geqslant 1$

$\displaystyle\sum_{n=1}^{\infty}\,n^{r-1}\,\sup_{k\in\mathbb{Z}_{+}}\,\sup_{\theta\in\Theta_{c}}{\mathsf{P}}_{k,\theta}\Big{(}\sup_{\vartheta\in[\theta-\delta,\theta+\delta]}\Big{|}\frac{1}{n}\lambda_{k,k+n}(\vartheta)$
$\displaystyle-I(\vartheta,\theta)\Big{|}>\varepsilon\Big{)}<\infty,$

which implies (53) for all $r\geqslant 1$.

Thus, the MS rule minimizes as $\alpha\to 0$ all positive moments of the
detection delay. All asymptotic assertions for the MSR rule presented in
Section V also hold with $I_{\theta}=\sum_{i=1}^{N}\theta_{i}^{2}Q_{i}/2$. In
particular, by Theorem 4, the MSR rule is also asymptotically optimal for all
$r\geqslant 1$ if the prior distribution of the change point is either heavy-
tailed or asymptotically flat.

Since by condition ${\mathbf{C}}_{2}$ the MS and MSR procedures are
asymptotically optimal for almost arbitrary mixing distribution $W(\theta)$,
in this example it is most convenient to select the conjugate prior,
$W(\theta)=\prod_{i=1}^{N}F(\theta_{i}/v_{i})$, where $F(y)$ is a standard
normal distribution and $v_{i}>0$, in which case the MS and MSR statistics can
be computed explicitly.

Note that this example arises in certain interesting practical applications,
as discussed in [33]. For example, surveillance systems (radar, acoustic,
EO/IR) typically deal with detecting moving and maneuvering targets that
appear at unknown times, and it is necessary to detect a signal from a
randomly appearing target in clutter and noise with the smallest possible
delay. In radar applications, often the signal represents a sequence of
modulated pulses and clutter/noise can be modeled as a Markov Gaussian process
or more generally as a $p$-th order Markov process (see, e.g, [36, 50]). In
underwater detection of objects with active sonars, reverberation creates very
strong clutter that represents a correlated process in time [51], so that
again the problem can be reduced to detection of a signal with an unknown
intensity in correlated clutter. In applications related to detection of point
and slightly extended objects with EO/IR sensors (on moving and still
platforms such as space-based, airborne, ship-board, ground-based), sequences
of images usually contain a cluttered background which is correlated in space
and time, and it is a challenge to detect and track weak objects in correlated
clutter [44].

Yet another challenging application area where the multichannel model is
useful is cyber-security [46, 47, 49]. Malicious intrusion attempts in
computer networks (spam campaigns, personal data theft, worms, distributed
denial-of-service (DDoS) attacks, etc.) incur significant financial damage and
are a severe harm to the integrity of personal information. It is therefore
essential to devise automated techniques to detect computer network intrusions
as quickly as possible so that an appropriate response can be provided and the
negative consequences for the users are eliminated. In particular, DDoS
attacks typically involve many traffic streams resulting in a large number of
packets aimed at congesting the target’s server or network. As a result, these
attacks usually lead to abrupt changes in network traffic and can be detected
by noticing a change in the average number of packets sent through the
victim’s link per unit time. Figure 1 illustrates how the multichannel anomaly
Intrusion Detection System works for detecting a real UDP packet storm. The
multichannel MSR algorithm with the AR$(1)$ model and uniform prior
$W(\theta_{i})$ on a finite interval $[1,5]$ was used. The first plot shows
packet rate. It is seen that there is a slight change in the mean, which is
barely visible. The second plot shows the behavior of the multi-cyclic MSR
statistic $W_{n}=\log R_{n}^{W}$, which is restarted from scratch every time a
threshold exceedance occurs. Threshold exceedances before the UDP DDoS attack
starts (i.e., false alarms) are shown by green dots and the true detections
are marked by red dots.

Figure 1: Detection of the UDP DDoS packet storm attack: upper picture — raw
data (packet rate); bottom — log of the MSR statistic.

######  Example 2 (Detection of Changes in a Hidden Markov Model).

The following example, which deals with a two-state hidden Markov model with
i.i.d. observations in each state may be of interest, in particular, for rapid
detection and tracking of sudden spurts and downfalls in activity profiles of
terrorist groups that could be caused by various factors such as changes in
the organizational dynamics of terrorist groups, counterterrorism activity,
changing socio-economic and political contexts, etc. In [52], based on the
analysis of real data from Fuerzas Armadas Revolucionarias de Colombia (FARC)
terrorist group from Colombia (RDWTI) it was shown that two-state HMMs can be
recommended for detecting and tracking sudden changes in activity profiles of
terrorist groups. The HMM framework provides good explanation capability of
past/future activity across a large set of terrorist groups with different
ideological attributes.

Specifically, let $\upsilon_{n}\in\\{1,2\\}$ be a two-state Markov chain with
the transition matrix

$\displaystyle[P_{\theta}(\upsilon_{n-1}=i,\upsilon_{n}=l)]=\left[\begin{array}[]{cc}1-\beta_{\theta}&\beta_{\theta}\\\
\gamma_{\theta}&1-\gamma_{\theta}\end{array}\right]$

and stationary initial distribution
${\mathsf{P}}_{\theta}(\upsilon_{0}=2)=1-{\mathsf{P}}_{\theta}(\upsilon_{0}=1)=\pi_{\theta}(2)=\gamma_{\theta}/(\beta_{\theta}+\gamma_{\theta})$
for some $\beta_{\theta},\gamma_{\theta}\in[0,1]$, where the parameter
$\theta$ equals $\theta_{0}$ in the pre-change mode ($\theta_{0}$ is known)
and $\theta\in\Theta$ in the post-change mode (unknown). Suppose that
conditioned on $\upsilon_{n}$ the observations $X_{n}$ are i.i.d. with
densities $p_{\theta}(X_{n}|\upsilon_{n}=l)=p_{\theta}^{(l)}(X_{n})$, $l=1,2$.

Introduce the probabilities
$P_{\theta,n}:={\mathsf{P}}_{\theta}({\mathbf{X}}^{n},\upsilon_{n}=2)$ and
$\widetilde{P}_{\theta,n}:={\mathsf{P}}_{\theta}({\mathbf{X}}^{n},\upsilon_{n}=1)$.
Straightforward computations show that for $n\geqslant 1$

$\displaystyle P_{\theta,n}$
$\displaystyle=\left[P_{\theta,n-1}\,(1-\gamma_{\theta})+\widetilde{P}_{\theta,n-1}\,\beta_{\theta}\right]\,p_{\theta}^{(2)}(X_{n});$
$\displaystyle\widetilde{P}_{\theta,n}$
$\displaystyle=\left[P_{\theta,n-1}\,\gamma_{\theta}+\widetilde{P}_{\theta,n-1}\,(1-\beta_{\theta})\right]\,p_{\theta}^{(1)}(X_{n})$

with initial values $P_{\theta,0}=\pi_{\theta}(2)$ and
$\widetilde{P}_{\theta,0}=\pi_{\theta}(1)=1-\pi_{\theta}(2)$. Denote
$p_{0,\theta}({\mathbf{X}}^{n})=p_{\theta}({\mathbf{X}}^{n})$ and
$p_{\infty}({\mathbf{X}}^{n})=p_{\theta_{0}}({\mathbf{X}}^{n})$. Since
$p_{\theta}({\mathbf{X}}^{n})=P_{\theta,n}+\widetilde{P}_{\theta,n}$ we obtain
that

$p_{k,\theta}({\mathbf{X}}_{k+1}^{n}|{\mathbf{X}}_{0}^{k})=\frac{P_{\theta,n}+\widetilde{P}_{\theta,n}}{P_{\theta,k}+\widetilde{P}_{\theta,k}}$

and

$\lambda_{k,k+n}(\theta)=\log\left(\frac{P_{\theta,k+n}+\widetilde{P}_{\theta,k+n}}{P_{\theta_{0},k+n}+\widetilde{P}_{\theta_{0},k+n}}\cdot\frac{P_{\theta_{0},k}+\widetilde{P}_{\theta_{0},k}}{P_{\theta,k}+\widetilde{P}_{\theta,k}}\right).$

For the sake of simplicity, consider now the symmetric case where
$\beta_{\theta}=\gamma_{\theta}=1/2$ for all $\theta\in\Theta+\theta_{0}$.
Then

$\displaystyle P_{\theta,n}$
$\displaystyle=\frac{1}{2^{n}}p_{\theta}^{(2)}(X_{n})\prod_{i=1}^{n-1}\left[p_{\theta}^{(1)}(X_{n})+p_{\theta}^{(2)}(X_{n})\right],$
$\displaystyle\widetilde{P}_{\theta,n}$
$\displaystyle=\frac{1}{2^{n}}p_{\theta}^{(1)}(X_{n})\prod_{i=1}^{n-1}\left[p_{\theta}^{(1)}(X_{n})+p_{\theta}^{(2)}(X_{n})\right]$

and we obtain that the LLR is

$\lambda_{k,k+n}(\theta)=\sum_{i=k+1}^{k+n}\log\left(\frac{p_{\theta}^{(1)}(X_{i})+p_{\theta}^{(2)}(X_{i})}{p_{\theta_{0}}^{(1)}(X_{i})+p_{\theta_{0}}^{(2)}(X_{i})}\right).$

Condition ${\mathbf{C}}_{1}$ holds with

$I_{\theta}=\int\log\left(\frac{p_{\theta}^{(1)}(x)+p_{\theta}^{(2)}(x)}{p_{\theta_{0}}^{(1)}(x)+p_{\theta_{0}}^{(2)}(x)}\right)\frac{p_{\theta}^{(1)}(x)+p_{\theta}^{(2)}(x)}{2}\,\mathrm{d}x$

being the Kullback–Leibler information number since by the SLLN
$n^{-1}\lambda_{k,k+n}(\theta)\to I_{\theta}$ ${\mathsf{P}}_{k,\theta}$-a.s.
(assuming that $I_{\theta}<\infty$). Condition (52) usually holds if the
$(r+1)$-th absolute moment of the increment of the LLR is finite:

$\displaystyle\int\left|\log\left(\frac{p_{\theta}^{(1)}(x)+p_{\theta}^{(2)}(x)}{p_{\theta_{0}}^{(1)}(x)+p_{\theta_{0}}^{(2)}(x)}\right)\right|^{r+1}\times$
$\displaystyle\frac{1}{2}\left[p_{\theta}^{(1)}(x)+p_{\theta}^{(2)}(x)\right]\,\mathrm{d}x<\infty.$

This is the case, for example, if the observations are Gaussian with unit
variance and different mean values in pre- and post-change modes as well as
for different states, i.e.,
$p_{\theta}^{(l)}(y)=\varphi(y-\mu_{\theta}^{(l)})$ ($\theta=\theta_{0}$ or
$\theta\neq\theta_{0}$, $l=1,2$). It is easily verified that the
Kullback–Leibler number $I_{\theta}$ is finite and that condition (52) is
satisfied for all $r\geqslant 1$. Therefore, in this case, the MS and MSR
detection rules are asymptotically optimal, minimizing asymptotically all
positive moments of the detection delay.

##  VIII Concluding Remarks

1\. In the case where the increments $\\{\Delta\lambda_{i}(\theta)\\}$ of the
LLR $\lambda_{k,n}(\theta)=\sum_{i=k+1}^{n}\Delta\lambda_{i}(\theta)$ are
independent (but not necessarily identically distributed), condition
${\mathbf{C}}_{2}$ in Theorem 1 and Theorem 3 and condition ${\mathbf{C}}_{3}$
in Theorem 2 and Theorem 4 can be relaxed in the following condition: for all
$\ell\geqslant k$ and $k\in\mathbb{Z}_{+}$

${\mathsf{P}}_{k,\theta}\left(\frac{1}{n}\int_{\Gamma_{\delta,\theta}}\lambda_{\ell,\ell+n}(\vartheta)\,\mathrm{d}W(\vartheta)<I_{\theta}-\varepsilon\right)\xrightarrow[n\to\infty]{}0.$
(57)

More specifically, the MS rule asymptotically minimizes all moments of the
delay to detection under the right-tail and left-tail conditions
${\mathbf{C}}_{1}$ and (57). Also, assertions of Theorem 2 and Theorem 4 for
the MSR rule hold for all $r\geqslant 1$ under conditions ${\mathbf{C}}_{1}$
and (57). The proof can be built by considering the cycles
$[k+(n-1)N_{A},k+nN_{A}]$, $n=1,2,\dots$ of the length $N_{A}=1+\lfloor\log
A/(I_{\theta}+\mu-\varepsilon)\rfloor$ and slightly modifying of the technique
developed by Tartakovsky [26] in the case of complete knowledge of the post-
change distribution.

2\. Since we do not assume a class of models for the observations such as
Gaussian, Markov or HMM and build the decision statistics on the LLR process
$\lambda_{k,k+n}(\theta)$, it is natural to impose conditions on the behavior
of $\lambda_{k,k+n}(\theta)$, which is expressed by conditions
${\mathbf{C}}_{1}$, ${\mathbf{C}}_{2}$ and ${\mathbf{C}}_{3}$, related to the
law of large numbers for the LLR and rates of convergence in the law of large
numbers. The assertions of Theorems 1–4 hold if
$n^{-1}\lambda_{k,k+n}(\theta)$ and $n^{-1}\log\Lambda_{k,k+n}^{W}$ converge
uniformly $r$-completely to $I_{\theta}$ under ${\mathsf{P}}_{k,\theta}$,
i.e., when for all $\varepsilon>0$ and $\theta\in\Theta$

$\displaystyle\sum_{n=1}^{\infty}\,n^{r-1}\,\sup_{k\in\mathbb{Z}_{+}}{\mathsf{P}}_{k,\theta}\left(\left|\frac{1}{n}\lambda_{k,k+n}(\theta)-I_{\theta}\right|>\varepsilon\right)<\infty,$
$\displaystyle\sum_{n=1}^{\infty}\,n^{r-1}\,\sup_{k\in\mathbb{Z}_{+}}{\mathsf{P}}_{k,\theta}\left(\left|\frac{1}{n}\log\Lambda_{k,k+n}^{W}-I_{\theta}\right|>\varepsilon\right)<\infty.$
(58)

However, verifying the $r$-complete convergence condition (58) for the
weighted LLR $\log\Lambda_{k,k+n}^{W}$ is typically much more difficult than
checking conditions ${\mathbf{C}}_{2}$ and ${\mathbf{C}}_{3}$ for the local
values of the LLR in the vicinity of the true parameter value. For the simple
post-change hypothesis, sufficient conditions for the class of ergodic Markov
models are given in [29] and for HMMs in [27]. In these cases, the LLR process
is a Markov random walk and one of the key conditions is finiteness of the
$(r+1)$-th moment of its increment.

3\. As expected, the results indicate that the MSR rule is not asymptotically
optimal when the prior distribution of the change point has an exponential
tail (i.e., $\mu>0$), but it is asymptotically optimal for heavy-tailed prior
distributions (i.e., $\mu=0$) and also when $\mu\to 0$ with a certain rate.

4\. The results show that first-order asymptotic optimality properties of the
MS and MSR procedures hold for practically arbitrary weight function
$W(\theta)$, in particular for any prior that has strictly positive values on
$\Theta$. Therefore, the selection of $W(\theta)$ can be based solely on the
computational aspects. The conjugate prior is typically the best choice when
possible. However, if the parameter is vector and the parameter space is
intricate, constructing mixture statistics may be difficult. In this case,
discretizing the parameter space and selecting the prior
$W(\theta=\theta_{i})$ concentrated on discrete points $\theta_{i}$,
$i=1,\dots,N$, suggested and discussed in [53] for the hypothesis testing
problems, is perhaps the best option. Then one can easily compute the MS and
MSR statistics (as long as the LR $\Lambda_{k,k+n}(\theta)$ can be computed)
at the expense of losing optimality between the points $\theta_{i}$ since the
resulting discrete versions are asymptotically optimal only at the points
$\theta_{i}$.

## Acknowledgement

The author would like to thank Prof. Sergey Pergamenchtchikov for pointing out
that conditions (52) and (53) are sufficient for condition ${\mathbf{C}}_{3}$,
which was useful in verification of ${\mathbf{C}}_{3}$ in examples. Thanks
also go to referees whose comments improved the presentation.

## Appendix: Proofs

###### Proof:

For $\varepsilon\in(0,1)$ and $\delta>0$, define
$N_{\alpha}=N_{\alpha}(\varepsilon,\delta,\theta)=(1-\varepsilon)|\log\alpha|/(I_{\theta}+\mu+\delta)$.
By the Chebyshev inequality,

$\displaystyle{\mathcal{R}}_{k,\theta}^{r}(T)\geqslant{\mathsf{E}}_{k,\theta}[(T-k)^{+}]^{r}$
$\displaystyle\geqslant N_{\alpha}^{r}{\mathsf{P}}_{k,\theta}(T-k>N_{\alpha})$
$\displaystyle\geqslant
N_{\alpha}^{r}\left[{\mathsf{P}}_{k,\theta}(T>k)-{\mathsf{P}}_{k,\theta}(k<T<k+N_{\alpha})\right],$

where ${\mathsf{P}}_{k,\theta}(T>k)={\mathsf{P}}_{\infty}(T>k)$, so that

$\begin{split}&\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathcal{R}}_{k,\theta}^{r}(T)\\\
&\geqslant
N_{\alpha}^{r}\Big{[}\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathsf{P}}_{\infty}(T>k)\\\
&-\sup_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathsf{P}}_{k,\theta}(k<T<k+N_{\alpha})\Big{]}.\end{split}$
(A.1)

Thus, to prove the lower bound (22) we need to show that, for arbitrary small
$\varepsilon$ and $\delta$ and all fixed $k\in\mathbb{Z}_{+}$,

$\lim_{\alpha\to
0}\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathsf{P}}_{\infty}(T>k)=1$ (A.2)

and

$\lim_{\alpha\to
0}\sup_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathsf{P}}_{k,\theta}(k<T<k+N_{\alpha})=0.$
(A.3)

First, note that

$\alpha\geqslant\sum_{i=k}^{\infty}\pi_{i}{\mathsf{P}}_{\infty}(T\leqslant
i)\geqslant{\mathsf{P}}_{\infty}(T\leqslant k){\mathsf{P}}(\nu\geqslant k),$

and hence,

$\inf_{T\in{\mathbb{C}}(\alpha,\pi)}{\mathsf{P}}_{\infty}(T>k)\geqslant
1-\alpha/{\mathsf{P}}(\nu\geqslant k),~{}~{}k\in\mathbb{Z}_{+},$ (A.4)

which approaches $1$ as $\alpha\to 0$ for any fixed $k\in\mathbb{Z}_{+}$.
Thus, (A.2) follows.

Now, introduce

$\displaystyle U_{\alpha,k}(T)$
$\displaystyle=e^{(1+\varepsilon)I_{\theta}N_{\alpha}}{\mathsf{P}}_{\infty}\left(k<T<k+N_{\alpha}\right),$
$\displaystyle\beta_{\alpha,k}(\theta)$
$\displaystyle={\mathsf{P}}_{k,\theta}\left(\frac{1}{N_{\alpha}}\max_{1\leqslant
n\leqslant
N_{\alpha}}\lambda_{k,k+n}(\theta)\geqslant(1+\varepsilon)\,I_{\theta}\right).$

By inequality (3.6) in [24],

${\mathsf{P}}_{k,\theta}\left(k<T<k+N_{\alpha}\right)\leqslant
U_{\alpha,k}(T)+\beta_{\alpha,k}(\theta).$ (A.5)

Using inequality (A.4) and the fact that by condition (17), for all
sufficiently large $N_{\alpha}$ (small $\alpha$), there exists a (small)
$\delta$ such that

$\frac{|\log{\mathsf{P}}(\nu>k+N_{\alpha})|}{k+N_{\alpha}}\leqslant\mu+\delta,$

in just the same way as in the proof of Lemma 1 in [26] we obtain that for a
sufficiently small $\alpha$

$\displaystyle\sup_{T\in{\mathbb{C}}(\alpha,\pi)}U_{\alpha,k}(T)\leqslant\exp\left\\{-\frac{I_{\theta}\varepsilon^{2}|\log\alpha|}{I_{\theta}+\mu+\delta}+(\mu+\delta)k\right\\}.$
(A.6)

The right-hand side approaches zero as $\alpha\to 0$ for any fixed
$k\in\mathbb{Z}_{+}$ and any $\varepsilon>0$ and $\delta>0$. Also, by
condition ${\mathbf{C}}_{1}$, $\beta_{\alpha,k}(\theta)\to 0$ for all
$k\in\mathbb{Z}_{+}$, and therefore, (A.3) holds. This completes the proof of
the lower bound (22). ∎

###### Proof:

(i) For $k\in\mathbb{Z}_{+}$, define the stopping times

$\displaystyle\tau_{A}^{(k)}=$ $\displaystyle\inf\\{n\geqslant
1:\log\Lambda_{k,k+n}^{W}+|\log{\mathsf{P}}(\nu\geqslant k+n)|$
$\displaystyle\quad\geqslant\log(A/\pi_{k})\\}.$

Obviously, for any $n>k$,

$\displaystyle\log S_{n}^{W}$
$\displaystyle\geqslant\log\left(\frac{\pi_{k}}{{\mathsf{P}}(\nu\geqslant
n)}\Lambda_{k,n}^{W}\right)$
$\displaystyle=\log\Lambda_{k,n}^{W}+\log\pi_{k}-\log{\mathsf{P}}(\nu\geqslant
n),$

and hence, for every $A>0$, $(T_{A}-k)^{+}\leqslant\tau_{A}^{(k)}$.

Let
$N_{A}=N_{A}(\varepsilon,\theta)=1+\lfloor\log(A/\pi_{k})/(I_{\theta}+\mu-\varepsilon)\rfloor$.
Using the same chain of equalities and inequalities as in (A.5) in [26], we
obtain that for any $k\in\mathbb{Z}_{+}$ the following inequality holds:

$\displaystyle{\mathsf{E}}_{k,\theta}\left[(T_{A}-k)^{+}\right]^{r}\leqslant{\mathsf{E}}_{k,\theta}\left[\left(\tau_{A}^{(k)}\right)^{r}\right]$
$\displaystyle\leqslant
N_{A}^{r}+r2^{r-1}\sum_{n=N_{A}}^{\infty}n^{r-1}{\mathsf{P}}_{k,\theta}\left(\tau_{A}^{(k)}>n\right).$
(A.7)

It is easily seen that for all $k\in\mathbb{Z}_{+}$ and $n\geqslant N_{A}$

$\displaystyle{\mathsf{P}}_{k,\theta}\left(\tau_{A}^{(k)}>n\right)$
$\displaystyle\leqslant{\mathsf{P}}_{k,\theta}\Bigg{\\{}\frac{\log\Lambda_{k,k+n}^{W}}{n}<\frac{1}{n}\log\left(\frac{A}{\pi_{k}}\right)$
$\displaystyle-\frac{|\log{\mathsf{P}}(\nu\geqslant k+n)|}{n}\Bigg{\\}}$
$\displaystyle\leqslant{\mathsf{P}}_{k,\theta}\Bigg{\\{}\frac{\log\Lambda_{k,k+n}^{W}}{n}<I_{\theta}+\mu-\varepsilon$
$\displaystyle-\frac{|\log{\mathsf{P}}(\nu\geqslant k+n)|}{n}\Bigg{\\}}.$

Since, by condition $\mathbf{CP1}$, $N_{A}^{-1}|\log{\mathsf{P}}(\nu\geqslant
k+N_{A})|\to\mu$ as $A\to\infty$, for a sufficiently large value of $A$ there
exists a small $\kappa=\kappa_{A}$ ($\kappa_{A}\to 0$ as $A\to\infty$) such
that

$\left|\mu-\frac{|\log{\mathsf{P}}(\nu\geqslant
k+N_{A})|}{N_{A}}\right|<\kappa.$

Hence, for all sufficiently large $A$,

${\mathsf{P}}_{k,\theta}\left(\tau_{A}^{(k)}>n\right)\leqslant{\mathsf{P}}_{k,\theta}\left(\frac{1}{n}\log\Lambda_{k,k+n}^{W}<I_{\theta}-\varepsilon-\kappa\right).$

Also,

$\log\Lambda_{k,k+n}^{W}\geqslant\inf_{\vartheta\in\Gamma_{\delta,\theta}}\lambda_{k,k+n}(\vartheta)+\log
W(\Gamma_{\delta,\theta}),$

where
$\Gamma_{\delta,\theta}=\\{\vartheta\in\Theta\,:\,|\vartheta-\theta|<\delta\\}$.
Thus, for all sufficiently large $n$ and $\varepsilon_{1}>0$,

$\displaystyle{\mathsf{P}}_{k,\theta}\left(\tau_{A}^{(k)}>n\right)\leqslant{\mathsf{P}}_{k,\theta}\Big{(}\frac{1}{n}\inf_{\vartheta\in\Gamma_{\delta,\theta}}\lambda_{k,k+n}(\vartheta)$
$\displaystyle<I_{\theta}-\varepsilon-\kappa-\frac{1}{n}\log
W(\Gamma_{\delta,\theta})\Big{)}$
$\displaystyle\leqslant{\mathsf{P}}_{k,\theta}\left(\frac{1}{n}\inf_{\vartheta\in\Gamma_{\delta,\theta}}\lambda_{k,k+n}(\vartheta)<I_{\theta}-\varepsilon_{1}\right).$
(A.8)

Using (Proof:), (A.8), and inequality
${\mathsf{P}}_{\infty}(T_{A}>k)>1-[A{\mathsf{P}}(\nu>k)]^{-1}$ (see (A.4)), we
obtain

$\displaystyle{\mathcal{R}}_{k,\theta}^{r}(T_{A})=\frac{{\mathsf{E}}_{k,\theta}\left[\left(T_{A}-k\right)^{+}\right]^{r}}{{\mathsf{P}}_{\infty}(T_{A}>k)}$
$\displaystyle\leqslant\frac{\left(1+\left\lfloor\frac{\log(A/\pi_{k})}{I_{\theta}+\mu-\varepsilon}\right\rfloor\right)^{r}+r2^{r-1}\,\Upsilon_{k,r}(\theta,\varepsilon_{1})}{1-1/(A{\mathsf{P}}(\nu\geqslant
k))}.$ (A.9)

Since, by condition ${\mathbf{C}}_{2}$,
$\Upsilon_{k,r}(\theta,\varepsilon_{1})<\infty$ for all $k\in\mathbb{Z}_{+}$
and $\theta\in\Theta$, this implies the asymptotic upper bound

${\mathcal{R}}_{k,\theta}^{m}(T_{A})\leqslant\left(\frac{\log
A}{I_{\theta}+\mu}\right)^{m}(1+o(1)),\quad A\to\infty$ (A.10)

(for all $0<m\leqslant r$ and $\theta\in\Theta$), which along with the lower
bound

${\mathcal{R}}_{k,\theta}^{m}(T_{A})\geqslant\left(\frac{\log
A}{I_{\theta}+\mu}\right)^{m}(1+o(1)),\quad A\to\infty$ (A.11)

proves the asymptotic relation (26). Note that the lower bound (A.11) follows
immediately from the lower bound (23) in Lemma 1 by replacing $\alpha$ with
$1/(A+1)$ since it follows from (24) that $T_{A}\in\mathbb{C}(1/(A+1),\pi)$.

We now get to proving (27). Since the MS rule $T_{A}$ belongs to class
$\mathbb{C}(1/(A+1),\pi)$, replacing $\alpha$ by $1/(A+1)$ in the asymptotic
lower bound (22), we obtain that under the right-tail condition
${\mathbf{C}}_{1}$ the following asymptotic lower bound holds for all $r>0$
and $\theta\in\Theta$:

${\bar{\mathcal{R}}}_{\pi,\theta}^{r}(T_{A})\geqslant\left(\frac{\log
A}{I_{\theta}+\mu}\right)^{r}(1+o(1)),~{}~{}A\to\infty.$ (A.12)

Thus, to prove (27) it suffices to show that, under the left-tail condition
${\mathbf{C}}_{2}$, for $0<m\leqslant r$ and $\theta\in\Theta$

${\bar{\mathcal{R}}}_{\pi,\theta}^{m}(T_{A})\leqslant\left(\frac{\log
A}{I_{\theta}+\mu}\right)^{m}(1+o(1),~{}~{}A\to\infty.$ (A.13)

Using (Proof:) and (A.8), we obtain that for any
$0<\varepsilon<I_{\theta}+\mu$

$\begin{split}&{\mathsf{E}}^{\pi}_{\theta}[(T_{A}-\nu)^{+}]^{r}=\sum_{k=0}^{\infty}\pi_{k}{\mathsf{E}}_{k,\theta}\left[(T_{A}-k)^{+}\right]^{r}\\\
&\leqslant\sum_{k=0}^{\infty}\pi_{k}\left(1+\frac{\log(A/\pi_{k})}{I_{\theta}+\mu-\varepsilon}\right)^{r}+r2^{r-1}{\displaystyle\sum_{k=0}^{\infty}}\pi_{k}\Upsilon_{k,r}(\theta,\varepsilon_{1}).\end{split}$
(A.14)

This inequality together with the inequality $1-\mathsf{PFA}(T_{A})\geqslant
A/(1+A)$ yields

$\begin{split}&{\bar{\mathcal{R}}}_{\pi,\theta}^{r}(T_{A})=\frac{\sum_{k=0}^{\infty}\pi_{k}{\mathsf{E}}_{k,\theta}\left[(T_{A}-k)^{+}\right]^{r}}{1-\mathsf{PFA}(T_{A})}\\\
&\leqslant\frac{{\displaystyle\sum_{k=0}^{\infty}}\pi_{k}\left(1+\frac{\log(A/\pi_{k})}{I_{\theta}+\mu-\varepsilon}\right)^{r}+r2^{r-1}{\displaystyle\sum_{k=0}^{\infty}}\pi_{k}\Upsilon_{k,r}(\theta,\varepsilon_{1})}{A/(1+A)}.\end{split}$
(A.15)

By condition ${\mathbf{C}}_{2}$,
$\sum_{k=0}^{\infty}\pi_{k}\Upsilon_{k,r}(\theta,\varepsilon_{1})<\infty$ for
any $\varepsilon_{1}>0$ and any $\theta\in\Theta$ and, by condition (18),
$\sum_{k=0}^{\infty}\pi_{k}|\log\pi_{k}|^{r}<\infty$, which implies that, as
$A\to\infty$, for all $0<m\leqslant r$ and all $\theta\in\Theta$

${\bar{\mathcal{R}}}_{\pi,\theta}^{m}(T_{A})\leqslant\left(\frac{\log
A}{I_{\theta}+\mu-\varepsilon}\right)^{r}(1+o(1)).$

Since $\varepsilon$ can be arbitrarily small, the upper bound (A.13) follows
and the proof of the asymptotic expansion (27) is complete.

(ii) Setting $A=A_{\alpha}=(1-\alpha)/\alpha$ in (26) and (27) yields as
$\alpha\to 0$

$\begin{split}{\mathcal{R}}^{m}_{k,\theta}(T_{A_{\alpha}})\sim\left(\frac{|\log\alpha|}{I_{\theta}+\mu}\right)^{m},\\\
{\bar{\mathcal{R}}}^{m}_{\pi,\theta}(T_{A_{\alpha}})\sim\left(\frac{|\log\alpha|}{I_{\theta}+\mu}\right)^{m},\end{split}$
(A.16)

which along with the lower bounds (23) and (22) in Lemma 1 completes the proof
of (28) and (29). Obviously, all assertions in (ii) are correct if threshold
$A_{\alpha}$ is so selected that $T_{A_{\alpha}}\in{\mathbb{C}}(\alpha,\pi)$
and $\log A_{\alpha}\sim|\log\alpha|$ as $\alpha\to 0$. The proof is complete.
∎

###### Proof:

Let
$N_{\alpha}=(1-\varepsilon)|\log\alpha|/(I_{\theta}+\mu_{\alpha}+\delta_{\alpha})$,
where $\delta_{\alpha}>0$ and goes to 0 as $\alpha\to 0$. Analogously to
(A.1),

$\begin{split}&\inf_{T\in{\mathbb{C}}(\alpha)}{\mathcal{R}}_{k,\theta}^{r}(T)\\\
&\geqslant
N_{\alpha}^{r}\Big{[}\inf_{T\in{\mathbb{C}}(\alpha)}{\mathsf{P}}_{\infty}(T>k)\\\
&-\sup_{T\in{\mathbb{C}}(\alpha)}{\mathsf{P}}_{k,\theta}(k<T<k+N_{\alpha})\Big{]}\\\
\geqslant&N_{\alpha}^{r}\Big{[}1-\alpha/{\mathsf{P}}(\nu\geqslant k)\\\
&-\sup_{T\in{\mathbb{C}}(\alpha)}{\mathsf{P}}_{k,\theta}(k<T<k+N_{\alpha})\Big{]},\end{split}$
(A.17)

where we used the fact that
$\inf_{T\in{\mathbb{C}}(\alpha)}{\mathsf{P}}_{\infty}(T>k)\geqslant
1-\alpha/{\mathsf{P}}(\nu\geqslant k)$ (see (A.4)). Using (A.5) and (A.6), we
obtain

$\displaystyle\sup_{T\in{\mathbb{C}}(\alpha)}{\mathsf{P}}_{k,\theta}(k<T<k+N_{\alpha})\leqslant\beta_{\alpha,k}(\theta)$
$\displaystyle+\exp\left\\{-\frac{\varepsilon^{2}I_{\theta}|\log\alpha|}{I_{\theta}+\mu_{\alpha}+\delta_{\alpha}}+(\mu_{\alpha}+\delta_{\alpha})k\right\\}.$

By condition ${\mathbf{C}}_{1}$, $\beta_{\alpha,k}(\theta)$ goes to zero as
$\alpha\to 0$ for all $k\in\mathbb{Z}_{+}$. Obviously, the second term
vanishes as $\alpha\to 0$ for all $\varepsilon\in(0,1)$ and all
$k\in\mathbb{Z}_{+}$. It follows that, for all $k\in\mathbb{Z}_{+}$ and
$\theta\in\Theta$,

$\sup_{T\in{\mathbb{C}}(\alpha)}{\mathsf{P}}_{k,\theta}(k<T<k+N_{\alpha})\to
0\quad\text{as}~{}\alpha\to 0$

and using (A.17) we obtain that for all $0<\varepsilon<1$, $r>0$, and
$\theta\in\Theta$ as $\alpha\to 0$

$\inf_{T\in{\mathbb{C}}(\alpha)}{\mathcal{R}}_{\theta,k}^{r}(T)\geqslant(1-\varepsilon)^{r}\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{r}(1+o(1)).$

Since $\varepsilon$ can be arbitrarily small, the lower bound (31) follows. ∎

###### Proof:

Setting $A=(1-\alpha)/\alpha$ in inequality (A.15), we obtain

$\displaystyle{\bar{\mathcal{R}}}_{\pi^{\alpha},\theta}^{r}(T_{A})\leqslant(1-\alpha)^{-1}\sum_{k=0}^{\infty}\pi_{k}^{\alpha}\left(1+\frac{\log((1-\alpha)/\alpha\pi_{k}^{\alpha})}{I_{\theta}+\mu_{\alpha}-\varepsilon}\right)^{r}$
$\displaystyle+r2^{r-1}\sup_{k\in\mathbb{Z}_{+}}\Upsilon_{k,r}(\theta,\varepsilon_{1}).$

Using conditions (33) and ${\mathbf{C}}_{3}$ and taking into account that
$\mu_{\alpha}\to 0$ as $\alpha\to 0$ yields

${\bar{\mathcal{R}}}_{\pi^{\alpha},\theta}^{r}(T_{A_{\alpha}})\leqslant\left(\frac{|\log\alpha|}{I_{\theta}-\varepsilon}\right)^{r}(1+o(1)).$

Since $\varepsilon$ can be arbitrary small, we obtain the asymptotic upper
bound

${\bar{\mathcal{R}}}_{\pi^{\alpha},\theta}^{r}(T_{A_{\alpha}})\leqslant\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{r}(1+o(1)),$

as $\alpha\to 0$, which along with the lower bound (30) proves (34). Clearly,
this upper bound holds if we take any $A=A_{\alpha}$ such that
$\mathsf{PFA}(T_{A_{\alpha}})\leqslant\alpha$ and $\log
A_{\alpha}\sim|\log\alpha|$ as $\alpha\to 0$.

Next, substituting $A=(1-\alpha)/\alpha$ in (A.9) (or more generally any $A$
such that $\log A\sim|\log\alpha|$ and $\mathsf{PFA}(T_{A})\leqslant\alpha$),
we obtain

$\displaystyle{\mathcal{R}}_{k,\theta}^{r}(T_{A})\leqslant$
$\displaystyle\frac{\left[1+\left\lfloor\log\frac{((\alpha/(1-\alpha)\pi_{k}^{\alpha})}{I_{\theta}+\mu_{\alpha}-\varepsilon}\right\rfloor\right]^{r}+r2^{r-1}\,\Upsilon_{k,r}(\theta,\varepsilon_{1}+\delta_{\alpha})}{1-1/(A{\mathsf{P}}(\nu\geqslant
k))},$

which due to conditions ${\mathbf{C}}_{3}$ and (33) and the fact that
$\mu_{\alpha},\delta_{\alpha}\to 0$ implies that, for all fixed
$k\in\mathbb{Z}_{+}$ and all $\theta\in\Theta$ as $\alpha\to 0$,

${\mathcal{R}}_{k,\theta}^{r}(T_{A})\leqslant\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{r}(1+o(1)).$

This upper bound together with the lower bound (31) yields (35) and the proof
is complete. ∎

###### Proof:

(i) For $\varepsilon\in(0,1)$, let
$M_{A}=M_{A}(\varepsilon,\theta)=(1-\varepsilon)I_{\theta}^{-1}\log A$.
Similarly to (A.1) we obtain

$\begin{split}{\mathcal{R}}_{k,\theta}^{r}(\widetilde{T}_{A})&\geqslant
M_{A}^{r}\big{[}{\mathsf{P}}_{\infty}(\widetilde{T}_{A}>k)\\\
&-{\mathsf{P}}_{k,\theta}(k<\widetilde{T}_{A}<k+M_{A})\big{]}\end{split}$
(A.18)

and similarly to (A.5),

${\mathsf{P}}_{k,\theta}\left(0<\widetilde{T}_{A}-k<M_{A}\right)\leqslant
U_{A,k}(\widetilde{T}_{A})+\beta_{A,k}(\theta),$ (A.19)

where

$\displaystyle U_{A,k}(\widetilde{T}_{A})$
$\displaystyle=e^{(1+\varepsilon)I_{\theta}M_{A}}{\mathsf{P}}_{\infty}\left(0<\widetilde{T}_{A}-k<M_{A}\right),$
$\displaystyle\beta_{A,k}(\theta)$
$\displaystyle={\mathsf{P}}_{k,\theta}\left(\frac{1}{M_{A}}\max_{1\leqslant
n\leqslant
M_{A}}\lambda_{k,k+n}(\theta)\geqslant(1+\varepsilon)\,I_{\theta}\right).$

Since

$\displaystyle{\mathsf{P}}_{\infty}\left(0<\widetilde{T}_{A}-k<M_{A}\right)$
$\displaystyle\leqslant{\mathsf{P}}_{\infty}\left(\widetilde{T}_{A}<k+M_{A}\right)$
$\displaystyle\leqslant(k+\omega+M_{A})/A,$

we have

$U_{A,k}(\widetilde{T}_{A})\leqslant\frac{k+\omega+(1-\varepsilon)I_{\theta}^{-1}\log
A}{A^{\varepsilon^{2}}}.$ (A.20)

Therefore, $U_{A,k}(\widetilde{T}_{A})\to 0$ as $A\to\infty$ for any fixed
$k$. Also, $\beta_{A,k}(\theta)\to 0$ by condition ${\mathbf{C}}_{1}$, so that
${\mathsf{P}}_{k}\left(0<\widetilde{T}_{A}-k<M_{A}\right)\to 0$ for any fixed
$k$. Since ${\mathsf{P}}_{\infty}(\widetilde{T}_{A}>k)>1-(\omega+k)/A$, it
follows from (A.18) that for an arbitrary $\varepsilon\in(0,1)$ as
$A\to\infty$

${\mathcal{R}}_{k,\theta}^{r}(\widetilde{T}_{A})\geqslant\left(\frac{(1-\varepsilon)\log
A}{I_{\theta}}\right)^{r}(1+o(1)),$

which yields the asymptotic lower bound (for any fixed $k\in\mathbb{Z}_{+}$
and $\theta\in\Theta$)

${\mathcal{R}}_{k,\theta}^{r}(\widetilde{T}_{A})\geqslant\left(\frac{\log
A}{I_{\theta}}\right)^{r}(1+o(1)),\quad A\to\infty.$ (A.21)

To prove (37) it suffices to show that

${\mathcal{R}}_{k,\theta}^{r}(\widetilde{T}_{A})\leqslant\left(\frac{\log
A}{I_{\theta}}\right)^{r}(1+o(1)),\quad A\to\infty.$ (A.22)

For $k\in\mathbb{Z}_{+}$, define the stopping times

$\displaystyle\tilde{\tau}_{A}^{(k)}=\inf\\{n\geqslant
1:\log\Lambda_{k,k+n}^{W}\geqslant\log A\\}.$

Obviously, for any $n>k$, $\log R_{n}^{W}\geqslant\log\Lambda_{k,n}^{W}$, and
hence, for every $A>0$,
$(\widetilde{T}_{A}-k)^{+}\leqslant\tilde{\tau}_{A}^{(k)}$. Analogously to
(Proof:), we have

$\displaystyle{\mathsf{E}}_{k,\theta}\left[(\widetilde{T}_{A}-k)^{+}\right]^{r}\leqslant{\mathsf{E}}_{k,\theta}\left[\left(\tilde{\tau}_{A}^{(k)}\right)^{r}\right]$
$\displaystyle\leqslant\widetilde{M}_{A}^{r}+r2^{r-1}\sum_{n=\widetilde{M}_{A}}^{\infty}n^{r-1}{\mathsf{P}}_{k,\theta}\left(\tilde{\tau}_{A}^{(k)}>n\right),$
(A.23)

where
$\widetilde{M}_{A}=\widetilde{M}_{A}(\varepsilon,\theta)=1+\lfloor\log(A)/(I_{\theta}-\varepsilon)\rfloor$.
For a sufficiently large $n$ similarly to (A.8) we have

$\displaystyle{\mathsf{P}}_{k,\theta}\left(\tilde{\tau}_{A}^{(k)}>n\right)\leqslant{\mathsf{P}}_{k,\theta}\left(\frac{1}{n}\inf_{\vartheta\in\Gamma_{\delta,\theta}}\lambda_{k,k+n}(\vartheta)<I_{\theta}-\varepsilon\right).$
(A.24)

Using (Proof:) and (A.24), we obtain the inequality

$\begin{split}&{\mathsf{E}}_{k,\theta}\left[\left(\widetilde{T}_{A}-k\right)^{+}\right]^{r}\\\
&\leqslant\left(1+\left\lfloor\frac{\log
A}{I_{\theta}-\varepsilon}\right\rfloor\right)^{r}+r2^{r-1}\,\Upsilon_{k,r}(\theta,\varepsilon),\end{split}$
(A.25)

which along with the inequality
${\mathsf{P}}_{\infty}(\widetilde{T}_{A}>k)>1-(\omega+k)/A$ implies the
inequality

$\displaystyle{\mathcal{R}}_{k,\theta}^{r}(\widetilde{T}_{A})=\frac{{\mathsf{E}}_{k,\theta}\left[\left(\widetilde{T}_{A}-k\right)^{+}\right]^{r}}{{\mathsf{P}}_{\infty}(\widetilde{T}_{A}>k)}$
$\displaystyle\leqslant\frac{\left(1+\left\lfloor\frac{\log
A}{I_{\theta}-\varepsilon}\right\rfloor\right)^{r}+r2^{r-1}\,\Upsilon_{k,r}(\theta,\varepsilon)}{1-(\omega+k)/A}.$
(A.26)

Since, by condition ${\mathbf{C}}_{2}$,
$\Upsilon_{k,r}(\theta,\varepsilon)<\infty$ for all $k\in\mathbb{Z}_{+}$ and
$\theta\in\Theta$, this implies the asymptotic upper bound (A.22) and
completes the proof of the asymptotic approximation (37).

We now continue with proving (38). By the Chebyshev inequality,

$\displaystyle{\bar{\mathcal{R}}}_{\pi,\theta}^{r}(\widetilde{T}_{A})\geqslant{\mathsf{E}}_{\theta}^{\pi}[(\widetilde{T}_{A}-k)^{+}]^{r}$
$\displaystyle\geqslant
M_{A}^{r}{\mathsf{P}}_{\theta}^{\pi}(\widetilde{T}_{A}-\nu>M_{A})$
$\displaystyle\geqslant
M_{A}^{r}\left[{\mathsf{P}}_{\theta}^{\pi}(\widetilde{T}_{A}>\nu)-{\mathsf{P}}_{\theta}^{\pi}(\nu<T<\nu+M_{A})\right]$
$\displaystyle\geqslant
M_{A}^{r}\left[1-\frac{\bar{\nu}+\omega}{A}-{\mathsf{P}}^{\pi}_{\theta}\left(0<\widetilde{T}_{A}-\nu<M_{A}\right)\right].$
(A.27)

Let $K_{A}$ be an integer number that approaches infinity as $A\to\infty$.
Using (A.19) and (A.20), we obtain the following upper bound

$\displaystyle{\mathsf{P}}^{\pi}_{\theta}(0<\widetilde{T}_{A}-\nu<M_{A})$
$\displaystyle=\sum_{k=0}^{\infty}\pi_{k}{\mathsf{P}}_{k,\theta}\left(0<\widetilde{T}_{A}-k<M_{A}\right)$
$\displaystyle\leqslant{\mathsf{P}}(\nu>K_{A})+\sum_{k=0}^{\infty}\pi_{k}U_{A,k}(\widetilde{T}_{A})+\sum_{k=0}^{K_{A}}\pi_{k}\beta_{A,k}$
$\displaystyle\leqslant{\mathsf{P}}(\nu>K_{A})$
$\displaystyle+\frac{\bar{\nu}+\omega+(1-\varepsilon)I_{\theta}^{-1}\log
A}{A^{\varepsilon^{2}}}+\sum_{k=0}^{K_{A}}\pi_{k}\beta_{A,k},$ (A.28)

where the first two terms go to zero as $A\to\infty$ since $\bar{\nu}$ and
$\omega$ are finite (by Markov’s inequality
${\mathsf{P}}(\nu>K_{A})\leqslant\bar{\nu}/K_{A}$) and the last term also goes
to zero by condition ${\mathbf{C}}_{1}$ and Lebesgue’s dominated convergence
theorem. Thus, for all $0<\varepsilon<1$,
${\mathsf{P}}^{\pi}_{\theta}(0<\widetilde{T}_{A}-\nu<M_{A})$ approaches $0$ as
$A\to\infty$. Using inequality (A.27), we obtain that for any
$0<\varepsilon<1$ as $A\to\infty$

${\bar{\mathcal{R}}}_{\pi,\theta}^{r}(\widetilde{T}_{A})\geqslant(1-\varepsilon)^{r}\left(\frac{\log
A}{I_{\theta}}\right)^{r}(1+o(1)),$

which yields the asymptotic lower bound (for any $r>0$ and $\theta\in\Theta$)

${\bar{\mathcal{R}}}_{\pi,\theta}^{r}(\widetilde{T}_{A})\geqslant\left(\frac{\log
A}{I_{\theta}}\right)^{r}(1+o(1)),\quad A\to\infty.$ (A.29)

To obtain the upper bound it suffices to use inequality (A.25), which along
with the fact that
${\mathsf{P}}^{\pi}(\widetilde{T}_{A}>\nu)>1-(\bar{\nu}+\omega)/A$ yields (for
every $0<\varepsilon<I_{\theta}$)

$\displaystyle{\bar{\mathcal{R}}}_{\pi,\theta}^{r}(\widetilde{T}_{A})=\frac{\sum_{k=0}^{\infty}\pi_{k}{\mathsf{E}}_{k}[(\widetilde{T}_{A}-k)^{+}]^{r}}{{\mathsf{P}}^{\pi}(\widetilde{T}_{A}>\nu)}$
$\displaystyle\leqslant\frac{\left(1+\frac{\log
A}{I_{\theta}-\varepsilon}\right)^{r}+r2^{r-1}\,\sum_{k=0}^{\infty}\pi_{k}\Upsilon_{k,r}(\theta,\varepsilon)}{1-(\omega+\bar{\nu})/A}.$
(A.30)

Since by condition ${\mathbf{C}}_{2}$,

$\sum_{k=0}^{\infty}\pi_{k}\Upsilon_{k,r}(\theta,\varepsilon)<\infty\quad\text{for
any}~{}\varepsilon>0~{}\text{and}~{}\theta\in\Theta,$

we obtain that, for every $0<\varepsilon<I_{\theta}$ as $A\to\infty$,

${\bar{\mathcal{R}}}_{\pi,\theta}^{r}(\widetilde{T}_{A})\leqslant\left(\frac{\log
A}{I_{\theta}-\varepsilon}\right)^{r}(1+o(1)).$

Since $\varepsilon$ can be arbitrarily small, this implies the asymptotic (as
$A\to\infty$) upper bound

${\bar{\mathcal{R}}}_{\pi,\theta}^{r}(\widetilde{T}_{A})\leqslant\left(\frac{\log
A}{I_{\theta}}\right)^{r}(1+o(1)),$ (A.31)

which along with the lower bound (A.29) completes the proof of (i).

(ii) To prove (40) and (39) it suffices to substitute $\log A\sim|\log\alpha|$
(in particular, we may take $A=(b\,\omega+\bar{\nu})/\alpha$) in (38) and
(37). ∎

###### Proof:

Previous results make the proof elementary. Indeed, substitution
$A=A_{\alpha}=(b_{\alpha}\omega_{\alpha}+\bar{\nu}_{\alpha})/\alpha$ in
(Proof:) yields the upper bound

$\displaystyle{\bar{\mathcal{R}}}_{\pi^{\alpha},\theta}^{r}(\widetilde{T}_{A_{\alpha}})\leqslant$
$\displaystyle\frac{\left(1+\frac{\log((\omega_{\alpha}+\bar{\nu}_{\alpha})/\alpha)}{I_{\theta}-\varepsilon}\right)^{r}+r2^{r-1}\,\sup_{k\geqslant
0}\Upsilon_{k,r}(\theta,\varepsilon)}{1-\alpha},$

which implies the asymptotic upper bound

${\bar{\mathcal{R}}}_{\pi^{\alpha},\theta}^{r}(\widetilde{T}_{A_{\alpha}})\leqslant\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{r}(1+o(1)),\quad\alpha\to
0,$

since, by condition (41),
$\log[(\omega_{\alpha}+\bar{\nu}_{\alpha})/\alpha]\sim|\log\alpha|$ and by
condition ${\mathbf{C}}_{3}$, $\sup_{k\geqslant
0}\Upsilon_{k,r}(\theta,\varepsilon)<\infty$ for all $\theta\in\Theta$. This
upper bound along with the lower bound (30) in Lemma 3 proves (42).

Finally, the asymptotic upper bound

$\displaystyle{\mathcal{R}}_{k,\theta}^{r}(\widetilde{T}_{A_{\alpha}})\leqslant\left(\frac{|\log\alpha|}{I_{\theta}}\right)^{r}(1+o(1)),\quad\alpha\to
0,$

for all $k\in\mathbb{Z}_{+}$ and $\theta\in\Theta$ follows immediately from
(A.26) with
$A=A_{\alpha}=(c_{\alpha}\omega_{\alpha}+\bar{\nu}_{\alpha})/\alpha$, which
along with the lower bound (31) in Lemma 3 proves (43). ∎

###### Proof:

Since $\Theta$ is compact it follows from the asymptotic approximation (27) in
Theorem 1 that as $A\to\infty$

$\begin{split}\int_{\Theta}{\bar{\mathcal{R}}}_{\pi,\vartheta}^{r}(T_{A})\,{\mathrm{d}}W(\vartheta)&=\int_{\Theta}\left(\frac{\log
A}{I_{\vartheta}+\mu}\right)^{r}{\mathrm{d}}W(\vartheta)(1+o(1))\\\
&=D_{\mu,r}(\log A)^{r}(1+o(1)).\end{split}$

Since $\mathsf{PFA}(T_{A})<1/A$, we obtain the following asymptotic
approximation for the integrated risk

$\rho_{\pi,W}^{c,r}(T_{A})\sim D_{\mu,r}\,c\,(\log
A)^{r}\quad\text{as}~{}A\to\infty.$ (A.32)

Next, it is easily seen that, for any $r\geqslant 1$ and $\mu\in(0,\infty)$,
threshold $A_{c,r}$ goes to infinity as $c\to 0$ with such rate that $\log
A_{c,r}\sim|\log c|$. As a result, we obtain that

$\rho_{\pi,W}^{c,r}(T_{A_{c,r}})\sim D_{\mu,r}\,c\,|\log
c|^{r}\quad\text{as}~{}~{}c\to 0.$

All it remains to do is to prove the lower bound

$\inf_{T\geqslant 0}\rho_{\pi,W}^{c,r}(T)\geqslant D_{\mu,r}\,c\,|\log
c|^{r}(1+o(1))\quad\text{as}~{}~{}c\to 0.$ (A.33)

In fact, since

$\lim_{c\to 0}\frac{G_{c,r}(A_{c,r})}{D_{\mu,r}\,c\,|\log c|^{r}}=1,$

it suffices to prove that

$\frac{\inf_{T\geqslant 0}\rho_{\pi,W}^{c,r}(T)}{G_{c,r}(A_{c,r})}\geqslant
1+o(1)\quad\text{as}~{}c\to 0.$ (A.34)

This can be done by contradiction. Indeed, suppose that (A.34) is wrong, i.e.,
there exists a stopping rule $T=T_{c}$ such that

$\frac{\rho_{\pi,W}^{c,r}(T_{c})}{G_{c,r}(A_{c,r})}<1+o(1)\quad\text{as}~{}c\to
0.$ (A.35)

Let $\alpha_{c}=\mathsf{PFA}(T_{c})$. First, $\alpha_{c}\to 0$ as $c\to 0$
since

$\alpha_{c}\leqslant\rho_{c,r}^{\pi,W}(T_{c})<G_{c,r}(A_{c,r})(1+o(1))\to
0\quad\text{as}~{}~{}c\to 0.$

Second, it follows from Lemma 1 that, as $\alpha_{c}\to 0$,

${\mathcal{R}}_{\pi,W}^{r}(T_{c})\geqslant\int_{\Theta}(I_{\vartheta}+\mu)^{-r}{\mathrm{d}}W(\vartheta)|\log\alpha_{c}|^{r}(1+o(1)),$

and hence, as $c\to 0$,

$\displaystyle\rho_{\pi,W}^{c,r}(T_{c})$
$\displaystyle=\alpha_{c}+c\,(1-\alpha_{c}){\mathcal{R}}_{\pi,W}^{r}(T_{c})$
$\displaystyle\geqslant\alpha_{c}+c\,D_{\mu,r}|\log\alpha_{c}|^{r}(1+o(1)).$

Thus,

$\displaystyle\frac{\rho_{\pi,W}^{c,r}(T_{c})}{G_{c,r}(A_{c,r})}$
$\displaystyle\geqslant\frac{G_{c,r}(1/\alpha_{c})+c\,D_{\mu,r}|\log\alpha_{c}|^{r}o(1)}{\min_{A>0}G_{c,r}(A)}$
$\displaystyle\geqslant 1+o(1),$

which contradicts (A.35). Hence, (A.34) follows and the proof is complete. ∎

###### Proof:

(i) Using (A.14), we obtain

$\begin{split}&\int_{\Theta}{\mathsf{E}}^{\pi^{c}}_{\vartheta}[(T_{A}-\nu)^{+}]^{r}\,{\mathrm{d}}W(\vartheta)\\\
&\leqslant\sum_{k=0}^{\infty}\pi_{k}^{c}\int_{\Theta}\left(1+\frac{\log(A/\pi_{k}^{c})}{I_{\vartheta}+\mu_{c}-\varepsilon}\right)^{r}{\mathrm{d}}W(\vartheta)\\\
&+r2^{r-1}\int_{\Theta}\Upsilon_{r}(\vartheta,\varepsilon_{1})\,{\mathrm{d}}W(\vartheta),\end{split}$

where the last term is finite since $\Theta$ is compact and
$\Upsilon_{r}(\vartheta,\varepsilon_{1})<\infty$ for all $\vartheta\in\Theta$
due to condition ${\mathbf{C}}_{3}$ and where

$\sum_{k=0}^{\infty}\pi_{k}^{c}|\log\pi_{k}^{c}|^{r}=o(|\log
c|^{r})\quad\text{as}~{}c\to 0$

by assumption (46). Recall that, as established in the proof of Theorem 5
above, $\log A_{c,r}\sim|\log c|$ as $c\to 0$ when $A_{c,r}$ satisfies (47)
and that $\mu_{c}\to 0$. Therefore, as $c\to 0$,

$\displaystyle\int_{\Theta}{\mathsf{E}}^{\pi^{c}}_{\vartheta}[(T_{A_{c,r}}-\nu)^{+}]^{r}\,{\mathrm{d}}W(\vartheta)$
$\displaystyle\leqslant\int_{\Theta}\left(\frac{|\log
c|}{I_{\vartheta}-\varepsilon}\right)^{r}{\mathrm{d}}W(\vartheta)(1+o(1)).$

Since $\varepsilon$ can be arbitrary small, we obtain

$\displaystyle
c\,\int_{\Theta}{\mathsf{E}}^{\pi^{c}}_{\vartheta}[(T_{A_{c,r}}-\nu)^{+}]^{r}\,{\mathrm{d}}W(\vartheta)$
$\displaystyle\leqslant D_{r}\,c\,|\log c|^{r}(1+o(1))\quad\text{as}~{}c\to
0.$

Since $\mathsf{PFA}(T_{A_{c,r}})<1/A_{c,r}=o(c|\log c|^{r})$ it follows that

$\rho_{\pi^{c},W}^{c,r}(T_{A_{c,r}})\leqslant D_{r}\,c\,|\log
c|^{r}(1+o(1))\quad\text{as}~{}c\to 0.$ (A.36)

The lower bound

$\inf_{T\geqslant 0}\rho_{\pi^{c},W}^{c,r}(T)\geqslant D_{r}\,c\,|\log
c|^{r}(1+o(1))\quad\text{as}~{}~{}c\to 0$ (A.37)

can be deduced using Lemma 3 and the argument essentially similar to that used
in the proof of the lower bound (A.33) above with
$G_{c,r}(A)=1/A+c\,D_{r}(\log A)^{r}$.

Using the asymptotic upper bound (A.36) and the lower bound (A.37)
simultaneously, we obtain (48), which completes the proof of (i).

(ii) In order to prove (51) it suffices to prove the asymptotic upper bound

$\rho_{\pi^{c},W}^{c,r}(\widetilde{T}_{A_{c,r}})\leqslant D_{r}\,c\,|\log
c|^{r}(1+o(1))\quad\text{as}~{}c\to 0.$ (A.38)

Define

$\widetilde{G}_{c,r}(A)=(\omega_{c}b_{c}+\bar{\nu}_{c})/A+c\,D_{r}(\log
A)^{r}.$

Threshold $A_{c,r}$ that satisfies equation (50) minimizes
$\widetilde{G}_{c,r}(A)$, and it is easily seen that $\log A_{c,r}\sim|\log
c|$ as $c\to 0$ since, by assumption (49),
$\omega_{c}b_{c}+\bar{\nu}_{c}=o(|\log c|)$ as $c\to 0$.

Using inequality (A.25), we obtain

$\displaystyle\int_{\Theta}{\mathsf{E}}^{\pi^{c}}_{\vartheta}[(\widetilde{T}_{A}-\nu)^{+}]^{r}\,{\mathrm{d}}W(\vartheta)$
$\displaystyle\leqslant\int_{\Theta}\left(1+\frac{\log
A}{I_{\vartheta}-\varepsilon}\right)^{r}\,{\mathrm{d}}W(\vartheta)$
$\displaystyle\quad+r2^{r-1}\int_{\Theta}\Upsilon_{r}(\vartheta,\varepsilon)\,{\mathrm{d}}W(\vartheta),$

where the last term is finite since $\Theta$ is compact and
$\Upsilon_{r}(\vartheta,\varepsilon)<\infty$ for all $\vartheta\in\Theta$ due
to condition ${\mathbf{C}}_{3}$. Therefore, for an arbitrary small
$\varepsilon$ as $c\to 0$,

$\displaystyle\int_{\Theta}{\mathsf{E}}^{\pi^{c}}_{\vartheta}[(\widetilde{T}_{A}-\nu)^{+}]^{r}\,{\mathrm{d}}W(\vartheta)$
$\displaystyle\leqslant\int_{\Theta}\left(\frac{|\log
c|}{I_{\vartheta}-\varepsilon}\right)^{r}\,{\mathrm{d}}W(\vartheta)(1+o(1)),$

which implies that, as $c\to 0$,

$c\,\int_{\Theta}{\mathsf{E}}^{\pi^{c}}_{\vartheta}[(\widetilde{T}_{A}-\nu)^{+}]^{r}\,{\mathrm{d}}W(\vartheta)\leqslant
D_{r}\,c\,|\log c|^{r}(1+o(1)).$

Since
$\mathsf{PFA}(\widetilde{T}_{A_{c,r}})\leqslant(\omega_{c}b_{c}+\bar{\nu}_{c})/A_{c,r}=o(c|\log
c|^{r})$, we obtain (A.38), which along with the lower bound (A.37) proves
(51). The proof of (ii) is complete. ∎

## References

  * [1] A. N. Shiryaev, “On optimum methods in quickest detection problems,” _Theory of Probability and its Applications_ , vol. 8, no. 1, pp. 22–46, Jan. 1963.
  * [2] G. Lorden, “Procedures for reacting to a change in distribution,” _Annals of Mathematical Statistics_ , vol. 42, no. 6, pp. 1897–1908, Dec. 1971.
  * [3] E. S. Page, “Continuous inspection schemes,” _Biometrika_ , vol. 41, no. 1–2, pp. 100–114, Jun. 1954.
  * [4] G. V. Moustakides, “Optimal stopping times for detecting changes in distributions,” _Annals of Statistics_ , vol. 14, no. 4, pp. 1379–1387, Dec. 1986.
  * [5] M. Pollak, “Optimal detection of a change in distribution,” _Annals of Statistics_ , vol. 13, no. 1, pp. 206–227, Mar. 1985.
  * [6] A. N. Shiryaev, “The problem of the most rapid detection of a disturbance in a stationary process,” _Soviet Mathematics – Doklady_ , vol. 2, pp. 795–799, 1961, translation from Doklady Akademii Nauk SSSR, 138:1039–1042, 1961.
  * [7] S. W. Roberts, “A comparison of some control chart procedures,” _Technometrics_ , vol. 8, no. 3, pp. 411–430, Aug. 1966.
  * [8] G. V. Moustakides, A. S. Polunchenko, and A. G. Tartakovsky, “A numerical approach to performance analysis of quickest change-point detection procedures,” _Statistica Sinica_ , vol. 21, no. 2, pp. 571–596, Apr. 2011\.
  * [9] A. S. Polunchenko and A. G. Tartakovsky, “On optimality of the Shiryaev–Roberts procedure for detecting a change in distribution,” _Annals of Statistics_ , vol. 38, no. 6, pp. 3445–3457, Dec. 2010.
  * [10] M. Pollak and A. G. Tartakovsky, “Optimality properties of the Shiryaev–Roberts procedure,” _Statistica Sinica_ , vol. 19, no. 4, pp. 1729–1739, Oct. 2009.
  * [11] A. G. Tartakovsky, M. Pollak, and A. S. Polunchenko, “Third-order asymptotic optimality of the generalized Shiryaev–Roberts changepoint detection procedures,” _Theory of Probability and its Applications_ , vol. 56, no. 3, pp. 457–484, Sep. 2012.
  * [12] A. Bissell, “CUSUM techniques for quality control,” _Journal of the Royal Statistical Society - Series C Applied Statistics_ , vol. 18, no. 1, pp. 1–30, 1969.
  * [13] G. E. Box, A. Luceno, and M. del Carmen Paniagua-Quinones, _Statistical Control by Monitoring and Adjustment (2nd ed.)_. New York, USA: John Wiley & Sons, Inc, 2009.
  * [14] S. V. Crowder, D. M. Hawkins, M. R. Reynolds Jr., and E. Yashchin, “Process control and statistical inference,” _Journal of Quality Technology_ , vol. 29, no. 2, pp. 134–139, Apr. 1997.
  * [15] D. M. Hawkins and D. H. Olwell, _Cumulative Sum Charts and Charting for Quality Improvement_ , ser. Series in Statistics for Engineering and Physical Sciences. USA: Springer-Verlag, 1998.
  * [16] D. M. Hawkins, P. Qiu, and C. W. Kang, “The changepoint model for statistical process control,” _Journal of Quality Technology_ , vol. 35, no. 4, pp. 355–366, Oct. 2003.
  * [17] D. C. Montgomery, _Introduction to Statistical Quality Control (6th ed.)_. John Wiley & Sons, Inc, 2008.
  * [18] C. S. Van Dobben de Bruyn, _Cumulative Sum Tests: Theory and Practice_ , ser. Statistics Monograph. London, UK: Charles Griffin and Co. Ltd, 1968, vol. 24.
  * [19] G. B. Wetherill and D. W. Brown, _Statistical Process Control: Theory and Practice (3rd ed.)_ , ser. Texts in Statistical Science. London, UK: Chapman and Hall, 1991.
  * [20] R. H. Woodward and P. L. Goldsmith, _Cumulative Sum Techniques_ , ser. Mathematical and Statistical Techniques for Industry. Edinburgh, UK: Oliver and Boyd for Imperial Chemical Industries, Ltd., 1964, vol. 3.
  * [21] W. H. Woodall, “Control charts based on attribute data: Bibliography and review,” _Journal of Quality Technology_ , vol. 29, no. 2, pp. 172–183, Apr. 1997.
  * [22] ——, “Controversies and contradictions in statistical process control,” _Journal of Quality Technology_ , vol. 32, no. 4, pp. 341–350, Oct. 2000\.
  * [23] 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, Nov. 1998.
  * [24] A. G. Tartakovsky and V. V. Veeravalli, “General asymptotic Bayesian theory of quickest change detection,” _Theory of Probability and its Applications_ , vol. 49, no. 3, pp. 458–497, Jul. 2005.
  * [25] M. Baron and A. G. Tartakovsky, “Asymptotic optimality of change-point detection schemes in general continuous-time models,” _Sequential Analysis_ , vol. 25, no. 3, pp. 257–296, Oct. 2006, invited Paper in Memory of Milton Sobel.
  * [26] A. G. Tartakovsky, “On asymptotic optimality in sequential changepoint detection: Non-iid case,” _IEEE Transactions on Information Theory_ , vol. 63, no. 6, pp. 3433–3450, Jun. 2017.
  * [27] C. D. Fuh and A. G. Tartakovsky, “Asymptotic Bayesian theory of quickest change detection for hidden Markov models,” _IEEE Transactions on Information Theory_ , 2018, under review.
  * [28] C.-D. Fuh, “SPRT and CUSUM in Hidden Markov Models,” _Annals of Statistics_ , vol. 31, no. 3, pp. 942–977, Jun. 2003.
  * [29] S. Pergamenchtchikov and A. G. Tartakovsky, “Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data,” _Statistical Inference for Stochastic Processes_ , Oct. 2016.
  * [30] V. P. Dragalin, “Asymptotic solutions in detecting a change in distribution under an unknown parameter,” _Statistical Problems of Control_ , vol. 83, pp. 45–52, 1988, in Russian.
  * [31] D. O. Siegmund and B. Yakir, “Minimax optimality of the Shiryayev–Roberts change-point detection rule,” _Journal of Statistical Planning and Inference_ , vol. 138, no. 9, pp. 2815–2825, Sep. 2008.
  * [32] M. Basseville and I. V. Nikiforov, _Detection of Abrupt Changes – Theory and Application_ , ser. Information and System Sciences Series. Englewood Cliffs, NJ, USA: Prentice-Hall, Inc, 1993, Online.
  * [33] A. G. Tartakovsky, I. V. Nikiforov, and M. Basseville, _Sequential Analysis: Hypothesis Testing and Changepoint Detection_ , ser. Monographs on Statistics and Applied Probability. Boca Raton, London, New York: Chapman & Hall/CRC Press, 2014.
  * [34] M. Basseville, “Detecting changes in signals and systems - A survey,” _Automatica_ , vol. 24, no. 3, pp. 309–326, May 1988.
  * [35] ——, “On-board component fault detection and isolation using the statistical local approach,” _Automatica_ , vol. 34, no. 11, pp. 1391–1416, Nov. 1998.
  * [36] P. A. Bakut, I. A. Bolshakov, B. M. Gerasimov, A. A. Kuriksha, V. G. Repin, G. P. Tartakovsky, and V. V. Shirokov, _Statistical Radar Theory_. Moscow, USSR: Sovetskoe Radio, 1963, vol. 1 (G. P. Tartakovsky, Editor), in Russian.
  * [37] A. Chen, T. Wittman, A. G. Tartakovsky, and A. L. Bertozzi, “Efficient boundary tracking through sampling,” _Applied Mathematics Research Express_ , vol. 2, no. 2, pp. 182–214, 2011.
  * [38] S. Kent, “On the trail of intrusions into information systems,” _IEEE Spectrum_ , vol. 37, no. 12, pp. 52–56, Dec. 2000.
  * [39] R. L. Mason and J. C. Young, _Multivariate Statistical Process Control with Industrial Application_. Philadelphia, PA, USA: SIAM, 2001.
  * [40] A. S. Polunchenko, G. Sokolov, and A. G. Tartakovsky, “Optimal design and analysis of the exponentially weighted moving average chart for exponential data,” _Sri Lankan Journal of Applied Statistics, Special Issue: Modern Statistical Methodologies in the Cutting Edge of Science_ , vol. 15, no. 4, pp. 57–80, Dec. 2014.
  * [41] D. Siegmund, “Change-points: From sequential detection to biology and back,” _Sequential Analysis_ , vol. 32, no. 1, pp. 2–14, Jan. 2013.
  * [42] A. G. Tartakovsky, _Sequential Methods in the Theory of Information Systems_. Moscow, RU: Radio i Svyaz’, 1991, in Russian.
  * [43] A. G. Tartakovsky and V. V. Veeravalli, “Change-point detection in multichannel and distributed systems,” in _Applied Sequential Methodologies: Real-World Examples with Data Analysis_ , ser. Statistics: a Series of Textbooks and Monographs, N. Mukhopadhyay, S. Datta, and S. Chattopadhyay, Eds. New York, USA: Marcel Dekker, Inc, 2004, vol. 173, pp. 339–370.
  * [44] A. G. Tartakovsky and J. Brown, “Adaptive spatial-temporal filtering methods for clutter removal and target tracking,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 44, no. 4, pp. 1522–1537, Oct. 2008.
  * [45] P. Szor, _The Art of Computer Virus Research and Defense_. Upper Saddle River, NJ, USA: Addison-Wesley Professional, 2005.
  * [46] A. G. Tartakovsky, “Rapid detection of attacks in computer networks by quickest changepoint detection methods,” in _Data Analysis for Network Cyber-Security_ , N. Adams and N. Heard, Eds. London, UK: Imperial College Press, 2014, pp. 33–70.
  * [47] A. G. Tartakovsky, B. L. Rozovskii, R. B. Blaźek, and H. Kim, “Detection of intrusions in information systems by sequential change-point methods,” _Statistical Methodology_ , vol. 3, no. 3, pp. 252–293, Jul. 2006.
  * [48] ——, “A novel approach to detection of intrusions in computer networks via adaptive sequential and batch-sequential change-point detection methods,” _IEEE Transactions on Signal Processing_ , vol. 54, no. 9, pp. 3372–3382, Sep. 2006.
  * [49] A. G. Tartakovsky, A. S. Polunchenko, and G. Sokolov, “Efficient computer network anomaly detection by changepoint detection methods,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 7, no. 1, pp. 4–11, Feb. 2013.
  * [50] M. A. Richards, _Fundamentals of Radar Signal Processing_ , ser. 2nd edition. USA: McGraw-Hill Education Europe, 2014.
  * [51] J. Marage and Y. Mori, _Sonar and Underwater Acoustics_. London, Hoboken: STE Ltd and John Wiley & Sons, 2013\.
  * [52] V. Raghavan, A. Galstyan, and A. G. Tartakovsky, “Hidden Markov models for the activity profile of terrorist groups,” _Annals of Applied Statistics_ , vol. 7, pp. 2402–24 307, 2013.
  * [53] G. Fellouris and A. G. Tartakovsky, “Almost optimal sequential tests of discrete composite hypotheses,” _Statistica Sinica_ , vol. 23, no. 4, pp. 1717–1741, 2013.

|  Alexander G. Tartakovsky (M’01-SM’02) research interests include
theoretical and applied statistics; applied probability; sequential analysis;
changepoint detection phenomena; and a variety of applications including
statistical image and signal processing; video tracking; detection and
tracking of targets in radar and infrared search and track systems; near-Earth
space informatics; information integration/fusion; intrusion detection and
network security; and detection and tracking of malicious activity. He is the
author of two books (the third is in preparation), several book chapters, and
over 100 papers. Dr. Tartakovsky is a Fellow of the Institute of Mathematical
Statistics and a senior member of IEEE. He received several awards, including
a 2007 Abraham Wald Award in Sequential Analysis. Dr. Tartakovsky obtained a
Ph.D. degree and an advanced Doctor-of-Science degree both from Moscow
Institute of Physics and Technology, Russia (FizTech). During 1981–92, he was
first a Senior Research Scientist and then a Department Head at the Institute
of Radio Technology (Moscow, Russian Academy of Sciences) as well as a
Professor at FizTech, working on the application of statistical methods to
optimization and modeling of information systems. From 1993 to 1996, Dr.
Tartakovsky worked at the University of California, Los Angeles (UCLA), first
in the Department of Electrical Engineering and then in the Department of
Mathematics. From 1997 to 2013, he was a Professor in the Department of
Mathematics and the Associate Director of the Center for Applied Mathematical
Sciences at the University of Southern California (USC), Los Angeles. From
2013 to 2015, he was a Professor of Statistics in the Department of Statistics
at the University of Connecticut, Storrs. Currently, he is the Head of the
Space Informatics Laboratory at FizTech as well as Vice President of AGT
StatConsult, Los Angeles, California.
---|---