Serguei M Pergamenchtchikov

Alexander G Tartakovsky

Valentin S Spivak

Minimax and pointwise sequential changepoint detection and identification for general stochastic models

Keywords: Asymptotic optimality, changepoint detection, composite post-change hypotheses, detection and localization of epidemics, quickest change detection-identification. 2010 MSC: Primary 62L10, 62L15, Secondary 60G40, 60J05, 60J20

This paper considers the problem of joint change detection and identification assuming multiple composite postchange hypotheses. We propose a multihypothesis changepoint detection-identification procedure that controls the probabilities of false alarm and wrong identification. We show that the proposed procedure is asymptotically minimax and pointwise optimal, minimizing moments of the detection delay as probabilities of false alarm and wrong identification approach zero. The asymptotic optimality properties hold for general stochastic models with dependent observations. We illustrate general results for detection-identification of changes in multistream Markov ergodic processes. We consider several examples, including an application to rapid detection-identification of COVID-19 in Italy. Our proposed sequential algorithm allows much faster detection of COVID-19 than standard methods.

Introduction

As discussed in [START_REF] Nikiforov | A generalized change detection problem[END_REF][START_REF] Tartakovsky | Sequential Change Detection and Hypothesis Testing: General Non-i.i.d. Stochastic Models and Asymptotically Optimal Rules[END_REF][START_REF] Tartakovsky | An asymptotic theory of joint sequential changepoint detection and identification for general stochastic models[END_REF][START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF], in a variety of applications it is important not only to quickly detect abrupt changes but also to diagnose them (e.g., to determine which change in a set of possible changes has occurred). This problem of change detection and diagnosis applies, for example, to rapid detection and identification of intrusions in computer networks, object detection with various sensors, integrity monitoring of navigation systems, and early detection and localization of epidemics. Often called Change Detection and Isolation, the problem is a generalization of the quickest change detection problem to the case of multiple post-change hypotheses and can be formulated as joint change detection and identification. Nikiforov [START_REF] Nikiforov | A generalized change detection problem[END_REF] first considered the change detection-isolation problem in a minimax setting for independent and identically distributed (i.i.d.) observations (in pre-change and post-change modes with different distributions) and simple post-change hypotheses. Several versions of the multihypothesis CUSUM-type and SR-type procedures, which have minimax optimality properties in the classes of rules with constraints imposed on the average run length to a false alarm and conditional probabilities of false isolation, are proposed by Nikiforov [START_REF] Nikiforov | A simple recursive algorithm for diagnosis of abrupt changes in random signals[END_REF][START_REF] Nikiforov | A lower bound for the detection/isolation delay in a class of sequential tests[END_REF] and Tartakovsky [START_REF] Tartakovsky | Multidecision quickest change-point detection: Previous achievements and open problems[END_REF]. Dayanik et al. [START_REF] Dayanik | Asymptotically optimal Bayesian sequential change detection and identification rules[END_REF] proposed an asymptotically optimal Bayesian detection-isolation rule assuming that the prior distribution of the change point is geometric also in the i.i.d. case. However, in many practical applications, the i.i.d. assumption is too restrictive -the observations may be either non-identically distributed or dependent or both, i.e., non-i.i.d. Also, the post-change distribution is usually not completely known. Lai [START_REF] Lai | Sequential multiple hypothesis testing and efficient fault detection-isolation in stochastic systems[END_REF] provided a certain generalization for the non-i.i.d. case and composite hypotheses for a specific loss function. Recently, Tartakovsky [START_REF] Tartakovsky | An asymptotic theory of joint sequential changepoint detection and identification for general stochastic models[END_REF] developed a general asymptotic multistream Bayesian theory of sequential change detection and identification for low rates of false alarms and misidentification, assuming [START_REF] Baron | Change-Point Detection in Binomial Thinning Processes, with Applications in Epidemiology[END_REF] there are multiple data streams, [START_REF] Dayanik | Asymptotically optimal Bayesian sequential change detection and identification rules[END_REF] the change occurs in some data stream(s) at an unknown random point in time, and (3) it is necessary to detect the change as soon as possible and identify which data streams are affected. However, a non-Bayesian multistream change detection-identification theory for non-i.i.d. data is still missing.

The primary goal of this paper is to provide a general non-Bayesian asymptotic multistream change detectionidentification theory (minimax and pointwise) for non-i.i.d. data and composite post-change hypotheses. This theory generalizes changepoint detection theory (with no identification) developed by Pergamenchtchikov and Tartakovsky [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF]. In Section 2, we describe the general stochastic model and provide basic notation. In Section 3, we introduce main conditions. In Section 4, we introduce the change detection-identification rule. In Section 5, we derive the information lower bounds for moments of the detection delay in the class of changepoint detectionidentification rules with constraints imposed on the probabilities of false alarm and wrong identification. In Section 6, we prove asymptotic optimality of the proposed detection-identification rule as the probabilities of false alarm and misidentification go to zero. We show that the lower bounds are attained for this procedure under very general conditions. In Section 7, we illustrate general results for detection-identification of changes in Markov ergodic processes. In Section 8, we consider two examples -detection-identification of changes in [START_REF] Baron | Change-Point Detection in Binomial Thinning Processes, with Applications in Epidemiology[END_REF] the parameters of multivariate linear difference equations and (2) the correlation coefficients of multistream p-th order autoregressive models. In Section 9, we propose a specific model for epidemics and show that the proposed change detection-identification rule is asymptotically optimal. We also apply our rule for detection of COVID-19 in Italy and show that it allows for much earlier detection of COVID-19 than standard methods.

Basic notation

We consider the N independent streams of observations (X 1,l ) l 1 , . . . , (X N,l ) l 1 . For any 1 i N, ν 0 and θ i from an open set Θ i ⊆ R m we denote by P i,ν,θ i the distribution of the observations (X i,l ) l 1 in R ∞ . In the case when ν = ∞, this distribution will be denoted by P * . We use the convention that X i,ν is the last pre-change observation. Write X n i = (X i,1 , . . . , X i,n ) for the concatenation of the first n observations in the ith data stream. Let now for any 1 i N f * i, j (y j |y 1 , . . . , y j-1 ) j 1 and f i,θ i , j (y j |y 1 , . . . , y j-1 ) j 1

(2.1) be sequences of conditional densities of X i, j given X j-1 i with respect to some non-degenerate σ-finite measure. Note that for 1 i N the density q i of X n i in R n has the following form q i,ν,θ i (y 1 , . . . ,

y n ) =           
q * i (y 1 , . . . , y n ) for ν n ; ν l=1 f * i,l (y l |y 1 , . . . , y j-1 ) n l=ν+1 f i,θ i ,l (y l |y 1 , . . . , y l-1 ) for ν < n ,

where q * i (y 1 , . . . , y n ) = n l=1 f * i,l (y l |y 1 , . . . , y l-1 ). Denote by γ a random variable with values in {1, . . . , N} and assume that the change can occur only in the data stream (X γ,l ) l 1 with probability υ i = P(γ = i). For ν 1 and θ = (θ 1 , . . . , θ N ) ∈ Θ = Θ 1 × . . . × Θ N the joint density of the observations X n 1 , . . . , X n N is given by

p ν,θ (y 1,1 , . . . , y N,n ) = N i=1 υ i p i,ν,θ (y 1,1 , . . . , y N,n ) , (2.3)
where p i,ν,θ i (y 1,1 , . . . , y N,n ) = q i,ν,θ i (y i,1 , . . . , y i,n ) N l i q * l (y l,1 , . . . , y l,n ) .

(2.4)

In the sequel we denote by M the set of all Markov times with respect to the filtration (F n ) n 0 where F 0 = {Ω, ∅} and F n = σ X i, j , 1 i N , 1 j n .

Note that when n > k and ϑ ∈ Θ i the Radon-Nykodim density (likelihood ratio)

g * i,k,n = g * i,k,n (ϑ) = dP i,k,ϑ dP * F n = e Z k i,n (ϑ) , (2.5)
where

Z k i,n (ϑ) = n l=k+1 log f i,ϑ,l (X i,l |X l-1 i ) f * i,l (X l |X l-1 i ) (2.6)
is the log-likelihood ratio, and for any (θ i , θ j ) ∈ Θ i × Θ j with i j the Radom-Nikodym density

g i, j,k,n = g i, j,k,n (θ i , θ j ) = dP i,k,θ i dP j,k,θ j F n = e Z k i,n (θ i )-Z k j,n (θ j ) . (2.7)
A sequential change detection-identification procedure δ is a pair δ = (T, d), where T is a stoping time from M, i.e., for any 1 i N, k 0 and ϑ ∈ Θ i the probability P i,k,ϑ (T < ∞) = 1, and d is a decision rule, i.e., a random variable with the values in {1, . . . , N} which is measurable with respect to the σ-field F T . We denote by S the class of all sequential procedures. For r 1 and θ i ∈ Θ i , define the risk for a sequential procedure δ = (T, d) ∈ S associated with the conditional r-th moment of the detection delay

R i,k,θ i (δ) = E i,k,θ i (T -k) r 1 {d=i} |T > k , (2.8)
where E i,k,θ i is the expectation with respect to the distribution

P i,k,θ i in R ∞ .
Introduce the conditional probability of false alarm P * (T < k+m * , d = i|T k) on the event {d = i} in the interval [k, k + m * ), i.e., the probability of raising the alarm with the decision d = i that there is a change in the ith stream when there is no change. Also, introduce the misidentification probabilities P i,k,θ i (d = j|T > k), i j, i, j = 1, . . . , N.

For any N × N matrix β = (β i, j ) 1 i, j N with 0 < β i, j < 1, m * 1 and k * > m * we introduce the class of change detection-identification rules

H(β, k * , m * ) =      δ ∈ S : sup 1 k k * -m * max 1 i N P * (T < k + m * , d = i|T k) β i,i 1 , max 0 k k * max 1 i N sup θ∈Θ i max 1 j i N P i,k,θ i (d = j|T > k) β i, j 1
       . (2.9)
Our goal is to find a sequential procedure asymptotically optimal in two problems in the class of detectionidentification rules H(β, k * , m * ): the pointwise minimization

inf δ∈H(β,k * ,m * ) R i,k,θ i (δ) for every 1 i N , k 0 and θ i ∈ Θ i (2.10)
and the minimax optimization

inf δ∈H(β,k * ,m * ) sup k 0 R i,k,θ i (δ) for every 1 i N and θ i ∈ Θ i . (2.11)
The parameters k * and m * will be specified later.

Main conditions

For a fixed θ i ∈ Θ i , we assume the following conditions for the log-likelihood ratio (LLR) processes (Z k i,n (θ i )) n k+1 introduced in (2.6) for 1 i N and θ i ∈ Θ i . (A 1 ) For any 1 i, j N there are Θ i × Θ j → R + positive continuous functions I i, j with

0 < inf (θ i ,θ j )∈Θ i ×Θ j I i, j (θ i , θ j ) sup (θ i ,θ j )∈Θ i ×Θ j I i, j (θ i , θ j ) < ∞ (3.1)
such that for any k 0, ε > 0 and θ

= (θ 1 , . . . θ N ) ∈ Θ 1 × . . . × Θ N lim n→∞ max 1 i j N P i,k,θ i Z k i,k+n (θ i ) -Z k j,k+n (θ j ) > (1 + ε)I i, j (θ i , θ j )n = 0 (3.2) and lim n→∞ max 1 i N P i,k,θ i Z k i,k+n (θ i ) > (1 + ε) I i (θ i )n = 0 , (3.3
)

where I i (θ i ) = I i,i (θ i , θ i ) for θ i ∈ Θ i .
In order to study asymptotic approximations to risks of the change detection-identification rule introduced below in Section 4 and for establishing its asymptotic optimality, we impose the following left-tail conditions: (A 2 (r)) For any 1 i, j N there are Θ i × Θ j → R + positive continuous functions I i, j with the property (3.1) such that for every θ = (θ 1 , . . . , θ N ) ∈ Θ 1 × . . . × Θ i = Θ and for any 0

< ε < 1 lim ζ→0 sup θ∈Θ max 1 i N ∞ n=1 n r-1 sup k 0 P i,k,θ i inf |u-θ i |<ζ Z k i,k+n (u) < (1 -ε) I i (θ i )n < ∞ (3.4)
and

lim ζ→0 sup θ∈Θ max 1 i j N ∞ n=1 n r-1 sup 0 k ζn P i,k,θ i inf |u-θ i |<ζ Z k i,k+n (u) -Z * j,k+n < (1 -ε) I i (θ i )n < ∞ , (3.5)
where Z * j,n = max 0 l n sup z∈Θ j Z l j,k+n (z).

Remark 1. This is always true for i.i.d. data models with Kullback-Leibler informations given by

I i, j (θ i , θ j ) = log        f i,θ i (x) f j,θ j (x)        f i,θ i (x)dµ(x) and I i (θ i ) = log       f i,θ i (x) f * i (x)       f i,θ i (x)dµ(x) for (θ i , θ j ) ∈ Θ i × Θ j .

Sequential change detection-identification procedure

First introduce weight distributions (W i (ϑ)) 1 i N , which are probability measures on the sets Θ i , i.e. W i (Θ i ) = 1 for any 1 i N. In what follows, we assume that W i (•) satisfy the following condition: (C W ) For any ε > 0 and any ϑ ∈ Θ i the measure W i {u ∈ Θ i : |u -ϑ| < ε} > 0. Now, for some fixed 0 < < 1 we set

π k = π k ( ) = (1 -) k , k = 0, 1, 2, . . . (4.1)
and using this distribution we set

L i,n = n-1 k=0 π k Θ i g * i,k,n (ϑ)W i (dϑ) and L i,n = n-1 k=0 π k sup θ∈Θ i g * i,k,n (ϑ) . (4.2)
Using these statistics we define the following random N × N matrix U n as

< U n > i, j = L i,n L j,n if i j and < U n > i,i = L i,n l n π l , (4.3)
where < U > i, j is the (i, j)th element of the matrix U. Finally, using this matrix we set

T * i,A = inf      n 1 : min 1 j N < U n > i, j A i, j 1      , (4.4)
where A = (A i, j ) 1 i, j N is a N × N matrix with positive elements which will be specified later. In the definitions of stopping times we set inf{∅} = +∞. The sequential change detection-identification procedure δ * A = (T * A , d * A ) that will be studied in this paper has the form

T * A = min 1 i N T * i,A and d * A = i if T * i,A = T * A . (4.5)
If there are several numbers i for which T * i,A = T * A we can take arbitrary. Note that, as we will see later in Proposition 2, the condition (A * 2 (r)) implies that T * A is a P i,k,θ i -proper stopping time, that is, for any 1 i N, k 1 and

θ i ∈ Θ i P i,k,θ i (T * A < ∞) = 1 . (4.6)
Now, for any sequential procedure δ = (T, d) ∈ S we set

PFA i (δ) = ∞ k=0 π k P * (T k , d = i) (4.7)
and

PMI i, j (δ) = ∞ k=0 π k sup θ i ∈Θ i P i,k,θ i (T > k , d = j) . (4.8)
For some N × N matrix α = (α i, j ) with 0 < α i, j < 1 and some fixed 0 < < 1, define the following Bayesian class:

∆(α, ) =      δ ∈ S : max       max 1 i N PFA i (δ) α i,i , max 1 i, j N,i j PMI i, j (δ)) α i, j       1      .
(4.9)

Next, for any arbitrary fixed matrix β = (β i, j ) 1 i, j N and 0 < < 1 introduce two matrices α 1 = (α (1) i, j ) 1 i, j N and α 2 = (α (2) i, j ) 1 i, j N as

α (1) i, j = β i,i (1 -) k * 1 + tr β 1 {i= j} + β i, j (1 -) k * 1 + tr β 1 {i j} (4.10) and α (2) i, j = β i,i + (1 -) m * +1 1 {i= j} + β i, j + (1 -) k * +1 1 {i j} . (4.11)
The following proposition compares classes (2.9) and (4.9).

Proposition 1. For any matrix β = (β i, j ) 1 i, j N , 1 m * < k * and 0 < < 1 the following inclusions hold

∆(α 1 , ) ⊂ H(β, k * , m * ) ⊂ ∆(α 2 , ) . (4.12)
Proof. First note that if δ = (T, d) ∈ ∆(α 1 , ), then for any 1 i N and k 1

α (1) i,i ∞ l=0 π l P * (T l , d = i) P * (T k , d = i) ∞ l=k π l = (1 -) k P * (T k , d = i) ,
i.e., for k 1

P * (T k , d = i) (1 -) -k α (1)
i,i and P * (T k)

N j=1 P * (T k , d = j) (1 -) -k tr α 1 . (4.13)
Therefore, for any 1 i N and

1 k k * -m * P * (T < k + m * , d = i|T k) = P * (k T < k + m * , d = i) 1 -P * (T < k) P * (T k * , d = i) 1 -P * (T k * ) (1 -) -k * α (1) i,i 1 -(1 -) -k * tr α 1 := β i,i .
Moreover, for i j and any k 1

α (1) i, j π k sup θ i ∈Θ i P i,k,θ i (T > k , d = j) = (1 -) k sup θ i ∈Θ i P i,k,θ i (T > k , d = j) ,
i.e., in view of (4.13), for 1 k k * and θ i ∈ Θ i

P i,k,θ i (d = j|T > k) = P i,k,θ i (T > k , d = j) P i,k,θ i (T > k) = P i,k,θ i (T > k , d = j) 1 -P * (T > k)
α (1) i, j

-1 (1 -) -k 1 -P * (T k)
α (1) i, j

-1 (1 -) -k * 1 -(1 -) -k * tr α 1 = β i, j .
This implies, that δ ∈ H(β, k * , m * ), i.e., we get the first inclusion in (4.12).

Let now δ = (T, d) ∈ H(β, k * , m * ), i.e., for any 1 k k *m * and 1 i N

β i,i P * (T < k + m * , d = i|T k) = P * (k T < k + m * , d = i) P * (T k) P * (k T < k + m * , d = i)
and, in particular,

β i,i P * (T < 1 + m * , d = i) .
Therefore,

k 0 π k P * (T k , d = i) P * (T < 1 + m * , d = i) + k m * +1 π k β i,i + (1 -) m * +1 = α (2) i,i .
Furthermore, for any i j,

θ i ∈ Θ i and 0 k k * β i, j P i,k,θ i (d = j|T > k) P i,k,θ i (k < T < ∞ , d = j) , i.e., k 0
π k P i,k,θ i (T > k , d = j) β i, j + k>k * π k = β i, j + (1 -) k * +1 = α i, j .
Thus, we obtain the last inclusion (4.12). Hence Proposition 1.

The first question we ask is how to select the thresholds in the procedure (4.5) to imbed it into class ∆(α, ρ). To study this question we need the following probability measures on N × R ∞ which for any 1 i N are defined as

Q i (J × A) = k∈J π k Θ i P i,k,ϑ (A) W i (dϑ) , J ⊆ N and A ∈ B(R ∞ ) , (4.14)
where N = {0, 1, . . .} and B(R ∞ ) is the cylinder field in R ∞ . In the sequel we denote by E Q i the expectation over the probability measure Q i . One can check directly that

Q i ν n|F n = 1 1+ < U n > i,i , (4.15)
where the matrix U n is defined in (4.3).

Lemma 1. For all 1 i N the probabilities (4.7) satisfy the inequalities

PFA i (δ * A ) 1 1 + A i,i . (4.16)
Proof. Note that

PFA i (δ * A ) = ∞ k=0 π k P * T * A k , d = i = ∞ k=0 π k Θ i P i,k,ϑ T * i,A k , d = i W i (dϑ) ∞ k=0 π k Θ i P i,k,ϑ T * i,A k W i (dϑ) = Q i ν T * i,A = E Q i Q i ν T * i,A |F T * i,A
.

Therefore, using (4.15) and (4.4) we obtain that

PFA i (δ * A ) E Q i         1 1+ < U T * i,A > i,i         1 1 + A i,i ,
which completes the proof.

Lemma 2. For any 1 i, j N, i j the PMI probabilities of the procedure (4.5) satisfy the inequalities

PMI i, j (δ * A ) 1 A j,i . (4.17)
Proof. First note that for the rule (4.4) we obtain that for any j i and

θ i ∈ Θ i P i,k,θ i T * A > k , d = j P i,k,θ i k < T * j,A < ∞ 1 A j,i E i,k,θ i < U T * j,A > j,i 1 k<T * j,A <∞ = 1 A j,i E * < U T * j,A > j,i g i,k,T * j,A (θ i )1 k<T * j,A <∞ .
Therefore, in view of the definition in (4.2), we get

k 0 π k P i,k,θ i T * A > k , d = j 1 A j,i E *           < U T * j,A > j,i T * j,A -1 k=0 π k g i,k,T * j,A (θ i )1 T * j,A <∞           1 A j,i E * < U T * j,A > j,i L i,T * j,A 1
T * j,A <∞ = 1 A j,i E * L j,T * j,A 1
T * j,A <∞ .
Moreover, note that

E * L j,T * j,A 1
T * j,A <∞ = k 0 π k Θ i E * g j,k,T * j,A (θ i )1 k<T * j,A <∞ W i (dθ i ) = k 0 π k Θ i P i,k,θ i k < T * j,A < ∞ W i (dθ i )) 1 ,
which implies upper bound (4.17) Now, if we take in (4.4)

A i, j = 1 α i,i -1 1 {i= j} + 1 α j,i 1 {i j} (4.18)
then using the property (4.6) and the upper bounds (4.16) and (4.17) we obtain that under condition (A * 2 (r)) the sequential procedure (4.5) belongs to class ∆( , α) for any 0 < < 1 and α = (α i, j ) 1 i, j N with 0 < α i, j < 1. Therefore, if we take

A i, j = 1 + tr β β i,i (1 -) k * -1 1 {i= j} + 1 + tr β β j,i (1 -) k * 1 {i j} , (4.19)
we obtain that for any 0 < < 1 the sequential procedure (4.5) belongs to class H(β, k * , m * ).

Information lower bounds

Bayesian setting

For any matrix α = (α i, j ) 1 i, j N and any parameter value

θ i ∈ Θ i define b i,α (θ i ) = max 1 j N | log α j,i | ι i, j (θ i ) and ι i, j (θ i ) = I i (θ i ) 1 { j=i} + I i, j (θ i ) 1 { j i} , (5.1)
where the function

I i (•) is defined in (3.3) and I i, j (θ i ) = inf ϑ∈Θ j I i, j (θ i , ϑ) for θ i ∈ Θ i .
In what follows we will always suppose without special emphasis that inf θ j ∈Θ j I i, j (θ i , θ j ) > 0 for all θ i ∈ Θ i , j i and i = 1, . . . , N (see condition (3.1)). Write α max = max 1 i, j N α i, j and ∆ α = ∆(α, α ) (in case where = α depends on α). The following theorem establishes information lower bounds in the Bayesian problem. These bonds will be used to obtain asymptotic lower bounds for R i,k,θ i (δ) in class H (β, k * , m * ) (see Theorem 2) and to prove asymptotic optimality of the proposed detection-identification procedure in this class.

Theorem 1. Assume that the right-tail probability convergence condition (A 1 ) holds and in (4.1) the parameter of the geometric prior distribution is a function of α, i.e., = α , such that lim

α max →0 α + | log α | | log α max | = 0 . (5.2)
Then, for any r 1, k 0, θ i ∈ Θ i , and 1 i N the following asymptotic lower bounds hold:

lim inf α max →0 inf δ∈∆ α E i,k,θ i (T -k) r + 1 {d=i} |b i,α (θ i )| r 1 . (5.3)
Proof. To prove this theorem it suffices to show that for any j i and (θ i , θ j )

∈ Θ i × Θ j ( j = 1, . . . , N) inf δ∈∆ α E i,k,θ i (T -k) r + 1 {d=i} (1 + ψ α,i, j (θ i , θ j )) | log α j,i | r I r i, j (θ i , θ j ) , (5.4)
and for any j = i and

θ i ∈ Θ i inf δ∈∆ α E i,k,θ i (T -k) r + 1 {d=i} (1 + ψ α,i,i (θ i , θ i )) | log α i,i | r I r i (θ i ) , (5.5)
where the term ψ α,i, j (θ i , θ j ) is such that lim

α max →0 |ψ α,i, j (θ i , θ j )| = 0 for any (θ i , θ j ) ∈ Θ i × Θ j and 1 j N .
To prove (5.4) note that condition (3.2) implies that for any ε > 0, k 0 and (θ i , θ j ) ∈ Θ i × Θ j with j i

P i,k,θ i Z k i,k+M (θ i ) -Z k j,k+M (θ j ) (1 + ε)I i, j M ----→ M→∞ 0 , (5.6)
where

I i, j = I i, j (θ i , θ j ). Define for (θ i , θ j ) ∈ Θ i × Θ j D i, j,k (δ) = P i,k,θ i k < T k + M i, j , d = i and M i, j = M i, j (θ i , θ j ) = (1 -ε) | log α j,i | I i, j .
We now show that for any k 0, 0 < ε < 1 and 1 j i N lim

α max →0 sup δ∈∆ α D i, j,k (δ) = 0 . (5.7)
Using definition (2.7) we can obtain that for m = k + M i, j

D i, j,k (δ) = E j,k,θ j g i, j,k,m 1 {k T m , d=i} e (1+ε)I i, j M i, j P j,k,θ j (k < T m , d = i) + P i,k,θ i Z k i,m (θ i ) -Z k j,m (θ j ) (1 + ε)I i, j M i, j .
(5.8)

Using the definition of PMI ji (δ) in (4.8) along with the fact that PMI ji (δ) α j,i for any δ ∈ ∆(α, α ) we get

α j,i l 0 π l sup θ j ∈Θ j P j,l,θ j (T > l, d = i) π k P j,l,θ j (T > l, d = i) π k P j,k,θ j (k < T m, d = i) = α (1 -α ) k P j,k,θ j (k < T m, d = i)
for any θ j ∈ Θ j and any k 0, so that sup

δ∈∆ α P j,k,θ j (k < T m , d = i) -1 α (1 -α ) -k α j,i = e -| log α j,i |-log α +k α ,
where in view of (5.2) the term α =log(1α ) → 0 as α max → 0. So the first term on the right-hand side of the inequality (5.8) can be estimated as

exp (1 + ε)I i, j M i, j -log α + k α + log α j,i exp -ε 2 | log α j,i | -log α + k α exp -ε 2 | log α max | -log α + k α
and by condition (5.2) it goes to zero as α max → 0. Therefore, (5.8) and (5.6) impliy (5.7) for any j i.

Let now i = j. Using the definition (2.5) we can rewrite the inequality (5.8) as

D i,i,k (δ) = E * g * i,k,m 1 {k T m , d=i} e (1+ε) I i (θ i )M i,i P * (k < T m , d = i) + P i,k,θ i Z k i,m (θ i ) (1 + ε) I i (θ i )M i,i , (5.9)
where I i (θ i ) = I i,i (θ i , θ i ) and where by condition (3.3) lim

M ii →∞ P i,k,θ i Z k i,k+M ii (θ i ) > (1 + ε) I i (θ i )M ii = 0 for any θ i ∈ Θ i . (5.10)
Now, the definition of class ∆ α = ∆(α, α ) in (4.9) implies that for any δ ∈ ∆ α , any k 1 and all i = 1, . . . , N

α ii 1 π P * (T l, d = i) P * (T k, d = i) k =1 α (1 -α ) l-1 = (1 -α ) k P * (T k, d = i),
which yields sup

δ∈∆ α P * (T k , d = i) α i,i (1 -α ) -k = e -| log α i,i |+k α . (5.11)
Therefore, the first term on the right side of the inequality (5.9) may be estimated as

e (1+ε) I i,i (θ i )M i,i -| log α i,i |+ α k+ α M i,i e -ε 2 | log α i,i |+ α k+ α M i,i
and it goes to zero for any fixed 0 k < ∞ as α max → 0, which along with (5.10) implies (5.7) for i = j.

To obtain lower bounds (5.4) and (5.5) note that for any 1 j N

E i,k,θ i (T -k) r + 1 {d=i} E i,k,θ i (T -k) r + 1 {T >k+M i, j , d=i} M r i, j P i,k,θ i T > k + M i, j , d = i = M r i, j P i,k,θ i (T > k , d = i) -D i, j,k (δ) .
(5.12)

Using the upper bound (5.11), we get

P i,k,θ i (T > k , d = i) = P i,k,θ i (d = i) -P i,k,θ i (T k , d = i) = P i,k,θ i (d = i) -P * (T k , d = i) 1 - N l=1,l i P i,k,θ i (d = l) -α i,i (1 -α ) -k .
Next, it follows from (4.8) and (4.9) that for l i sup

θ i ∈Θ i P i,k,θ i (T > k , d = l) α i,l α (1 -α ) -k = e log α i,l -log α +k α ,
i.e., for any l i and

θ i ∈ Θ i P i,k,θ i (d = l) = P * (T k , d = l) + P i,k,θ i (T > k , d = l) α l,l (1 -) -k + α i,l α (1 -α ) -k = e log α i,l +k α + e log α i,l -log α +k α .
Thus, in view of (5.2) for any

θ i ∈ Θ i P i,k,θ i (T > k , d = i) → 1 as α max → 0
and using (5.12) and (5.7), we finally obtain the asymptotic inequality

E i,k,θ i (T -k) r + 1 {d=i}       (1 -ε) | log α j,i | I i, j (θ i , θ j )       r (1 + o(1)), α max → 0
(where o(1) → 0), which holds for an arbitrary ε ∈ (0, 1), so letting ε → 0 implies lower bounds (5.4) (for j i) and (5.5) (for j = i). The proof is complete.

The local constraints setting

To find asymptotic lower bounds for the problems (2.10) and (2.11) in addition to condition (A 1 ) we impose the following condition.

β max →0 β = 0 , lim β max →0 | log β | | log α (2) max |
= 0 and lim

β max →0 max 1 i, j N | log α (2) i, j | | log β i, j | -1 = 1 , (5.13)
where α (2) max = max 1 i, j N α (2) i, j and β max = max 1 i, j N β i, j . For example, we can take

m * β = [| log β min |/ β ] , k * β = ǩ m * β and β = 1 1 + | log β max | , (5.14)
where [x] is the integer part of the x, β min = min 1 i, j N β i, j and ǩ > 1 is some fixed number.

The following theorem establishes asymptotic lower bounds in class of detection-identification procedures H (β, k * , m * ).

Theorem 2. Assume that conditions (A 1 ) and (H 1 ) hold. Then, for any r 1, k 0, 1 i N and θ i ∈ Θ i , lim inf

β max →0 inf δ∈H(β,k * ,m * ) R i,k,θ i (δ) b r i,β (θ i ) 1 , (5.15)
where the denominator b i,β (θ i ) is defined in (5.1) by replacing the matrix α with β.

Proof. First of all, note that the last condition in (5.13) implies that for any 1 i N and θ i ∈ Θ i lim

β max →0 b i,α 2 (θ i ) b i,β (θ i ) = 1 .
It is clear that the last inclusion in (4.12) implies that for all k 0 and sufficiently small β > 0 inf

δ∈H(β,k * ,m * ) R i,k,θ i (δ) inf δ∈∆(α 2 , β ) R i,k,θ i (δ) inf δ∈∆(α 2 , β ) E i,k,θ i (T -k) r + 1 {d=i} .
Now, the lower bounds (5.15) directly follow from the lower bounds (5.3) and condition (H 1 ).

Upper bounds and asymptotic optimality

We begin with studying the sequential procedure (4.5) for large threshold values A i, j . For any matrix A = (A i, j ) 1 i, j N with A i, j > 1 and any ϑ ∈ Θ i define

B i,A (ϑ) = max 1 j N log A i, j ι i, j (ϑ) , (6.1)
where the "information" functions ι i, j (•) are defined in (5.1). We need the following condition:

(H 2 ) The matrix A = (A i, j ) 1 i, j N is such that lim A min →∞ max 1 i N max 1 j N log A i, j log A i,i -1 = 0 .
A min →∞ max 1 i N sup θ i ∈K sup 1 k k * R i,k,θ i (δ * A ) B r i,A (θ i ) 1 , (6.2)
where θ = (θ 1 , . . . , θ N ), A min = min 1 i, j N A i, j and k * is such that k * = o(log A min ) as A min → ∞.

Proof. First, note that in view of (4.17) δ * A belongs to class ∆( , α) with

α i, j = 1 1 + A i,i 1 {i= j} + 1 1 + A j,i 1 {i j} .
Therefore, using the upper bound (4.13), we obtain that uniformly over

1 k k * P i,k,θ i (T * A > k) = P * (T * A > k) 1 -(1 -) -k N j=1 1 1 + A j, j 1 -(1 -) -k * N j=1 1 1 + A j, j → 1 , A min → ∞ .
Therefore, to obtain the inequality (6.2) it suffices to show that lim sup

A min →∞ max 1 i N sup θ i ∈K sup 1 k k * E i,k,θ i [(T * A -k) r + ]1 {d * A =i} B r i,A (θ i ) 1 . (6.3)
Note also that by condition (A 2 ) for arbitrary 0 < ε < 1 we can chose such 0 < ζ < 1 for which ϑ : |ϑ -

θ i | < ζ ⊂ Θ i for all 1 i N, U * 1 (ζ) = max 1 i N sup θ i ∈K ∞ n=1 n r-1 sup k 0 P i,k,θ i inf |u-θ i |<ζ Z k i,k+n (u) < (1 -ε) I i (θ i )n < ∞ and U * 2 (ζ) = max i j sup θ i ∈K ∞ n=1 n r-1 max 0 k ζn P i,k,θ i inf |u-θ i |<ζ Z k i,k+n (u) -Z * j,k+n < (1 -ε) I i (θ i )n < ∞ .
Now, for an arbitrary ϑ ∈ Θ i , we set

n * i = n * i,A (ϑ) = 1 + ε 1 -ε κ i,A B i,A (ϑ) + 1 and κ i,A = max 1 j N log A i, j log A i,i . (6.4)
Note that in view of the properties (3.1) and the fact that k * = o(log A min ) we can conclude that for a sufficiently large A min we have k * ζn * i . Moreover,

E i,k,θ i (T * A -k) r + 1 {d * A =i} n 0 n r-1 P i,k,θ i T * i,A > k + n 1 + (n * i ) r + n>n * i n r-1 P i,k,θ i T * i,A > k + n . (6.5)
Now, the definition (4.4) implies that

P i,k,θ i T * i,A > k + n = P i,k,θ i       max 1 l n+k min 1 j N < U l > i, j A i, j < 1       N j=1 P i,k,θ i < U k+n > i, j < A i, j , i.e. P i,k,θ i T * i,A > k + n N j=1 P i,k,θ i log < U k+n > i, j < log A i, j . (6.6)
Using (4.3) we obtain that for i j

P i,k,θ i log < U k+n > i, j < log A i, j = P i,k,θ i log L i,k+n -log L j,k+n < log A i, j (6.7)
and for i = j

P i,k,θ i log < U k+n > i,i < log A i,i = P i,k,θ i log L i,k+n -(k + n) log(1 -) < log A i,i . (6.8) Note that log L i,k+n log π k {|υ-θ i |<ζ} g * i,k,k+n (υ)W i (dυ) inf {|υ-θ i |<ζ} Z k i,k+n (υ) + l i ( ) ,
where

l i ( ) = -log -k * log(1 -) -log W i z ∈ Θ i : |z -θ i | < ζ . Since | log | = o(log A min ) and k * = o(log A min ), we get lim A min →∞ max 1 i N l i ( ) log A min = 0 .
Obviously, log L j,k+n Z * j,k+n . Moreover, taking into account that for any 1 j N

n * i (1 + ε) log A i, j (1 -ε) I i (θ i )
we can obtain that for any j i,

θ i ∈ Θ i , n > n * i > k * /ζ and 0 k k * and for sufficiently large A min for which max 1 i N l i ( ) ε log A min P i,k,θ i log < U k+n > i, j < log A i, j P i,k,θ i inf {|υ-θ i |<ζ} Z k i,k+n (υ) -Z * j,k+n < log A i, j + l i ( ) max 0 l ζn P i,l,θ i inf |υ-θ i |<ζ Z l i,l+n (υ) -Z * j,l+n < (1 -ε) I i (θ i )n
and

P i,k,θ i log < U k+n > i,i < log A i,i P i,k,θ i inf {|υ-θ i |<ζ} Z k i,k+n (υ) < log A i,i + l i ( ) max 0 l ζn P i,l,θ i inf |υ-θ i |<ζ Z l i,l+n (υ) < (1 -ε) I i (θ i )n .
Therefore, from (6.5) we get

E i,k,θ i (T * A -k) r + 1 {d * A =i} 1 + (n * i ) r + U * 1 (ζ) + U * 2 (ζ) 1 + 1 + ε 1 -ε r κ r i,A B r i,A (θ i ) + U * 1 (ζ) + U * 2 (ζ) ,
and using the condition (H 2 ), we get lim sup

A min →∞ max 1 i N sup θ i ∈K sup 1 k k * E i,k,θ i (T * A -k) r + 1 {d * A =i} B r i,A (θ i ) 1 + ε 1 -ε r .
Since ε can be arbitrarily small, taking the limit as ε → 0, we obtain the bound (6.3), which completes the proof of Proposition 2.

Remark 2. If both left-tail and right-tail conditions (A 1 ) and (A 2 ) hold along with conditions (H 1 ) and (H 2 ), then inverting the equality (4.19) and using Theorem 2 (with β replaced with A -1 ) and Proposition 2 simultaneously it can be shown that the following asymptotic equalities for the moments of delay of the procedure δ A hold for any fixed k, θ i ∈ Θ i and all i = 1, . . . , N:

R i,k,θ i (δ A ) = max 1 j N log A i, j ι i, j (θ i ) (1 + o(1)) = max        log A i,i I i (θ i ) , max 1 j i N log A i, j I i, j (θ i )        (1 + o(1)) as A min → ∞.
To obtain the optimal detection rate we need to impose the following condition: (H 3 ) Parameters opt and k * are functions of β, i.e. opt = opt β , k * = k * β and m * = m * β , such that lim

β max →0 | log opt | | log β max | = 0 and lim β max →0 max 1 i, j N | log α (1) i, j | | log β i, j | -1 = 0 , (6.9)
where

α (1) i, j = β i,i (1 -opt ) k * 1 {i= j} + β i, j opt (1 -opt ) k * 1 {i j} .
For example, for some ǩ > 1 we can take

m * β =       | log β min | β       , k * β = ǩm * β , opt = | log β max | β | log β min |(1 + | log β |) and β = 1 1 + | log β max | . ( 6
β max →0 max 1 i N max 1 j N | log β j,i | | log β i,i | -1 = 0 , (6.11)
we obtain that the conditions (H 1 ) -(H 3 ) hold.

Denote by δ opt β = (T opt , d opt ) the procedure (4.5) with = opt and

A i, j = A opt i, j (β) = 1 + tr β β i,i (1 -opt ) k * -1 1 {i= j} + 1 + tr β β j,i ( opt )(1 -opt ) k * 1 {i j} , (6.12)
that is,

T opt β = min 1 i N T opt i,β and d opt β = i if T opt i,β = T opt β , (6.13)
where

T opt i,β = inf        n 1 : min 1 j N < U n > i, j A opt i, j (β) 1        . (6.14)
The following theorem deduces the pointwise and minimax optimality properties of the procedure δ opt β .

Theorem 3. Assume that conditions (A 1 )-(A 2 ) and (H 1 )-(H 3 ) hold true. Then the procedure δ opt β is optimal in the pointwise sense, i.e., for any θ i ∈ Θ i , 1 i N, and for every fixed k 0 lim

β max →0 inf δ∈H(β,k * ,m * ) R i,k,θ i (δ) R i,k,θ i (δ opt β )
= 1 and lim

β max →0 R i,k,θ i (δ opt β ) b r i,β (θ i ) = 1 . (6.15)
Also, for any k * = o(| log β max |) as β max → 0 the procedure δ opt β is optimal in the minimax sense, i.e., for any θ i ∈ Θ i and 1 i N, lim

β max →0 inf δ∈H(β,k * ,m * ) max 1 k k * R i,k,θ i (δ) max 1 k k * R i,k,θ i (δ opt β )
= 1 and lim

β max →0 max 1 k k * R i,k,θ i (δ opt β ) b r i,β (θ i ) = 1 . (6.16)
Proof. By condition (H 3 ) lim

β max →0 max 1 i, j N | log A opt i, j (β)| | log β j,i | -1 = 0,
so that using the asymptotic upper bound (6.2) in Proposition 2 we obtain the asymptotic upper bound lim sup

β max →0 max 1 i N sup θ i ∈K sup 1 k k * R i,k,θ i (δ opt β ) B r i,β (θ i ) 1 . (6.17)
Comparing this bound with the lower bound (5.3) in Theorem 1 yields (6.15) and (6.16).

The next theorem also shows that the procedure δ opt β = (T opt , d opt ) is "robust" in the following sense

R * β (δ) = sup θ∈Θ max 1 i N max 1 k k * R i,k,θ i (δ) b r i,β (θ i ) . ( 6
β max →0 inf δ∈H(β,k * ,m * ) R * β (δ) R * β (δ opt β ) = 1 . (6.19)
The proof is similar to the proof of Theorem 2 in [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF] for the single-stream detection problem and is omitted.

Detection-identification of changes in homogeneous Markov models

Let the observations (X i,n ) n 1 be time homogeneous Markov processes with values in a measurable space (X i , B i ) defined by a family of the transition probabilities (P θ i i (x, A)) θ i ∈Θ i for some fixed parameter set Θ i ⊆ R p . In the sequel we denote by E θ i i,x (•) the expectation with respect to this probability. Moreover, we assume that for any 1 i N the observations (X i,n ) n 1 are Markov processes, such that (X i,n ) 1 n ν is a homogeneous process with the transition (from x to y) density f * i (y|x) and in the case when ν = +∞ this process is ergodic with the ergodic distribution λ * ,i . We denote by P * the distribution of the observations (X i,n ) 1 i N,n 1 of this process when ν = ∞. The expectation with respect to this distribution will be denoted by E * (•). In addition, we assume that for any 1 i N the process (X i,n ) n>ν is homogeneous positive ergodic with the transition density f i,θ i (y|x) and the ergodic (stationary) distribution λ θ i ,i (θ i ∈ Θ i ). The densities f * i (y|x) and ( f i,θ i (y|x)) θ ∈ Θ i are calculated with respect to a sigma-finite positive measure µ i on B i . In this case, we can represent the LLR process Z k i,n (u) defined in (2.6) as

Z k i,n (u) = n j=k+1 g i (u, X i, j , X i, j-1 ) , g i (u, y, x) = log f i,u (y|x) f * i (y|x) . ( 7.1)
We also assume that densities f i,u (y|x) are continuously differentiable with respect to u in a compact set

Θ i ⊆ Θ i . Now we set h(x, y) = max 1 i N max u∈ Θ i max 1 j p |∂g i (u, y, x)/∂u j | (7.2) and h i (θ i , y) = X i h(y, x) f i,θ i (y|x) µ i (dy) , θ i ∈ Θ i .
For some q > 0 define

g * q (x) = sup n 1 max 1 i N sup θ i ∈Θ i E θ i i,x |g i (θ, X i,n , X i,n-1 )| q and h * q (x) = sup n 1 max 1 i N sup θ i ∈Θ i E θ i i,x |h(X i,n , X i,n-1 )| q . (7.3)
Also, define

J i (θ i , x) = X i g i (θ i , y, x) f i,θ i (y|x) µ i (dy) and J * i (θ i , x) = X i g i (θ i , y, x) f * i (y|x) µ i (dy) . (7.4)
Obviously, J i (θ i , x) 0 and J * i (θ i , x) 0. Write

J i (θ i ) = X i J i (θ i , x)λ θ i ,i (dx) and J * i (θ i ) = X i J * i (θ i , x)λ * ,i (dx) . (7.5)
Introduce the following conditions. (C 1 ) For any

1 i N there exist sets C i ∈ B i with µ i (C i ) < ∞ such that (C1.1) f * = min 1 i N inf θ i ∈Θ i inf x,y∈C i f i,θ i (y|x) > 0. (C1.2) For any 1 i N there exists X i → [1, ∞) Lyapunov's function V i such that • V i (x) J i (θ i , x) and V i (x) h i (θ i , x) for any θ i ∈ Θ i and x ∈ X i . • max 1 i N sup x∈C i V i (x) < ∞.
• There exist 0 < ρ < 1 and m * > 0 such that for all 1 i N, x ∈ X i and θ i ∈ Θ i ,

E θ i i,x [V i (X i,1 )] (1 -ρ)V i (x) + m * 1 C i (x) . (7.6)
(C 2 (q)) There exists q > 2 such that for any

1 i N sup k 1 E * [g * q (X i,k )] < ∞ , sup k 1 E * [h * q (X i,k )] < ∞ and sup k 1 E * [υ * q (X i,k )] < ∞ ,
where the functions g * q (x) and h * q (x) are given in (7.3) and

υ * q (x) = sup 1 i N , n 0 sup θ i ∈Θ i E θ i i,x V i (X i,n ) q . (7.7) (C 3 (q))
The function g i (u, y, x) can be represented as

g i (u, y, x) -J * i (u) = m l=1 α i,l (u)ǧ i,l (y, x) (7.8)
with α j,l (u) and ǧi,l (y, x) such that for any 1 i N and 1 l m

sup u∈Θ i |α j,l (u)| < ∞ and sup n 1 n -q/2 E * n j=1 ǧi,l (X i, j , X i, j-1 ) q < ∞ .
Theorem 5. Assume that conditions (C 1 ) -(C 3 (q)) hold true and the functions J i (θ i ) and -J * i (θ i ) defined in (7.4) are continuous and positive for θ i ∈ Θ i . Then conditions (A 1 ) and (A 2 (r)) are satisfied for any 0 < r < q/2 with

I i, j (θ i , θ j ) = J i (θ i ) 1 {i= j} + [J i (θ i ) -J * j (θ j )]1 {i j} . (7.9)
Proof. Note first that conditions (3.3) and (3.4) follow from Theorem 8 in [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF] that uses the uniform geometric ergodicity property and concentration inequalities methods developed in [START_REF] Galthouk | Uniform concentration inequality for ergodic diffusion processes observed at discrete times[END_REF][START_REF] Galthouk | Geometric ergodicity for classes of homogeneous Markov chains[END_REF]. To prove condition (3.5) we observe that condition (C 3 ) and the Chebyshev inequality imply that for any a > 0

sup n 1 n q/2 max 1 i N max 1 k n P *        sup θ i ∈Θ i |∆ k i,n (θ i )| > an        < ∞ , (7.10)
where

∆ k i,n (θ i ) = Z k i,n -J * i (θ i )(n -k) = n j=k+1 g i (θ i , X i, j , X i, j-1 ) -J * i (θ i ) .
Taking into account that J * j (θ i ) 0, we obtain that for any ε > 0 and 1 j N

P * Z * j,n > εn P *         max 1 k n sup θ j ∈Θ j |∆ k j,n (θ j )| > εn         n max 1 k n P *         sup θ j ∈Θ j |∆ k j,n (θ j )| > εn         .
Therefore, (7.10) implies the condition (3.5) for r < q/2. Remark 3. The function J i (•) is called the Kullback-Leibler divergence for the Markov processes (see, e.g., [START_REF] Girardin | Kullback-Leibler Approach to CUSUM Quickest Detection Rule for Markovian Time Series[END_REF]).

Note that condition (C1.1) does not always hold for the process (X i,n ) n 1 directly. For example, this condition does not hold for the practically important autoregression process of the order more than one. For this reason, we need to weaken this requirement. Similarly to [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data[END_REF] we assume that there exists p 2 for which the process ( X ι i,n ) n ν for ν ι = ν/pι and 0 ι p -1 defined as X ι i,n = X i,np+ι satisfies the following conditions: (C 1 ) There exist sets C i ∈ B i with µ i (C i ) < ∞ such that (C 1.1) min 1 i N inf 1 ι p inf θ i ∈Θ i inf x,y∈C f ι i,θ i (y|x) > 0 , where f ι i,θ i (y|x) is the transition density for the process ( X ι i,n ) n ν i .

(C 1.2) For any 1 i N there exists

X i → [1, ∞) Lyapunov's function V i such that max 1 i N max 1 j p sup θ i ∈Θ i sup x∈X i E θ i i,x V i (X i, j ) V i (x) < ∞ and sup θ i ∈Θ i λ θ i ,i (V i ) < ∞ . • V i (x) J i (θ i , x) and V i (x) h i (θ i , x) for θ i ∈ Θ i and x ∈ X i and max 1 i N sup θ i ∈Θ i sup x∈C i V i (x) < ∞.
• For any 1 i N, there exist 0 < ρ < 1 and m * > 0 such that for all x ∈ X i , θ i ∈ Θ i , and 0 ι p -1

E θ i i,x V i ( X ι i,1 ) (1 -ρ)V i (x) + m * 1 C i (x) . (7.11)
Similarly to Theorem 5 we can prove, using Theorem 9 in [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF], the following result.

Theorem 6. Assume that conditions (C 1 ) and (C 2 (q)) hold, the processes ( X ι i,n ) n ν satisfy the condition (C 3 (q)), and the functions J i (θ i ) and -J * i (θ i ) defined in (7.4) are continuous and positive for θ i ∈ Θ i . Then conditions (A 1 ) and (A 2 (r)) hold for any 0 < r < q/2 with the functions I i, j defined in (7.9).

To check the condition C 3 (q)) we need to obtain concentration inequality for the homogenous Markov process (X i,n ) n 1 with the transition density f * i (y|x). The following condition is sufficient for this purpose: (C * 3 (q)) For any 1 i N there exist sets C i ∈ B i with

µ i (C i ) < ∞ such that 1. min 1 i N inf x,y∈C i f * i (y|x) > 0. 2. For any 1 i N there exists X i → [1, ∞) Lyapunov's function V i such that • max 1 i N sup x∈C i V i (x) < ∞.
• There exist 0 < ρ < 1 and m * > 0 such that for all 1 i N, x ∈ X i and θ i ∈ Θ i ,

E * x [V i (X i,1 )] (1 -ρ)V i (x) + m * 1 C i (x) . ( 7

.12)

• There exists q > 0 such that for any x i ∈ X i max

1 i N sup j 1 E * x i [V q i (X i, j )] < ∞ . (7.13)
3. The functions ǧi,l (y, x) in (7.8) are such that for any

1 i N and x ∈ X i max 1 l m X i ǧi,l (y, x) f * i (y|x)µ i (dy) V i (x) and sup j 1 E * x |ǧ i,l (X i, j , X i, j-1 )| q < ∞ .
Proposition 1 from [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data[END_REF] provides the following result.

Proposition 3. The condition (C * 3 (q)) implies the condition (C 3 (q)).

Examples

Example 1: Change in the parameters of multivariate linear difference equations

Consider the multivariate models in R p given by

X i,n = Γ * i,n 1l {n ν} + Γ i,n 1l {n>ν} X i,n-1 + w i,n , (8.1)
where Γ * i,n and Γ i,n are p × p random matrixes and (w i,n ) n 1 is an i.i.d. sequence of Gaussian random vectors N(0, Q * i ) in R p with the positive definite p × p matrix Q * i . Assume also that

Γ * i,n = θ * i + B i,n and Γ i,n = θ i + B i,n (8.2)
and (B i,n ) n 1 are i.i.d. Gaussian random matrices N(0 , Q i ), where the p 2 × p 2 matrix

Q i = E[B i,1 ⊗ B i,1
] is positive definited. Assume, in addition, that all eigenvalues of the matrix

E[Γ * i,1 ⊗ Γ * i,1 ] = θ * i ⊗ θ * i + Q i
are less than one in module. Define

Θ st i = {θ i ∈ R p 2 : max 1 j p 4 i e j (θ i ⊗ θ i + Q i ) < 1}} \ {θ * i } , (8.3)
where e j (Γ) is the jth eigenvalue of matrix Γ, and assume further that in (8.2) the matrices θ i ∈ Θ st i . In this case, the processes (X i,n ) n 1 (for ν = ∞) and (X i,n ) n>ν (for ν < ∞) 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 Γ * i, j w i,l and ς i,θ = l 1 l-1 j=1 Γ i, j w i,l
i.e., the corresponding invariant measures λ * ,i and λ θ,i on R p are defined as

λ * ,i (dx) = P(ς * i ∈ dx) and λ θ,i (dx) = P(ς i,θ ∈ dx)
Note that in this case the Markov processes (X i,n ) n ν and (X i,n ) n>ν have the following transition densities in R p ,

θ i ∈ Θ i f * i (y|x) = exp - |η * i (y,x)| 2 2 (2π) p/2 det(G i (x)) and f i,θ i (y|x) = exp - |η θ i ,i (y,x)| 2 2 (2π) p/2 det(G i (x)) , (8.4)
where

η * i (y, x) = G -1/2 i (x)(y -θ * i x), η θ i ,i (y, x) = G -1/2 i (x)(y -θ i x), θ i ∈ Θ i and G i (x) = E [B i,1 xx B i,1 ] + Q * i = Q i Vect(xx ) + Q * i .
Therefore, in this case,

g i (θ i , y, x) = log f i,θ i (y|x) f * i (y|x) = y G -1 i (x)(θ i -θ * i )x + x (θ * i ) G -1 i (x) θ * i x -x θ i G -1 i (x) θ i x 2 .

Now we set

L i,n = opt n-1 k=0 (1 -opt ) k Θ i e n j=k+1 g i (θ i ,X i, j ,X i, j-1 ) W i (dθ i ) (8.5)
and

L i,n = opt n-1 k=0 (1 -opt ) k sup θ∈Θ i e n j=k+1 g i (θ i ,X i, j ,X i, j-1 ) , (8.6)
where opt is defined in (6.10). The random N × N matrix (4.3) has the following form

< U n > i, j = L i,n L j,n if i j and < U n > i,i = L i,n (1 -opt ) n , (8.7)
and the corresponding change detection-identification procedure δ opt β = (T opt β , d opt β ) is defined by (6.13)-(6.14) with the threshold matrix A = A opt β given by (6.12). As shown in [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF], conditions (C 1 ) and (C 2 (r)) hold for any r > 0. Moreover, one can calculate directly that

J i (θ i ) = 1 2 E ς i,θ i (θ i -θ * i ) G -1 i (ς i,θ i )(θ i -θ * i )ς i,θ i and J * i (θ i ) = - 1 2 E (ς * i ) (θ i -θ * i ) G -1 i (ς * i )(θ i -θ * i )ς * i .
To check the condition (C 3 ) denote θ i = θ * iu. It can be easily shown that for 1 i N

g i (u, y, x) -J * i (u) = - p s 1 ,s 2 =1 < θ i > s 1 ,s 2 p k=1 D (i,1) s 1 ,s 2 ,k (x) < η * i (y, x) > k - 1 2 p s 1 ,s 2 ,s 3 ,s 4 =1 < θ i > s 1 ,s 2 < θ i > s 3 ,s 4 D (i,2) s 1 ,s 2 ,s 3 ,s 4 (x) ,
where

D (i,1) s 1 ,s 2 ,k (x) =< G -1/2 i (x) > s 1 ,k < x > s 2 , D (i,2) s 1 ,s 2 ,s 3 ,s 4 (x) = b s 1 ,s 2 ,s 3 ,s 4 (x) -E * [b s 1 ,s 2 ,s 3 ,s 4 (ς * i )] and b s 1 ,s 2 ,s 3 ,s 4 (x) =< x > s 2 < x > s 4 < G -1 i (x) > s 1 ,s 3 . Note that for any z ∈ R p and |z| = 1 z G i (x)z = |x| 2 (Vect( xz )) Q i Vect( xz ) + z Q * i z
, where x = x/|x|. Taking into account that the matrices Q i are positive definite, we obtain that for some c * > 0 max

1 i N |G -1 i (x)| c * 1 + |x| 2 . (8.8)
Therefore, the functions D (i,1) s 1 ,s 2 ,k (x) and b s 1 ,s 2 ,s 3 ,s 4 (x) are bounded. Moreover, as shown in [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF] (Example 1), the Lyapunov function for the process (8.1) (with ν = +∞) has the form

V(x) = v * 1 + (x T x) δ
for some constant v * 1, a fixed matrix T and any δ > 0. Since in this case max 1 i N sup j 1 E * [X 2 i, j ] < ∞, we obtain that condition (C * 3 (q)) holds true for any q > 0. Now, taking into account that under P * the random vectors (η * i (X i, j , X i, j-1 )) 1 i N , j 1 are i.i.d. (0, I p ) Gaussian (I p is the unity matrix in R p ), we obtain the condition (C 3 (q)) for any q > 0 using Proposition 3. Therefore, Theorems 3 and 4 imply that the sequential procedure δ opt β defined in (6.13)-(6.14) is asymptotically optimal and robust in the pointwise and minimax senses for any compact sets Θ i ⊂ Θ st i and for any r > 0.

Example 2: Change in the correlation coefficients of autoregressive models

Consider the problem of detecting the change of the correlation coefficient in the pth order AR process which in the ith stream satisfies the recursion

X i,n = a (n) i,1 X i,n-1 + . . . + a (n) i,p X i,n-p + w i,n , for n 1, (8.9)
where

a (n) i,l = θ * l 1l {n ν} + θ i,l 1l {n>ν} and (w i,n ) n 1 are i.i.d. Gaussian random variables with E [w i,1 ] = 0, E [w 2 i,1 ] = 1.
In the sequel, we use the notation θ * i = (θ * i,1 , . . . , θ * i,p ) and θ i = (θ i,1 , . . . , θ i,p ) . Hereafter denotes the transposition operation. The corresponding conditional densities X i,n |X i,n-1 , . . . , X i,n-p for ν n and ν > n, θ i ∈ Θ i , are

f * i (y|x) = 1 (2π) p/2 exp        - (η * i (y, x)) 2 2        and f i,θ i (y|x) = 1 (2π) p/2 exp        - (η θ i ,i (y, x)) 2 2        , (8.10)
where

η * i (y, x) = y -(θ * i ) x and η θ i ,i (y, x) = y -(θ i ) x. Therefore, for any θ i ∈ R p , y ∈ R and x = (x 1 , . . . , x p ) ∈ R p g i (θ i , y, x) = log f i,θ i (y|x) f * i (y|x) = y 1 (θ i -θ * i ) x + ((θ * i ) x) 2 -(θ i x) 2 2 . (8.11)
The process (8.9) is not Markov, but the p-dimensional processes 8.12) are Markov. Now, for any ϑ = (ϑ 1 , . . . , ϑ p ) ∈ R p we difine

Φ i,n = (X i,n , . . . , X i,n-p+1 ) ∈ R p , i = 1, . . . , N (
Λ(ϑ) =                  ϑ 1 ϑ 2 . . . ϑ p 1 0 . . . 0 . . . . . . . . . . . . 0 0 . . . 1 0                  .
Using this matrix it is easy to show that the processes (Φ i,n ) n ν and (Φ i,n ) n>ν+p satisfy the following stochastic linear equations:

Φ i,n = Λ * ,i Φ i,n-1 + w i,n for n ν and Φ i,n = Λ i Φ i,n-1 + w i,n for n > ν , (8.13)
where

Λ * ,i = Λ(θ * i ), Λ i = Λ(θ i ) and w i,n = (w i,n , 0, . . . , 0) ∈ R p . Obviously, E[ w n w n ] = B =             1 . . . 0 . . . . . . . . . 0 . . . 0             .
Assume that all eigenvalues of the matrices Λ * ,i = Λ i (θ * i ) in modules are less than 1 and that θ i belongs to the set

Θ st i = {ϑ ∈ R p : max 1 j p |e j (Λ i (ϑ))| < 1} \ {θ * i } , (8.14)
where e j (Λ) is the ith eigenvalue of the matrix Λ. In this case, the processes (8.13) have the ergodic distributions defined by the random vectors

ς * i = l 1 (Λ * ,i ) l-1 w i,l and ς i,θ = l 1 (Λ i ) l-1 w i,l
which are (0, F * ) and (0, F i (ϑ)) Gaussian vectors in R p , where

F * = n 0 (Λ * ,i ) n B (Λ * ,i ) n and F i (ϑ) = n 0 Λ n i B(Λ i ) n .

Now we set

L i,n = opt n-1 k=0 (1 -opt ) k Θ i e n j=k+1 g i (ϑ,X i, j ,Φ i, j-1 ) W i (dϑ) (8.15)
and

L i,n = opt n-1 k=0 (1 -opt ) k sup θ∈Θ i e n j=k+1 g i (ϑ,X i, j ,Φ i, j-1 ) , (8.16)
where opt is defined in (6.10). The random N × N matrix (4.3) has the following form

< U n > i, j = L i,n L j,n if i j and < U n > i,i = L i,n (1 -opt ) n .
(8.17)

and the corresponding change detection-identification procedure δ opt β = (T opt β , d opt β ) is defined in (6.13)-(6.14) with the threshold matrix A = A opt β given by (6.12). As shown in [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF], conditions (C 1 ) and (C 2 (r)) hold for any r > 0 and any compact sets Θ i ⊂ Θ st i for the function I i, j defined in (7.9) with

J i (ϑ) = 1 2 (ϑ -θ * i ) F(ϑ)(ϑ -θ * i ) and J i (ϑ) = - 1 2 (ϑ -θ * i ) F * (ϑ -θ * i ) . (8.18)
It should be noted that in the scalar case, i.e., when p 1 = . . . = p N = 1,

J i (ϑ) = (ϑ -θ * i ) 2 2(1 -ϑ 2 )
and

J i (ϑ) = - (ϑ -θ * i ) 2 2(1 -(ϑ * i ) 2 )
.

Write θ i = θ * i -u.
To check the condition (C 3 ) direct calculations show that for 1 i N

g i (u, y, x) -J * i (u) = -θ i η i (y, x) - 1 2 θ i xx -E[ς * i,1 (ς * i,1 ) ] θ i .
Therefore, taking into account that in this case max 1 i N sup j 1 E * |X i, j | q < ∞ for any q > 0 we obtain that condition (C * 3 (q)) holds for any q > 0. Now, taking into account that under the probability measure P * the random variables (η * i (X i, j , Φ i, j-1 )) 1 i N , j 1 are i.i.d. N(0, 1) we obtain the condition (C 3 (q)) for any q > 0 using Proposition 3. Therefore, Theorems 3 and 4 imply that the sequential procedure δ opt β is asymptotically optimal and robust in the pointwise and minimax senses for any compact sets Θ i ⊂ Θ st i and for any r > 0.

Application to epidemics detection and localization

Near optimality

We begin with considering the epidemiological statistical models proposed in [START_REF] Baron | Change-Point Detection in Binomial Thinning Processes, with Applications in Epidemiology[END_REF]. Assume that for any 1 i N the observations (X i,n ) 1 n ν and (X i,n ) n>ν are homogenous Markov processes with the values in the finite space (X, µ), X i = {0, . . . , D} and µ{0} = . . . = µ{D} = 1. In this model, the conditional X i,n |X i,n-1 densities for n ν and for n > ν are defined respectively as

f * i (y|x) = x y (p * i ) x-y (1 -p * i ) y and f i,θ i (y|x) = x y θ x-y i (1 -θ i ) y , (9.1)
where 0 < p * i < 1 and θ i ∈ Θ i ⊂ [0, 1]. The probabilities p * i are non-epidemic (normal) infection rates and the Θ i are the sets of epidemic values of the infection parameters θ i . In this case, the functions g i defined in (7.1) for any 0 < θ i < 1, x, y ∈ X have the following forms

g i (θ i , y, x) = log f i,θ i (y|x) f * i (y|x) = (x -y) log θ i p * i + y log 1 -θ i 1 -p * i , i = 1, . . . , N. . (9.2)
So the functions (7.4) are

J i (θ i , x) = x y=0 (x -y) log θ i p * i + y log 1 -θ i 1 -p * i x y θ x-y i (1 -θ i ) y
and

J * i (θ i , x) = x y=0 (x -y) log θ i p * i + y log 1 -θ i 1 -p * i x y (p * i ) x-y (1 -p * i ) y .
One can check directly that the set C = {0} is an accesible atom for the Markov chains (X i,n ) n>ν . Obviously, if X i,n-1 = 0 then X i,n = 0 almost surely. Define the Markov time

τ = inf{n 1 : X i,n = 0} . If X i,0 = 0 then τ = 1, i.e., E θ i i,x=0 [τ] = 1.
Therefore, for any 0 < θ i < 1 the chain is ergodic with the ergodic distribution λ θ i (Γ) = 1 {0∈Γ} for any Γ ⊆ X (point measure). See, e.g., Theorems 10.2.1 and 10.2.2 in [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF]. In this case, for any compact sets Θ i ⊂ Θ min

1 i N inf θ i ∈Θ i inf x,y∈C f i,θ i (y|x) = 1 .
Let us select

V(x) = V * e γx , (9.3)
where γ > 0 and V * 1. For any x 1 we have

E θ i x [V(X 1 )] V(x) = x y=0 V(y) V(x) x y θ x-y i (1 -θ i ) y = (1 -θ i ) x + x-1 y=0 V(y) V(x) x y θ x-y i (1 -θ i ) y (1 -θ i ) x + e -γ x-1 y=0 x y θ x-y i (1 -θ i ) y = (1 -e -γ )(1 -θ i ) x + e -γ (1 -e -γ )(1 -θ i ) + e -γ .
So, if we take γ = log 2 in (9.3), we obtain that for 1 i N and

θ i ∈ Θ i E θ i x [V(X i,1 )] V(x) 2 -θ i 2 1 -ρ with ρ = min 1 i N inf θ i ∈Θ i θ i 2 .
By Theorem A1 in [START_REF] Pergamenchtchikov | Asymptotically optimal pointwise and minimax change-point detection for general stochastic models with a composite post-change hypothesis[END_REF], the Markov chain (X i,n ) n>ν is uniformly geometric ergodic and for some positive constants

κ * and R * sup n 0 e κ * n max 1 i N sup x∈X i sup θ i ∈Θ i sup 0 g V 1 V(x) |E θ i,x [g(X i,n )] -g(0)| R * .
Therefore, Theorem 5 implies conditions (A 1 ) and (A 2 (r)) with J i (θ i ) = J i (θ i , 0) = 0 and J * j (θ j ) = J * i (θ i , 0) = 0 for all r > 0. This means that we cannot use the procedures (4.4) for this problem directly. However, in practice the values of the observations X i,n are sufficiently large, i.e., D → ∞, and usually the number of the infected populations is not too large, i.e., X i,n D for some 0 < < 1. So it is more natural to modify the initial model and study the limiting model when D is sufficiently large. Note that in this case observations in the binomial models (9.1) can be represented as

X i,n = (1 -ϑ)X i,n-1 + X i,n-1 j=1 (η n, j -1 + ϑ) ,
where (η n, j ) j 1 is i.i.d. sequence of Bernoulli random variables with P(η n, j = 1) = 1 -ϑ and independent from X i,n-1 and where ϑ = θ i and p * i in the post-change and pre-change modes, respectively. Using the Gaussian approximation for the last sum 1

X i,n-1 X i,n-1 j=1 (η n, j -1 + ϑ) ∼ N(0, σ 2 ϑ ) , σ 2 ϑ = ϑ(1 -ϑ) ,
we obtain the following model

X i,n = (1 -ϑ)X i,n-1 + σ ϑ |X i,n-1 |ξ i,n ,
where (ξ i,n ) n 1 is the sequence of i.i.d. normal N(0, 1) random variables. Thus, in place of the original Bernoulli model we will use the following model: the observations X i,k before change are defined as

X i,n = (1 -p * i )X i,n-1 + σ * i |X i,n-1 | ξ i,n , σ * i = p * (1 -p * ) , (9.4)
and after change as

X i,n = (1 -θ i )X i,n-1 + σ θ i |X i,n-1 | ξ i,n , (9.5)
where θ i ∈ Θ i ⊂ [0, 1] and (ξ i,n ) n 1 are i.i.d. N(0, 1) random variables. In this case, the spaces (X i , B i , µ i ) are:

X = R * = R \ {0}, B i = B(R * )
is the Borel field and µ i = µ is the Lebesgue measure on B(R * ). Obviously,

f * i (y|x) = 1 σ * i √ 2π|x| exp - [y -(1 -p * )x] 2 2(σ * i ) 2 |x| and f θ i (y|x) = 1 σ θ i √ 2π|x| exp        - [y -(1 -θ i )x] 2 2σ 2 θ i |x|        . (9.6)
Using definitions (7.2) and (7.4) we obtain that for

x ∈ R * g i (θ i , y, x) = log σ * i σ θ i + (η * i (y, x)) 2 2 - (η θ i ,i (y, x)) 2 2 , (9.7)
where

η * i (y, x) = y -(1 -p * )x σ * i √ |x| and η θ i ,i (y, x) = y -(1 -θ i )x σ * θ i √ |x| .
In this case,

L i,n = opt n-1 k=0 (1 -opt ) k Θ i e n j=k+1 g i (θ i ,X i, j ,X i, j-1 ) W i (dθ i ) (9.8)
and

L i,n = opt n-1 k=0 (1 -opt ) k sup θ∈Θ i e n j=k+1 g i (θ i ,X i, j ,X i, j-1 ) , (9.9)
where opt is defined in (6.10). The elements of the random N × N matrix (4.3) have the following form

< U n > i, j = L i,n L j,n if i j and < U n > i,i = L i,n (1 -opt ) n , (9.10)
and the corresponding change detection-identification procedure δ opt β = (T opt β , d opt β ) is defined in (6.13)-(6.14) with the threshold matrix A = A opt β given by (6.12). Let us check conditions (C 1 ) -(C 3 ). To this end, first note that

J i (θ i , x) = 1 2       log p * i (1 -p * i ) θ i (1 -θ i ) -1 + θ i (1 -θ i ) p * i (1 -p * i ) + (θ i -p * i ) 2 p * i (1 -p * i ) |x|       (9.11)
and

J * i (θ i , x) = 1 2       log p * i (1 -p * i ) θ i (1 -θ i ) + 1 - p * i (1 -p * i ) θ i (1 -θ i ) - (θ i -p * i ) 2 θ i (1 -θ i ) |x|       . (9.12)
Taking into account that the function zlog z -1 > 0 for all z > 0 and z 1 we obtain that inf x J i (θ i , x) > 0 and sup x J i (θ i , x) < 0 for all θ i p * i . Recall that p * i and θ i are the infection rates, where p * is normal non-epidemic value and θ i is epidemic value. So, if pi is the epidemic threshold for the ith stream, then Θ i ⊂ ( pi , 1) and for all p * i < pi min

1 i N inf θ i ∈Θ inf x J i (θ i , x) > 0 . (9.13)
Now we need to check the conditions of Theorem 5. First, note that the definition (9.6) yields that for any B > 0

min 1 i N inf θ i ∈Θ i inf |y| B inf |x| B f θ i (y|x) > 0 .
From (9.11) it is easy to deduce that for any compact sets Θ i ⊂ ( pi , 1)

g * = max 1 i N max x∈R sup θ i ∈Θ i J i (θ i , x) 1 + |x| < ∞ . (9.14)
Moreover, note that 2 |x| and, therefore, using the definition (7.2) we obtain h(x, y) = max

∂g i (ϑ, y, x) ∂ϑ = 2ϑ -1 ϑ(1 -ϑ) - (y -(1 -ϑ)x)x ϑ(1 -ϑ)|x| + (y -(1 -ϑ)x) 2 2ϑ 2 (1 -ϑ)
1 i N max u∈Θ i |∂g i (u, y, x)/∂u| ȟ 1 + |x| + |y| + y 2 |x| , (9.15)
where ȟ = max 1 i N max ϑ∈Θ i ϑ -2 (1 -ϑ) -2 . Therefore, taking into account, that in this case f i,ϑ (y|x) = f ϑ (y|x) for all 1 i N, we get for any ϑ

∈ Θ i h i (ϑ, y) = h(ϑ, y) = R h(y, x) f ϑ (y|x) dy ȟ 1 + |x| + R |y| f ϑ (y|x) dy + 1 |x| R y 2 f ϑ (y|x) dy ȟ 1 + |x| + (1 -ϑ)|x| + σ ϑ |x| + (1 -ϑ) 2 |x| + σ 2 ϑ |x| 4 ȟ(1 + |x|) .
To check the conditions (C1.2) we set

V(x) = V * (1 + |x|) and V * = g * + 4 ȟ .
For the model (9.5) we have

E θ i i,x [V(X i,1 )] V * 1 + (1 -θ i )|x| + σ θ i |x|E|ξ 1 | , i.e., lim sup B→∞ sup |x|>B max 1 i N sup θ i ∈Θ i E θ i i,x [V(X i,1 )] V(x) 1 -min 1 i N inf θ i ∈Θ i θ i .
Therefore, there exists B > 0 such that for all |x| > B max

1 i N sup θ i ∈Θ i E θ i i,x [V(X i,1 )] (1 -ρ)V(x) and ρ = 1 2 min 1 i N inf θ i ∈Θ i θ i .
Obviously, this inequality implies condition (C 1 ) with C = {x ∈ R : |x| B}. Using Theorem 15.01 in [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF] and Proposition A.1 in the Appendix, it is easy to deduce that the processes (9.4) and (9.5) are stationary with the ergodic distributions defined by the random variables ς * i and ς θ i ,i such that for any q > 0

E|ς * i | q < ∞ and E|ς θ i ,i | q < ∞ . (9.16)
Hence, from (9.11) and (9.12) we get

J i (θ i ) = 1 2       log p * i (1 -p * i ) θ i (1 -θ i ) -1 + θ i (1 -θ i ) p * i (1 -p * i ) + (θ i -p * i ) 2 p * i (1 -p * i ) E|ς θ i ,i |       (9.17)
and

J * i (θ i ) = 1 2       log p * i (1 -p * i ) θ i (1 -θ i ) + 1 - p * i (1 -p * i ) θ i (1 -θ i ) - (θ i -p * i ) 2 θ i (1 -θ i ) E|ς * i |       . (9.18)
As far as the condition (C 2 ) is concerned it follows from (9.7) and (9.15) that there exists a constant c * > 0 such that for all x, y ∈ R * max

1 i N sup θ i ∈Θ i |g i (θ i , y, x)| + h i (x, y) c * 1 + |x| + |y| + y 2 |x| .
Note that for any m 1 there exists a constant C m > 0 for which for any 1 i N and

θ i ∈ Θ i E i,θ i X 2m i,n |X i,n-1 C m (X 2m i,n-1 + |X i,n-1 | m ) .
Hence, for any m 1 there exists a constant C m > 0 such that

E θ i i,x [g 2m i (θ i , X i,n , X i,n-1 )] C m 1 + E θ i i,x [X 2m i,n-1 ] + E θ i i,x [|X i,n-1 | m ] C m 1 + E θ i i,x [X 2m i,n-1
] and

E θ i i,x [h 2m i (X i,n , X i,n-1 )] C m 1 + E θ i i,x [X 2m i,n-1 ] .
To check the condition (C 3 ) we can obtain directly from (9.18) that for 1 i N

g i (u, y, x) -J * i (u) = 1 2 1 - p * i (1 -p * i ) u(1 -u) ((η * i (y, x)) 2 -1) - (u -p * i ) 2 2u(1 -u) |x| -E[|ς * i |] - p * i (1 -p * i ) u(1 -u) (u -p * i )xη * i (y, x) .
By Proposition A.1 (see the appendix) max 1 i N sup j 1 E * |X i, j | q < ∞ for any q > 0. Also, under P * the random variables (η * i (X i, j , X i, j-1 )) 1 i N , j 1 are i.i.d. N(0, 1), so that condition (C * 3 (q)) holds for any q > 0, which implies condition (C 3 (q)) for any q > 0 (see Proposition 3). Thus, it follows from Theorems 3 and 4 that the sequential detection-identification procedure δ opt β = (T opt β , d opt β ) defined in (6.13)-(6.14) is asymptotically optimal (as β max → 0) and robust in the pointwise and minimax senses for any r > 0.

Monte Carlo

To get operating characteristics of the proposed detection-identification algorithm not only in the asymptotic case but also for reasonable probabilities of false alarm and misidentification, we perform Monte Carlo (MC) simulations for the modified Bernoulli model (9.4), (9.5) with X i,n = Y i,n /V i . The values of Y i,n correspond to the number of susceptible at the n-th point in time for the ith population (n 0, i = 1, . . . , N) and the values of V i to the number of susceptible at the initial moment, i.e. Y i,0 = V i . In simulations, we set the initial value Y i,0 = V i = 0.5(i + 1) • 10 4 for 1 i N. Without loss of generality we assume that the change occurs in the Nth stream. Then (9.4) for 1 i N -1 reduces to

X i,n = (1 -p * i )X i,n-1 + σ * i |X i,n-1 | ξ i,n , σ * i = p * i (1 -p * i ) V i
, X i,0 = 1, and (9.5) to

X N,n = (1 -ϑ)X i,n-1 + σ ϑ |X N,n-1 | ξ N,n , σ ϑ = ϑ(1 -ϑ) V N , X N,0 = 1, where ϑ = ϑ n = p * N + (p -p * N )1 {n>ν} .
In each MC run m, using formulas (9.7)-(9.10) and (6.12), we get a pair δ * ,m A = (T * ,m A , d * ,m A ) -the stopping time and the number of the stream where the change is detected (m = 1, . . . , M, M is the total number of MC runs).

The theoretic estimate of the expected detection delay for i = N is given by the second asymptotic formula in (6.15) with r = 1, i.e.,

R N,ν,θ N ≈ max 1 j N | log β j,N | ι N, j (θ N ) for θ N = p .
Since calculation of ι N, j (θ N ) analytically is difficult we evaluate it using MC simulations. To this end, we first estimate the conditional informations

J i (ϑ, x) = R g i (ϑ, y, x) f ϑ (y|x)dy and J * i (ϑ, x) = R g i (ϑ, y, x) f * i (y|x)dy
and then we calculate the Kullback-Leibler divergences by MC as

I N (ϑ) = 1 K ν+K n=ν+1 J N (ϑ, X N,n ) and I * i (ϑ) = 1 K K n=1 J * i (ϑ, X i,n ) for 1 i N -1 . (9.19) 25
By the law of large numbers for Markov chains the MC estimates I i (ϑ) and I * i (ϑ) converge to the true values J i (ϑ) and J * i (ϑ) defined in (7.5). Then (5.1) and (7.9) reduce to

ι N, j (θ N ) = I N (θ N )1 { j=N} + (I N (θ N ) -max ϑ∈Θ j I * j (ϑ))1 { j N} .
(9.20)

The MC estimate of the expected detection delay (in the Nth stream) is calculated from the formula:

R = M m=1 (T * ,m A -ν)1 (T * ,m A >ν) 1 {d * ,m A =N} M m=1 1 {T * ,m A >ν} .
In particular, for ν = 0, which is used in simulations, it reduces to

R = 1 M M m=1 T * ,m A 1 {d * ,m A =N} .
The MC estimate of the false alarm probability (ν = +∞) is:

P N = max 1 k * -m * M m=1 1 { T * ,m A < +m * } 1 {d * ,m A =N} M m=1 1 {T * ,m A } ,
and the MC estimates of the miss identification probabilities are:

P j,N = max ν< ν+k * M m=1 1 {T * ,m A > } 1 {d * ,m A = j} M m=1 1 {T * ,m A > } for 1 j N -1 .
In simulations, we assume that the number of streams N = 5; the parameters of the observed process are p * i = 1/(100 + i), 1/(50 + i); q = p/p * N = 1.1, 1.15, 1.2; for calculation of thresholds A i, j we use (6.10) and (6.12) with β i, j = ε i+ j , ε = 0.3, 0.1, 0.01 and ǩ = 2, 1.55, 1.23. We also assume that the change occurs from the very beginning, i.e., at the time ν = 0, in which case ϑ = p.

The results are shown in Table 1 and Table 2. It is seen that the detection-identification algorithm has good performance. Even for small false alarm and miss identification probabilities the average detection delay is small. Therefore, we recommend using this algorithm in practice for the detection and localization of epidemics. Also, the asymptotic approximations for the average detection delay are quite accurate and, therefore, can be used for the evaluation of the performance of the detection-identification procedure in practice. In Subsection 9.1, we applied the proposed sequential detection-identification algorithm to epidemic models and showed it to be asymptotically optimal when the probabilities of wrong identification and false alarm are small. In this subsection, we demonstrate that the proposed detection-identification procedure can be effectively applied for the localization of COVID-19, i.e., for the detection of the epidemic anomalies and identification of the affected region. Consider the case of Italy.

ε ǩ q P1,N P2,N P3,N P4,N P N R R N,0,θ N 0.3 2
Let H i,n be the number of hospitalized people at the n-th moment for the ith region. (Since the shortage of hospital beds presented a major challenge in Italy during the first wave of COVID-19, we focus on hospitalizations. However, this model also applies to other kinds of observations, e.g., number of infected people, number of visits to the doctor [START_REF] Baron | Change-Point Detection in Binomial Thinning Processes, with Applications in Epidemiology[END_REF].) Then, Y i,n = V i -H i,n , where V i is the total number of hospital beds, i.e., Y i,n is potentially free beds for new hospitalizations at the n-th moment for the ith region. Then the observation, as in (9.2), will be X i,n = Y i,n /V i .

We use the data provided by Sito del Dipartimento della Protezione Civile -Emergenza Coronavirus: la risposta nazionale (the Italian Department of Civil Protection). This data includes information on hospitalizations by region each day. We consider five Italian regions: Sicily, Lazio, Tuscany, Venice, and Lombardy. We use the proposed detection-identification algorithm to detect the presence of COVID-19 in a given region. Fig. 1 shows raw observations for five different regions, detection and identification of a region with a COVID outbreak in Italy by the proposed algorithm (blue vertical line), and the official introduction of a regional quarantine (red vertical line) in Lombardy.

It is known that Lombardy became the epicenter of the spread of COVID not only in Italy but throughout Europe. According to Fig. 1, the proposed algorithm detected COVID in Italy 9 days prior to the imposition of quarantine protocols in Lombardy (February 28, 2020 vs. March 8, 2020). The proposed detection-identification algorithm could therefore be a useful tool for researchers and public health aurhorities in detecting and localizing epidemics.

Conclusion

1. In this paper, we ignore the possible indifference zone Θ ind of parameter values where the probabilities of false alarms and misidentification are too close to be reasonably distinguishable. In the indifference zone, the constraints on the erroneous decisions are not imposed, but still, the expected detection delays (or more generally moments of delay) have to be minimized for all possible parameter values, including those in the indifference zone. The modification of the proposed procedure to take into account an indifference zone, if needed, is straightforward. For the sake of brevity, the details are omitted.

2. As in the recent paper by Tartakovsky [START_REF] Tartakovsky | An asymptotic theory of joint sequential changepoint detection and identification for general stochastic models[END_REF], we focus on the multistream changepoint model (2.1)-(2.2). It is worth noting that the same results hold in the single-stream detection-isolation problem when the observations {X n } n 1 represent either a scalar process or a vector process but all components of this process change at time ν. Specifically, in change detection and isolation, the post-change hypothesis H ν,i,θ i , θ ∈ Θ i corresponding to the ith type of change usually involves unknown parameters θ i and, therefore, is composite. Under the hypothesis H ν,i,θ i , θ ∈ Θ i the post-change conditional density function is f i,θ i ,n (X n |X n-1 1 ), n > ν, while the pre-change density is f * n (X n |X n-1 ), n ν, where X t = (X 1 , . . . , X t ). Hence, introducing parametric families of densities { f i,θ i ,n (X n |X n-1 ), θ i ∈ Θ i } and for i = 1, . . . , N and Θ i ⊂ Θ considering the model 1

p(X n |H ν,i,θ i ) =        q * (X n )
for ν n ; q * (X ν ) n l=ν+1 f i,θ i ,l (X l |X l-1 ) for ν < n , (

where p(X n |H ν,i,θ i ) stands for the joint density of the first n observations X n conditioned on the hypothesis H ν,i,θ i and q * (X s ) = s l=1 f * l (X l |X l-1 ) for s 1, we arrive at the single-stream model that has all features of the previous multistream model (2.1)-(2.2). In fact, setting X n = (X 1,n , . . . , X N,n ), where the components of this vector are mutually independent and assuming that the change may occur only in a single component, we obtain

p(X n |H ν,i,θ i ) =        N i=1 q * i (X n i ) for ν n ; q * i (X ν i ) n l=ν+1 f i,θ i ,l (X i,l |X l-1 i ) 1 j i N n l=1 f * j (X j,l )|X l-1 j ) for ν < n ,
where X n i = (X 1,i , . . . , X i,n ), X n = (X n 1 , . . . , X n N ), and q * i (X s ) = s l=1 f * i,l (X l |X l-1 i ). Obviously, this joint density is the same as the one in (2.4), so that in the case of mutually independent streams the multistream model defined in (2.1)-(2.2) is a particular case of the model (10.1).

3. All previous results can be generalized for the case when the change points are different for different streams, i.e., when ν = ν i .

4. For independent observations as well as for a variety of Markov and certain hidden Markov models (see, e.g., Subsections 8.1 and (8.2) and Section 9), the decision statistics < U n > i, j defined in (4.3) can be computed relatively easily, in which case implementation of the proposed change detection-identification procedure is not an issue. In general, however, the computational complexity of rule δ A may be high. To avoid computational difficulties rule δ A can be modified into a window-limited version where the summation in the decision statistics over potential change points ν is restricted to the sliding window of specific fixed size = β , which is a function of the error probabilities constraints β. Following guidelines of [START_REF] Tartakovsky | An asymptotic theory of joint sequential changepoint detection and identification for general stochastic models[END_REF] (Ch 3, Sec 3.10) where asymptotic optimality of mixture window-limited rules was established in the single-stream case, it can be shown that the window-limited version of the multihypothesis detection-identification procedure also has asymptotic optimality properties as long as the size of the window β goes to infinity as β max → 0 at such a rate that β /| log β max | → ∞.

By the Hölder inequality,

E ϑ i,x [X 2m i,k ] 2 2m-1          x 2m + σ 2m ϑ ϑ 2m-1 k j=1 (1 -ϑ) k-j E ϑ i,x [|X i,k | m ξ 2m i, j ]          2 2m-1        x 2m + (2m -1)!!σ 2m ϑ ϑ 2m sup k 0 E ϑ i,x |X i,k | m        .
Now, using the induction assumption (A.3) and that |x + y| α |x| α + |y| α for 0 < α 1, we obtain

E ϑ i,x |X i,k | m E ϑ i,x |X i,k | 2(m-1) m/(2m-2) C m/(2m-2) m 1 + x 2(m-1) m/(2m-2) C m 1 + x 2m .
This implies the second inequality in(A.1), completing the proof.

(H 1 )

 1 The parameters , m * and k * in (4.11) are functions of β, i.e. = β , m * = m * β and k * = k * β , such that lim

Proposition 2 .

 2 If conditions (A 2 ) and (H 2 ) hold true, then for any 1 i N and any compact set K ⊂ Θ the sequential procedure (4.5), in which | log | = o(log A min ) as A min → ∞, admits the following upper bound lim sup

. 10 )

 10 Then under the conditions limβ max →0 log | log β min | | log β max | = 0 and lim

.18) Theorem 4 .

 4 Suppose that conditions (A 1 )-(A 2 ) and (H 1 )-(H 3 ) hold and k * = o(| log β max |) as β max → 0. Then lim

Fig. 1 :

 1 Fig. 1: Detection and identification of the region with an outbreak of the COVID-19 epidemic in Italy: the proposed algorithm vs. the imposition of quarantine protocols in Lombardy. The time of detection and identification by our algorithm is shown by blue vertical line and the time of the official imposition of quarantine protocols by red vertical line.

Table 1 :

 1 Operating characteristics of the detection-identification procedure for p * i = 1 100+i (MC simulations with 10 5 runs).

Table 2 :

 2 Operating characteristics of the detection-identification procedure for p * i = 1 50+i (MC simulations with 10 5 runs).

	ε	ǩ	q	P1,N	P2,N	P3,N	P4,N	P N	R	R N,0,θ N
	0.3	2	1.1	0.00076 0.00062 0.00033 0.00016 0.0004	3.92	3.89
	0.3	2	1.15 0.00078 0.00162 0.0004	0.0003	0.0007	2.03	2.29
	0.3	2	1.2	0.0073	0.0078	0.0019	0.0009	0.0045	1.24	1.65
	0.1 1.55 1.1	0.0002 0.00022 0.00004 0.00006 0.00014 4.50	5.23
	0.1 1.55 1.15 0.00018 0.00082 0.00026 0.00016 0.00044 2.26	3.08
	0.1 1.55 1.2	0.00342 0.00447 0.00142 0.00049 0.0017	1.33	2.21
	0.01 1.23 1.1	0.00004 0.00004 0.00002 0.00002 0.00002 5.74	7.91
	0.01 1.23 1.15 0.00002 0.00022 0.00008 0.00001 0.00008 2.78	4.65
	0.01 1.23 1.2	0.00084 0.00145 0.00056 0.00019 0.0003	1.57	3.35
	9.3. Detection of COVID-19 in Italy

Often, θ i ≡ θ does not depend on i in practice.

Acknowledgements

The work of S.M. Pergamenchtchikov was partially supported by the RSF grant 20-61-47043 (National Research Tomsk State University). The work of A.G. Tartakovsky was supported in part by the Russian Science Foundation Grant 18-19-00452 at the Moscow Institute of Physics and Technology (Space Informatics Laboratory).

Appendix A. Moment properties of the epidemic models Proposition A.1. For any integer m 1 and for any compact set Θ i ⊆ Θ the process X i,n defined in (9.4) and (9.5) has the following moment properties

Proof. We prove only the second inequality in (A.1) since the proof of the first one is essentially similar. To this end, we first show that for any x ∈ R sup

It is easily seen that for the model (9.5) we have

For the sake of brevity write

]. Taking into account that x 1 + x 2 , we obtain

Let now υ n = y n -(1 -ϑ) 2 y n-1 . Clearly υ n σ 2 ϑ and

This implies inequality (A.2) and, therefore, the second inequality in (A.1) for m = 1.

For an arbitrary m 1 this inequality can be proved by induction as follows. Assume that the second inequality in (A.1) is true for m -1 and m 2, i.e., there exists a constant C m 1 such that for any

To show that it holds for m, using the initial condition X i,0 = x, we represent the process (9.5) as

(1 -ϑ) k-j |X i, j-1 |ξ i, j .


Jong-Geol Kim

Khaled S Gazi

Mart Krupovic

Sung-Keun Rhee
email: rhees@cbnu.ac.kr

ICTV Virus Taxonomy Profile: Thaspiviridae 2021

Keywords: ICTV Report, taxonomy, Thaspiviridae. 001631

Members of the family Thaspiviridae have linear dsDNA genomes of 27 to 29 kbp and are the first viruses known to infect mesophilic ammonia-oxidizing archaea of the phylum Thaumarchaeota. The spindle-shaped virions of Nitrosopumilus spindle-shaped virus 1 possess short tails at one pole and measure 64±3 nm in diameter and 112±6 nm in length. This morphology is similar to that of members of the families Fuselloviridae and Halspiviridae. Virus replication is not lytic but leads to growth inhibition of the host. This is a summary of the International Committee on Taxonomy of Viruses (ICTV) Report on the family Thaspiviridae, which is available at ictv. global/ report/ thaspiviridae.

VIRION

The virion of Nitrosopumilus spindle-shaped virus 1 is 64±3 nm in diameter and 112±6 nm in length with a short tail at one pole (Table 1, Fig. 1). The predicted major capsid protein (81 amino acids) contains two highly hydrophobic α-helical regions. The spindle-shape morphology of the virion is very similar to those of members of the families Fuselloviridae [START_REF] Krupovic | Unification of the globally distributed spindle-shaped viruses of the Archaea[END_REF] and Halspiviridae [START_REF] Bath | His1 and His2 are distantly related, spindle-shaped haloviruses belonging to the novel virus group, Salterprovirus[END_REF], which infect hyperthermophilic and hyperhalophilic archaea, respectively. When associated with the host cells, some virions are observed as elongated structures, with long thin tails connected to the cell surface [START_REF] Häring | Virology: independent virus development outside a host[END_REF][START_REF] Kim | Spindleshaped viruses infect marine ammonia-oxidizing thaumarchaea[END_REF].

GENOME

The genome of Nitrosopumilus spindle-shaped virus 1 is linear dsDNA (27-29 kbp), terminating with 176 bp inverted repeats (Fig. 2). The virus genome is predicted to carry 48 genes. With one exception, the proteins predicted to be encoded by Nitrosopumilus spindle-shaped virus 1 are unrelated to those of other archaeal and bacterial viruses. The exception, protein-primed B DNA polymerase, is also found in several groups of archaeal viruses and non-viral mobile genetic elements which, similar to Nitrosopumilus spindle-shaped virus 1, have linear genomes with terminal inverted repeats [START_REF] Kim | Spindleshaped viruses infect marine ammonia-oxidizing thaumarchaea[END_REF].

REPLICATION

The virus establishes a chronic infection and its replication is not lytic, with virions being continuously extruded into the environment [START_REF] Kim | Spindleshaped viruses infect marine ammonia-oxidizing thaumarchaea[END_REF]. The virus genome is likely to be replicated by the virus-encoded protein-primed family B DNA polymerase, as has been inferred for haloarchaeal halspiviruses [START_REF] Bath | His1 and His2 are distantly related, spindle-shaped haloviruses belonging to the novel virus group, Salterprovirus[END_REF] and crenarchaeal ampullaviruses [START_REF] Prangishvili | ICTV Virus Taxonomy Profile: Ampullaviridae[END_REF]. In addition, the virus encodes

RESOURCES

Full ICTV Report on the family Thaspiviridae: ictv. global/ report/ thaspiviridae.

Funding information

Production of this Profile, the ICTV Report, and associated resources was funded by a grant from the Wellcome Trust (WT108418AIA) and the National Research Foundation of Korea (NRF) grants funded by the Ministry of Science, ICT & Future Planning (2021R1A2C3004015).

Fig. 1 .

 1 Fig. 1. (Left) Transmission electron micrograph of negatively-stained virions of Nitrosopumilus spindle-shaped virus 1. (Right) Virus particles attached to the surface of a host cell.

Fig. 2 .

 2 Fig. 2. Genome maps of Nitrosopumilus spindle-shaped virus 1 isolates NSV1-1 and NSV1-2, and of the haloarchaeal halspivirus His1. Shared ORFs are connected by shaded areas based on sequence identity. Functionally equivalent (but not necessarily homologous) genes are indicated with matching colours. Filled circles indicate terminal inverted repeats. pPolB, protein-primed family B DNA polymerase; MCP, major capsid protein (putative); wHTH, winged helix-turn-helix; GTase, glycosyltransferase; MTase, DNA methyltransferase; PCNA, proliferating cell nuclear antigen.

Table 1 .

 1 Characteristics of members of the family Thaspiviridae

	Translation	Not characterized
	Host range	Ammonia-oxidizing archaea of the genus Nitrosopumilus
	Taxonomy	Single genus with one species

Example:

Nitrosopumilus spindle-shaped virus 1 (MK570053), species Nitmarvirus NSV1, genus Nitmarvirus Virion Spindle-shaped, measuring 64±3 nm in diameter and 112±6 nm in length, with short fibres at one pole. Genome Linear dsDNA (27-29 kbp) with 176 bp terminal inverted repeats Replication Non-lytic, chronic infection. Protein-primed family B DNA polymerase is involved in viral DNA replication a proliferating cell nuclear antigen which is also likely to be involved in viral genome replication. TAXONOMY Current taxonomy: ictv. global/ taxonomy. The single genus Nitmarvirus includes one species Nitmarvirus NSV1.

Acknowledgements

Members of the ICTV Report Consortium are Stuart G. Siddell, Elliot J. Lefkowitz, Sead Sabanadzovic, Peter Simmonds, F. Murilo Zerbini, Donald B. Smith, Richard J. Orton and Mart Krupovic.

Conflicts of interest

The authors declare that there are no conflicts of interest.