有限相依随机序列的非贝叶斯变点最优监测.pdf

应用概率统计第 40 卷第 2 期2024 年 4 月Chinese Journal of Applied Probability and StatisticsApr.,2024,Vol.40,No.2,pp.277-286doi:10.3969/j.issn.1001-4268.2024.02.004The Optimality in Non-Bayesian Change-Point Detection forFinite Observation SequenceHAN Dong(Department of Statistics,School of Mathematical Sciences,Shanghai Jiao Tong University,Shanghai,200240,China)TSUNG Fugee(Department of Industrial Engineering and Decision Analytics,The Hong Kong Universityof Science and Technology,Hongkong;Data Science and Analytics Thrust,The Hong Kong University of Science and Technology(Guangzhou),Guangzhou,520700,China)Abstract:This paper studies the non-Bayesian change-point detection of finite dependent sam-ples sequence.By presenting the nonnegative dynamic random control limits,we not only con-structed and proved two optimal control charts,but also obtained the expressions for the minimumvalues of Lordens measure and Pollaks measure that are easier to calculate than the original def-inition.Keywords:optimal control chart;non-Bayesian change-point detection;dependent observationsequence2020 Mathematics Subject Classification:62L10Citation:HAN D,TSUNG F G.The optimality in non-Bayesian change-point detection for finiteobservation sequenceJ.Chinese J Appl Probab Statist,2024,40(2):277286.1IntroductionOne of the main objectives of SPC is to raise an alarm as soon as a change occursat some change-point in an observation sequence,subject to a restriction on the rateof false alarms.The need for abrupt changes to be detected quickly with a low falsealarm rate in a stochastic system arises in a variety of applications,including qualitycontrol,segmentation of signals,biomedical signal processing,financial engineering,andfault detection in complex structures,see,for example,18.The project was supported by the National Natural Science Foundation of China(Grant Nos.72371271,11531001).Corresponding author,E-mail:seasonust.hk.Received November 17,2023.278Chinese Journal of Applied Probability and StatisticsVol.40There are mainly two settings in the change-point detection:one is Bayesian change-point detection in which the distribution of the change-point is known912,another isnon-Bayesian or minimax(worst possible)change-point detection in which the change-point is non-random and unknown1316.A recent review of change-point detection theoryin both Bayesian and non-Bayesian settings can be found in the reference 17.Next we recall some known results for the non-Bayesian change-point detection.Con-sider a mutually independent infinite observation sequence,X0,X1,X2,whose distri-bution may change at some time 1(change-point).We assume that the known proba-bility density function(pre-change density function)of observations X0,X1,X2,Xn,is p0()for n ,which is also known and differs from p0().Denote by P(E)theprobability distribution(expectation)with the density function of p1()when the changeoccurs at.When =,i.e.,a change never occurs,we denote the probability distribu-tion(expectation)by P0(E0)with the density function p0()for all time t 0.Generally speaking,any control chart(or sequential test)for change-point detectioncan be modeled as a stopping time or an alarm time T 1 which is adapted to thefiltration Ftt0,where Ft=Xk,0 6 k 6 t denotes the smallest-algebra withrespect to which all of the random variables X0,X1,Xtare measurable.We usuallyassume that X0 x0(a constant)and F0=,.The optimality of the stopping timeusually means that the detection delay(T +1)+measured in some sense is the smallestamong all stopping times with a false alarm rate no less than a given value 1,i.e.,E(T).So far,there exists two major non-Bayesian measures to evaluate the performance ofa control chart in detecting the change-point17.The first one is Lordens measure JL()proposed by Lorden13JL(T)=supk1esssupEk(T k+1)+|Fk1,(1)which denotes the worst average delay of the alarm time T,where esssup denotes theessential upper bound.The second one is Pollaks measure,JP(T)proposed by Pollak14,also considers the worst average delay of a control chart T,which can be written asJP(T)=supk1Ek(T k+1|T k).(2)No.2HAN D.,TSUNG F.G.:The Optimality in Non-Bayesian Change-Point Detection279Moustakides15proved that the following classical upper-sided CUSUM chartTC(c)=minn 1:max16k6nni=nk+1lnk lnc=minn 1:Yn cis optimal under the Lordens measure JL(),that is,infT:E0(T)JL(T)=JL(TC(c),where Y0=0,Yn=max1,Yn1n,n=p1(Xn)/p0(Xn)for n 1 and the constantcontrol limit c=c 0 satisfies E0TC(c)=1.Polunchenko and Tartakovsky16proved that the following Shiryaev-Roberts chartTSRwith a specially designed deterministic nonnegative number r for an exponential modelTSR(c)=minn 1:rnk=1k+nt=1nk=tk cis optimal under the Pollaks measure JP(T),that is,infT:E0(T)JP(T)=JP(TSR(c),where the constant control limit csatisfies E0TSR(c)=1.It can be seen that the above two control charts are based on two assumptions:thereis an infinite observation sequence and the infinite observation sequence is independent.In fact,it is unrealistic to have an infinite independent observation sequence,unless theobservation time is infinite.Moreover,for some special needs and under some specificconditions,people can only obtain finite observation samples.Additionally,there are veryfew cases where infinite observation sequence is mutually independent.Hence,one of interesting questions is that how to construct the non-Bayesian optimalcontrol chart in monitoring the change-point for a finite dependent samples sequence?Note that Han et al.18have constructed and proved the Bayesian optimal control chartsfor a finite dependent samples sequence.In the paper,we will further study the questionof constructing the non-Bayesian optimal control chart under the non-Bayesian measurefor a finite dependent samples sequence.2Construction of Two Non-Bayesian Control ChartsConsider finite dependent observations,X0,X1,X2,XN.Without loss of gener-ality,we assume N 2.Let =k(1 6 k 6 N)be the change-point which is non-random280Chinese Journal of Applied Probability and StatisticsVol.40and unknown,and let both the pre-change and the post-change joint probability densi-ties p0(x0,x1,xN)and pk(x0,x1,xk,xN)be known,where(x0,x1,xN)S RN+1and R=(,+).Denote the pre-change and the post-change conditionalprobability densities respectively by p0k(xk|xk1,x0)and p1k(xk|xk1,x0)for1 6 k 6 N.When N,i.e.,a change never occurs in N observations X1,X2,XN,the probability distribution and the expectation are denoted by P0and E0respective-ly for all observations X0,X1,X2,XNwith the pre-change joint probability densityp0(x0,x1,xN).When Xk,0 6 k 6 N is a process taking the discrete values,theabove joint probability densities and conditional probability densities will be consideredas the joint probabilities and conditional probabilities,for example,p0(x0,x1,xN)=P0(X0=x0,X1=x1,XN=xN).If the post-change joint probability densities are unknown,but the possibility(prob-ability distribution)that the post-change joint probability densities occur is known,thatis,there is a random parameter vector kwith the known probability distribution Qk()on the set Dksuch that the probability that the post-change joint probability density atchange-point time k being pk,(x0,x1,xk,xN)is Qk(),then we can define a newjoint probability density e pk(x0,x1,xk,xN)in the followinge pk(x0,x1,xN)=Dkpk,(x0,x1,xN)dQk()for 1 6 k 6 N.The density function e pk(x0,x1,xN)can be considered as a knownpost-change joint probability density function after change-point time k for 1 6 k 6N.In particular,e pk(x0,x1,xN)=pk,v0(x0,x1,xN)=pk(x0,x1,xN)whenQk(Vk=v0)=1.Thus,without loss of generality,we will regard e pk(x0,x1,xN)aspk(x0,x1,xN)in the following sections.Here,Ekand Ek,denote respectively theexpectation associated with the post-change density functions pkand pk,for 1 6 k 6 N.For simplicity we assume that the following ratio of post-change conditional proba-bility density to the pre-change conditional probability density satisfiesk=p1k(Xk|Xk1,X0)p0k(Xk|Xk1,X0)k)respectively,where T TNand TNis a set of all the control charts T satisfying T=n Fn=Xk,0 6 k 6 n for 0 6 n 6 N and T N=T=N+1 FN.In order to construct two optimal control charts respectively under the measuresJL,N()and JP,N(),let D=dk,0 6 k 6 N be a set of a series of nonnegativebounded numbers dk and W=wk,0 6 k 6 N be a set of a series of nonnegativebounded random variables wk satisfying d0=0,0 N+1k=1dk16 N,w0=0,wk Fkfor 0 6 k 6 N and 0 k(c)andTW(c)=min1 6 k 6 N+1:Zk k(c)for c 0,where Y0=0,Yk=(Yk1+dk)k,1 6 k 6 N,YN+1,YN,Z0=0,Zk=(Zk1+wk)k,1 6 k 6 N,ZN+1,ZN,and the two nonnegative random control limitsk(c),0 6 k 6 N+1 and k(c),0 6 k 6 N+1 are determined by the followingrecursive equationsN+1(c)=0,N(c)=cdN,k(c)=cdk+E0k+1(c)Yk+1+|Fk(4)for 0 6 k 6 N 1 andN+1(c)=0,N(c)=cwN,k(c)=cwk+E0k+1(c)Zk+1+|Fk(5)for 0 6 k 6 N 1 respectively.The expressions for the minimum values of Lordens measure JP,N()and Pollaksmeasure JL,N()and two optimal control charts TD(c)and TW(c)are given in the followingTheorem 1.282Chinese Journal of Applied Probability and StatisticsVol.40Theorem 1Letksatisfy(3)for1 6 k 6 N.Let1and2be two positive numberssatisfying0 1,21JP,N(T)=11infdkE0(TD(c1)k=1Yk1),(7)infTTN:sfE0(Tk=1wk)2JL,N(T)=11infwkE0(TW(c2)k=1Zk1),(8)whereY0=0,Yk=(Yk1+dk)k,Z0=0,Zk=(Zk1+wk)kfor1 6 k 6 N,TD(c)andTW(c)are defined in the followingTD(c)=min1 6 k 6 N+1:Yk k(c),(9)TW(c)=min1 6 k 6 N+1:Zk k(c),(10)where the two nonnegative dynamic random control limitskandkcan be defined like(4)and(5)by usingdk,Ykandwk,Zkrespectively.ProofSince JP,N(T)Ek(T k)+/P0(T k)for 1 6 k 6 N,P0(T N+1)=0and EN+1(T N 1)+=0 for T TN,it follows thatJP,N(T)=Nk=1dkP0(T k)JP,N(T)Nk=1dkP0(T k)Nk=1dkP0(T k)Ek(T k)+/P0(T k)Nk=1dkP0(T k)=Nk=1dkEk(T k)+Nk=1dkP0(T k)(11)for all T TN.Note that wkI(T k)Fkfor 0 6 k 6 N.By the definition of EkandJL,N(T)we can similarly get thatJL,N(T)=Nk=1E0wkI(T k)JL,N(T)Nk=1E0wkI(T k)No.2HAN D.,TSUNG F.G.:The Optimality in Non-Bayesian Change-Point Detection283Nk=1E0wkI(T k)Ek(T k)+|FkNk=1E0wkI(T k)=Nk=1E0EkwkI(T k)(T k)+|FkNk=1E0wkI(T k)=Nk=1Ekwk(T k)+Nk=1E0wkI(T k)(12)for T TN.From(11)and(12)it follows that there are a series of nonnegative boundednumbers dk,0 6 k 6 N and a series of nonnegative bounded random variables wk,0 6k 6 N such thatJP,N(T)=supdkNk=1dkEk(T k)+Nk=1dkP0(T k)=Nk=1dkEk(T k)+Nk=1dkP0(T k),(13)JL,N(T)=supwkNk=1Ekwk(T k)+Nk=1wkP0(T k)=Nk=1Ekwk(T k)+Nk=1E0wkI(T k).(14)We can select dk,0 6 k 6 N and wk,0 6 k 6 N according to the following method.Take i and j such thatJP,N(T)=sup16k6NEk(T k|T k)=Ei(T i|T i),JL,N(T)=sup16k6NesssupEk(T k)+|Fk=esssupEj(T j)+|Fj.Then we may select di=d 0,dk=0,k=i and wj=w 0,wk=0,k=j.Obviously,for different T TN,the selected dkor wjwill also be different,that is,dkor wjrely onT TN.On the other hand,since(Tk)+=Nm=kI(T m),T m Fmfor 1 6 m 6 NandYk=(Yk1+dk)k=kj=1djkl=jl,Zk=(Zk1+wk)k=kj=1wjkl=jlfor 1 6 k 6 N,it follows thatNk=1dkEk(T k)+=E0Nk=1dkNm=kI(T m)mj=kj=E0Nm=1YmI(T m)=E0(Tk=1Yk1)(15)andNk=1Ekwk(T k)+=E0Nk=1wkNm=kI(T m)mj=kj284Chinese Journal of Applied Probability and StatisticsVol.40=E0Nm=1ZmI(T m)=E0(Tk=1Zk1).(16)Moreover,Nk=1dkP0(T k)andNk=1E0wkI(T k)can be written asNk=1dkP0(T k)=E0(Tk=1dk1),Nk=1E0wkI(T k)=E0(Tk=1wk1)(17)respectively.Hence,by(15)(17),the two equations in(13)and(14)can be written inthe followingJP,N(T)=E0(Tk=1Yk1)E0(Tk=1dk1),JL,N(T)=E0(Tk=1Zk1)E0(Tk=1wk1)respectively,that is,(6)is true.By using dk,Yk and wk,Zk,we can define two nonnegative dynamic randomcontrol limits k and k like(4)and(5),and two control charts TD(c)in(9)and TW(c)in(10).By the definition of TD(c)and TW(c),we know that both E0(TD(c)k=1dk1)andE0(TW(c)k=1wk1)are continuous and increasing on c,it follows that there is a positivenumber c1and c2such thatE0(TD(c1)k=1dk)=1,E0(TW(c2)k=1wk1)=2.By the similar method of proving Theorem 1 in 18,we can prove thatE0(Tk=1Yk1)E0(Tk=1dk1)E0(TD(c1)k=1Yk1)E0(TD(c1)k=1dk1)=E0(TD(c1)k=1Yk1)1,(18)E0(Tk=1Zk1)E0(Tk=1wk1)E0(TW(c2)k=1Zk1)E0(TW(c2)k=1wk1)=E0(TW(c2)k=1Zk1)2(19)for all T TNwith E0(Tk=1dk1)1and E0(Tk=1wk1)2.The two inequal-ities(18)and(19)mean that both control charts TD(c)and TW(c)are optimal withE0(TD(c1)k=1dk)=1and E0(TW(c2)k=1wk1)=2.Thus,by using(6),(18)and(19),wecan get(7)and(8).It completes the proof of Theorem 1.?3Conclusion and QuestionBy presenting the nonnegative dynamic random control limits,we construct and provetwo optimal control charts TD(c)and TW(c)under two non-Bayesian or minimax measuresNo.2HAN D.,TSUNG F.G.:The Optimality in Non-Bayesian Change-Point Detection285JP,N()and JL,N()respectively for N finite dependent observation sequence.Moreover,we obtained the expressions for the minimum values of Lordens measure and Pollaksmeasure that are easier to calculate than the original definition.A question worth studying is:under what conditions do the results of Theorem 1 stillhold when the number of observed samples N approaches infinity?References1 BASSEVILLE M,NIKIFOROV I V.Detection of Abrupt Changes:Theory and ApplicationsM.Englewood Cliffs,NJ:Prentice-Hall,1993.2 MONTGOMERY D C.Introduction to Statistical Quality ControlM.6th ed.New York:Wiley,2008.3 POOR H V,HADJILIADIS O.Quickest DetectionM.Cambridge,UK:Cambridge University Press,2009.4 FRICKER R D.Introduction to Statistical Methods for Biosurveillance With an Emphasis on Syn-dromic SurveillanceM.Cambridge,UK:Cambridge University Press,2013.5 SIEGMUND D.Change-points:from sequential detection to biology and backJ.Sequential Anal,2013,32(1):214.6 QIU P H.Introduction to Statistical Process ControlM.New York:Chapman and Hall/CRC,2013.7 WOODALL W H,ZHAO M J,PAYNABAR K,et al.An overview and perspective on social networkmonitoringJ.IIE Trans,2017,49(3):354365.8 BERSIMIS S,SGORA A,PSARAKIS S.The application of multivariate statistical process monitoringin non-industrial processesJ.Qual Technol Quant Manag,2018,15(4):526549.9 SHIRYAEV A N.On optimum methods in quickest detection problemsJ.Theory Probab Appl,1963,8(1):2246.10 SHIRYAEV A N.Optimal Stopping RulesM.New York:Springer-Verlag,1978.11 TARTAKOVSKY A G.Asymptotic optimality in Bayesian changepoint detection problems underglobal false alarm probability constraintJ.Theory Probab Appl,2009,53(3):443466.12 HAN D,TSUNG F G,XIAN J G.On the optimality of Bayesian change-point detectionJ.AnnStatist,2017,45(4):13751402.13 LORDEN G.Procedures for reacting to a change in distributionJ.Ann Math Statist,1971,42(6):18971908.14 POLLAK M.Optimal detection of a change in distributionJ.Ann Statist,1985,13(1):206227.15 MOUSTAKIDES G V.Optimal stopping times for detecting changes in distributionsJ.Ann Statist,1986,14(4):13791387.16 POLUNCHENKO A S,TARTAKOVSKY A G.On optimality of the Shiryaev-Roberts procedure fordetecting a change in distributionJ.Ann Statist,2010,38(6):34453457.17 JOHNSON P,MORIARTY J,PESKIR G.Detecting changes in real-time data:a users guide tooptimal detectionJ.Philos Trans Roy Soc A,2017,375(2100):20160298(16 pages).286Chinese Journal of Applied Probability and StatisticsVol.4018 HAN D,TSUNG F G,XIAN J G,et al.Optimal