# Distributions of Patterns of Pair of Successes Separated by Failure Runs of Length at Leastk1 and at Most k2 Involving Markov Dependent Trials: GERT Approach

Authors: Kanwar Sen; Pooja Mohan; Manju Lata Agarwal
Journal: Journal of Quality and Reliability Engineering
 (2013)

---

## Abstract

We use the Graphical Evaluation and Review Technique (GERT) to obtain probability generating functions of the waiting time distributions of 1st, andmth nonoverlapping and overlapping occurrences of the pattern Λfk1,k2=SFF⋯F︸k1≤kf≤k2S(k1>0), involving homogenous Markov dependent trials. GERT besides providing visual picture of the system helps to analyze the system in a less inductive manner. Mean and variance of the waiting times of the occurrence of the patterns have also been obtained. Some earlier results existing in literature have been shown to be particular cases of these results.


---

## Body

## 1. Introduction

Probability generating functions of waiting time distributions of runs and patterns have been studied and utilized in various areas of statistics and applied probability, with applications to statistical quality control, ecology, epidemiology, quality management in health care sector, and biological science to name a few. A considerable amount of literature treating waiting time distributions have been generated, see Fu and Koutras [1], Aki et al. [2], Koutras [3], Antzoulakos [4], Aki and Hirano [5], Han and Hirano [6], Fu and Lou [7], and so forth. The books by Godbole and Papastavridis [8], Balakrishnan and Koutras [9], Fu and Lou [10] provide excellent information on past and current developments in this area.The probability generating function is very important for studying the properties of waiting time distributions of runs and patterns. Once a potentially problem-specific statistic involving runs and patterns has been defined, the task of deriving its distribution can be very complex and nontrivial. Traditionally, combinatorial methods were used to find the exact distributions for the numbers of runs and patterns. By using the theory of recurrent events, Feller [11] obtained the probability generating function for waiting time of a success run A=SS⋯S︸k of size k in a sequence of Bernoulli trials. Fu and Chang [12] developed general method based on the finite Markov chain imbedding technique for finding the mean and probability generating functions of waiting time distributions of compound patterns in a sequence of i.i.d. or Markov dependent multistate trials. Ge and Wang [13] studied the consecutive-k-out-of-n: F system involving Markov Dependence.Graphical Evaluation and Review Technique (GERT) has been a well-established technique applied in several areas. However, application of GERT in reliability studies has not been reported much. It is only recently that Cheng [14] analyzed reliability of fuzzy consecutive-k-out-of-n: F system using GERT. Agarwal et al. [15, 16], Agarwal & Mohan [17] and Mohan et al. [18] have also studied reliability of m-consecutive-k-out-of-n: F system and its various generalizations using GERT, and illustrated the efficiency of GERT in reliability analysis. Mohan et al. [19] studied waiting time distributions of 1st, and mth nonoverlapping and overlapping occurrences of the pattern Λk=SFF⋯F︸kS, involving Markov dependent trials, using GERT. In this paper, probability generating functions of the waiting time distributions of 1st, and mth nonoverlapping and overlapping occurrences of a pattern involving pair of successes separated by a run of failures of length at least k1 and at most k2, Λfk1,k2=SFF⋯F︸k1≤kf≤k2S(k1>0), involving Homogenous Markov Dependence, that is, probability that component i fails depends only upon the state of component (i-1) and not upon the state of the other components, (Ge and Wang [13]) have been studied using GERT. Mean and variance of the time of their occurrences can then be obtained easily. Some earlier results existing in literature have been shown to be particular cases.


## 2. Notations and Assumptions

Λ
f
k
1
,
k
2
=
S
F
F
⋯
F
︸
k
1
≤
k
f
≤
k
2
S: pair of successes separated by a run of failures of length at least k1 and at most k2, k1>0.
X
i: indicator random variable for state of trial i, Xi=0 or 1 according as trial i is success or failure.
p
0
,
q
0: Pr{X1=0}; q0=1-p0
p
1
,
q
1: Pr{Xi=0∣Xi-1=0}, probability that trial i is a success given that preceding trial (i-1) is also a success, for i=2,3,…;q1=1-p1.
p
2
,
q
2: Pr{Xi=0∣Xi-1=1}, probability that trial i is a success given that preceding trial (i-1) is a failure, for i=2,3,…;q2=1-p2.


## 3. Brief Description of GERT and Definitions

GERT is a procedure for the analysis of stochastic networks having logical nodes (or events) and directed branches (or activities). It combines the disciplines of flow graph theory, MGF (Moment Generating Function), and PERT (Project Evaluation and Review Technique) to obtain a solution to stochastic networks having logical nodes and directed branches. The nodes can be interpreted as the states of the system and directed branches represent transitions from one state to another. A branch has the probability that the activity associated with it will be performed. Other parameters describe the activities represented by the branches.A GERT network in general contains one of the following two types oflogical nodes (Figure 1):(a)
nodes withExclusive-Or input function and Deterministic output function and(b)
nodes withExclusive-Or input function and Probabilistic output function.Type of GERT nodes.
(a)
Deterministic output
(b)
Probabilistic outputExclusive-Or Input. The node is realized when any arc leading into it is realized. However, one and only one of the arcs can be realized at a given time.Deterministic Output. All arcs emanating from the node are taken if the node is realized.Probabilistic Output. Exactly one arc emanating from the node is taken if the node is realized.In this paper type (b) nodes are used.The transmittance of an arc in a GERT network, that is, the generating function of the waiting time for the occurrence of required system state is the correspondingW-function. It is used to obtain the information of a relationship, which exists between the nodes.If we defineW(s∣r), as the conditional W function associated with a network when the branches tagged with a z are taken r times, then the equivalent W generating function can be written as follows:
(1)W(s,z)=∑r=0∞W(s∣r)zr.
The function W(0,z) is the generating function of the waiting time for the network realization.Mason’s Rule (Whitehouse [20], pp. 168–172). In an open flow graph, write down the product of transmittances along each path from the independent to the dependent variable. Multiply its transmittance by the sum of the nontouching loops to that path. Sum these modified path transmittances and divide by the sum of all the loops in the open flow graph yielding transmittance T as follows:
(2)T=[∑(path*∑nontouchingloops)]∑loops,
where
(3)∑loops=1-(∑firstorderloops)+(∑secondorderloops)-⋯∑nontouchingloops=1-(∑firstordernontouchingloops)+(∑secondordernontouchingloops)-(∑thirdordernontouchingloops)+⋯For more necessary details about GERT, one can see Whitehouse [20], Cheng [14] and Agarwal et al. [15].


## 4. Waiting Time Distribution of the PatternΛfk1,k2

Theorem 1.
W
S
F
F
⋯
F
︸
k
1
≤
k
f
≤
k
2
S
(
0
,
z
), the probability generating function for the waiting time distribution of the 1st occurrence of the pattern Λfk1,k2 involving Homogenous Markov Dependence is given by
(4)WSFF⋯F︸k1≤kf≤k2S(0,z)=(q0p2z2+p0z(1-q2z))×(q1p2q2k1-1zk1+1(1-(q2z)k2-k1+1))×((1-q2z)(1-q2z-p1z-q1p2z2+q2p1z2-q1p2q2k2zk2+2+q1p2q2k1-1zk1+1))-1.
Then,
(5)E[W(Λfk1,k2)]=E[Λfk1,k2minimumnumberoftrialsrequiredtoobtainthepatternΛfk1,k2]=q2(q1+p2)+q1q2k1(q0+p2)(1-q2k2-k1+1)q1p2q2k1(1-q2k2-k1+1),(6)Var[W(Λfk1,k2)]=d2WSFF⋯F︸k1≤kf≤k2S(0,z)dz2|z=1Var[W(Λfk1,k2)]=+E[W(Λfk1,k2)]-(E[W(Λfk1,k2)])2.The GERT network for this pattern is represented by Figure2 where each node represents a specific state as described below:S: initial node1A: a trial resulting in failure0i: a trial resulting in success corresponding to beginning of the ith occurrence of the pattern Λfk1,k2, i=1,2,…m1: a component is in failed state preceded by working componentj: jth contiguous failed trial preceded by a success trial, j=2,…,k1-1,k1,k1+1,…,k2,k2+10i: ith occurrence of the required pattern, i=1,2,…,m.Figure 2
GERT network representing 1st occurrence of the patternΛfk1,k2=SFF⋯F︸k1≤kf≤k2S.There are in allk2+5 nodes designated as S,1A,01,1,2,…,k1-1,k1,k1+1,…,k2-1,k2,k2+1 and 01 representing specific states of the system, that is, a sequence of homogenous Markov dependent trials. GERT network can be summarized as follows. If the first trial results in failure then state 1A is reached from S with conditional probability q0 otherwise state 01 with conditional probability p0. Further, if the preceding trial is failure (state 1A) followed by a contiguous success trial then state 01 is reached from state 1A with conditional probability p2 otherwise it continues to move in state 1A with conditional probability q2. State 01 represents first occurrence of a success trial (may or may not be preceded by failed trials) and if next contiguous trial(s) is (are) also success then it continues to move in state 01 with conditional probability p1 otherwise it moves in state 1 with conditional probability q1. Again if the next contiguous trial results in failure then system state 2 occurs with conditional probability q2 otherwise state 01 with conditional probability p2. Similar procedure is followed till k1 contiguous failed trials occur preceded by a success trial. Now, if the next contiguous trial is failure then state k1+1 is reached with conditional probability q2 otherwise state 01, first occurrence of required pattern. However, if the system is in state k1+1 and next contiguous trial is failure system moves to state k1+2 with conditional probability q2. Again a similar procedure is followed till node k2. However, if there occur k2-k1+1 contiguous failed trials after state k1 then the system moves to node k2+1 and continues to move in that state until a success trial occurs at which it moves to state 01 and again a similar procedure is followed for the remaining trials till state 01, first occurrence of the required pattern. Details on the derivation of the theorem are given in the appendix.Theorem 2.
W
S
F
F
⋯
F
︸
k
1
≤
k
f
≤
k
2
S
n
o
(
0
,
z
)
m, the probability generating function for the waiting time distribution of the mth nonoverlapping occurrence of the pattern Λfk1,k2 involving Homogenous Markov Dependence is given by
(7)WSFF⋯F︸k1≤kf≤k2Sno(0,z)m=(q0p2z2+p0z(1-q2z))×(p2q1q2k1-1zk1+1{1-(q2z)k2-k1+1})m×(p1z(1-q2z)+q1p2z2)m-1(1-q2z)-m×(1-q2z-p1z+q2p1z2-q1p2z2=(p0z)+q1p2q2k1-1zk1+1-q1p2q2k2zk2+2)-m.
Then,
(8)E[Wno(Λfk1,k2)]=E[Λfk1,k2minimumnumberoftrialsrequiredtoobtainthemthnonoverlappingoccurrenceofpatternΛfk1,k2]=q1q2k1(1-q2k2-k1+1)×(p1-p0+m(q1+p2))+mq2(q1+p2)×(q1p2q2k1(1-q2k2-k1+1))-1,
and Var[Wno(Λfk1,k2)] can be obtained by applying (6).The GERT network form=2 (say) nonoverlapping occurrence of the pattern Λfk1,k2 is represented by Figure 3. Each node represents a specific state as described earlier in Figure 2.Figure 3
GERT network representing themth (m=2, here) nonoverlapping occurrence of the pattern Λfk1,k2=SFF⋯F︸k1≤kf≤k2S.Theorem 3.
W
S
F
F
⋯
F
︸
k
1
≤
k
f
≤
k
2
S
o
(
0
,
z
)
m, the probability generating function for the waiting time distribution of the mth overlapping occurrence of the pattern Λfk1,k2 involving Homogenous Markov Dependence is given by
(9)WSFF⋯F︸k1≤kf≤k2So(0,z)m=(q0p2z2+p0z(1-q2z))×(q1p2q2k1-1zk1+1{1-(q2z)k2-k1+1})m×((1-q2z)(1-q2z-p1z-q1p2z2+q2p1z2-q1p2q2k2zk2+2+q1p2q2k1-1zk1+1))-m.
Then,
(10)E[Wo(Λfk1,k2)]=E[Λfk1,k2minimumnumberoftrialsrequiredtoobtainthemthoverlappingoccurrenceofpatternΛfk1,k2]=q1q2k1(1-q2k2-k1+1)(q0+p2)+mq2(q1+p2)q1p2q2k1(1-q2k2-k1+1).
and Var[Wo(Λfk1,k2)] can be obtained by applying  (6).The GERT network formth (m=2, say), overlapping occurrence of the pattern Λfk1,k2 is represented by Figure 4. Each node represents a specific state as described earlier in Figure 2.Figure 4
GERT network representing themth (m=2, here) overlapping occurrence of the pattern Λfk1,k2=SFF⋯F︸k1≤kf≤k2S.Particular Cases. (i) For k1=kf=k2=k-2, p0=p1=p2=p, and q0=q1=q2=q, in the pattern Λfk1,k2, that is, for a run of at most k-2 failures bounded by successes, the probability generating function becomes
(11)WSFF⋯F︸k-2S(0,z)=(pz)2(1-(qz)k-1)(1-qz)(1-z+(pz(1-(qz)k-1))),
verifying the results of Koutras [3, Theorem 3.2].(ii) Ifk1=1, kf=k2=k, that is, pair of successes are separated by a run of failures of length at least one and at most k, that is, SFF⋯F︸1≤kS then (4), (7), and (9), respectively, become
(12)WSFF⋯F︸1≤kS(0,z)=(q0p2z2+p0z(1-q2z))(p2q1z2(1-(q2z)k))(1-q2z)(1-q2z-p1z+q2p1z2-q1p2q2kzk+2).WSFF⋯F︸1≤kSno=(q0p2z2+p0z(1-q2z))(q1p2z2+p1z(1-q2z))m-1×(q1p2z2(1-(q2z)k))m(1-q2z)-m×(1-p1z-q2z+p1q2z2-p2q1q2kzk+2)-m.WSFF⋯F︸1≤kSo(0,z)=(q0p2z2+p0z(1-q2z))(p2q1z2(1-(q2z)k))m(1-q2z)(1-q2z-p1z+q2p1z2-p2q1q2kzk+2)m.(iii) Ifk1=k and k2→∞, then it reduces to the pattern Λ≥k=SFF⋯F︸≥kS, that is,
(13)WSFF⋯F︸≥kS(0,z)=(q0p2z2+p0z(1-q2z))(p2q1q2k-1zk+1)×((1-q2z)(-q1p2z2(1-(q2z)k-1)1-q2z-p1z+q2p1z2-q1p2z2(1-(q2z)k-1)))-1.(iv) Ifk1=kf=k2=k,then (4), (7), (9) reduce to the results of Mohan et al. [19], that is,
(14)WSFF⋯F︸kS(0,z)=(q0p2z2+p0z(1-q2z))(q1p2q2k-1zk+1)×(1-q2z-p1z-p2q1z2+p1q2z2-q1p2q2kzk+2q0p2z2+q1p2q2k-1zk+1)-1,WSFF⋯F︸kSno(0,z)m=(q0p2z2+p0z(1-q2z))(p2q1q2k-1zk+1)m×[p1z(1-q2z)+p2q1z2]m-1×[1-q2z-p1z-q1p2z2+q2p1z2-q1p2q2kzk+2+q1p2q2k-1zk+1]-m,WSFF⋯F︸kSo(0,z)m=(q0p2z2+p0z(1-q2z))(p2q1q2k-1zk+1)m(1-q2z)m-1×(1-q2z-p1z-q1p2z2+q2p1z2-q1p2q2kzk+2+q1p2q2k-1zk+1)-m.


## 5. Conclusion

In this paper we proposed Graphical Evaluation and Review Technique (GERT) to study probability generating functions of the waiting time distributions of1st, and mth nonoverlapping and overlapping occurrences of the pattern Λfk1,k2=SFF⋯F︸k1≤kf≤k2S(k1>0), involving homogenous Markov dependent trials. We have also demonstrated the flexibility and usefulness of our approach by validating some earlier results existing in literature as particular cases of these results.



---

*Source: 494976-2013-06-05.xml*