Serguei Pergamenchtchikov
email: serge.pergamenchtchikov@univ-rouen.fr

Alexander G Tartakovsky
email: alexg.tartakovsky@gmail.com

Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data

Keywords: Asymptotic optimality, Change-point detection, Shiryaev-Roberts procedure, Sequential detection

We consider the quickest change-point detection problem in pointwise and minimax settings for general dependent data models. Two new classes of sequential detection procedures associated with the maximal "local" probability of a false alarm within a period of some fixed length are introduced. For these classes of detection procedures, we consider two popular risks: the expected positive part of the delay to detection and the conditional delay to detection. Under very general conditions for the observations, we show that the popular Shiryaev-Roberts procedure is asymptotically optimal, as the local probability of false alarm goes to zero, with respect to both these risks pointwise (uniformly for every possible point of change) and in the minimax sense (with respect to maximal over point of change expected detection delays). The conditions are formulated in terms of the rate of convergence in the strong law of large numbers for the log-likelihood ratios between the "change" and "no-change" hypotheses, specifically as a uniform complete convergence of the normalized log-likelihood ratio to a positive and finite number. We also develop tools and a set of sufficient conditions for verification of the uniform complete convergence for a large class of Markov processes. These tools are based on concentration inequalities for functions of Markov processes and the Meyn-Tweedie geometric ergodic theory. Finally, we check these sufficient conditions for a number of challenging examples (time series) frequently arising in applications, such as autoregression, autoregressive GARCH, etc.

Introduction

The problem of rapid detection of abrupt changes in a state of a process or a system arises in a variety of applications from engineering problems (e.g., navigation integrity monitoring [START_REF] Basseville | Detection of Abrupt Changes: Theory and Applications[END_REF]; [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]]), military applications (e.g., target detection and tracking in heavy clutter [START_REF] Tartakovsky | Sequential Methods in the Theory of Information Systems. Radio i Svyaz[END_REF]; [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]]) to cyber security (e.g., quick detection of attacks in computer networks [START_REF] Kent | On the trial of intrusions into information systems[END_REF]; [START_REF] Tartakovsky | Rapid detection of attacks in computer networks by quickest change-point detection methods[END_REF]; [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]Tartakovsky et al. ( , 2006a,b),b)]). In the present paper, we are interested in a sequential setting assuming that as long as the behavior of the observation process is consistent with a "normal" (initial in-control) state, we allow the process to continue. If the state changes, then we need to detect this event as rapidly as possible while controlling for the risk of false alarms. In other words, we are interested in designing the quickest change-point detection procedure that optimizes the tradeoff between a measure of detection delay and a measure of the frequency of false alarms.

There are four conventional approaches to the optimum tradeoff problem: Bayesian, generalized Bayesian, multicyclic detection of changes in a stationary regime, and minimax (see Tartakovsky et al. (2014, Ch 6)). In the Bayesian context, proposed by [START_REF] Girshick | A Bayes approach to a quality control model[END_REF] and [START_REF] Shiryaev | The problem of the most rapid detection of a disturbance in a stationary process[END_REF][START_REF] Shiryaev | On optimum methods in quickest detection problems[END_REF], the change point is assumed to be random with a geometric prior distribution, and the optimality criterion is to minimize the weighted Bayes-type expected detection delay subject to an upper bound on the weighted probability of a false alarm. Until the 1990s, most of the work related to the optimality issue in change detection had been done in the iid case, assuming that observations are independent and identically distributed (iid) with one law before the change and with another distribution after the change. In particular, in the 1960s, [START_REF] Shiryaev | The problem of the most rapid detection of a disturbance in a stationary process[END_REF][START_REF] Shiryaev | On optimum methods in quickest detection problems[END_REF] found an optimal Bayes solution showing that a detection procedure based on thresholding the posterior probability of the change up to the current moment is strictly optimal for any value of the weighted false alarm probability. Much later, in 2004Much later, in -2006, a , a general Bayesian asymptotic theory of change-point detection (for very general non-iid models and arbitrary prior distributions of the change point) was developed by Tartakovsky and Veeravalli (2005) in discrete time and [START_REF] Baron | Asymptotic Bayesian change-point detection theory for general continuoustime models[END_REF] in continuous time.

By contrast, in a minimax formulation, proposed by [START_REF] Lorden | Procedures for reacting to a change in distribution[END_REF] and [START_REF] Pollak | Optimal detection of a change in distribution[END_REF], the change point is assumed to be an unknown non-random number and the goal is to minimize the worst-case delay (with respect to the point of change) subject to a lower bound on the mean time until false alarm. Specifically, in 1971[START_REF] Lorden | Procedures for reacting to a change in distribution[END_REF] suggested the worst-worst-case average delay to detection measure ESADD(τ ) = sup ν 0 ess sup E ν (τ -ν|τ > ν, F ν ) that should be minimized in the class of procedures H γ = {τ : E ∞ τ γ} for which the average run length (mean time) to false alarm E ∞ τ is not smaller than a given number γ > 1. Here τ is a generic change detection procedure (stopping time), E ν stands for the operator of expectation when the change point is ν (ν = ∞ corresponds to a no-change scenario) and F ν = σ(X 1 , . . . , X ν ) is the sigma-algebra generated by the first ν observations X 1 , . . . , X ν . [START_REF] Lorden | Procedures for reacting to a change in distribution[END_REF] developed an asymptotic minimax theory of change detection (in the iid case) as γ → ∞, proving in particular that Page's CUSUM procedure [START_REF] Page | Continuous inspection schemes[END_REF]] is asymptotically first-order minimax. Later in 1986, [START_REF] Moustakides | Optimal stopping times for detecting changes in distributions[END_REF] established strict optimality of CUSUM for any value of the average run length to false alarm γ > 1. In the 1980s, [START_REF] Pollak | Optimal detection of a change in distribution[END_REF] introduced a less pessimistic worst-case detection delay measure -maximal conditional average delay to detection,

SADD(τ ) = sup ν 0 E ν (τ -ν|τ > ν), (1.1)
and found an almost optimal procedure that minimizes SADD(τ ) subject to the constraint on the average run length to false alarm (i.e., in the class H γ ) as γ becomes large. Pollak's idea was to modify the Shiryaev-Roberts statistic by randomization of the initial condition in order to make it an equalizer.

Pollak proved that the randomized Shiryaev-Roberts procedure that starts from a random point sampled from the quasi-stationary distribution of the Shiryaev-Roberts statistic is asymptotically nearly minimax within an additive vanishing term. Since the Shiryaev-Roberts-Pollak procedure is an equalizer, it is tempting to conjecture that it may be strictly optimal for any value of γ, which is not true, as the articles of [START_REF] Moustakides | A numerical approach to performance analysis of quickest change-point detection procedures[END_REF] and [START_REF] Polunchenko | On optimality of the Shiryaev-Roberts procedure for detecting a change in distribution[END_REF] indicate.

As we already mentioned above, in the early stages the theoretical development was focused primarily on the iid case. However, in practice the observations may be non-identically distributed and dependent. A general asymptotic minimax theory of change-point detection for non-iid models was developed by [START_REF] Lai | Sequential changepoint detection in quality control and dynamical systems[END_REF][START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF] (see also [START_REF] Fuh | SPRT and CUSUM in hidden Markov models[END_REF] for hidden Markov models with a finite state-space). In particular, for a low false alarm rate (large γ) the asymptotic minimaxity of the CUSUM procedure was established in [START_REF] Fuh | SPRT and CUSUM in hidden Markov models[END_REF]; [START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF].

In the iid case, the suitably standardized distributions of the stopping times of the CUSUM and Shiryaev-Roberts detection procedures are asymptotically exponential for large thresholds and fit well into the geometric distribution even for a moderate false alarm rate (see Pollak and Tartakovsky (2009b)). In this case, the average run length to false alarm is an appropriate measure of false alarms. However, for non-iid models the limiting distribution is not guaranteed to be exponential or even close to it. In general, we cannot even guarantee that large values of the average run length to false alarm will produce small values of the maximal local false alarm probability. Therefore, the average run length to false alarm is not appropriate in general, and instead it is more adequate to use the local conditional false alarm probability, as suggested in [START_REF] Tartakovsky | Asymptotic performance of a multichart CUSUM test under false alarm probability constraint[END_REF]; [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]. This issue is extremely important for non-iid models, as a discussion in [START_REF] Mei | Is average run length to false alarm always an informative criterion?[END_REF]; [START_REF] Tartakovsky | Discussion on "Is average run length to false alarm always an informative criterion?[END_REF] shows. See also [START_REF] Lai | Sequential changepoint detection in quality control and dynamical systems[END_REF][START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF].

Other approaches to sequential change detection as well as a comparison of several popular change detection procedures, such as CUSUM, Shiryaev-Roberts, and EWMA procedures can be found in Basseville (1988,1998); [START_REF] Basseville | Detection of Abrupt Changes: Theory and Applications[END_REF]; [START_REF] Benveniste | The asymptotic local approach to change detection and model validation[END_REF]; [START_REF] Brodsky | Nonparametric Methods in Change-point Problems[END_REF]; [START_REF] Hawkins | Cumulative Sum Charts and Charting for Quality Improvement[END_REF]; [START_REF] Mason | Multivariate Statistical Process Control with Industrial Application[END_REF]; Monigomery (2008); [START_REF] Moustakides | Numerical comparison of CUSUM and Shiryaev-Roberts procedures for detecting changes in distributions[END_REF][START_REF] Moustakides | A numerical approach to performance analysis of quickest change-point detection procedures[END_REF]; [START_REF] Polunchenko | Optimal design and analysis of the exponentially weighted moving average chart for exponential data[END_REF]; [START_REF] Srivastava | Comparison of EWMA, CUSUM and Shiryayev-Roberts procedures for detecting a shift in the mean[END_REF]; [START_REF] Stoumbos | The state of statistical process control as we proceed into the 21st century[END_REF].

In the present paper, we pursue two objectives. First, in Section 2, we introduce two novel classes of change-point detection procedures, which, instead of imposing a lower bound on the average run length to false alarm, require more adequate upper bounds on the uniform probability of false alarm or uniform conditional probability of false alarm in the spirit of works by [START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF], [START_REF] Tartakovsky | Asymptotic performance of a multichart CUSUM test under false alarm probability constraint[END_REF] and [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]. However, these classes slightly differ from those proposed in [START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF]; [START_REF] Tartakovsky | Asymptotic performance of a multichart CUSUM test under false alarm probability constraint[END_REF]; [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]. This modification allows us to substantially relax Lai's essential supremum conditions [START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF]], which do not hold for certain interesting practical models. In fact, our conditions are equivalent to the uniform version of the complete convergence for the loglikelihood ratio processes, i.e., they are related to the rate of convergence in the strong law of large numbers for the log-likelihood ratio between the "change" and "no-change" hypotheses. We concentrate on a minimax problem of minimizing Pollak's maximal conditional average delay to detection defined in (1.1) as well as on a pointwise problem of minimizing the conditional average delay to detection E ν (τ -ν|τ > ν) for every change point ν 0. For the sake of completeness, we also consider the other popular risks sup ν 0 E ν (τ -ν) + and E ν (τ -ν) + , ν 0, while we strongly believe that the conditional versions E ν (τ -ν|τ > ν) and (1.1) are more appropriate for most applications. We consider extremely general non-iid stochastic models for the observations, and it is our goal to find reasonable sufficient conditions for the observation models under which the Shiryaev-Roberts (or CUSUM) procedure is asymptotically optimal. To achieve the first goal we exploit the asymptotic Bayesian theory of changepoint detection developed by Tartakovsky and Veeravalli (2005) that offers a constructive and flexible approach for studying asymptotic efficiency of Bayesian type procedures. It turns out that a similar method can be used for the analysis of minimax risks and that the complete convergence type conditions for the log-likelihood ratio processes proposed in [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]; Tartakovsky and Veeravalli (2005) are also sufficient in the minimax setting. These sufficient conditions as well as the main results related to asymptotic optimality of the Shiryaev-Roberts procedure in the classes of procedures with upper bounds on the weighted false alarm probability and local false alarm probabilities are given, correspondingly, in Section 3 and Section 4.

The second objective is to find a method for verification of the required sufficient conditions in a number of particular, still very general, challenging models. The natural question is how one may check the proposed sufficient conditions and even whether there are more or less general models, except of course the iid case, for which these conditions hold. To this end, we focus on the class of data models for which one can exploit the method of geometric ergodicity for homogeneous Markov processes, first proposed by [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF] and then further developed by Galthouk andPergamenshchikov (2013, 2014) for statistical applications. These results are presented in Section 5 and show that our sufficient conditions for pointwise and minimax optimality hold for homogeneous Markov ergodic processes. In Section 6, these conditions are further illustrated for several examples that include autoregressive, autoregressive GARCH, and other models widely used in many applications, in particular for modeling of dynamics of financial indices; see, e.g., [START_REF] Shiryaev | From Stochastic Calculus to Mathematical Finance[END_REF]. All auxiliary results needed for the proofs as well as proofs of theorems for the Bayes-type class in Section 3 are presented in Appendix A, and in Appendix B we give certain useful results from the geometric ergodic theory of Markov processes.

It is worth mentioning that the recently submitted article by Tartakovsky (submitted 2016) uses a similar (but average, not uniform) r-complete version of the strong law of large numbers for establishing asymptotic optimality properties of the Shiryaev procedure in the Bayesian problem with general prior distributions, i.e., confirming a long-standing conjecture of Tartakovsky and Veeravalli (2005) that the r-quick convergence may be relaxed into the r-complete convergence. Also, a similar approach has been undertaken by Fellouris and Tartakovsky (submitted 2015) in the problem of testing composite hypotheses in a multi-stream setup when detecting an unknown number of signals. Note that the latter problem is not a change-point detection problem but rather the hypothesis testing problem.

Notation, problem formulation and detection procedures

Assume that we are able to observe a series of consecutive random variables X 1 , X 2 , . . . , which may change statistical properties at an unknown point in time ν ∈ {0, 1, 2, . . . }. We use the convention that X ν is the last pre-change observation. Write X n = (X 1 , . . . , X n ) for the concatenation of the first n observations. Let p ν (X n ) = p(X n |ν) be the joint probability density of the vector X n when the change point ν is fixed and finite and let p ∞ (X n ) = p(X n |ν = ∞) stand for the pre-change joint density (when the change never occurs). Let {f 0,n (X n |X n-1 )} n 1 and {f 1,n (X n |X n-1 )} n 1 be two sequences of conditional densities of X n given X n-1 with respect to some non-degenerate sigma-finite measure µ(x).

We are interested in the general non-iid case that

p ν (X n ) = p ∞ (X n ) = n i=1 f 0,i (X i |X i-1 1 ) for ν n, p ν (X n ) = ν i=1 f 0,i (X i |X i-1 ) × n i=ν+1 f 1,i (X i |X i-1 ) for ν < n.
(2.1)

In other words, {f 0,n (X n |X n-1 )} n 1 and {f 1,n (X n |X n-1 )} n 1 are the pre-change and post-change conditional densities, respectively, so that if the change occurs at time ν = k, then the conditional density of the (k + 1)-th observation changes from f 0,k+1 (X k+1 |X k ) to f 1,k+1 (X k+1 |X k ). Note that the post-change densities may depend on the change point ν, i.e., f

1,n (X n |X n-1 ) = f (ν) 1,n (X n |X n-1
) for n > ν. We omit the superscript ν for brevity.

Let P k and E k denote the probability and expectation when ν = k < ∞, and let P ∞ and E ∞ denote the same when there is no change, i.e., ν = ∞. Obviously, the general non-iid model given by (2.1) implies that under the measure P ∞ the conditional density of X n given X n-1 is f 0,n (X n |X n-1 ) for all n 1 and under P k , for any 0 k < ∞, the conditional density of

X n is f 0,n (X n |X n-1 ) if n k and is f 1,n (X n |X n-1 ) if n > k.
In the particular iid case, the observed random variables X 1 , X 2 , . . . are iid until a change with a common density f 0 (x) and after the change occurs, the observations are again iid, but with another density f 1 (x). Therefore, in this case, the conditional densities f 0,i (X i |X i-1 ) and f 1,i (X i |X i-1 ) in (2.1) are replaced by f 0 (X i ) and f 1 (X i ), respectively.

A sequential detection procedure is a stopping (Markov) time τ for an observed sequence {X n } n 1 , i.e., τ is an extended integer-valued random variable, such that the event {τ n} belongs to the sigmaalgebra F n = σ(X 1 , . . . , X n ). We denote by M the set of all stopping times. A false alarm is raised whenever the detection is declared before the change occurs, i.e., when τ ν. (Recall that X ν+1 is the first post-change observation.) The goal of the quickest change-point detection problem is to develop a detection procedure that guarantees a stochastically small delay to detection τ -ν provided that there is no false alarm (i.e., τ > ν) under a given (typically low) risk of false alarms.

Let P (n) k

= P k | Fn denote a restriction of the probability measure P k to the sigma-algebra F n . Then the likelihood ratio between the hypotheses "H k : ν = k" that the change happens at k < ∞ and "H ∞ : ν = ∞" that there is never a change (i.e., the Radon-Nikodým density dP

(n) k /dP (n)
∞ ) can be represented in the following exponential form dP

(n) k dP (n) ∞ (X n ) = e Z k n , (2.2)
where for k n -1

Z k n = n j=k+1 log f 1,j (X j |X j-1 ) f 0,j (X j |X j-1
) .

The process (Z k n ) n k+1 is the log-likelihood ratio (LLR) process between the hypotheses H k (k = 0, 1, . . . ) and H ∞ .

In this paper, we study the Shiryaev-Roberts (SR) procedure given by the following stopping time

T (h) = inf n 1 : n k=1 e Z k-1 n h , (2.3)
where h > 0 is some fixed positive threshold which will be specified later. We set inf{∅} = +∞. In the iid case, this procedure has certain interesting strict optimality properties (see Pollak and Tartakovsky (2009a) and [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]).

Another popular change detection procedure is the CUSUM procedure given by the stopping time

T CS (a) = inf n 1 : max 1 k n Z k-1 n a , a > 0.
It may be shown that this procedure has essentially the same asymptotic performance as the SR procedure. In fact, using essentially the same line of argument, it can be proved that both procedures are first-order asymptotically optimal under the same general conditions. For this reason, we consider only the SR procedure.

Our main goal is to show that the SR detection procedure T (h) is nearly optimal in two pointwise and minimax problems described below. We will also show that this procedure is asymptotically pointwise and minimax optimal in a class of Bayes-type procedures (see Section 3).

To describe these problems we introduce for any 0 < β < 1, m * 1 and k * > m * the following classes of change detection procedures

H(β, k * , m * ) = τ ∈ M : sup 1 k k * -m * P ∞ (k τ < k + m * ) β (2.4)
and

H * (β, k * , m * ) = τ ∈ M : sup 1 k k * -m * P ∞ (τ < k + m * |τ k) β .
(2.5)

Note that the probability P ∞ (k τ < k + m) is the probability of false alarm in the time interval [k, k + m -1] of the length m, which we refer to as the local probability of false alarm (LPFA), and the probability

P ∞ (τ < k + m|τ k) = P ∞ (k τ < k + m|τ k)
is the corresponding local conditional probability of false alarm (LCPFA).

We consider two risks: positive part detection delay risk

R ν (τ ) = E ν (τ -ν) + (2.6)
and conditional detection delay risk

R * ν (τ ) = E ν (τ -ν | τ > ν) (2.7)
(compare with (1.1)) and the following problems: the pointwise minimization, i.e., for any ν 0

inf τ ∈H(β,k * ,m * ) R ν (τ ) and inf τ ∈H * (β,k * ,m * ) R * ν (τ ) ; (2.8)
and the minimax optimization

inf τ ∈H(β,k * ,m * ) sup 0 ν<∞ R ν (τ ) and inf τ ∈H * (β,k * ,m * ) max 0 ν k * R * ν (τ ) .
(2.9)

The parameters k * and m * will be specified later.

In addition, we consider a Bayesian-type problem of minimizing the risks (2.6) and (2.7) in a class of procedures with the given weighted probability of false alarm. This problem is formulated and solved in the next section.

It would be more natural to address the classes of detection procedures with the given LPFA and LCPFA defined as

LPFA(τ ) = sup 1 k<∞ P ∞ (k τ < k + m * ) and LCPFA(τ ) = sup 1 k<∞ P ∞ (k τ < k + m * |τ k)
and the maximal risks sup

0 ν<∞ R ν (τ ) and sup 0 ν<∞ R * ν (τ ) ,
i.e., the optimality criteria as in [START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF], [START_REF] Tartakovsky | Asymptotic performance of a multichart CUSUM test under false alarm probability constraint[END_REF] and [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF]. However, in this case, one requires much stronger essential supremum conditions on the tail probabilities of the log-likelihood ratio, which do not hold in certain interesting examples (see Remark 3 below for details). For this reason, we modified these more natural optimality criteria. In the following, we suppose that k * , m * and m * -k * go to infinity as β → 0, so that for practical purposes the optimality criteria (2.9), considered in the present paper, are not too much different from the criteria (2.10). At the same time, this allows us to substantially relax the sufficient conditions for asymptotic optimality of the detection procedures. We need the following definition.

Definition 1 For k = 0, 1, . . . and r > 0, we say that the normalized LLR process n -1 Z k n+k converges r-completely to a constant I under the probability measure

P k as n → ∞ if ∞ n=1 n r-1 P k n -1 Z k n+k -I > ε < ∞ for all ε > 0. (2.11) If ∞ n=1 n r-1 sup k 0 P k n -1 Z k n+k -I > ε < ∞ for all ε > 0 (2.12)
we say that n -1 Z k n+k converges to a constant I uniformly r-completely as n → ∞.

The r-complete convergence is an extension (for r = 1) of the complete convergence introduced by [START_REF] Hsu | Complete convergence and the law of large numbers[END_REF]. It was introduced and extensively used for various hypothesis testing and change detection problems by [START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF].

In the following, we mostly deal with the case that r = 1. In this case, we refer to (2.11) as P k -complete convergence and to (2.12) as uniform complete convergence.

Note that, for any r 1, r-complete convergence implies almost sure convergence of n -1 Z k n+k to I under P k . Hence it can be interpreted as a rate of convergence in the strong law of large numbers. See Tartakovsky et al. (2014, Ch 2) for further details.

Asymptotic optimality in the Bayesian-type class

We begin with considering a Bayesian-type class of change detection procedures that upper-bounds a weighted probability of false alarm PFA(τ ) = ∞ k=0 P k (τ k)P(ν = k), assuming that the change point ν is a random variable independent of the observations with prior distribution P(ν = k), k = 0, 1, 2, . . . . However, instead of considering a Bayes risk (weighted average delay to detection)

E(τ -ν|τ > ν) = ∞ k=0 P(ν = k)R k (τ ) 1 -PFA(τ ) , (3.1)
as it was done by Tartakovsky and Veeravalli (2005) and Tartakovsky (submitted 2016), we are interested in risks (2.6) and (2.7), i.e., in the optimization problems

inf {τ :PFA(τ ) α} R k (τ ) and inf {τ :PFA(τ ) α} R * k (τ ) for all k 0 , (3.2)
and inf

{τ :PFA(τ ) α} sup k 0 R k (τ ) and inf {τ :PFA(τ ) α} max 0 k k * R * k (τ ), (3.3)
where 0 < α < 1 is a prespecified (usually relatively small) number.

In what follows, for simplicity of the presentation, assume that the prior probability distribution P(ν = k) of the change point ν is geometric with the parameter 0 < < 1, i.e.,

P(ν = k) = π k ( ) = (1 -) k , k = 0, 1, 2, . . . . (3.4)
Using this distribution we introduce the probability measure on the Borel σ-algebra in R ∞ × N as

Q (A × J) = k∈J π k ( ) P k (A) , A ∈ B(R ∞ ) , J ⊆ N .
Now, for some fixed 0 < , α < 1, we define the following Bayesian class of change-point detection procedures with the weighted PFA Q (τ ν) = PFA(τ ) not greater that the given number α:

∆(α, ) = {τ ∈ M : Q (τ ν) α} =    τ ∈ M : k 1 π k ( ) P ∞ (τ k) α    , (3.5)
where we took into account that

P k (τ k) = P ∞ (τ k).
It follows from Tartakovsky and Veeravalli (2005) that in the Bayesian setting, when one wants to minimize the weighted average delay to detection (3.1), the asymptotically (as α → 0) optimal detection procedure in the class (3.5) is the Shiryaev detection procedure that raises an alarm at the first time such that the posterior probability g

n ( ) = Q (ν < n | F n ) exceeds threshold 1 -α, i.e., τ b (α, ) = inf{n 1 : g n ( ) 1 -α} .
Note that it is easy to show [Tartakovsky and Veeravalli (2005)] that τ b ∈ ∆(α, ) for any 0 < α, < 1.

Using the LLR process (Z k n ) 0 k n-1 defined in (2.2), the posterior probability g n ( ) can be represented as

g n ( ) = Λ n ( )/[1/ + Λ n ( )],
where

Λ n ( ) = n-1 k=0 (1 -) -(n-k) e Z k n . (3.6)
Therefore, the Shiryaev procedure can be also written as

τ (α, ) = inf {n 1 : Λ n ( ) (1 -α)/( α)} . (3.7)
Note first that, as ρ → 0, the statistic Λ n ( ) converges to the SR statistic,

Λ n ( ) ---→ ρ→0 n k=1 e Z k-1 n .
Thus, if we are interested in small values of , as it is the case in the following, then the behavior of the Shiryaev procedure (3.7) is similar to that of the SR procedure T (h) so long as we can define the threshold h = h α is such a way that PFA(T (h α )) α. Hence, instead of considering the procedure τ (α, ), which is shown in Tartakovsky and Veeravalli (2005) and Tartakovsky (submitted 2016) to be asymptotically optimal in the Bayesian context with respect to the weighted average delay to detection (3.1), we will focus on the SR procedure.

Asymptotic lower bounds

In general, we do not assume any particular model or even class of models for the observations, and as a result, there is no "structure" of the LLR process. We therefore have to impose some conditions on the behavior of the LLR process at least for large n. It is natural to assume that there exists a positive finite number I such that Z k n /(n -k) converges almost surely to I under P k , i.e., (A 1 ) Assume that there exists a number I > 0 such that for any k 0

1 n Z k k+n P k -a.s. -----→ n→∞ I . (3.8)
This is always true for iid data models with

I = I(f 1 , f 0 ) = E 0 Z 1 0 = log f 1 (x) f 0 (x) f 1 (x)dµ(x)
being the Kullback-Leibler information number. It turns out that the a.s. convergence condition (3.8) is sufficient for obtaining lower bounds for all positive moments of the detection delay.

The following theorem establishes asymptotic lower bounds for the optimization problems (3.2) and (3.3). We write ∆(α) for the class ∆(α, α ) when the parameter = α depends on α.

Theorem 1 Assume that the almost sure convergence condition (A 1 ) holds and in (3.4) the parameter of the geometric prior distribution = α → 0 as α → 0. Then, for any ν 0,

lim inf α→0 1 | log α| inf τ ∈∆(α) sup ν 0 R ν (τ ) lim inf α→0 1 | log α| inf τ ∈∆(α) R ν (τ ) 1 I (3.9) and lim inf α→0 1 | log α| inf τ ∈∆(α) sup ν 0 R * ν (τ ) lim inf α→0 1 | log α| inf τ ∈∆(α) R * ν (τ ) 1 I . (3.10) Proof. See Appendix A, Section A.2.
Observe that the lower bounds (3.9) and (3.10) can be generalized for all positive moments of the detection delay

E ν [(τ -ν) r | τ > ν] and E ν [(τ -ν) + ]
r , r > 1. Indeed, using Jensen's inequality

E ν [(τ -ν) + ] r [E ν (τ -ν) + ]
r , we immediately obtain that under the conditions of Theorem 1, for any

ν 0, lim inf α→0 1 | log α| r inf τ ∈∆(α) E ν (τ -ν) + r 1 I r (3.11)
and analogously lim inf

α→0 1 | log α| r inf τ ∈∆(α) E ν [(τ -ν) r | τ > ν] 1 I r .
(3.12)

Since higher moments of the detection delay may also be of interest, the asymptotic lower bounds (3.11) and (3.12) can be useful for establishing asymptotic optimality properties of the SR procedure with respect to the risks

E ν [(τ -ν) r | τ > ν] and E ν [(τ -ν) + ]
r for r > 1 uniformly for all ν 0, as well as with respect to the maximal risks.

Asymptotic optimality of the Shiryaev-Roberts procedure

In order to study asymptotics for the average detection delay of the SR procedure and for establishing its asymptotic optimality, we impose the following constraint on the rate of convergence for

Z k,n = 1 n Z k k+n -I . (3.13) (A 2 ) Assume that Z k,n converges uniformly completely to 0 as n → ∞, i.e., for any ε > 0 Υ * (ε) = ∞ n=1 sup k 0 P k Z k,n > ε < ∞ . (3.14) Write R n = n k=1 e Z k-1 n
for the SR statistic and denote as T (h) = T (α, ) the SR procedure when the threshold h = h(α, ) is selected as h(α, ) = (1 -α)/ α, i.e.,

T (α, ) = inf n 1 : R n 1 -α α . (3.15)
Lemma 1 The SR procedure T (α, ) given by (3.15) belongs to the class ∆(α, ) for any 0 < α, < 1.

Proof. Note that the stopping time (3.7) can be written as

τ b (α, ) = inf n 1 : n k=1 (1 -) -[n-(k-1)] e Z k-1 n h(α, ) (see (3.6)). Obviously, τ b (α, )
T (α, ) almost surely for any 0 < α, < 1. Since by (2.11) in Tartakovsky and Veeravalli ( 2005) PFA( τ b (α, )) α, it follows that, for any 0 < α, < 1, T (α, ) ∈ ∆(α, ) and the proof is complete.

In what follows, we assume that the parameter is a function of α, i.e. = α , such that lim α→0 α = 0 and lim

α→0 | log α | | log α| = 0 . (3.16) Moreover, let k * be a function of α, i.e. k * = k * α , such that lim α→0 k * α = ∞ and lim α→0 (| log α| + k * α log(1 -α )) = +∞ . (3.17)
Denote as T α = T (h α ) the SR procedure defined in (3.15) when the threshold h(α, α ) = h α is selected as h α = (1 -α)/( α α). Note that if conditions (3.16) hold, then h α → ∞ as α → 0. Clearly, we need the threshold to become large for small α; otherwise the problem is degenerate. By Lemma 1, this choice of the threshold guarantees that T α ∈ ∆(α, α ) = ∆(α) for every 0 < α < 1.

The following theorem identifies the asymptotic upper bounds for the risks of the SR procedure. The proof is given in the Appendix A (see Section A.3).

Theorem 2 (i) Assume that the uniform complete convergence condition (A 2 ) holds for some 0 < I < ∞, and the parameter 0 < = α < 1 in the SR procedure (3.15) satisfies conditions (3.16). Then

lim sup α→0 1 | log α| sup ν 0 R ν (T α ) 1 I . (3.18)
(ii) Assume that in addition to conditions (A 2 ) and (3.16), conditions (3.17) hold for k * = k * α . Then

lim sup α→0 1 | log α| max 0 ν k * α R * ν (T α ) 1 I . (3.19)
Finally, combining Theorem 1 and Theorem 2, we conclude that the SR procedure is first-order asymptotically uniformly pointwise optimal and minimax in the class ∆(α), which is formalized in the next theorem.

Theorem 3 (i) Assume that the uniform complete convergence condition (A 2 ) holds for some 0 < I < ∞, and the parameter 0 < = α < 1 in the SR procedure (3.15) satisfies conditions (3.16). Then

lim α→0 inf τ ∈∆(α) R ν (τ ) R ν (T α ) = 1 for all ν 0 (3.20)
and

lim α→0 inf τ ∈∆(α) sup ν 0 R ν (τ ) sup ν 0 R ν (T α ) = 1 . (3.21) Moreover, as α → 0, inf τ ∈∆(α) R ν (τ ) ∼ R ν (T α ) ∼ | log α| I for all ν 0 and inf τ ∈∆(α) sup ν 0 R ν (τ ) ∼ sup ν 0 R ν (T α ) ∼ | log α| I .
(ii) Assume that in addition to conditions (A 2 ) and (3.16) conditions (3.17) hold for k * = k * α . Then

lim α→0 inf τ ∈∆(α) R * ν (τ ) R * ν (T α )
= 1 for all fixed ν 0 (3.22)

and

lim α→0 inf τ ∈∆(α) max 0 ν k * α R * ν (τ ) max 0 ν k * α R * ν (T α ) = 1 . (3.23) Moreover, as α → 0, inf τ ∈∆(α) R * ν (τ ) ∼ R * ν (T α ) ∼ | log α| I for all fixed ν 0 and inf τ ∈∆(α) max 0 ν k * α R * ν (τ ) ∼ max 0 ν k * α R * ν (T α ) ∼ | log α| I .
Proof. All assertions follow from Theorem 1 and Theorem 2 in an obvious manner.

The above asymptotic optimality results can be generalized for higher moments of the detection delay if the uniform complete convergence condition (A 2 ) is strengthened into the uniform r-complete convergence condition for some r > 1. In particular, the following result holds true.

Theorem 4 Let conditions (3.16) and (3.17) hold and, for some r > 1 and all ε > 0,

∞ n=1 n r-1 sup k 0 P k Z k,n > ε < ∞ . (3.24)
Then the SR procedure T α is first-order asymptotically uniformly pointwise optimal and minimax in the class ∆(α, α ) = ∆(α) with respect to the moments of the detection delay up to order r: for all 1 r as α → 0

E ν (T α -ν) |T α > ν ∼ inf τ ∈∆(α) E ν (τ -ν) |τ > ν ∼ | log α| I for all fixed ν 0 (3.25) and sup 0 ν k * α E ν (T α -ν) |T α > ν ∼ inf τ ∈∆(α) sup 0 ν k * α E ν (τ -ν) |τ > ν ∼ | log α| I . (3.26)
Proof. See Section A.4 in Appendix A.

Remark 1 While for the sake of simplicity we consider the geometric prior distribution with the small parameter α → 0 as α → 0, all the asymptotic results hold true for an arbitrary prior distribution π α k such that the mean value of the change point E ν = ∞ k=1 kπ α k approaches infinity as α → 0, assuming that conditions (3.16) and (3.17) hold with α replaced by (

∞ k=1 kπ α k ) -1 .
Remark 2 Analogous asymptotic optimality results hold for the Shiryaev procedure τ (α) defined in (3.7).

The proofs are essentially similar.

Asymptotic optimality in classes with given local probabilities of false alarm

We now proceed with tackling the pointwise and minimax problems (2.8) and (2.9) in the classes of procedures with given LPFA and LCPFA. The method of establishing asymptotic optimality of the SR procedure is again based on the lower-upper bounding technique. Specifically, we first obtain asymptotic lower bounds for the risk R ν (τ ) in the class H (β, k * , m * ) and for the risk R * ν (τ ) in the class H * (β, k * , m * ), and then we show that these asymptotic lower bounds are attained for the SR procedure T (h) with a certain threshold h = h β . Note that the asymptotic optimality results of the previous section are essential, since asymptotic optimality in classes H (β, k * , m * ) and H * (β, k * , m * ) is obtained by imbedding these classes in the class ∆(α, ρ) with specially selected parameters ρ and α.

Asymptotic lower bounds

For any 0 < β < 1, m * 1 and k * > m * , define For example, we can take

α 1 = α 1 (β, m * ) = β + (1 -1,β ) m * +1 and α 2 = α 2 (β, k * ) = β(1 -2,β ) k * , ( 4
1,β = 1 1 + | log β| , δβ = δ * | log β| and 0 < δ * < 1 . (4.3)
To find asymptotic lower bounds for the problems (2.8) and (2.9) in addition to condition (A 1 ) we impose the following condition related to the growth of the window size m * in the LPFA:

(H 1 ) The size of the window m * in (4.1) is a function of β, i.e. m * = m * β , such that lim β→0 | log α 1,β | | log β| = 1 , (4.4)
where α 1,β = α 1 (β, m * β ). The following theorem establishes asymptotic lower bounds.

Theorem 5 Assume that conditions (A 1 ) and (H 1 ) hold. Then, for any k * > m * and ν 0,

lim inf β→0 1 | log β| inf τ ∈H(β,k * ,m * ) sup ν 0 R ν (τ ) lim inf β→0 1 | log β| inf τ ∈H(β,k * ,m * ) R ν (τ ) 1 I (4.5) and lim inf β→0 1 | log β| inf τ ∈H * (β,k * ,m * ) sup ν 0 R * ν (τ ) lim inf β→0 1 | log β| inf τ ∈H * (β,k * ,m * ) R * ν (τ ) 1 I . (4.6)
Proof. By Proposition 4 (see Appendix A), for all ν 0 and for a sufficiently small β > 0 (for which the conditions of this proposition hold)

inf τ ∈H(β,k * ,m * ) R ν (τ ) inf τ ∈∆(α 1,β , 1,β ) R ν (τ ) .
Now inequality (3.9) and condition (H 1 ) imply immediately (4.5). Proposition 5 (see Appendix A) implies that for all ν 0 and for a sufficiently small β > 0 (for which the conditions of this proposition hold)

inf τ ∈H(β,k * ,m * ) R * ν (τ ) inf τ ∈∆(α * 1,β , 1,β ) R * ν (τ ) .
Inequality (3.10) and condition (H 1 ) imply immediately (4.6).

Asymptotic optimality of the Shiryaev-Roberts procedure

To establish asymptotic optimality properties of the SR procedure with respect to the risks R ν (τ ) (for all ν 0) and sup ν 0 R ν (τ ) in the class H (β, k * , m * ) we need the uniform complete convergence condition (A 2 ) as well as the following condition.

(H 2 ) Parameter k * in (4.1) is a function of β, i.e. k * = k * β , such that lim β→0 | log α 2,β | | log β| = 1 , (4.7)
where α 2,β = α 2 (β, k * β ). The conditions (4.4) and (4.7) hold, for example, if

m * β = | ln β|/ 1,β and k * β = κ m * β , (4.8)
where κ > 1 is some fixed parameter. Hereafter x denotes the integer number less than or equal to x.

Next, denote by T β the SR procedure T (h β ) defined in (2.3) with the threshold h β given by

h β = 1 -α 2,β 2,β α 2,β .
(4.9)

The following theorem establishes first-order asymptotic optimality of the SR procedure T β with respect to the risks R ν (τ ) and sup ν 0 R ν (τ ) in the class H (β, k * , m * ) as β → 0, i.e., T β is an asymptotic solution of the problems (2.8) and (2.9) as the LPFA vanishes.

Theorem 6 If conditions (H 1 ) and (H 2 ) hold, then, for any 0 < β < 1, the SR procedure T β with the threshold h β given by (4.9) belongs to the class H (β, k * , m * ). If, in addition, condition (A 2 ) is satisfied, then the SR procedure T β is first-order asymptotically uniformly pointwise optimal and minimax in the class H (β, k * , m * ), i.e.,

lim β→0 inf τ ∈H(β,k * ,m * ) R ν (τ ) R ν (T β )
= 1 for all ν 0 (4.10)

and

lim β→0 inf τ ∈H(β,k * ,m * ) sup ν 0 R ν (τ ) sup ν 0 R ν (T β ) = 1 . (4.11)
Also, as β → 0, the following first-order asymptotic approximations hold for the pointwise and maximal risks:

R ν (T β ) ∼ inf τ ∈H(β,k * ,m * ) R ν (τ ) ∼ | log β| I
for any ν 0 (4.12)

and

sup ν 0 R ν (T β ) ∼ inf τ ∈H(β,k * ,m * ) sup ν 0 R ν (τ ) ∼ | log β| I . (4.13)
Proof. By Lemma 1, the SR procedure T (α, ) ∈ ∆(α, ) for any 0 < α, < 1. Moreover, note that the definition (4.9) yields T β = T (α 2,β , 2,β ), i.e., T β ∈ ∆(α 2,β , 2,β ). Using Proposition 4, we obtain that T β ∈ H (β, k * , m * ) for any 0 < β < 1. Furthermore, condition (H 2 ) and the definition of 2,β in (4.2) imply directly that lim β→0 log h β /| log β| = 1. Thus, the asymptotic upper bound (A.3) (with r = 1) in Proposition 3 implies the following upper bound lim sup

β→0 1 | log β| sup ν 0 R ν (T β ) 1 I .
The asymptotic equalities (4.10) and (4.11) follow immediately from this upper bound and the lower bounds (4.5) in Theorem 5. The asymptotic expansions (4.12) and (4.13) are obvious. Now we define

α 3 = α 3 (β, k * ) = β(1 -2,β ) k * 1 + β , (4.14)
where the function 2,β is defined in (4.2).

To prove asymptotic optimality in the class H * (β, k * , m * ) with respect to the risk R * ν (τ ) we need the following condition. where α 3,β = α 3 (β, k * β ). We can take, for example, the parameters k * = k * β and m * = m * β as in (4.8). It is easy to see that lim

β→0 | log α 3,β | + k * β log(1 -2,β ) = +∞ . (4.16)
I moved this one here. I think that this is the place for it, but check. (AT) Denote by T * β the SR procedure T (h * β ) defined in (2.3) with the threshold h * β given by

h * β = 1 -α 3,β 2,β α 3,β .
(4.17)

Theorem 7 If conditions (H 1 ) and (H 3 ) hold, then, for any 0 < β < 1, the SR procedure T * β with the threshold h * β given by (4.17) belongs to the class H * (β, k * , m * ). Assume that in addition condition (A 2 ) is satisfied. Then the SR procedure T * β is first-order asymptotically uniformly poitwise optimal and minimax in the class H * (β, k * , m * ), i.e.,

lim β→0 inf τ ∈H * (β,k * ,m * ) R * ν (τ ) R * ν (T * β )
= 1 for all fixed ν 0 . (4.18)

and

lim β→0 inf τ ∈H * (β,k * ,m * ) max 0 ν k * β R * ν (τ ) max 0 ν k * β R * ν (T * β ) = 1 . (4.19)
Also, as β → 0, the following first-order asymptotic approximations hold for the pointwise and maximal risks:

R * ν (T * β ) ∼ inf τ ∈H(β,k * ,m * ) R * ν (τ ) ∼ | log β| I for any ν 0 (4.20) and sup 0 ν k * β R * ν (T * β ) ∼ inf τ ∈H(β,k * ,m * ) sup 0 ν k * β R * ν (τ ) ∼ | log β| I . (4.21)
Proof. By Lemma 1, the SR procedure T (α, ) ∈ ∆(α, ) for any 0 < α, < 1. Now, note that the definition (4.17) yields T * β = T (α 3,β , 2,β ), i.e., T * β ∈ ∆(α 3,β , 2,β ). Using Proposition 5, we obtain that the stopping time T * β belongs to H * (β, k * , m * ) for any 0 < β < 1. Next, in view of the definition of h * β in (4.17) and of the form of the function 2,β in (4.2) we obtain, using condition (H 3 ), that lim β→0 log h * β /| log β| = 1. Thus, by (A.4) (with r = 1) in Proposition 3, lim sup

β→∞ 1 | log β| R * ν (T * β ) 1 I for all ν 0.
Comparing to the reverse inequality (4.5) implies (4.18). Asymptotic approximations (4.20) are obvious from (4.5) and (4.18). Using inequality (A.14) and (4.16) we obtain

P ∞ T * β k * β e log α 3,β -k * β log(1-2,β ) → 0 as β → 0 . Therefore, min 0 k k * β P k T * β > k = min 0 k k * β P ∞ T * β > k = P ∞ T * β > k * β = 1 -P ∞ T * β k * β → 1 as β → 0 .
Note that the maximal risk max

0 ν k * β R * ν (T * β ) can be estimated as max 0 ν k * β R * ν (T * β ) max 0 ν k * β R ν (T * β ) min 0 ν k * β P ∞ T * β > ν .
Asymptotic equality (A.5) with r = 1 in Proposition 3 implies that max

0 ν k * β R ν (T * β ) sup 0 ν<∞ R ν (T * β ) = log h * β I (1 + o(1)) as β → 0.
Since, as we mentioned above, lim β→0 log h * β /| log β| = 1, we obtain the upper bound lim sup ess sup P ν max

β→∞ 1 | log β| max 0 ν k * β R * ν (T * β ) 1 I . ( 4
1 i n Z ν ν+i I(1 + ε)n | F ν = 0 for all ε > 0 , (4.23)
where the parameter I is given in condition (A 1 ). Clearly, condition (4.23) is much stronger than the a.s. convergence condition (A 1 ) required in Theorem 5, and it does not hold in many important practical cases. Also, Lai's condition (24) in [START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF] for asymptotic optimality of the CUSUM procedure in the classes H γ and

H(β) = {τ : sup k 1 P ∞ (k τ < k + m * β ) β} is: lim n→∞ sup ν ess sup P ν Z ,n -ε | F = 0 for all ε > 0 . (4.24)
Typically this condition is more difficult to check than the uniform complete convergence condition (A 2 ) required in Theorem 7, which in fact can be relaxed to

∞ n=1 sup ν 0 P ν Z ν,n < -ε < ∞
(see Remark 4). In addition, for certain models condition (4.24) does not hold, while condition (A 2 ) holds (see, e.g., an example in Subsection 6.1 below). On the other hand, in the iid case condition (4.24) is less stringent than (A 2 ).

As in Theorem 4, the results of Theorem 6 and Theorem 7 can be extended to higher moments of the detection delay by strengthening the complete convergence with the uniform r-complete convergence (3.24). More specifically, the following asymptotic optimality result holds true.

Theorem 8 Assume that conditions (H 1 ) and (H 3 ) hold, and in addition, for some r > 1 the uniform r-complete convergence condition (3.24) is satisfied. Then, for any 0 < β < 1, the SR procedure T * β with the threshold h * β given by (4.17) belongs to the class H * (β, k * , m * ) and as β → 0 for any 0 < r

E ν (T * β -ν) |T * β > ν ∼ inf τ ∈H * (β,k * ,m * ) E ν (τ -ν) |τ > ν ∼ | log β| I for all ν 0 (4.25)
and max

0 ν k * β E ν (T * β -ν) |T * β > ν ∼ inf τ ∈H * (β,k * ,m * ) max 0 ν k * β E ν (τ -ν) |τ > ν ∼ | log β| I .
(4.26)

Therefore, the SR procedure T * β is first-order asymptotically uniformly pointwise optimal and also minimax in the class H * (β, k * , m * ) with respect to the moments of the detection delay up to order r.

Proof. The facts that T * β ∈ H * (β, k * , m * ) for any 0 < β < 1 and that log h * β ∼ | log β| as β → 0 were established in Theorem 7. Now, using (A.4) in Proposition 3 (along with the equality lim β→0 P ∞ (T * β > ν) = 1, ν 0), we obtain the upper bound

E ν (T * β -ν) r |T * β > ν | log β| I r (1 + o(1)) as β → 0.
Jensen's inequality and the lower bound (4.6) yield, for any r 1 and ν 0,

inf τ ∈H * (β,k * ,m * ) sup ν 0 E ν [(τ -ν) r |τ > ν] inf τ ∈H * (β,k * ,m * ) E ν [(τ -ν) r |τ > ν] | log β| I r (1 + o(1)),
which along with the previous upper bound proves (4.25).

To prove (4.26) it suffices to show that lim sup

β→0 max 0 ν k * β E ν (T * β -ν) r |T * β > ν | log β| r 1 I r . (4.27) Note that max 0 ν k * β E ν (T * β -ν) r |T * β > ν max 0 ν k * β E ν (T * β -ν) + ] r min 0 ν k * β P ∞ T * β > ν ,
where min

0 ν k * β P ∞ T * β > ν = P ∞ T * β > k * β → 1 as β → 0 .
As a result, using (A.5) in Proposition 3, we obtain max

0 ν k * β E ν (T * β -ν) r |T * β > ν sup 0 ν<∞ E ν (T * β -ν) + ] r P ∞ T * β > k * β = (log h * β /I) r (1 + o(1)) P ∞ T * β > k * β = | log β| I r (1 + o(1)).
This obviously yields the upper bound (4.27) and the proof is complete.

Remark 4 The uniform r-complete convergence condition (3.24) can be relaxed to the following onesided version: for some r > 1 and any ε > 0

∞ n=1 n r-1 sup ν 0 P ν Z ν,n < -ε < ∞.
In this case, one needs to additionally require the almost sure convergence condition (A 1 ), which guarantees condition (A.1) in Proposition 3.

Concentration inequalities for functions of homogeneous Markov processes

In this section, we obtain certain sufficient conditions for homogeneous Markov processes in order to verify condition (A 2 ) for this class of processes. Let (X n ) n 1 be a time homogeneous Markov process with values in a measurable space (X , B) with the transition probability P (x, A) defined in (B.2). In the sequel, we denote by E x (•) the expectation with respect to this probability. In addition, we assume that this process is geometrically ergodic, i.e., (B 1 ) Assume that there exist positives constants 0 < R < ∞, κ > 0, probability measure λ on (X , B) and the Lyapunov

X → [1, ∞) function V with λ(V) < ∞, such that sup n 0 e κn sup 0<f V sup x∈R 1 V(x) |E x f (X n ) -λ(f )| R .
Now, for some r > 0, we set

υ * r (x) = sup n 0 E x (V(X n )) r .
(5.1)

Let g be a measurable X × X → R function such that the following integrals exist g(u) = X g(v, u) P (u, dv) and λ( g) = X ×X g(v, u) P (u, dv) λ(du) .

(5.2)

(B 2 ) Assume that the function g is such that | g(x)| V(x) for all x ∈ X .
We study the concentration properties for the process W n (g) = n j=1 g(X j , X j-1 ), or equivalently the properties of the deviation W n (g) = n -1 W n (g) -λ( g).

Similarly to (5.1), we define for some r > 0

g * r (x) = sup j 1 E x |g(X j , X j-1 )| r .
(5.3) Now we set

W * r = 4 r-1 1 + u * r + |λ( g)| r + (16r) r/2 and u * r =
2rR 2 e κ e κ -1 r/2 .

(5.4)

Proposition 1 Assume that conditions (B 1 ) and (B 2 ) hold. Then for any x ∈ X and r 2, for which υ * r (x) < ∞ and g * r (x) < ∞, one has

E x | W n (g)| r W * r 1 + υ * r (x) + g * r (x) n r/2
for any n 2.

(5.5)

Proof. Note that we can represent the term W n (g) as

W n (g) = (n -1) λ( g) + g(x) + U n-1 + M n , (5.6)
where

U n = n j=1 g(X j ) -λ( g) := n j=1 u j and M n = n j=1
g(X j , X j-1 ) -g(X j-1 ) .

To estimate the powers of the U n we need to estimate the corresponding coefficient b j,n (r) from Proposition 6 (see Appendix B). To this end, note that for j l

E x u j |F l = E x u j |X 1 , . . . , X l = ω l-j (X l ) ,
where ω m (x) = E x g(X m ) -λ( g). Now, by condition (B 1 ), for any x ∈ X and any m 0, | ω m (x)| R V(x) e -κm , i.e., for any j l 1

|E x u j |F l | R V(X l ) e -κ(j-l) .
In particular, we have |u l | R V(X l ). Therefore, the coefficients (B.1) can be estimated as

b j,n (r) R 2 e κ e κ -1 υ * r (x) 2/r
and by Proposition 6 we get

E x |U n | r u * r υ * r (x) n r/2
, where u * r is defined in (5.1). Similarly, to estimate the martingale M n we make use of Proposition 6. Note that in this case the coefficient (B.1) has the form b j,n (r) = (E x |g(X j , X j-1 ) -g(X j-1 )| r ) 2/r , and it can be estimated for j 1 as b j,n (r) 2 r-1 E x g(X j , X j-1 ) r + E x g(X j-1 ) r 2/r .

Taking into account Jensen's inequality and the definition (5.3), we obtain that b j,n (r) 4(g * r (x)) 2/r , and therefore, from Proposition 6 it follows that for n 1, E x |M n | r (8r) r/2 g * r (x)n r/2 . Therefore, taking into account that

| W n (g)| | g(x)| + |λ( g)| + |U n-1 | + |M n | n ,
we obtain, for any n 1,

E x | W n (g)| r 4 r-1 n r/2 | g(x)| r + |λ( g)| r + u * r υ * r (x) + (8r) r/2 g * r (x) 4 r-1 n r/2 (1 + u * r ) υ * r (x) + |λ( g)| r + (8r) r/2 g * r (x) W * r 1 + υ * r (x) + g * r (x) n r/2 .
Hence Proposition 1. As we will see later in Section 6, condition (B 1 ) does not hold directly for some time series. For this reason, we introduce the following modification of this condition.

(B 1 ) Assume that there is some integer p 1 such that for any 0 ι p -1 there exist positive constants 0

< R ι < ∞, κ ι > 0, probability measure λ ι on X and the Lyapunov X → [1, ∞) function V ι with λ ι (V ι ) < ∞, such that sup l 0 e κ ι l sup 0<f V ι sup x∈R 1 V ι (x) E x f (X pl+ι ) -λ ι (f ) R ι .
Similarly to (5.1) we introduce

υ * r,ι (x) = sup j 0 E x V ι (X pj+ι ) r and υ * r,max (x) = max 0 ι p-1 υ * r,ι (x) (5.7)
and impose the following condition:

(B 2 ) Assume that the function g defined in (5.2) is such that | g(x)| min 0 ι p-1 V ι (x) for all x ∈ X . Now we set W n (g) = n -1 W n (g) -λ( g), where λ(g) = (1/p) p ι=0 λ ι (g).
Proposition 2 Assume that conditions (B 1 ) and (B 2 ) hold. Then for any x ∈ X and any r 2, for which υ * r,max (x) < ∞ and g * r (x) < ∞, there exists a constant W * r > 0 such that

E x |W n (g)| r W 1 + υ * r,max (x) + g * r (x) n r/2
for any n 2 .

(5.8)

Proof. Note that the term W n (g) can be represented as W n (g) = W n,1 (g) + M n , where W n,1 (g) = n j=1 g(X j-1 ) and M n is defined in (5.6). Let now n -1 = mp + r for some 0 r p -1. Thus,

W n,1 (g) = p-1 ι=0 m l=0 g(X pl+ι ) - p-1 ι=r+1 g(X pm+ι ) = nλ( g) + p-1 ι=0 U m,ι -rλ( g) - p-1 ι=r+1 g(X pm+ι ) ,
where U m,ι = m l=0 g(X pl+ι ) -λ( g) . In just the same way as in the proof of Proposition 1, we obtain that for some constant u * r,ι > 0 (5.9) where u * r,max = max 0 ι u * r,ι . Furthermore,

E x |U m,ι | r u * r,ι υ * r,ι (x) m r/2 u * r,max υ * r,max (x) n r/2 ,
|W n (g)|| r n |λ( g)| + 1 n p-1 ι=0 |U m,ι | + 1 n |M n | + 1 n p-1 ι=r+1 | g(X pm+ι )| .
Using the upper bound (5.9) in this inequality, we obtain the inequality (5.8).

We return to the detection problem for Markov processes, assuming that the sequence (X n ) n 1 is a Markov process, such that (X n ) 1 n ν is a homogeneous process with the transition (from x to y) density f 0 (y|x) and (X n ) n>ν is homogeneous positive ergodic with the transition density f 1 (y|x) and the ergodic (stationary) distribution λ. The densities f 0 (y|x) and f 1 (y|x) are calculated with respect to a sigma-finite positive measure µ on B.

In this case, we can represent the process Z k n defined in (2.2) as

Z k n = n j=k+1 g(X j , X j-1 ) , g(y, x) = log f 1 (y|x) f 0 (y|x) .
(5.10) Therefore, in this case,

g(x) = X g(y, x) f 1 (y|x) µ(dy) .
(5.11)

We now formulate the conditions that are sufficient for the main condition (A 2 ) to hold in the case of Markov processes. We write E x,0 for the expectation with respect to the distribution P x,0 (•) = P 0 (•|X 0 = x).

(C 1 ) Assume that there exists a set C ∈ B with µ(C) < ∞ such that

(C1.1) f * = inf x,y∈C f 1 (y|x) > 0. (C1.2) There exists X → [1, ∞) Lyapunov's function V such that V(x) g(x) and V * = sup x∈C V (x) < ∞. (C1.3) For some 0 < ρ < 1 and D > 0 and for all x ∈ X , E x,0 V(X 1 ) (1 -ρ)V(x) + D1l {C} (x). (C 2 ) Assume that there exists r > 2 such that ǧr = sup k 1 E ∞ g * r (X k ) < ∞ and υr = sup k 1 E ∞ υ * r (X k ) < ∞ , where g * r (x) = sup n 1 E x,0 [g(X n , X n-1 ] r and υ * r (x) = sup n 0 E x,0 [V(X n )] r .
Theorem 9 Conditions (C 1 ) and (C 2 ) imply condition (A 2 ) with I = λ( g).

Proof. Note first that in the Markov case

Z k k+n = 1 n n l=1
g(X l+k , X l+k-1 ) -λ( g) .

(5.12)

Therefore, using the fact that the process (X n ) n ν+1 is homogeneous, we obtain

P ν | Z ν ν+n | ε = E ν Ψ n (X ν ) = E ∞ Ψ n (X ν ) ,
where

Ψ n (x) = P x,0 (| W n | ε). Note now that in view of condition (C 1 ), for any x ∈ C, P x,0 (A) = A f 1 (y|x) µ(dy) A∩C f 1 (y|x) µ(dy) f * µ(A ∩ C) = δς(A) ,
where δ = f * µ(C) and ς(A) = µ(A ∩ C)/µ(C). So Theorem 11 in Appendix B implies condition (B 1 ), and therefore, Proposition 1 yields

Ψ n (x) W * r 1 + υ * r (x) + g * r (x) n r/2 ε r for any x ∈ X ,
where W * r is defined in (5.4). Thus, using condition (C 2 ) we obtain that sup

ν 0 P ν | Z ν ν+n | ε W * r (1 + ǧr + υr ) n r/2 ε r .
This implies immediately that for any positive ε the sum defined in (3.14) is bounded as

Υ * (ε) W * r (1 + ǧr + υr ) ε r n 1 1 n r/2 .
Hence Theorem 9. Now we obtain sufficient conditions for (B 1 ) and (B 2 ). To this end, we denote by f p (y|x) the conditional density of X k+p with respect to X k .

(C 1 ) Assume that there exist an integer p 1 and a set C ∈ B with µ(C) < ∞ such that

(C 1.1) f * = inf x,y∈C f p (y|x) > 0 . (C 1.2) There exists X → [1, ∞) Lyapunov's function V such that V(x) g(x) and V * = sup x∈C V (x) < ∞. (C 1.3) For some 0 < ρ < 1 and D > 0 and for all x ∈ X , E x,1 V(X p ) (1 -ρ)V(x) + D1l {C} (x).
Theorem 10 Conditions (C 1 ) and C 2 ) imply condition (A 2 ) with I = λ( g).

Proof. First, let X l = X k+pl+ι for some fixed 0 ι p -1. Condition (C 1 ) implies that for any 0 ι p -1 the transition probability of the homogeneous Markov process ( X l ) l 1 for any x ∈ C

Px (A) = A f p (y|x) µ(dy) A∩C f 1 (y|x) µ(dy) f * µ(A ∩ C) = δς(A) ,
where δ = f * µ(C) and ς(A) = µ(A ∩ C)/µ(C). So Theorem 11 implies condition (B 1 ) with the same R ι = R, λ ι = λ, V ι = V and κ ι for 0 ι p -1. Hence, in this case λ = λ and, therefore, for any x ∈ X by Proposition 2 and condition (C 2 ) for the process Z k k+n defined in (5.12) we obtain that sup

ν 0 P ν | Z ν ν+n | ε W * r (1 + ǧr + υr ) n r/2 ε r .
This implies immediately that for any ε > 0 the sum defined in (3.14) is bounded as

Υ * (ε) W * r (1 + ǧr + υr ) ε r n 1 1 n r/2 .
Hence Theorem 10.

Examples

We now present several examples that illustrate the general theory developed in Sections 3 and 4. The main goal is to verify condition (A 2 ) in order to be able to apply the theorems proved in Sections 3 and 4 and establish asymptotic pointwise and minimax optimality of the SR detection procedure.

Example 1: Two dimensional AR process

This example motivates the necessity of relaxing conditions (4.23) and (4.24) proposed by [START_REF] Lai | Information bounds and quick detection of parameter changes in stochastic systems[END_REF] in certain interesting problems. It shows that both conditions (4.23) and (4.24) do not hold, while our uniform complete convergence condition (A 2 ) holds.

Hereafter the prime in the vector Y denotes the transposition. Consider the two dimensional autoregressive (AR) process X k = (X 1,k , X 2,k ) defined as

X k = Λ 1l {k ν} + A k X k-1 + ξ k , (6.1)
where

Λ = λ 1, , 0 0 , λ 2 , A k = σ 1 η 1,k , 0 0 , σ 2 η 2,k and ξ k = ξ 1,k ξ 2,k .
Here the sequences (η 1,k ) k 1 and (η 2,k ) k 1 are iid normal N (0, 1) random variables independent of the sequence (ξ k ) k 1 , which is the iid sequence of N (0, Q) random vectors with

Q = 1 + ρ 2 , ρ ρ , 1
and ρ > 0 is some fixed number which will be specified later. It is clear that the iid random matrices (A k ) k 1 in (6.1) are such that

E[A 1 ⊗ A 1 ] =        σ 2 1 , 0 , 0 , 0 0 , 0 , 0 , 0 0 , 0 , 0 , 0 0 , 0 , 0 , σ 2 2        .
As to the coefficients σ i , we choose them so that this matrix has the modules of its eigenvalues less than one, i.e., 0 < σ 2 1 < 1 and 0 < σ 2 2 < 1 . (6.2)

Under these conditions the process (X k ) k>ν has the stationary distribution in R 2 given by

ζ = ζ 1 ζ 2 = ∞ k=1 Π k-1 ξ k , (6.3)
where Π 0 = I 2 and Π m = m j=1 A j for m 1. One can deduce directly that this vector, conditioned on

G = σ{η 1,k , η 2,k , k 1}, is Gaussian N (0, F) with F = ∞ k=1 Π k-1 V Π k-1 = (1 + ρ 2 )ς 11 , ρς 12 ρς 12 , ς 22 , (6.4)
where

ς ij = ∞ k=1 σ k-1 i σ k-1 j k-1
l=1 η i,l η j,l . Note now that, conditioned on X k-1 , . . . , X 1 , the random vector

X k for k > ν is Gaussian N (0, D k-1 ) with D k-1 = G(X k-1 ), where for x = (x 1 , x 2 ) G(x) = 1 + ρ 2 + σ 2 1 x 2 1 , ρ ρ , 1 + σ 2 2 x 2 2 . (6.5)
So we can represent the LLR as

Y j = log f 1,j (X j |X j-1 ) f 0,j (X j |X j-1 ) = κ(X j-1 ) -j , (6.6)
where for any x = (x 1 , x 2 )

κ(x) = 1 2 x Λ G -1 (x) Λx and j = X j-1 Λ D -1 j-1 X j . (6.7)
Therefore, by the ergodic theorem,

P 0    lim n→∞ n -1 n j=1 Y j = E κ(ζ)    = 1 , i.e., I = E κ(ζ)
, where the vector ζ is defined in (6.3). Clearly, condition (4.24) in this case has the following form: for any ε > 0

lim n→∞ sup x∈R 2 P 0   n j=1 Y j < (I -ε)n | X 0 = x   = 0 ,
where I = E κ(ζ). We now establish that it does not hold by showing that for some 0

< ε < 1 lim inf n→∞ sup x∈R 2 P 0   n j=1 Y j < (I -ε)n | X 0 = x   > 0 . (6.8)
Observe first that for any n 1 sup

x∈R 2 P 0   n j=1 Y j < (I -ε)n | X 0 = x   lim x 2 →∞ P 0   n j=1 Y j < (I -ε)n | X 0 = (0, x 2 )  
and that for any x 1

κ 1 (x 1 ) = lim |x 2 |→∞ κ(x 1 , x 2 ) = λ 2 1 x 2 1 2(1 + ρ 2 + σ 2 1 x 2 1 ) + λ 2 2 2σ 2 2 and P 0 (lim n→∞ n -1 n j=1 κ 1 (X 1,j ) = I 1 ) = 1
, where

I 1 = E κ 1 (ζ 1 ) λ 2 1 E ζ 2 1 2(1 + ρ 2 ) + λ 2 2 2σ 2 2 = λ 2 1 E ς 11 2 + λ 2 2 2σ 2 2 = λ 2 1 2(1 -σ 2 1 ) + λ 2 2 2σ 2 2 .
Let us show now that there exist σ 1 > 0 and ρ > 0 for which I > I 1 . If so, then taking into account Lemma 2 in Appendix A, we obtain that for some ε > 0

lim n→∞ sup x∈R 2 P 0   n j=1 Y j < (I -ε)n | X 0 = x   = 1 .
Hence, (6.8) follows. Indeed, choosing in (6.1) the parameter σ 2 1 as a function of ρ such that σ 2 ρ 4 → 0 as ρ → ∞, we obtain in view of Lemma 3 in Appendix A that there exist σ 1 and ρ > 0 for which I > I 1 . This implies the inequality (6.8), and hence, condition (4.24) does not hold.

Note that condition (4.23) also does not hold. Indeed, in the case considered this condition has the following form: for any ε > 0

lim n→∞ sup x∈R 2 P 0   n j=1 Y j > (I + ε)n | X 0 = x   = 0 .
If we put ρ = 0, then we obtain that lim

|x 1 |,|x 2 |→∞ κ(x 1 , x 2 ) = λ 2 1 /(2σ 2 1 ) + λ 2 2 /(2σ 2
2 ) := κ * and κ * > κ(x 1 , x 2 ) for any x 1 and x 2 from R. Therefore, κ * > I = Eκ(ζ). Similarly to the above reasoning we obtain that for some ε > 0

lim n→∞ sup x∈R 2 P 0   n j=1 Y j > (I + ε)n | X 0 = x   lim n→∞ lim |x 1 |∧|x 2 |→∞ P 0   n j=1 Y j > (I + ε)n | X 0 = x   = 1 ,
where a ∧ b = min(a, b).

On the other hand, our uniform complete convergence condition (A 2 ) holds. Indeed, as we will see in Example 4 below, condition (A 2 ) holds even for a more general vector AR model than (6.1). Thus, the SR procedure is asymptotically minimax.

Example 2: Change in the correlation coefficient of the AR(1) model

Consider the change of the correlation coefficient in the first-order AR model

X n = ϑ n X n-1 + w n , (6.9)
where ϑ n = a 0 1l {n ν} + a 1 1l {n>ν} and (w n ) n 1 are iid not necessarily Gaussian random variables with E w 1 = 0, E w 2 1 = 1 and a known density ψ(x) such that for any n 1 inf -n x n ψ(x) > 0 . (6.10)

We assume that the parameters -1 < a i < 1 are known. In this case, the ergodic distributions for (X n ) n ν and (X n ) n ν+1 are given by the random variables w 0 and w 1 , respectively, which are defined as

w i = ∞ j=1 (a i ) j-1 w j , i = 0, 1 . (6.11)
The pre-change and post-change conditional densities are f 0 (X n |X n-1 ) = ψ(X n -a 0 X n-1 ) for all 1 n ν and f 1 (X n |X n-1 ) = ψ(X n -a 1 X n-1 ) for n > ν, where X 0 is an initial value independent of the sequence (w n ) n 1 . Note that condition (6.10) implies the lower bound (C1.1) in condition (C 1 ) for any "minorization" set of the form

C = [-n, n]. It is easily seen that g(y, x) = log f 1 (y|x) f 0 (y|x) = log ψ(y -a 1 x) ψ(y -a 0 x) (6.12) and g(x) = R log ψ(y -a 1 x) ψ(y -a 0 x) ψ(y -a 1 x) dy . (6.13)
Assume that there exist q * 1 and ι > 0 such that

E |w 1 | ι < ∞ , sup y,x∈R |g(y, x)| (1 + |y| ι + |x| ι )
q * and sup

x∈R g(x) (1 + |x| ι ) q * . (6.14)
For example, in the Gaussian case (i.e., ψ is (0, 1) Gaussian density),

g(y, x) = (y -a 0 x) 2 -(y -a 1 x) 2 2 and g(x) = (a 1 -a 0 ) 2 x 2 2 ,
i.e., conditions (6.14) are satisfied with ι = 2 and

q * = max 1, |a 2 1 -a 2 0 | + (a 1 -a 0 ) 2 + 1 2 .
Define the Lyapunov function as

V(x) = q * (1 + |x| ι ) . (6.15) Obviously, lim |x|→∞ E x,0 V(X 1 ) V(x) = lim |x|→∞ 1 + E |a 1 X + w 1 | ι 1 + |x| ι = |a 1 | ι < 1 .
Therefore, for any |a 1 | ι < ρ < 1 there exist n 1 and D > 0 such that condition (C 1 ) holds with C = [-n, n].

Let us check now condition (C 2 ). Assume that there exists r > 2 for which

R |v| r 1 ψ(v) dv < ∞, r 1 = ιr . (6.16) This condition implies that E | w 0 | r 1 < ∞ and E | w 1 | r 1 < ∞.
Moreover, taking into account the ergodicity properties, we obtain that for any x ∈ R

lim k→∞ E x,∞ |X k | r 1 = E | w 0 | r 1 < ∞ and lim k→∞ E x,0 |X k | r 1 = E | w 0 | r 1 < ∞ . (6.17)
Note also that under the probability P x,0 for any j 1, X j = a j 1 x+ j l=1 a j-l 1 w l . Therefore, E x,0 |X j | r1 2 r1 (|x| r1 + E 0,0 |X j | r1 ), i.e., using the last convergence in (6.17), we obtain that for some C * > 0

M * (x) = sup j 1 E x,0 |X j | r 1 C * (1 + |x| r 1 ) .
Using now the first convergence in (6.17), we obtain that sup k 1 E M * (X k ) < ∞. So the upper bounds in (6.14) imply condition (C 2 ). By Theorem 9, condition (A 2 ) holds for the model (6.9) if density ψ of the iid random variables (w n ) n 1 satisfies conditions (6.10) and (6.14). The Kullback-Leibler information number is

I = λ( g) = R R log ψ(y -a 1 x) ψ(y -a 0 x) ψ(y -a 1 x)dy λ(dx) ,
where λ is the distribution of w 1 given in (6.11). Hence, by Theorem 3 and Theorem 7, the SR procedure is asymptotically minimax with respect to the expected detection delays.

In the particular Gaussian case where ψ is N (0, 1), the random variable w 1 is N 0, (1 -a 2 1 ) -1 , and the Kullback-Leibler information number can be calculated explicitly, I = (a 1 -a 0 ) 2 /2(1 -a 2 1 ).

Example 3: AR process with ARCH(1) errors

Consider now the change of the correlation coefficient in the first-order AR model with ARCH(1) errors [START_REF] Borkovec | The tail of the stationary distribution of an autoregressive process with ARCH(1) errors[END_REF]], assuming that for n 1 (6.18) where an initial value X 0 is independent of the sequence (w n ) n 1 . The sequence ϑ n is defined in (6.9) with the known parameters a i such that a 2 i + σ 2 < 1. As in the model (6.9), we assume that (w n ) n 1 are iid not necessarily Gaussian random variables with E w 1 = 0, E w 2 1 = 1 and a known density ψ(x) satisfying condition (6.10). The variance σ 2 > 0 is known. In just the same way as in the model (6.9), we find that the pre-change and post-change conditional densities f 0 (X n |X n-1 ) and f 1 (X n |X n-1 ) are of the form

X n = ϑ n X n-1 + 1 + σ 2 X 2 n-1 1/2 w n ,
f 0 (y | x) = ψ (l 0 (y, x)) √ 1 + σ 2 x 2 and f 1 (y | x) = ψ (l 1 (y, x)) √ 1 + σ 2 x 2 ,
where l 0 (y, x) = (y -a 0 x)/ √ 1 + σ 2 x 2 and l 1 (y, x) = (y -a 1 x)/ √ 1 + σ 2 x 2 . Obviously, the property (6.10) implies the lower bound (C1.1) in condition (C 1 ). The function (6.12) is given by g(y, x) = log[ψ(l 1 (x, y))/ψ(l 0 (x, y))] and

g(x) = 1 √ 1 + σ 2 x 2 R log ψ (l 1 (y, x)) ψ (l 0 (y, x)) ψ (l 1 (y, x)) dy .
Assume that there exist q * 1 and ι > 0 such that sup

y,x∈R |g(y, x)| (1 + |l 0 (y, x)| ι + |l 1 (y, x)| ι )
q * and sup x∈R g(x) q * . (6.19)

For example, in the Gaussian case (i.e., ψ is standard Gaussian density),

g(y, x) = l 2 0 (y, x) -l 2 1 (y, x) 2 and g(x) = (a 1 -a 0 ) 2 x 2 2(1 + σ 2 x 2 ) ,
i.e., conditions (6.19) are satisfied with ι = 2. The Lyapunov function is any R → (1, +∞) function which satisfies the drift condition (C1.3). We set V(x) = q * (1 + |x| δ ) for 0 < δ < x * , where x * = min(x * ,0 , x * ,1 ) and x * ,i is a unique positive root of the equation κ(x) = 1, where κ(

x) = E |a i + σ w 1 | x .
It is well known [START_REF] Klüppelberg | The tail of the stationary distribution of a random coefficient AR(q) process with applications to an ARCH(q) process[END_REF]] that if E w 2 1 = 1, then x * > 2. Direct calculations yield (6.20) Therefore, for any κ(δ) < ρ < 1 there exist n 1 and D > 0 for which condition (C 1 ) holds with C = [-n, n].

lim |x|→∞ E x,0 V(X 1 ) V(x) = κ(δ) < 1 .
Next, we verify condition (C 2 ). To this end, note that under the probability P 0 we have

l 1 (X j , X j-1 ) = w j and |l 0 (X j , X j-1 )| |w j | + |a 1 -a 0 | σ .
So, for any r > 2 satisfying (6.16) with ι > 0 from condition (6.19), we obtain that, for some constant C * > 0, g * r (x) C * (1 + E|w 1 | ιr ), i.e., ǧr < ∞. Now we check the last inequality in (C 2 ). Fix r > 2 such that r 1 = δr < x * . Evidently, this is possible for a sufficiently small δ > 0. In analogy with (6.20) we can obtain that

lim |x|→∞ E x,0 V 1 (X 1 ) V 1 (x) = κ(r 1 ) < 1 ,
where V 1 (x) = 1+|x| r 1 . Therefore, conditions (H 1 ) and (H 2 ) hold, and using Theorem 11 in Appendix B, we obtain that for some constant C * > 0, sup j 1 E x,0 |X j | r 1 C * (1 + |x| r 1 ). Similarly we obtain that sup j 1 E ∞ |X j | r 1 < ∞, i.e., (C 2 ) is satisfied.

Thus, by Theorem 9, condition (A 2 ) holds for the model (6.18) where the iid random variables (w n ) n 1 have density ψ(x) that satisfies conditions (6.10) and (6.16) with ι > 0 from condition (6.19).

Note that in this case there exists the stationary distribution λ for (X n ) n>ν which in the Gaussian case, w n ∼ N (0, 1), is given by the following random variable (6.21) where (υ l ) l 1 is an iid N (a 1 , σ 2 ) sequence independent of (w j ) j 1 . The Kullback-Leibler information is (6.22) where

∞ j=1 j-1 l=1 υ l w j ,
I = R 1 √ 1 + σ 2 x 2 R log ψ (l 1 (y, x)) ψ (l 0 (y, x)) ψ (l 1 (y, x)) dy λ(dx) = (a 1 -a 0 ) 2 √ 2π E G( υ) ,
G(z) = 1 z ∞ 0 y 2 e -y 2 2z 2 1 + σ 2 y 2 dy and υ =   1 + ∞ j=2 j-1 l=1 υ 2 l   1/2
.

By Theorem 3 and Theorem 7, the SR procedure is asymptotically minimax.

6.4 Example 4: Change in the parameters of the multivariate linear difference equation Consider the multivariate model in R p given by (6.23) where A 0,n and A 1,n are p × p random matrixes and (w n ) n 1 is an iid sequence of Gaussian random vectors N (0, Q 0 ) in R p with the definite p × p matrix Q 0 . Assume also that A i,n = A i + B n and (B n ) n 1 are iid Gaussian random matrixes N (0 , Q 1 ), where the p 2 × p 2 matrix Q 1 is not necessary positive definite. Assume, in addition, that E[A i,1 ⊗ A i,1 ], i = 0, 1 have the modules less than one.

X n = A 0,n 1l {n ν} + A 1,n 1l {n>ν} X n-1 + w n ,
In this case, the processes (X n ) 1 n ν and (X n ) n>ν are ergodic with the ergodic distributions given by the vectors [START_REF] Klüppelberg | The tail of the stationary distribution of a random coefficient AR(q) process with applications to an ARCH(q) process[END_REF]] ς i = l 1 l-1 j=1 A i,j w l , i.e., the invariant measures λ i on R p are defined as λ i (A) = P(ς i ∈ Γ ) for any Γ ∈ B(R p ). As shown in [START_REF] Feigin | Random coefficient autoregressive processes: A Markov chain analysis of stationarity and finiteness of moments[END_REF], there exists a positive definite p × p matrix T and the constant K * > 0 such that the function V (x) = c(1 + x T x) and the set C = {x ∈ R p : x T x K * } satisfy condition (C1.3) for any c 1. The function g(y, x) can be calculated for any x, y from R p as

g(y, x) = |l 0 (y, x)| 2 -|l 1 (y, x)| 2 2 = y G -1 (x)(A 1 -A 0 )x + x A 0 G -1 (x) A 0 x -x A 1 G -1 (x) A 1 x 2 , where l i (y, x) = G -1/2 (x)(y -A i x) and G(x) = E[B 1 xx B 1 ] + Q 0 . From this we obtain that g(x) = 1 2 |G -1/2 (x)(A 1 -A 0 )x| = 1 2 x (A 1 -A 0 ) G -1 (x)(A 1 -A 0 )x .
Assume that sup

x∈R p |G -1/2 (x)(A 1 -A 0 )x| < ∞ . (6.24)
Note that for the model (6.1) this condition holds. So under this condition g * = sup x∈R p g(x) < ∞. Thus, choosing V (x) = c * (1 + (x T x) δ ) with c * = 1 + g * and any fixed 0 < δ < 1 and using the Jensen inequality yields condition (C 1 ). Let us check now condition (C 2 ). Note that under the probability P 0 we obtain that for any j 1 the vector ξ j = l 1 (X j , X j-1 ) is (0, I p ) Gaussian in R p . Moreover, by condition (6.24),

|l 0 (X j , X j-1 )| = |ξ j + G -1/2 (X j-1 )(A 1 -A 0 )X j-1 | |ξ j | + C *
for some positive C * . Clearly, ǧr < ∞ for any r > 0. We now check the last inequality in (C 2 ). First note that, as it is shown in [START_REF] Feigin | Random coefficient autoregressive processes: A Markov chain analysis of stationarity and finiteness of moments[END_REF], under our conditions E|ς i | 2 < ∞. Next, observe that under the probability P x,0

X j = l-1 j=1 A 1,j x + j l=1 l i=l+1 A 1,i w l .
So, for any 0 < q 2, E x,0 |X j | q C * (|x| q + E 0,0 |X j | q ). In view of the ergodicity property we obtain that lim

j→∞ E ∞ |X j | q = E ∞ |ς 0 | q < ∞ and lim j→∞ E 0,0 |X j | q = E 0,0 |ς 1 | q < ∞ ,
i.e., sup j 1 E x,0 |X j | q C * (1 + |x| q ) for some positive C * . So υr < ∞ for any r > 2 for which δr 2.

Hence, by Theorem 9, condition (A 2 ) is satisfied with I = E g(ς 1 ), and by Theorem 3 and Theorem 7 the SR detection procedure is asymptotically minimax. Let us now generalize the results of Subsection 6.2 for problem of detecting the change of the correlation coefficient in the p-th order AR process, assuming that for n 1 (6.25) where ϑ i,n = a 0,i 1l {n ν} + a 1,i 1l {n>ν} and (w n ) n 1 are iid, not necessarily Gaussian random variables with E w 1 = 0, E w 2 1 = 1. In the sequel, we use the notation a i = (a i,1 , . . . , a i,p ) . The process(6.25) is not Markov, but the p-dimensional process Xn = (X n , . . . , X n-p+1 ) ∈ R p (6.26) is Markov. Note that for n > ν Xn = A Xn-1 + wn , (6.27)

X n = ϑ 1,n X n-1 + . . . + ϑ p,n X n-p + w n ,
where Assume that all eigenvalues of the matrix A have the modules less than one. The ergodic distribution is given by the vector ς = l 1 A l-1 wl ∼ N (0, F), where

A =        a 1,1 , . . . , a 1,p 1
F = l 0 A l B (A ) l . (6.28)
Obviously, condition (C1.1) does not hold for the process (6.26).

To fulfill this condition we replace this process by the embedded homogeneous Markov process Y n = Xnp+ι for some 0 ι p -1. This process can be represented as

Z n = A p Z n-1 + ζ n , ζ n = p-1 j=0 A j wnp+ι-j . (6.29)
Clearly, ζ n is Gaussian with the parameters (0, Q), where Q = p-1 j=0 A j B (A ) j . One can check directly that this matrix is positive definite. Define the function V (x) : R p → R as (6.30) where c 1 will be specified later. Let t max = max x =1 x T x and t * = 1 -1/t max . Obviously, t max > 1, i.e., 0 < t * < 1. Now we set K

V (x) = c(1 + x T x) , T = ∞ l=0 (A ) pl A pl ,
= [(1 + E ζ 1 2 )/ρ] 1/2 with ρ = (1 -t * )/2 and D = 1 + T 1/2 A p 2 K 2 + E ζ 1 2 .
Next we need the minorizing measure in condition (H 1 ) on the Borel σ-field in R p . To this end, we define ν(Γ ) = mes(Γ ∩ C)/mes(C) for any Borel set Γ in R p , where mes(•) is the Lebesgue measure in R p . Finally, we show that, for any 0 ι < p, the Markov process (6.29) satisfies condition (C 1.3). Indeed, note that

E(V (Z 1 )|Z 0 = x) = c + cE T 1/2 (A p x + ζ 1 ) 2 = c + c (x (A p ) T A p x) + rE ζ 1 2 .
Taking into account that

x (A p ) T p x x T x = 1 - x 2 x T x 1 - 1 t max = t * , we obtain that, for x K, E(V (Z 1 ) | Z 0 = x) (1 -ρ) V (x). Moreover, g(x) = 1 2   p j=1 (a 1,j -a 0,j ) x j   2 p j=1 (a 1,j -a 0,j ) 2 2 |x| 2 .
Therefore, choosing in (6.30) c = 1 + p j=1 (a 1,j -a 0,j ) 2 /2, we obtain condition (C 1 ). Condition (C 2 ) can be checked in the same way as in Example 2. By Theorem 10, condition (A 2 ) holds with I = E g(ς) = a F a/2, where a = a 1 -a 0 and the matrix F is defined in (6.28), and the SR procedure is asymptotically minimax.

Monte Carlo simulations

For the purpose of evaluation of the non-asymptotic performance of the SR detection procedure and establishing accuracy of the first-order asymptotic approximations for the average delay to detection, we performed MC simulations for AR(1) model (6.9) in Example 2, Section 6.2. We assume that the noise model is Gaussian, i.e., w n ∼ N (0, 1) and independent. The pre-and post-change correlation coefficients a 0 and a 1 are selected as a 0 = 0.1 and a 1 = 0.5. Is this correct?? (AT) The change point is ν = 10. We denote by R ν (T β ) and R * ν (T * β ) the empirical pointwise risks (average delays to detection) for the SR detection procedures T β and T * β , correspondingly. These MC estimates of the risks were calculated on the basis of N = 10 6 replications. We use the functions and parameters defined in (4.3) and (4.8) with δ * = 1/ι and κ = 1.2. What is ι in δ * = 1/ι? (AT) The results of simulations are presented in Table 1. Recall that the first-order approximations (for large thresholds h or small LPFA β) to the average delays to detection

(ADD) R ν (T β ) = E ν (T β -ν) + and R * ν (T * β ) = E ν (T * β -ν|T * β > ν), R ν (T β ) ≈ log h β I , R * ν (T * β ) ≈ log h * β I (7.1)
follow from the results of Section 4 and Proposition 3. These first-order approximations (FOA ADD) are also included in the table for the LPFA ranging from 10 -1 to 10 -10 .

Table 1 The results of MC simulations for detecting a change in the correlation coefficient in the AR(1) model (6.9) It is seen that the first-order asymptotic approximations (7.1) are not especially accurate and constantly overestimate the real value of the ADD. This is expected since they do not account for an overshoot over the threshold at stopping and a negative constant C, which is approximately equal to

LPFA β MC ADD R ν (T β ) FOA ADD Rν (T β ) MC ADD R * ν (T * β ) FOA ADD R * ν (T * β ) 10 -
C ≈ -E 0 log 1 + ∞ n=1 exp - (X n -a 0 X n-1 ) 2 -(X n -a 1 X n-1 ) 2 2 .
Thus, for practical purposes it would be useful to obtain a higher order approximation (up to an additive vanishing term o(1)). However, this task is out of the scope of the present paper and will be considered elsewhere.

Proof. Let τ ∈ ∆(α 2 , 2,β ). Taking in (A.14) l = k * , we obtain sup

1 k k * -m * P ∞ (k τ < k + m * ) P ∞ (τ < k * ) α 2 (1 -2,β ) -k * = β .
Hence, τ ∈ H(β, k * , m * ), i.e., the first inclusion in (A.20) follows. Now, if τ ∈ H (β, k * , m * ), then P ∞ (τ < 1 + m * ) β. Therefore, taking in (3.4) = 1,β , we obtain Proof. First we show the left inclusion. Let τ ∈ ∆(α 3 , 2,β ). Then, taking into account the inequality (A.14) for any l = k * and using the definition of α 3 , we obtain that sup

1 k k * -m * P ∞ (τ < k + m * |τ k) sup 1 k k * -m * P ∞ (τ < k + m * ) P ∞ (τ k) P ∞ (τ < k * ) 1 -P ∞ (τ < k * ) α 3 (1 -2,β ) -k * 1 -α 3 (1 -2,β ) -k * = β ,
i.e., τ belongs to H(β, k * , m * ). Now we show the right inclusion in (4.7). Let τ be from H(β, k * , m * ). Then, using the definition of the class H(β, k * , m * ) in (A.20), we obtain that P ∞ (τ < m * + 1) β. Therefore, similarly to the proof of the right inclusion in (A.20) we obtain that τ ∈ ∆(α 1 , 1,β ), and the proof is complete.

A.6 Auxiliary results for Example 1, Subsection 6.1

Recall that κ(x) and j are defined in (6.7). where F j = σ{X 1 , . . . , X j }. Using the definition of the sequence j in (6.7), we obtain that

E 0 2 j |F j-1 = X j-1 Λ G -1 (X j-1 )Λ X j-1 σ 2 1 λ 2 1 + σ 2 2 λ 2 2 .
Thus, E 1 [( n j=1 j ) 2 |X 0 = X] σ 2 1 /λ 2 1 + σ 2 2 /λ 2 2 , which implies (A.22).

Lemma 3 Assume that in (6.1) the parameter σ 2 1 is such that lim ρ→∞ σ 2 1 ρ 4 = 0 . Then Proof. First note that for any x ∈ R 2 the inverse matrix for (6.5) can be written as

G -1 (x) = 1 det G(x) 1 + σ 2 2 x 2 2 , -ρ -ρ , 1 + ρ 2 + σ 2 1 x 2 1 and det G(x) = (1 + ρ 2 + σ 2 1 x 2 1 )(1 + σ 2 2 x 2 2 ) -ρ 2 = t 0 (x 2 2 ) + σ 2 1 x 2 1 t 1 (x 2 2 ) ,
where t 0 (x) = 1 + σ 2 2 (1 + ρ 2 ) x and t 1 (x) = 1 + σ 2 2 x. This function can be written as κ(x 1 , x 2 ) = 1 2 λ 2 1 a(x) -ρ λ 1 λ 2 b(x) + 1 2 λ 2 2 c(x) , (A.24)

where a(x) = x 2 1 t 1 (x 2 2 )/ det G(x), b(x) = x 1 x 2 / det G(x), and c(x) = x 2 2 (1 + ρ 2 + σ 2 1 x 2 1 )/ det G(x). Now to study the function (A.24) we represent the coefficient a(x) as a(x) = a 0 (x) -σ 2 1 a 1 (x), where a 0 (x) = x 2 1 t 3 (x 2 2 ), a 1 (x) = x 4 1 t 1 (x 2 2 )t 3 (x 2 2 )/[t 0 (x 2 2 ) + σ 2 1 x 2 1 t 1 (x 2 2 )] and t 3 (x) = t 1 (x)/t 0 (x). Taking into account that t 1 (x) t 0 (x) and that the random variable ζ 1 is G-conditionally Gaussian with the parameters 0 and (1 + ρ 2 )ς 11 , we obtain

E a 1 (ζ) E ζ 4 1 = 3 (1 + ρ 2 ) 2 E ς 2 11 ,
where ς 11 = ∞ k=1 σ 2(k-1) 1

k-1 l=1 η 2 1,l . We recall that G = σ{η 1,k , η 2,k , k 1}. Now, by the Bunyakovsky-Cauchy-Schwarz inequality,

E ς 2 11 1 1 -σ 2 1 k 1 σ 2(k-1) 1 E k-1 l=1 η 4 1,l = 1 1 -σ 2 1 k 1 σ 2 1 E η 4 1,1 k-1 = 1 (1 -σ 2 1 )(1 -3σ 2 1 )
.

Therefore, for any 0 < σ 0 < 1/3, lim sup By the Bunyakovsky-Cauchy-Schwarz inequality, the random variable ς * 0 a.s. Next, using the definitions of the random variables ς ij in (6.4), we obtain that ς * = 0 if and only if for any k 1

ρ→∞ 1 (1 + ρ 2 ) 2 sup 0<σ 2 1 σ 0 E |a 1 (ζ)| < ∞ .
σ k-1 1 k-1 l=1 η 1,l = σ k-1 2 k-1 l=1 η 2,l .
So, ς * > 0 a.s. Thus,

E(a 0 (ζ)|G) = E( ζ2 |G) E t 3 (ζ 2 2 )|G + κ2 E ζ 2 2 t 3 (ζ 2 2 )|G (1 + ρ 2 ς * ) E 1 1 + σ 2 2 (1 + ρ 2 )ζ 2 2 |G ,
and we obtain that Moreover, b(x) = b 0 (x)-σ 2 1 b 1 (x), where b 0 (x) = x 1 x 2 /t 0 (x 2 2 ) and b 1 (x) = x 3 1 x 2 t 3 (x 2 2 )/[t 0 (x 2 2 )+σ 2 1 x 2 1 t 1 (x 2 2 )]. Therefore, taking into account that E ζ|G = 0, we obtain

E (b 0 (ζ)|G) = E ζ 1 ζ 2 t 0 (ζ 2 2 ) |G = E κ ζ 2 2 t 0 (ζ 2 2 )
|G .

This implies immediately that

E b 0 (ζ) = E κ ζ 2 2 t 0 (ζ 2 2 ) = E ζ 2 2 t 0 (ζ 2 2 ) E (κ|G 1 ) = ρ E ζ 2 2 t 0 (ζ 2 2 )ς 22
.

It is easy to check that lim

ρ→∞ ρ E b 0 (ζ) = 1 σ 2 2 E 1 ς 22 1 σ 2 2 .
Taking into account here that t 3 (x) 1 we obtain that | b 1 (x) | |x 1 | 3 /σ 2 , i.e.,

E |b 1 (ζ)| 1 σ 2 E|ζ 1 | 3 = 2 √ 2 σ 2 √ π (1 + ρ 2 ) 3/2 E ς 3/2 11 2 √ 2 σ 2 √ π (1 + ρ 2 ) 3/2 E ς 2 11 .
Therefore, for any 0 < σ 0 < 1/3 lim sup

ρ→∞ 1 (1 + ρ 2 ) 3/2 sup 0<σ 2 1 σ 0 E |b 1 (ζ)| < ∞ .
Clearly, c(x) σ -2 2 . Thus, using the condition of this lemma we obtain (A.23).

  .1) where 2,β = δβ 1,β , the functions 0 < 1,β < 1 and 0 < δβ < 1 are such that lim β→0 1,β + δβ = 0 and lim β→0 | ln 1,β | + | ln δβ | | ln β| = 0 . (4.2)

(H 3 )

 3 Parameters k * and m * are functions of β, i.e. k * = k * β and m * = m * β , such that lim β→0 | log α 3,β | | log β| = 1 . (4.15)

6. 5

 5 Example 5: Change in the correlation coefficients of the AR(p) model

  (w n , 0, . . . , 0) ∈ R p .It is clear thatE[ wn w n ] = B =

  1,β ) P ∞ (τ < k) = m * +1 k=1 π k ( 1,β ) P ∞ (τ < k) + ∞ k=m * +2 π k ( 1,β ) P ∞ (τ < k) β + ∞ k=m * +2 π k ( 1,β ) = β + 1 -1,β m * +1 = α 1 , i.e., τ ∈ ∆(α 1 , 1,β). Hence both inclusions in (A.20) are proven.The following proposition allows us to compare the classes (2.5) and (3.5).Proposition 5 For any0 < β < 1, m * | log(1 -β)|/[| log(1 -1,β )|]-1 and k * m * , the following inclusions hold:∆(α 3 , 2,β ) ⊆ H * (β, k * , m * ) ⊆ ∆(α 1 , 1,β ) . (A.21)

  Now we calculate the expectation Ea 0 (ζ). To this end, we setζ = ζ 1 -κ ζ 2 and κ = E(ζ 1 ζ 2 |G)/E(ζ 2 2 |G) = ρ(ς 12 /ς 22 ). Conditioned on G, the random variable ζ is independent of ζ 2 ,and ζ is Gaussian with the parameters 0, E ( ζ2 |G) , whereE ( ζ2 |G) = E (ζ 2 1 |G) -(E (ζ 1 ζ 2 |G)) 2 E (ζ 2 2 |G) = (1 + ρ 2 )ς 11 -ρ 2 ς 2 12 ς 22 := 1 + ρ 2 ς * .

  ., lim ρ→∞ E a 0 (ζ) = +∞. Setting now G 1 = σ{ξ 2,l , η 2,l , l 1}, we obtainE (κ|G 1 ) = ρ E (ς 12 |G 1 )

Acknowledgements

The work of the first author was partially supported by the Russian Science Foundation (research project No. 14-49-00079, National Research University "MPEI", Moscow, Russia) and by the Academic D.I. Mendeleev Fund Program of the Tomsk State University (research project 8.1.55.2015 L). The work of the second author was supported in part by the U.S. Air Force Office of Scientific Research under MURI grant FA9550-10-1-0569, by the U.S. Defense Advanced Research Projects Agency under grant W911NF-12-1-0034 and by the U.S. Army Research Office under grants W911NF-13-1-0073 and W911NF-14-1-0246 at the University of Southern California, Department of Mathematics and at the University of Connecticut, Department of Statistics.

A Auxiliary results and proofs

A.1 Asymptotic properties of the SR procedure for large threshold values

The following proposition establishes asymptotic properties of the SR procedure for large h regardless of the optimality criteria. While it is being used in the proofs of asymptotic optimality of the SR procedure under considered criteria, it also interesting independently.

Proposition 3 Let T (h) be the SR procedure defined in (2.3). (i) Assume that there exists a positive and finite number I such that, for all ε > 0, the following conditions hold:

and, for some r 1, (ii) Asymptotic relations (A.3), (A.4), and (A.5) hold if

3), (A.4), and (A.5) with r = 1.

Proof. (i) Let n 0 = 1 + log h/(I -ε) . We have

Taking into account that R ν+n = ν+n i=1 e Z i-1 ν+n e Z ν ν+n , we obtain

Evidently, for any 0 < ε < I and any n n 0 , the last probability can be bounded as

and hence, for any 0 < ε < I and ν 0,

where, by condition (A.2), the last term on the right-hand side is finite. This immediately implies the following upper bounds for the moments of the detection delay (for any ν 0)

The upper bound (A.3) follows. To obtain the upper bound (A.4) for the conditional risk, it suffices to observe that Eν [(T (h) -ν) r |T (h) > ν] = Eν [(T (h) -ν) r ] + /P∞(T (h) > ν) and that P∞(T (h) > ν) 1 -ν/h → 1 as h → ∞ for every ν 0. The latter follows easily from the fact that Rn -n is a zero-mean P∞-martingale. Define M ε,h = (1 -ε) log h/(I + d), where as before d = -log(1 -). Replacing α in the proof of Theorem 1 in Section A.2 below by 1/h, in particular in (A.13), we obtain that, for any 0 < ε < 1,

By Lemma 1, PFA(T (h)) 1/(h + 1) := α * , and as in (A.14), we have

so that the first term in (A.10) goes to zero as h → ∞ for any ε > 0 and for any 0 < < 1. By condition (A.1), the second term also goes to zero as h → ∞, and therefore, lim h→∞ P 0 (T (h) > M ε,h ) = 1 for any 0 < ε < 1 and any 0 < < 1. Finally, Chebyshev's inequality yields

for arbitrary 0 < ε < 1 and 0 < < 1, and we obtain the asymptotic lower bound

which along with the upper bound (A.9) completes the proof of (A.5) in (i).

(ii) The uniform r-complete convergence condition (A.6) implies both conditions (A.1) and (A.2), and hence, (A.3), (A.4), and (A.5) hold true under (A.6).

(iii) Finally, when r = 1, condition (A.6) is nothing but the uniform complete convergence condition (A 2 ), and hence, (A.3), (A.4), and (A.5) hold true with r = 1 under (A 2 ). This completes the proof of all three assertions.

A.2 Proof of Theorem 1

First, note that it is not difficult to prove that condition (A 1 ) implies that for any ε > 0 and k 0

, the assertion (3.10) follows from the assertion (3.9), and hence it suffices to prove only inequality (3.9).

Define

Let us show that for any k 0 and 0 < ε < 1 lim

Indeed, using the change of measure trick, similarly to Tartakovsky and Veeravalli (2005) we obtain

The definition of the class ∆(α, ) in (3.5) implies that for any 0 < α, < 1 and for any l 1

Therefore, the first term in the right side of the inequality (A.13) may be estimated as

and it goes to zero for any fixed 0 k < ∞. By (A.11), the second term in (A.13),

approaches zero as α → 0 for all k 0, and we obtain (A.12). By the Chebyshev inequality,

From (A.14) we obtain immediately that for any fixed k 0

Therefore, for any ν 0 and for any small ε

Taking into account that dα = -log(1α) → 0 as α → 0 and letting ε → 0, we obtain the lower bounds (3.9). Hence Theorem 1.

A.3 Proof of Theorem 2

Proof of (i). In just the same way as in (A.8), we obtain that for all ν 0 and n n 0 = log hα/(I -ε) + 1,

and hence, for any 0 < ε < I,

Since the right-hand side does not depend on ν, we have (for any ν 0 and 0 < ε < I)

By condition (A 2 ), Υ * (ε) < ∞, so using condition (3.16) and the fact that ε is arbitrary yields the upper bound (3.18) and the assertion (i) follows.

Proof of (ii). In view of inequality (A.14), for any 0 ν k * α ,

Evidently, under conditions (3.16) and (3.17) the right-hand side approaches 1 as α → 0, which implies that Pν (Tα > ν) → 1 as α → 0 for all 0 ν k * α . Since Eν (Tα -ν|Tα > ν) = Eν (Tα -ν) + /P ν (Tα > ν), inequality (3.18) implies (3.19) for k * = k * α satisfying conditions (3.17) and the proof is complete.

A.4 Proof of Theorem 4

We give only a sketch of the proof and omit certain details. By (3.12), for all r 1 and for all ν 0, lim inf .17) (This bound holds since condition (3.24) obviously implies the a.s. convergence (A 1 ), which in turn implies (A.11) for all k 0.) Next, using the reasoning similar to that used in the proof of Proposition 3 in Section A.1, which has lead to inequality (A.7), we obtain A.18) where n 0 = 1 + log hα/(I -ε) and hα = (1 -α)/α α. By (A.15), for any 0 < ε < I and n n 0 , Pν (Tα > ν + n) Pν (| Zν,n| > ε), and we obtain

where the last term is finite due to condition (3.24) and log hα ∼ | log α| as α → 0 due to condition (3.16). Thus, for an arbitrary 0 < ε < I,

and we established the asymptotic upper bound lim sup

Applying this upper bound together with the lower bound (A.17) proves asymptotic relations (3.25).

The upper bound lim sup

can be established similarly to (3.19), using (A.19) and the fact that max

This upper bound and the lower bound (A.17) imply (3.26).

A.5 Auxiliary results for proving asymptotic optimality of the SR procedure in classes with given local probabilities of false alarm

The following proposition allows us to compare the classes (2.4) and (3.5).

Proposition 4 For any 0

-1 and k * > m * , the following inclusions hold:

B Auxiliary non-asymptotic bounds for the concentration inequalities

B.1 Correlation inequality

We now give the important correlation inequality proved in [START_REF] Galthouk | Uniform concentration inequality for ergodic diffusion processes observed at discrete times[END_REF].

Proposition 6 Let (Ω, F , (F j ) 1 j n , P) be a filtered probability space and (u j , F j ) 1 j n be a sequence of random variables such that, for some r 2, max

B.2 Geometric ergodicity for homogeneous Markov processes

We follow the Meyn-Tweedie approach (cf. [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF]). We recall some definitions from [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF] and [START_REF] Galthouk | Geometric ergodicity for classes of homogeneous Markov chains[END_REF] for a homogeneous Markov process (X n ) n 0 defined on a measurable state space (X , B(X )). Denote by P (x, •) , x ∈ X , the transition probability of this process, i.e., for any A ∈ B(X ), x ∈ X ,

2)

The n-step transition probability is P n (x, A) = P x (X n ∈ A).

We recall that a measure λ on B(X )) is called invariant (or stationary or ergodic) for this process if, for any A ∈ B(X ),

If there exists an invariant positive measure λ with λ(X ) = 1 then the process is called positive. Assume that the process (X n ) n 0 satisfies the following minorization condition:

(D 1 ) There exist δ > 0, a set C ∈ B(X ) and a probability measure ς on B(X ) with ς(C) = 1, such that for any A ∈ B(X ), for which ς(A) > 0, inf x∈C P (x, A) > δ ς(A).

Obviously, this condition implies that η = inf x∈C P (x, C) -δ > 0. Now we impose the drift condition.

(D 2 ) There exist a X → [1, ∞) function V, constants 0 < ρ < 1, D 1 and a set C from B(X ) such that V * = sup x∈C |V(x)| < ∞ and, for all x ∈ X , E x (V(X 1 ))

(1 -ρ)V(x) + D1l {C} (x) . (B.4)

In this case, we call V the Lyapunov function.

In this paper, we use the following theorem from [START_REF] Galthouk | Geometric ergodicity for classes of homogeneous Markov chains[END_REF].

Theorem 11 Let (X n ) n 0 be a homogeneous Markov process satisfying conditions (D 1 ) and (D 2 ) with the same set C ∈ B(X ). Then (X n ) n 0 is a positive geometric ergodic process, i.e.,

for some positive constants κ * and R * which are given in [START_REF] Galthouk | Geometric ergodicity for classes of homogeneous Markov chains[END_REF]. [START_REF] Tartakovsky | Detection of intrusions in information systems by sequential change-point methods[END_REF]. A novel approach to detection of intrusions in computer networks via adaptive sequential and batch-sequential change-point detection methods. IEEE Trans. Signal Proces. 54 3372-3382. Tartakovsky, A.G. and Veeravalli, V.V. (2005). General asymptotic Bayesian theory of quickest change detection.

Theory Probab. Appl. 49 458-497.