# ARL Estimation of the Control Chart of Log Likelihood Ratios’ Sum for Markov Sequence

Authors: Yi Guo; Lei Gao; Yan Zhu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

To evaluate the surveillance performance of a control chart with the charting statistic of the sum of log likelihood ratios in the statistical process control (SPC), in this paper, we give the proof procedure based on Markov chains for the asymptotic estimation of the average run length (ARL) for this kind of chart. The out-of-controlARL1 is approximately equal to 1 for any fixed in-control ARL0 with a negative control limit. By the equivalence between limit distribution of a sum and that of a suprema sum of Markov chain, we derive the estimation of ARL1 with a large enough positive control limit. Numerical experiments are conducted to confirm our results.


---

## Body

## 1. Introduction

The main aim of SPC is to detect an abrupt change in the observation of time series as soon as possible after the change has happened. The study, found in [1], is the first to show the design of the control chart for quickly detecting possible changes in the underlying process. Subsequently, a great number of control charts have been proposed and come into a wider use in many fields, such as environmental control [2, 3], biostatistics [4, 5], clinical medicine [6, 7], economics and finance [8], industrial quality and process control [9, 10], process monitoring [11–16], public health [7, 14, 16], and social network [17].Obviously, the research on constructing various control charts for surveillance has never stopped since Shewhart presented this method. The existing theoretical studies in statistical monitoring, on the whole, can be classified into three areas. The first category is the optimal economic or economic-statistical design, where, in most cases, the net sum of all costs is minimized [18–21]. The ideas of the second category are the choice of the statistical parameters of a control chart to minimize the out-of-control ARL1 for a given in-control ARL0 or a probability of false alarm, and it is named as the optimal statistical design [16, 22–25]. Recently, the theoretical approximation to ARL was proposed in [26]. Detecting changes in distribution of the optimal control charts is the last category, which can be regarded as a kind of optimal stopping time [27–29]. This metric for defining optimality is based on that it has smallest out-of-control ARL1 among all control charts with either a given probability of a false alarm no greater than a preset level, or a given false alarm rate no less than a given value. So, this more mathematical area is thus related to statistical design. In the following argument, we will focus on the third type of these bibliographies mentioned above.Consider the Gaussian observation sequenceX0,X1,X2,…, whose distribution may change at time τ≥1. Let p0x0,x1,x2,…,xnn<τ and pτxτ,xτ+1,…n≥τ be the prechange probability density function and the postchange probability density function of X0,X1,X2,…, respectively. Denote the postchange joint probability distribution, expectation, and variance by ℙτ,Eτ,andDτ, respectively. Especially, when the change time τ=∞, we suppose that a change never occurs. Frisén [30] showed that there exists a positive value c such that the control chart with the charting statistic of the sum of log likelihood ratios (SLR),(1)TSLRc=minn:∑k=1nXk−μ2≥c,n≥1,is optimal in the sense,(2)InfT:ℙ0T≥τ≥1−αE1T=E1TSLRc,when the change is the case of a shift in the mean of X0,X1,X2,…, where T denotes the control chart test, τ=1 is the change-point time, and c>0 is the constant control limit such that ℙ0TSLRc≥τ=1−α>0. Although the optimality of TSLR has been proved in [30], there were few surveys and bibliographies which considered the performance of the control chart TSLRfor monitoring the change point in the process.Therefore, in this paper, we regard the ARL as the criterion of optimality of a control chart. This is because the ARL is the connection among itself, control limit, and statistical properties of the observation sequenceX0,X1,X2,…. In Section 2, we prove that the out-of-control ARL1 is approximately equal to 1 for a given ARL0 as the control limit c is negative. In Section 3, we apply the equivalence between limit distribution of a sum and that of a suprema sum of Markov chain to obtain the estimation of ARL1 when the control limit is some large enough positive constant. Finally, we conduct some numerical experiments to verify our theoretical analysis in Section 4.


## 2. Estimation ofARL1 with a Negative Control Limit

In this section, we consider a constant control limitexpc to construct a control chart TZc and estimate the corresponding in-control ARL0 and out-of-control ARL1. Let the observations Xt0,Xt1,Xt2,… be a time-homogeneous Markov chain with the discrete state space S=s1,s2,…. Here, we consider only detecting the change at the initial time τ = 1, and the Markov chain Xtk,k≥0 is positive recurrence with the prechange transition probability p0y|x and the postchange transition probability p1y|x. For convenience, we use Xk instead of Xtk for k≥0. Similar to the notations defined in Section 1, we use ℙ0,E0, and D0 to denote, respectively, the prechange joint probability distribution, expectation, and variance of X0,X1,X2,….For ease of the subsequent analysis processing, we choose a large enough positive numberN to cut out the first N+1 terms of the sequence X0,X1,X2,…. In other words, the sequence X0,X1,X2,…,XN tends to X0,X1,X2,… when N goes to infinity. The optimality of the control chart TZc for the Markov chain X0,X1,X2,…,XN appeared in [31]. Now, we define the charting statistics as(3)Yk=∏j=1kp1Xj|Xj−1p0Xj|Xj−1,1≤k≤N.LetZj=lnp1Xj|Xj−1/p0Xj|Xj−1 for 1≤j≤N; then, lnYk=∑j=1kZj for 1≤k≤N. For any state si, let τki be the time of kth visit of state si and Nni be the number of times for visiting si from time 0 to time n. The cumulative sums of Zk and Zk−E1Zk on the kth block of time are, respectively, defined by(4)ηki=∑l=τk−1i+1τkiZl,η˜ki=∑l=τk−1i+1τkiZl−E1Zl,for k=1,2,…,Nni and τ01=0. Then, both η1,…,ηNni and η˜1,…,η˜Nni are sequences of independent and identically distributed (i.i.d.) random variables.Throughout this paper, we assume that(i)
ℙ0sj|si=0 if and only if ℙ1sj|si=0, as well as ℙ1sj|si/ℙ0sj|si has no atom with respect to ℙ0 for si,sj∈S. Here, we define 0/0 = 1.(ii)
supsi∈SE0Z12|X0=si<+∞.The sum ofZ1,…,ZN is written by SN=∑k=1NZk. Set μi,j=Ejη1i/Eτ1i, μ˜i,j=Ejη˜1i/Eτ1i, and σi,j=Ejη1i−Ejη1i2/Eτ1i and σ˜i,1=E1η˜1i−E1η˜1i2/Eτ1i. Moreover, for j=0,1, let(5)μ¯j=mini∈1,2,…μi,j,μ¯j=maxi∈1,2,…μi,j,σ¯j=mini∈1,2,…σi,j,σ¯j=maxi∈1,2,…σi,j,(6)μ˜¯1=maxi∈1,2,…μ˜i,1,σ˜¯1=maxi∈1,2,…σ˜i,1.Then, for largeN, we have(7)Ej∑k=1Nniηki=nμi,j1+o1,Dj∑k=1Nniηki=nσi,j21+o1.Now, we define a control chartTZc in the following with the charting statistics of the sum of log likelihood ratios for detecting the change in distribution of the Markov sequence X0,X1,…,XN:(8)TZc=minn:Yn≥expc,1≤n≤N=minn:∑k=1nZk≥c,1≤n≤N,for some constant c.Now, we are ready to estimateARL1. Based on Section 3 presented in [30], ARL0 is the average run length until an alarm is signaled, so ARL0 and E0TZc are equivalent. Consequently, we use the estimator of E0TZc to substitute ARL0 in the subsequent analysis. The main result is proposed in the following theorem.Theorem 1.
LetXk,k≥0 be a time-homogeneous Markov chain satisfying conditions (i) and (ii). Then, for a given ARL0=L and 1<ARL0<N+1, there exists a negative number c∗=c∗N,L such that(9)ARL0TZc∗=E0TZc∗=L,(10)ARL1TZc∗=E1TZc∗=1+o1,as N⟶∞.Proof.
Choose the control limitc1=c1N=μ¯0N and note that(11)E0η1i|X0=si=E0∑n=1NIτ1=n∑k=1NZk|X0=si=E0∑k=1∞Iτ1≥kZk|X0=si=∑k=1∞E0ζX0,⋯,Xk−1Zk|X0=si,where Iτ1≥k=ζX0,…,Xk−1∈ℱk−1. Let E0,si=E0ζX0,…,Xk−1Zk|X0=si. Using the law of total expectation and Markov property, we obtain(12)E0,siζX0,…,Xk−1Zk=E0,siE0,siζX0,…,Xk−1Zk|ℱk−1=E0,siζX0,…,Xk−1E0,siZk|Xk−1.
Sincelnx is a concave function, by Jensen’s inequality, we have(13)E0,siZk|Xk−1=E0,silnp1Xk|Xk−1p0Xk|Xk−1|Xk−1≤lnE0,sip1Xk|Xk−1p0Xk|Xk−1|Xk−1=0.
Substituting (13) into (12) and combining (11), we can get that μi,0<0 for any i. Similarly, we can prove μi,1>0 for any i. Hence, μ¯0,μ¯0<0 and μ¯1,μ¯1>0; then, limN⟶∞c1N=−∞. Letm˜=ε1N for some ε1<1, where x denotes the integer part of x. Then,(14)E0TZc1=ℙ0TZc1>0+∑m=1Nℙ0TZc1>m=1+∑m=1m˜−1ℙ0TZc1>m+∑m=m˜Nℙ0TZc1>m≤1+∑m=1m˜−1ℙ0TZc1>m+N−m˜+1ℙ0TZc1>m˜.
The total probability formula tells us that(15)ℙ0TZc1>m˜=ℙ0max1≤k≤m˜Sk≤c1≤ℙ0Sm˜≤c1=∑i=1∞ℙ0X0=siℙ0sm˜≤c1|X0=si.
Equations (4) and (7) yield that(16)ℙ0sm˜≤c1|X0=si=ℙ0∑k=1Nm˜iηki≤c1−∑k=τNm˜ii+1Nm˜iZk|X0=si=ℙ0−∑k=1Nm˜iηki−E0∑k=1Nm˜iηkiD0∑k=1Nm˜iηki≥−c1+m˜μi,01+o1σi,0m˜+∑k=τNm˜ii+1Nm˜iZkσi,0m˜|X0=si.
Note thatm˜=ε1N and ∑k=τNm˜ii+1Nm˜iZk/σi,0m˜ almost everywhere converges to 0 as N⟶∞; therefore,(17)−c1+m˜μi,01+o1σi,0m˜+∑k=τNm˜ii+1Nm˜iZkσi,0m˜=−μ¯0+ε1μi,0σi,0ε1N+o1.
Notice that, for a largex, the relationship between probability distribution function Φx and density function px of standard normal distribution is(18)1−Φx=pxx1+o1.
Combining (16)–(18) and the central limit theorem of Markov chain (see [32]), we can get that(19)ℙ0Sm˜≤c1|X0=si=1−Φ−μ¯0+ε1μi,0σi,0ε1N+o11+o1=σi,0ε11+o12πN−μ¯0+ε1μi,0exp−−μ¯0+ε1μi,022σi,02ε1N≤σ¯0ε11+o12πNμ¯0ε1−1exp−μ¯02ε1−122σ¯02ε1N.
Put (19) into (15) and combine ∑i=1∞ℙ0X0=si=1 to yield that(20)ℙ0TZc1>m˜≤σ¯0ε11+o12πNμ¯0ε1−1exp−μ¯02ε1−122σ¯02ε1N.
For1≤m≤m˜−1, by the Markov inequality and m˜=ε1N, we have(21)∑m=1m˜−1ℙ0TZc1>m=∑m=1m˜−1ℙ0Z1≤c1,…,∑k=1mZk≤c1≤m˜−1ℙ0Z1≤c1≤m˜ℙ0Z1≥−μ0N≤m˜E0,siZ12μ02N2=ε1E0,siZ12μ02N.
Inequality (21) implies that the value of ∑m=1m˜−1ℙ0TZc1>m tends to 0 as N⟶∞. Put (20) and (21) into (14); then, there exists some constant L such that(22)E0TZc1≤1+N−m˜+1σ¯0ε11+o12πNμ¯0ε1−1exp−μ¯02ε1−122σ¯02ε1N<L,for a large N.
Using Theorem 5.1.7 in [33], there exists a nonpositive number c2=c2N>c1N such that(23)E0TZc2>Lholds for a large enough N. Thus, we can choose a negative number c∗=c∗N satisfying c1<c∗<c2 and E0TZc∗=L.
Next, we prove (10). For any x>0, let c3=−μ¯0+xN. Similar to (20), we can get that(24)1≤E1TZc3=1+ℙ1TZc3>m≤1+∑m=1m˜−1ℙ1TZc3>m+N−m˜+1∑i=1∞ℙ1X0=siℙ1Sm˜≤c3|X0=si=1+o1+1+o1N−m˜+1Φ−μ¯0+xN+m˜μi,1σi,0m˜=1+o1+1+o1N−m˜+1σi,1m˜μ¯0+xN+m˜μi,1exp−μ¯0+xN+m˜μi,122σi,11m˜=1+o1+1+o11−ε1σ¯1ε1Nμ¯0+x+ε1μ¯12πexp−μ¯0+x+ε1μ¯122σ¯12N.
Note that the second and third terms on the right-hand side of the last inequality in (24) tends to 0 as N goes to infinity.
This completes the proof.


## 3. Estimation ofARL1 with a Positive Control Limit

In the subsequent discussion, we use the equivalence between limit distribution of a sum and that of a suprema sum of Markov chain to estimate the out-of-controlARL1 when the control limit c is a sufficiently large positive constant. The main result is presented in the following theorem.Theorem 2.
Assume thatXk,k≥0 is a homogeneous Markov chain. For any state si,i=1,2,… if(25)E1η1i2≤μ˜¯12+σ˜¯12<∞,then(26)c−clncμ¯1+1+o1σ¯1ε22πμ¯1lncexp−μ¯1c−clnc2σ¯12≤E1TZc≤c+clncμ¯1+σ¯11+o1c+clncε22πμ¯1clncexp−μ¯1clnc2σ¯12,for large N and c, where μ¯1,μ¯1,σ¯1,σ¯1 and μ˜¯1, σ˜¯1are defined in (5) and (6), respectively. The sign o⋅ denotes the infinitesimal of higher order and ε2:=expμ¯12/2σ¯12−1.Proof.
It follows from (8) that, for m≥1,(27)ℙ1TZc>m=ℙ1Z1≤c,Z1+Z2≤c,…,∑k=1mZk≤c=ℙ1max1≤k≤mSk≤c.
The estimation ofℙ1TZc>m is reduced to the estimation of ℙ1max1≤k≤mSk≤c. According to Theorem 2 in [34], we have the following conclusion:(28)limm⟶∞ℙ1max1≤k≤mSk−E1Sm≤xm=limm⟶∞ℙ1Sm−E1Sm≤xm.
Then, we use (28) to calculate the value of ℙ1TZc>m. Let c^=c−E1Sm=xm, where x∈ℝ and ℝ denotes the real number field. When m becomes sufficiently large, by (5), (27), and (28), we have(29)ℙ1TZc>m=ℙ1max1≤k≤mSk≤c=ℙ1Sm−E1Sm≤c^1+o1=ℙ1Sm−E1SmD1Sm≤c−E1SmD1Sm1+o1=Φc−mμi,1mσi,11+o1.
Letm^1=c+clnc/μi,1, and we have(30)E1TZc=∑m=1∞ℙ1TZc>m=∑m=1m^1ℙ1TZc>m+∑m=m^1+1∞ℙ1TZc>m=∑m=1m^1ℙ1TZc>m+1+o1∑m=m^1+1∞Φc−mμi,1mσi,1=∑m=1m^1ℙ1TZc>m+1+o1∑k=1∞Φc−m^1+kμi,1σi,1m^1+k,for the large enough m and c. When c goes to infinity, we deal with the second term on the right-hand side of (30) as follows:(31)Φc−m^1+kμi,1σi,1m^1+k=Φc−c/μi,1+clnc/μi,1+kμi,1σi,1c+clnc/μi,1+k=Φ−μi,1clnc+μi,1μi,1kσi,1c+clnc+μi,1k=1+o1σi,12πμi,1c+clnc+μi,1kclnc+μi,1kexp−μi,1clnc+μi,1k22σi,12c+clnc+μi,1k.
Note that, for a largec, we have(32)−μi,1clnc+μi,1k22σi,12c+clnc+μi,1k=−μi,12k2σi,12+μi,12kc−μi,1clnc−μi,12kclnc2σi,12c+clnc+μi,1k=−μi,12k2σi,12−μi,1clnc2σi,12+μi,1c2σi,121−cc+clnc+μi,1k=−μi,12k2σi,12−μi,1clnc2σi,12+oc.
We obtain the right-hand side of (30) as follows:(33)∑k=1∞Φc−m^1+kμi,1σi,1m^1+k≤σi,11+o1c+clnc2πμi,1clncexp−μi,1clnc2σi,12∑k=1∞exp−μi,12k2σi,12≤σi,11+o1c+clncε22πμi,1clncexp−μi,1clnc2σi,12,as c tends to infinity. Combining (30), (33), and ℙ1TZc>m≤1, we obtain(34)E1TZc=∑m=1m^1ℙ1TZc>m+σi,11+o1c+clncε22πμi,1clncexp−μi,1clnc2σi,12≤m^1+σ¯11+o1c+clncε22πμ¯1clncexp−μ¯1clnc2σ¯12≤c+clncμ¯1+σ¯11+o1c+clncε22πμ¯1clncexp−μ¯1clnc2σ¯12.
To prove the inequality on the left-hand side of (26), let m^2=c−clnc/μi,1, and c goes to infinity; then, we use (27) to yield that(35)E1TZc=∑m=1m^2ℙ1TZc>m+1+o1∑k=1∞Φc−m^2+kμi,1σi,1m^2+k=∑m=1m^2ℙ1max1≤k≤mSk−mμi,1σi,1m≤c−mμi,1σi,1m+1+o1∑k=1∞Φc−m^2+kμi,1σi,1m^2+k=∑m=1m^2G1c−mμi,1σi,1m+1+o1∑k=1∞Φc−m^2+kμi,1σi,1m^2+k,where G1x:=ℙ1max1≤k≤mSk−mμi,1/σi,1m≤xis the distribution function and m=1,2,…,m^2. Similar to the derivation of (33), let c tend to infinity; then, we obtain the estimation of the second term on the right-hand side of (35) as(36)∑k=1∞Φc−m^2+kμi,1σi,1m^2+k≥1+o1σ¯1ε22πμ¯1clncexp−μ¯1c−clnc2σ¯12.
For the first term on the right-hand side of (35), because the function c−mμi,1/σi,1m is monotonically decreasing in the interval 1,m^2 with respect to m and the distribution function G1x is monotonically nondecreasing in ℝ, we have(37)G1c−mμi,1σi,1m≥G1c−m^2μi,1σi,1m^2=G1μi,1clncσi,1c−clnc=G1μi,1lncσi,11−lnc/c≈1,for c⟶∞ and m∈1,m^2. By (35)–(37), we obtain(38)E1TZc≥m^2+1+o1σ¯1ε22πμ¯1clncexp−μ¯1c−clnc2σ¯12,for a large enough c. Combine (34) and (38) to yield (26). This completes the proof.


## 4. Numerical Experiment

In this section, we perform two numerical experiments to verify our theoretical results. In our first numerical experiment, letXk,k≥0 be a sequence of i.i.d. Gaussian random variables with the prechange and the postchange probability densities p0x=1/2πexp−x−μ02/2 and p1x=1/2πexp−x−μ12/2. It is assumed that the standard case of a shift in the mean of Xk,k≥0 from μ0 to μ1 is considered.According to the proof of Theorem1, the initial data is chosen as μ0=−1,μ1=100,andN=1000.Given different values of ARL0=250,370,500, we obtain the corresponding values of control limit c and ARL1, which are listed in Table 1.Table 1
Simulation values ofARL1 for N = 1000.
ARL0250370500ARL0251371501.1c−1.2760×106−1.8869×106−2.5488×106ARL1111These results suggest that the value ofE1TZc is equal to 1 with a negative control limit c and a given ARL0, which is predicted in Theorem 1.In the second experiment, we choosec=exp1−1/exp1+1N and N/100=1,5,10,50,100,500,1000. Let Xk,k≥0 be a homogeneous Poisson process with the prechange and the postchange parameters λ0 and λ1; then, the corresponding prechange and postchange transition probabilities are defined as(39)ℙrXk=j|Xk−1=i=λrΔtkj−ij−i!exp−λrt,0<i≤j,0,0≤j<i,where r=0,1 and iandj are arbitrary states from the state space S and Δtk=tk−tk−1 for k≥1.The results are obtained and presented in Table2, which show the ratio of E1TZc and c equals approximately 2.38 as N⟶∞. It implies that the value of E1TZc and the control limit c are the infinite of the same order, which is predicted by Theorem 2.Table 2
Ratios ofE1TZc and c with different choices of N.
N/1001510501005001000E1TZc/c2.38012.44822.38272.36622.40062.38532.3880



---

*Source: 6649949-2021-05-10.xml*