STATIONARY DISTRIBUTIONS FOR THE SUPERPOSITION OF MARKOV RENEWAL PROCESSES Department C. Y. Teresa Lam of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report No. 90-23 September 1990

Stationary Distributions for the Superposition of Markov Renewal Processes By C. Y. Teresa Lam* The University of Michigan This paper studies the steady state behavior of the superposition of p independent Markov renewal processes. The number of Markov renewal processes, p, is fixed, and we are interested in deriving the steady state behavior of the superposed process at the times of occurrence of events. In particular, we define the discrete superposition remaining and current life processes. The stationary distributions and related steady state properties of these processes are given. These results are applied to study both queueing and reliability problems. 1. Introduction and Summary. Let (Xi,Ti) = {Xi,nTin; n E {O, 1, 2,...}}, i = 1,2,...,p, be p > 2 independent stochastic processes. For each n E KV = {0, 1,2,...} and i E S = {1,2,...,p}, Xi,,n is a random variable taking values in a countable set &i, and T1,n is a random variable taking value in 32+ = [0,oo) such that 0 = Ti,o < Tijl < Ti,2 <.... For each i E 5, the stochastic process (Xi, T) = {Xin, Ti,; n E A/} is said to be a Markov renewal process with state space i provided that for all n E A/, vi,(i E i and t E A+, (Xi,n-+l = i Ti,n+l - Tin < t I Xi,o... Xi,n = i; Tio,...,T,n) *Research Supported in part by a fellowship from Horace H. Rackham School of Graduate Studies, The University of Michigan. AMS 1980 subject classifications. Primary 60K10, 6K15,6 60K20, 60K5, 90B22, 90B25; secondary 60G10. Key words and phrases. Discrete superposition remaining and current life processes, stationary distribution, superposition of Markov renewal processes, queueing networks, reliability problems. 1

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 2 = P(Xin+l =,Ti,n+l - Ti,n t Xn = v) = Qi(i,i,t) (1.1) independent of n. The family of probabilities Qi = {Qi(vi,(it);tvi( E,it E R+} is called a semi-Markov kernel of the ith process. Suppose that there are p > 2 independent Markov renewal processes in operations simultaneously. Consider the sequence of events formed by superposing the individual processes. Assume that concurrent events cannot occur with positive probability in the superposed process. Hence, at the time when an event occurs in the superposition process, only one of the process, say process i, moves from one state to another state and the process is semi-regenerate. This means that process i probabilistically starts over with initial conditions depending only on the state of the process at that time. In addition, the other processes have age D1,..., Di-1, Di+i,..., Dp and are in states Eli,..., Ep respectively. Dj s and Ej s are all random variables. Let Tn > 0 be the time of occurrence of the nth event in the superposed process. Let ~ = 1 x... x p, Si = {1,2,..., i - 1, i+ 1,..,p}, ti = {s:s E Ri'-' x {0} x Rpti} and i = UP _li. Define a stochastic process {Xn; n E AJ} such that Xn = (Sn,Rn) where Sn = (Sl,n, - - Spn), and Rn = (Rl,n,... Rp,n) = (Rl,n,.. Ri-l,n O, Ri+l,n,.., Rp,n) if the nth event of the superposed process comes from the ith component process. For j E Si, Rj,n is the remaining life of the jth component process at time Tn and this component process is in state Sjn E j. Also, the ith component process moves to state Si, at time Tn and define Ri,n = 0. Let us call {Xn; n E Jt} the discrete superposition remaining life process (DSRLP). The state space of this process is given by T = S x t and denote the associated a-algebra by Similarly, we can define a stochastic process {Yn; n E AJ} such that Yn = (SnCn), where

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 3 Sn = (,n,. * * Sp,n) and Cn = (Cl,n * * * v Cp,n) = (Cl,n * * * X Ci-l,n, 0, Ci+l,n * * * X Cp,n) if the nth event of the superposed process comes from the ith component process and this ith process moves to state Sin. For j E S, Cj,n is the current life of the jth component process at time Tn and this component process is in state Sj,n E Ej. Note that Ci,n is the current life of the ith process at time Tn and it is equal to zero. Let us call {Yn; n E.A} the discrete superposition current life process (DSCLP). Again, the state space of the process is given by T = ~ x A. In the case when | ~II =1 2 1=... =1 Sp 1= 1, DSRLP and DSCLP reduce respectively to the remaining life process {Rn; n E AJ} and the current life process {Cn; n G AJ} of the superposition of p independent renewal processes studied in Lam (1990a). When p = 2, DSCLP is closely related to the stochastic process {1Zn,2 Zn,In,Vn, U; n E n} presented in Cherry (1972), Cherry and Disney (1983). In this paper, we show that both DSRLP and DSCLP are Markov chains. Under certain regularity conditions on the individual component Markov renewal processes, DSRLP and DSCLP have a common unique stationary distribution II. DSRLP and DSCLP are useful in characterizing the steady state behavior of the superposition process at the times of occurrence of events. The continuous time properties of the superposed process are presented in Lam (1990b). This paper is organized as follows: Preliminaries and notations are given in Section 2. In Section 3, we derive the stationary distributions and related steady state properties of DSRLP and DSCLP. These results are applied to study individual blocking probability of queueing systems with superposition semi-Markovian arrivals, and system availability of a device with components connected both in parallel and in series. 2. Preliminaries and Notations. In this section, we present some definitions and results of Markov renewal theory from the literature which are useful in establishing the characteristics of DSRLP and DSCLP. In addition, we describe the assumptions which are made throughout the rest of the paper. The following definitions are adopted from Cherry and Disney (1983).

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 4 Definition 2.1. For i E S, the Markov renewal process (Xi, Ti) is said to be conservative if P(supTi < o) =0. (2.1) Definition 2.2. For i E S, define the random process Mi(t) associated with the Markov renewal process (Xi,Ti) by Mi(O) = 0 and Mi(t) = n for Ti,, < t < Ti,n+l. The process (Xi,Ti) is said to be regular if ~(Mi(t)) < oo for all t < oo. (2.2) Definition 2.3. For i E S, let Mi,,, (t) be the random process which counts the number of entrances of the Markov renewal process (Xi,Ti) to state ei E ~i during the interval [0, t) including, if applicable, the initial state at time Ti,o = O. The Markov renewal process (Xi, Ti) is said to be normal if, regardless of initial state, ~(Mi,ei(t)) < oo for allt E [0,oo). (2.3) The implications of the definitions above are discussed in Cherry and Disney (1983). In this paper, we exclude conditions which could cause non-regularities and, in particular, we assume that instantaneous transitions are impossible, that is, Q2(vi,i, 0) = 0 for all vi, i E Si and i E S. For all component processes, with probability one a non-zero time is spent between transitions. Furthermore, we assume that all the Markov renewal processes to be studied here are conservative, normal and regular. Let Qi(vi,(i) = Qi(vi,(i,oo) and Qi = {Qi(vi,(i);vi,(i E i}. Consider the Markov chain XY induced by Qi. By the usual decomposition theorems, we can partition the Markov chain Xi into disjoint classes of recurrent and transient cases. To study the steady state behavior of the superposed process, it is sufficient to consider component processes whose imbedded Markov chains are irreducible recurrent. Throughout the remainder of this paper, we shall assume that Xi is irreducible recurrent non-null and aperiodic for all i E S. Let Ai be the stationary distribution of Xi, i.e., for all (i E i, E Ai(vi)Qi(i,i) = Ai((i) and E A(v) =. (2.4) vi ES vi EWi

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 5 For each i E S and vi E ~i, let Fi(vi,t) =,iEe Qi(vi, i,t). Fi(vi,t) is the probability distribution of the sojourn time of the ith process in state vi E ri. Assume the mean sojourn time in vi is mi(vi) = fo~~(1 - Fi(vi, t)) dt < oo. Let pi = EZlEi, Ai(vi)mi(vi). We assume that all sojourn time probability distributions are absolutely continuous with respect to the Lebesgue measure and the probability density function is given by fi(vi, ). Furthermore, for each i E S, v-, (i E i, the semi-Markov kernel Qi(vi, (i, t) is also an absolutely continuous function in t E R+, i.e., the function t -) Qi(vi, t) has a derivative equal to qi(vi, (i,t) almost everywhere. The absolute continuity of the functions t -+ Qi(vi,i, t) ensure that simultaneous occurrence of events in the superposed process has probability zero. For each i E 5, let {Xi(t);t E R+} be the semi-Markov process associated with the Markov renewal process (Xi,Ti). From Definition (2.2), Mi(t) is the number of transitions in the ith process during the time interval (O,t]. Write Vi+(t) = TM,(t)+l - t and Vi-(t) = t - TM(t). Vi+ is therefore the time until the next jump and Vi- is the time since the last jump. Both are defined with respect to epoch t, and they are well defined for all t E R+ because all the component processes are conservative. {Xi(t), V+(t);t E R+} and {Xi(t), V-(t); t E R+} are the continuous remaining and current life processes associated with the ith process. From Cinlar (1969), provided that the Markov chain Xi is irreducible recurrent, then lim P(Xi(t) = i3, Vi+(t) > z I Xi(O) = e) = lim P(Xi(t) = /3i,Vi(t) > z I Xi(O) = el) t —oo t —+oo - (/i) (1 - Fi(i, y)) dy. (2.5) For a detailed study of the stationary measures of the continuous remaining and current life processes for Markov renewal processes, see Pyke and Schaufele (1966). 3. Stationary Distributions of DSRLP and DSCLP. In this section, we will show that both DSRLP and DSCLP are Markov chains. Furthermore, the stationary distributions of these processes both exist and are unique. We first define some notations. Let e = (ei,...,ep), 3 = (i,...,/p) and I(B) be an indicator function such that I(B) = 1 whenever event B occurs and zero otherwise. Define the reduced state space T = E x @ where i = UP11'i and C Pi such that if s = (s=,..,si-,O,1si+l,...,) G i, then

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 6 1. sj S Sk V j, k E Si and j 7 k, 2. sj O V j E Si. For any n > 1, we can now derive P(Sn = 3,Ri,n = 0,0 < Rj,n < rj;j E Si | Sn-l = eRkn-1 = O,Ru,n-1 = Su;u E Sk, Xn-2,.. *,XO) where e,e3 6 ~, rj E 3?+, j E Si, sk = (sl,...,Sk-1,0,Sk+l,...,Sp) E iSk and i,k E S. Note that it is sufficient to consider sk E'k, this is because we have assumed that simultaneous occurrence of events in the superposed process has probability zero. By conditioning on 1. if i = k, Tn - Tn-i = x, or equivalently, Rj,n = sj - x for all j E Sk, 2. if i k, Rk,n = x, we have P(Sn =, Ri,n = 0,0 < Rj,n < rj;j E Si I Sn_1 = e, Rk,n-1 =, Ru,n-1 = su; u E Sk, Xn-2, * * *Xo) min su ]uEsk qk(ek,3k,x) [I(O < s - x < ru)I(/3- = eu)] dx if i = k uESk = j fk(ek,i + x)I(/k = ek)I(si = min su) Qiei(ei, ii) Jo~ek,8~ t = = uESk 1 - Fi(e-,si) x fI [I(0<sj-si <rj)I(/j =ej)]dx ifi k j ES$ nSk = P(Sn = P,Rn,i = 0,0 < Rn,j < rj;j E Si Sn-1 =e,Rn-l,k = O,,R-l, = su;u E Sk) = Px({3} x Ai I (e, sk)) (3.1) where Ai = {x = (xl,...,xil,O,xi+,,....,p) E Ti xj < rj,rj E R+,j E Si} and sk = (S,...,Sk-l,0,Sc+l,. Sp)E =k. For n > 1, e,03 E R, rj E i+, j E Si, and i E S, define P(Sn =,3,Rin = 0,0 < Rj,n < rj;j E Si | Sn-_ = e, Rk,n-l = 0, (3.2) Ru,n-1 = Su; U E SkXn-2,..,Xo) = 0

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 7 whenever Sk = (Sl,...,sk-1,0, k+l,...,Sp) E Jk\tk and k E S. DSRLP is therefore a Markov chain with state space T and stationary transition probabilities given in (3.1) and (3.2). From Breiman (1968), the nonempty set A E e is called closed for the Markov chain {Xn; n E Af} if for all (e,s) E A, P(Xn+i E A |Xn = (e,s)) = 1, i.e., it is almost surely not possible to leave the nonempty measurable set A. Furthermore, the chain is called indecomposable if there are no two disjoint closed sets A1, A2 E. For each i E S, the Markov chain Xi is assumed to be irreducible recurrent aperiodic in Section 2, this together with the regularity conditions on the sojourn time distributions and semi-Markov kernels ensure that the Markov chain {Xn; n E JV} with transition probabilities given by (3.1) and 3.2) is indecomposable. Theorem 3.1. DSRLP has a unique stationary distribution given by P(S = 3, Ri = 0,0 < Rj < rj;j E Si) = (I/) Ai(I) [J() j - Fj(jy))dy (3.3) where S = (S1,...., Sp), 1/t = EjP=1 1/y;, rj E R+, j E Si, i E S and P3 E. Proof. It is easily checked that E E P(S = -3,Ri = 0,0 < R < oo;j E S,) i=1 P3E -=, z(I/) A(iO) 1 [j7 1 (1 - Fj(ij-,y))dy] 1. (3.4) i=1 ]E~ j=l,j:i Equation (3.3) is therefore a probability measure on S. By definition a distribution II is stationary for the stochastic process {Xn; n E AV} if II(A)= /J P(X2 e A I X1 = (e, s)) I((e, ds)) (3.5) eE~ for all A E B. Since the Markov chain is indecomposable, whenever the stationary distribution exists, it is unique (see Breiman (1968)). For reason of symmetry, it is sufficient to consider the event A = {3} x Al and Al = {s = (O,52,...,p)E 1 i I j < rj,r j E R+,j E S1}. (3.6)

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 8 Then the theorem is equivalent to II({/3} x A1) = ( A/ 1(1J) I [ 1 ( - Fj(I3j,y))dy. (3.7) To show that (3.7) satisfies Equation (3.5), we substitute (3.7) into the right hand side of (3.5). Results follow after some tedious but straightforward calculations. The details are given in the Appendix. o Before the stationary distribution of DSCLP is given, we first define some notations. Let c; E + for all i E S. 1. For k E 5, let Uk C R. such that (sl,...,Sp) E Uk if and only if (a) (S1,... Sk-1, 0,k+,...,Sp) E k, (b) < sj + sk- min su < Cj for all j E Sk, u ESk (c) 0 < sj < cj for all j E Sk, (d) 0 < min su < Sk < min(sj + sk - min s), uESk jESk uESk 2. For k E S and i E Sk, let Wk,i C P+ such that (si,...,Sp) E Wk,i if and only if (a) (1,..., Sk-1,0, Ok+l,.., Sp) E'ik, (b) 0 < sj < cj for all j E Sk, (c) O < sj + Sk < cj for all j E Si n Sk, (d) 0 < Sk < Ck. Now, for any n > 1, e,/3 E C, cj E R+, j E Si, sk = (si,...,Sk-1,0, k+,...,Sp) E'k and i, k E S, we can derive P(Sn = /3, C,n = 0,0 < Cj,, < Cj;j E Si I Sn-1 = e, Ck,n-1 = O,Cu,n-1 = Su; u e Sk, Yn-2,...,Yo) by conditioning on

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 9 1. if i = k, T, - Tn-_ = sk - min su, or equivalently, C,,, = Sk and s, = min su, UESk uESk 2. if i / k, T, - Tn- = sk, or equivalently, Cn,k = k.This gives P(Sn = -, Ci,n = 0,0 < Cj,n < cj;j e Si I Sn-1 = e, Ck,n-1 C,- = s; u E Sk, Yn-2,..,Yo) oqk(ek,/3k,Sk- min s,) uESk j [(1 Fu +es k)s ) I(3u = eu) I(WUk) dSk if i k = y({/3} x B( F(eSkisk)) (3.8) where Bi = {x = (x1,...,x1,0,x4+i,..1.,xp) E, | x < Cj,C3 E I(,j W Sk } and if = (51,...,Sk-1,Sk+1,.,Sp) E ick. Again, for any n > 1, e,/3 E, cj E +, j E Si and i C S, define P(Sn = -3,Ci,n = 0,0 < Cj,n cj;j E Si | Sn-l = e Ck,n-1 = 0, (3.9) CU,n-1 = Su; u E Sk, Yn-2,.. Yo) = 0 whenever sk = (Si,...,Skl,0,k+,,...,Sp) E'Ak\kk and k E S. DSCLP is therefore a Markov chain with state space T and stationary transition probabilities given by (3.8) and (3.9). Just like DSRLP, the Markov chain {Yn;n > 1} is indecomposable. The stationary distribution of DSCLP is given in the theorem below.

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 10 Theorem 3.2. DSCLP has a unique stationary distribution given by P(S = /3,C = 0,0 < Cj < cj;j E Si) = (I/ i) () j [ ) (l - Fj(j I,y))dy1, 3j=1,j6i]L (3.10) where S = (Si*,..., Sp), 1/1- = E^=l 1/1j, cj E R+, j E Si, i E S and 3 E ~. Proof. The proof is essentially the same as that for Theorem (3.1). Again, we need to verify for all A = {/3} x B1 E and B1 = {s = (0,52,...S,5p) E iI | sj < Cj,Cj E +,j E Si}, I(A)= E / P(Y2 E A I Y = (e, s)) n((e, ds)) (3.11) eE~ and 1(A) = (I/ ) Al(/i) [ j() J( - Fj(j 7y)) dy. (3.12) By substituting Expression (3.12) into the right hand side of (3.11) and simplify, result follows. Again, the details are given in the Appendix. n It immediate follows from Theorems (3.1) and (3.2) that when the superposed process is in equilibrium, the probability is u/,li for an event to come from the ith component process. Furthermore, POS^ A - (j ( 3'P(S 3=) /3Ai0,) = S / (/ll) [ij(/3Pi)jm()i (3.13).=l \^./ /V j=l,j ~i [ J and P(Sj = j,0 < Rj < rj;j E Si Ri = 0) = (1 - Fj (j,3y))dy. (3.14) Hence, conditional on knowing an event comes from the ith component process of an equilibrium superposed process, then {(Sj, Rj)}>= *j# are independent pairs of random variables and (Sj, R) follows the limiting continuous remaining or current life distribution of the jth component process given in Equation (2.5). The same result holds for DSCLP. Let T be the interevent time of the equilibrium superposed process and Xi(Pi) be a random variable whose distribution function is given by Fi(iO, t). By Theorem (3.1), the mean interevent

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 11 time of this equilibrium process is given by P(T > t)dt o i=1 PEo P too/i /1\ P = ZE Ai ( 1 -/) ) fi) Ai) (-,y)) (1 - F(3A, t))dt i=1,3E j=l,j=i = [E P ) I j ( -X Fj(-FIj y))dy = -. (3.15) Note that alternatively, we can define a stochastic process {Xn; n E A} such that Xn = (Sn, Rn) where Sn = (Sli,n,., Sp,n), and Rn = (Rln,..Rp,n) = (RlI,n.. Ri-l,n Xi(Si,n), 1Ri+li,n... Rp,n) if the nth event of the superposed process comes from the ith component process and this ith process moves to state Si,n. For j E S, Rj,n is the remaining life of the jth component process at time Tn and this component process is in state Sj,n E ~j. Note that the remaining life of the ith process is given by Ri,n = Xi(Si,n) where Xi(Si,n) has distribution function Fi(Si,n,t). Let us call {XI;n E nt} the alternative discrete superposition remaining life process (ADSRLP). The state space of this process is given by T = ~ x WR. Just like DSRLP and DSCLP, we can derive the transition probabilities for ADSRLP and show that it is a Markov chain. Also, similar arguments used in Theorems (3.1) and (3.2) can be applied to show that under the regularity conditions stated in Section 2 of this paper, ADSRLP has a unique stationary distribution and it is given by P(S = 3,0 < R < ri;i E S) (3.16) =' F (iS ri();,J(1 - Fj( j, )) dy,

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 12 where S = (S1,...,Sp), 1/,/ = EP= l/ j, rj E R+, j E S and 3 E ~. 4. Applications. In this section, the results obtained in the previous section are applied to the study of the individual blocking probability of queueing systems with steady state superposition of semi-Markovian arrivals, and system availability of a device with components connected both in parallel and in series. Example 1: Queues with superposition semi-Markovian arrivals Consider a single server queueing system with no waiting room. The arrival process is the superposition of p point processes. For the ith arrival process, suppose there are Ni types of customers. Assume Ni < oo for all i E S. Let Xint be the type of the nth arriving customer in the ith stream, n E A/, and the instants of arrivals be To,Ti,l,Ti,2.... Suppose (Xi,Ti) = {Xi,n,Ti,n;n E /} can be modeled by a Markov renewal process. We assume that the service times are independent and identically distributed whose common distribution function is 1 - e-", x E R+. There is no waiting room in this system. This means that a customer arrives and finds the server busy leaves the system and never returns. Let X and Xi(ei) be independent random variables whose distribution function are given by 1 - e"-a and Fi(ei,x) respectively. Suppose the arrival process is in equilibrium, let I be a random variable such that I = 1 if a customer arrives and finds the server busy and zero otherwise. Let t1 denotes the arrival instant of this arbitrary customer, and to be the arrival instant of the immediately preceding customer. The customer arrives at time tl and finds the system blocked if and only if the service of a preceding customer is not completed. It does not matter when this service started. The residue service time after the time instant to is exponentially distributed. For i = 0, 1, let (S(ti), R(ti)) = (Sl(ti),..., S(ti), Rl(ti),... Rp(t)) be the state of the equilibrium superposition remaining life process at time ti. By Theorem (3.1), we have p P(I= 1) = ZP(I= 1,Ri(to)=0) (4.17) i=l p = Z > P(S(to) = e, Ri(to) = 0, i=1 eEe x > mn(Rl~o),.. Ri-;-(to),XX;(e-),R-i, (to),... 7 p(to) I)

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 13 p = 1- E (S(to) = e, Ri(to) =, i=1 eE~ X _< min{Rl(to),..., Ri_l(to),Xi(e), Ri+l(to), *..., Rp(to)}) = 1- ('/') ZAi(ei) ae-(1 - Fi(e,x)) X ft } () J(1 -Fj(ejy))dy dx. Result (4.17) is a generalization of the result in Willie (1990) to steady state superposition of semi-Markovian arrivals. Suppose that there are p independent M/G/1 queues. For the ith queue, the waiting room is of size Ni - 1 < oo. It is well known that the departure process from a M/G/l/Ni queue can be modeled by a Markov renewal process whose state are queue lengths after departure and {Ti,n+l - Ti,n}nEr are times between departure. From Cinlar (1975a), if the imbedded Markov chain of the ith Markov renewal process is irreducible aperiodic with finitely many states and all states are recurrent, then the stationary distribution of this Markov chain, Ai, exists and is unique. Suppose the merged output of these p independent M/G/1/Ni queues with finite waiting room becomes the input of a single server queue with no waiting room. Call this queue the second stage queue. When the input to the second stage queue is in equilibrium, Equation (4.17) above gives the blocking probability of an arbitrary customer to this second stage queue. Note that the p M/G/1 queue here can be bulk service queues or the service times of these queues can be state dependent. For details, see Cinlar (1975b) or Lam (1990b). The result above also applies to the case when Ni = oo and the traffic intensity of the ith M/G/1 queue is less than 1. Example 2: System Availability Consider a device with p components connected in parallel. The device is not working when all the components are under repair. The ith component consists of a finite number of subcomponents connected in series. There are Ni < oo different types of subcomponents for component i, i E S. If

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 14 any one subcomponent fails, the whole component fails. Let X,,, be the type of the subcomponent causing the nth failure in the ith component, and Ti, be the times of successive failures. The time Tin+l - Ti7, between two failures is the sum of the repair time of the subcomponent which failed at Ti,n and a failure free interval following the repair. We suppose that subcomponent of type Pi E Ei = {1, 2,..., Ni} in the ith component has exponential lifetimes with parameter a(i, 3i), and suppose its repair time has distribution p(i,/3,*.). Under these assumptions, the failure process of the device can be modeled by the superposition of p independent Markov renewal processes. In particular, for each i E S, the semi-Markov kernel Qi is given by /t Qi(ei, 3i, t) = a a(i,/ i)e-a(i)uo(i, et - u) du (4.18) where ei,/3i E ~i and a(i) = EZE~, a(i,/3i). Also, Fi(ei,t)= - Qi(ei,/pi, t)= j - a(ea(()e-i, t - u)du. (4.19) From Cinlar (1975a), Example (10.6.23), Ai(,3i) = a(i,P3) for all /3i E i and i E S. If the mean repair time of type 3i subcomponent of the ith component is b(i, Pi), then mi(/3i) = b(i, 3i)+(l/a(i)). Let Xi(3ti) be a random variable whose distribution function is given by O(i,/i,.) and a(i)b(i) = ZiI, a(i,/,)b(i,/3i). Suppose that the failure process of device is in equilibrium. Let I be a random variable such that I = 1 if a failure in one of the components results in a failure of the device. This means that at some time t of the equilibrium superposed process, one component fails and all the other components are undergoing repair. Let ci = (cl,...,ci-1,ci+,...,Cp) E P+and H(/3,Ci)= = (I/) Ai(Ii) i -j(1- Fj(3rjy)) dy. (4.20) \P / p,/ j=l,jL' 13 We can now derive the steady state probability that the device fails at some time t and for the ith component, subcomponent of type /3 is undergoing repair at that time. p(I = 1,S = 3) p = (I = 1, S = 3, C = 0) i=l = ZP(S =- 3,Ci = 0,Cj _ Xj(1j);j e S/) i=l

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 15 p p (II 3- (j, cj) = L-1 7,cJ H(3,idc) / / ~~iP 1 P a(i, 3i) =- ( Ikl 1 + a(k)b(k)) = 1 + a(i)b(i) fI r a(j, /3)b(j, /3j ) jIji 1 + a(j)b() j=l,jZi (4.21) The asymptotic continuous time behavior of this system is studied in Lam (1990b). Appendix. To show that Expression (3.7) satisfies Equation (3.5)): First, let us define some notations. For m > 1, let i+ C 2m such that if (xl,..., Xm) E?,m then 1. xi 4 Xj Vi,j E {1,2,...,m} and i j j, 2. xi? L 0 i E {1,2,...,m}. Note that Rm\R+m is a set of Lebesgue measure zero in Rm. From equations (3.1), (3.5) and (3.7), [1/ ( i)] (2 A(1 p)e P(X2 E {3} x Al | X1 = (e, s)) I((e ds)) = E p- 1( fk(k,1s +x)I(si = min s)(Ql(ei,/3i)-Ql(el,/3i,si)) k=2 el EE1 + UESk x I I(0 < sj - s jES nSk < rj) dx Al(el) dsl n [(1j ESi nSk Fj(/j,, s)) dsj] +e E Ipel Ei-61 + / min Su "uEs0 ql(el,P31,) n I(0 < s, - x < ru)dx) xAl(el) H [(1 - Fj(/3j,sj))dsj] j ES1 P k= E E~ p-2 k=2 elEel + (' min Su uES lnSk (1 - Fk(/k,Sl))(Ql(el, 1 )- Ql(el, 1, sl)) ds max {0, sj - r} jESfnSl k xAi(el) Ij [(1-Fj(Ej,sj))dsj] j ES nSk

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 16 p -EE k=2 ei Eil min su uES nSk p-2 max {O,s - jESn1Sk, (1- Fk(/k,l + rk)) rj} x(Ql(el,Pl)-Ql(eiPisl))dsl )A(el) JJ [(1 j ES~ rnk - Fj(3j,sj))dsj] + eE P-l el Efi + (min Su uESi max{0, sj J'~<i - r i q(ei,/i,x) dx) -ri} J Al(el) H [(1- Fj(/3j,sj))dsj] j'~-i P = E E J-2 k=2el ~i + t( min Su uesl nSk (1 - Fk(k, sl))(Ql(el, l) - Ql(el, l, l)) ds max lO,s - r} iES1 nSk p - k=2e 1 -2 k=2 el Eel6 + xAi(ei) II [(1-Fj(]j,sj))dsj] j ES1 nSk min su + rk ESl nSk + (1- Fk(/k, v)) jmax {O,sj - rj} + rk jES1 nSk x(Ql(el,jpl)-Ql(el,Pl,v- rk))dv Al(el) II [(1- Fj(jsj))dsj] jeS1 nSk - 5,l(Qi(el,/3l)- Ql(el,Pi, min su))I(max{O,s - rj} < min su) xAl(e1) I| [(1- Fj(3j,sj))dsj] + E / (Ql(el'll) - Ql(el,Al,max{O, su - r }))I(max{O sj - rj} < min s) uES1 jESi uE uE ei 6E1 + xAl(el) n [(1- Fj(j, sj)) ds] 6ES1 p = E E -2 k=2 el ~^ "+ min su uESlns (1 - Fk( kis))(Ql(el,/1) - Q(el,/ 1, )) ds max {O,sj - rj} jES6i rSk xA(el) [(-Fj(j,sj))dsj] jiSl nSk

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 17 x(Qi(el,Pl)- Qi(ei,(l, v- rk))dv) Ai(el) I [(1- Fj(j,s))ds,] j ES1 nSk P r (r min su - e E I uEL on (1- Fk(/3k,Sk))(Ql(el, P) - Ql(el, 31,sk))dsk k2 ei +-2 max {O,s i- rj} k=2 el Eel + jESIlSk xl(el) n [(- Fj(j,s))ds] j ESi nSk +. j I(0= max{0,s- rj} < min s)(Ql(ei,/3i)-Ql(eil,/l,0)) (A.1) ei Ee1 + xAl(el) Hr [(1- Fj(pj,,s))dsj] jES1 P + E E Jp / (QO(el, 1) Ql(el,31 s rk))I(sk - rk = ma{o0,j - rj} < min su) k=2 eiEeI + xAi(el) H [(1 - Fj(-j,sj))dsj] jES1 = J, I(sj < rj;j e S1)A1(/1) rI [(1 - Fj(/,sj))dsj] (A.2) -~+ - j'ES1 [A/ A=fHi) ({2 3j(j)A) (A.3) -- i=l/ j=2 3 Expression (A.2) above follows from (A.1) because A1 is the stationary distribution of the Markov chain induced by Q1 and Ql(el, P1,0) = 0. To show that Expression (3.12) satisfies Equation (3.11)): First, let us define some notations and transformations. Let c, E R+ for all i E S. Also, note that for k E S and i E Sk, Uk and Wk,i are defined in Section 3. 1. For k E S and v E Sk, let Uk,v C Uk such that (s1,...,sp) 6 Uk,v if and only if sv = min su and (s,...,sp) E Uk. Obviously, U Uk,i = Uk. vESk

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 18 2. For k E S and v E Sk, let Uk, C + such that (Y1,..., Yp) E Ukv if and only if (a) (Y1,...,Yv-1,, Yv+i,... Yp) E iv, (b) 0< yj < cj foralljE Sv nSk, (c) O < Yv < Y< min {yj,cv}. jESvflSk Define a transformation f: Uk,v - Uk v such that (yl..., yp) = f(sl,..., s ) and (a) yj = sj + sk - sV for all j E Sv n Sk, (b) yj = sj if j = v,k. Obviously, the transformation is one to one and onto. Furthermore, the Jacobian determinant is equal to one. 3. For k E S and i E Sk, let Wi C R+ such that (yi,..., y) E Wki if and only if (a) (i,...,yi,0,Yi+i,..,Yp) E'i, (b) 0 < yj < cj for all j E Sin Sk, (c) 0 < k < min {yj,ck}. jESinSk Define a transformation g: Wk,i - Wki such that (yl,..., yp) = g(sl,...,Sp) and (a) yj = sj + Sk for all j E Si n Sk, (b) yj = sj if j = i,k. Again, the transformation is one to one and onto. Furthermore, the Jacobian determinant is equal to one. Now substituting Expression (3.12) into the right hand side of (3.11) and using the transformations defined above, we have [1/ (i1 i)] (i j)) e P(2 E {} x B1 Y1 = (e,s)) ((eds)) i~~i j=2 3 )e,

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 19 p = E E j A(el)q1(e1,1,s1 + Sk)(1- Fk(k,Sk)) [ H (1-F (Au+ S)) k=2 el EEl + LuSi nSjk xl(Wkl) [nI ds [JJ (1 -Fu(U/3,u + Si - minsl))1 IYES1 lEs1S1 u6S1<~^ + E A/ 1A(el)ql(el,1,7sl - min su) el EEl " xI(Ul) [n dsU LuES p = E j/ A(ei)q1(el,pil,Yi + yk)(l - Fk(/k, k)) n (1 - Fu(/3uyu)) k=2 ei EE1 + UES1 nSk X [(WLj) [ju dyu p +E E / lp Al(e1)q1(ei,0 i sl - s$v)(1 - Fv(pv, l)) v=2 el 6Ee1 - X [I ( 1 - Fu (Pu, + S - SV)) I(Ujiv) [5u Lu ES1 nSv, I-uES p E= E S J Ai(el)q1(ei,31,I k=2 el El1 + + yk)( - Fk(/3k, yk)) j1 (I1- Fu(u,yu))] LuESinSk I LUEs J +E E |p Al(el)ql(el,/1,yl - yv)(l - Fv(v, yl)) H (1 - Fu(]u,yu)) v=2 el Ee + uES] nS, LUu,,,iES,,.

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 20 p Cr i min {yu, C o I L PE I I JCj[ juESS {YuCk} Al(el)ql(ell,/l,y + Yk)dy) k=2 el E~1 JES1 rk x(l-Fk(/3k, k))dYk J (1- (j, )) jES nSk + I lic ES n[S, uEns {uc} J il (e1)ql(e l,llY1- y)dyv v=2 eEl 61 jESi Sv ( x(1-F,(/3,,yi))dyul (1 - F3 [,y,))dy j - ES$1nrt,.,(-jfjy)d] p F r min {YuCk} = E E I j I uEsl, nskl Al(el)(Ql(el,31)- Qi(el,/1, Yk)) k=2el E~1 jESn.Sl C< x(1- Fk(/3k,yk))dyk (1-FE jES, nSk v+E nS 1 v=2 el E~1 jESl nS] min {Yuv} uES1, nSv 0O x(l - F,(0,, yl))dJy ][ (l - Fj(j,yj))dy j j ES, nSv ~~~~~p,-, (~~~c~) min yucv}, = E [ 1 ueS1nS{Yu v}A(l)(l- Fv(3,yi))dyl] V=2EstS0 J LE/0 x F (1- F(yj))dyy1 [eS, nSv [1 /(i=l 1)] (I= T (A) (A.4)

SUPERPOSITION OF MARKOV RENEWAL PROCESSES 21 REFERENCES Breiman, L. (1968) Probability. Addision-Wesley, Reading, Mass. Cherry, W. P. (1972) The superposition of two independent Markov renewal processes. Ph. D. Dissertation, Department of Industrial and Operations Engineering, University of Michigan. Cherry, W. P. and Disney, R. L. (1983) The superposition of two independent Markov renewal processes. Zastos Mat., XVII, 567-602. Cinlar, E. (1969) Markov renewal theory. Adv. Appl. Prob., 1, 123-187. Cinlar, E. (1975a) Introduction to stochastic processes. Prentice-Hall. Cinlar, E. (1975b) Markov renewal theory: a survey. Management Science, vol 21, no. 7, 727-752. Lam C. Y. T. (1990a) Limiting Distributions of remaining life and current life in the superposition of Renewal processes. Working Paper, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor. Lam C. Y. T. (1990b) Superposition of Markov renewal processes and their applications. Technical Report 90-21, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor. Pyke, R. and Schaufele, R. (1966) The existence and uniqueness of stationary measures for Markov renewal processes. Ann. Math. Statist., 37, 1439-1462. Willie, H. (1990) Individual blocking probabilities in the loss system G1 +... + GN/M/1/0. Queueing Systems Vol 6, 109-112. Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109