SUPERPOSITION OF RENEWAL PROCESSES C.Y. Teresa Lagn Department of Industrial & O(erations Engineering University of Michigan Ann Arbor, MI 48109-2117 John P. Lehoczky Department of Statistics Carnegie Mellon University Pittsburgh, PA 15213 Technical Report 89-12 Revised October 1990

Superposition of Renewal Processes C. Y. Teresa Lam" John P. Lehoczky" Department of Industrial Department of Statistics and Operations Engineering Carnegie Mellon Universitv The University of Michigan Pittsburgh, PA 15213 Ann Arbor, MI 48109 Abstract This paper extends the asymptotic results for ordinary renewal processes to the superposition of independent renewal processes. In particular, the ordinary renewal functions, renewal equations, and the key Renewal Theorem are extended to the superposition of independent renewal processes. We fix the number of renewal processes, p, and study the asymptotic behavior of the superposition process when time, t, is large. The Key Superposition Renewal Theorem is applied to the study of (EP= G[i)/lM/1/1 queueing systemis. S-RENEWAL FUNCTIONS; S-RENEWAL EQUATIONS; KEY SUPERPOSITION RENEWAL THEOREM; (ZP_ GI,)/AM/1/1 QUEUEING SYSTEMS 1 Introduction In queueing or production networks, an individual service facility imay receive inl)puts frol malny different sources, some of which are outputs from other servers. To model the queue at some server, it may, therefore, be reasonable to postulate that the arrival process to that server is a, superposition of (nearly) statistically independent component processes. *Research Supported in part by a grant from the National Science Foundation DMS-87-O'537. 1

As pointed out by Albin (1982), if the arrival process to a queue is a superposition of many independent, relatively sparse component processes, one can invoke the theorem that a superposition process converges to a. Poisson process as the number of component processes tend to infinity, and approximately represent the analytically difficult superposition process by the simple Poisson process [Cinlar (1972)]. For example, the stream of calls arriving at a telephone exchange is the superposition of thousands of streams of calls generated by the individual customers. Albin (1982) did extensive simulations for a single server with exponentially distributed service times and with an arrival process which is the superposition of p independent renewal processes (the (I=1 Gi)/Ml/1 system). She showed that as p increases the average queue length approaches that of an M/Ml l/1 system, but that, for fixed p, the difference in average queue length between the (i 1 GI )/it/ l and 11M/M/ l systems dramratically increases as the traffic intensity increases from 0.5 to 0.9. In 1982, Whitt used the stationary-interval method and the asymptotic method to approximate the superposition arrival process of the ( ly GIc)/A/ll queue by a single renewal process. It is then easy to describe the steady-state distribution of the number of customers ii tl-h resulting GI/M/1 system. Whitt (1982) then compared the two approximating stea.dy-state distributions with the actual distribution as estimated by computer simulation. Albin (19-14) showed that the mean queue length for the (Z:P GI)/G/I1 system can be approximated by that of a suitably chosen GI/G/1 system. The appropriate independent interarrival time distribution is found as a function of p, the traffic intensity, and p by fitting curves of various forms to simulation results. Newell (1984) described in detail some of the qualitative properties of (E'i GIi)/G/1 systems and, in particular, showed that they approach limiiting NlJ/C/I behavior when p(l - p)2 is large. Suppose there is only a small number of arrival streams. say 2 to 10, and the traffic intensity is close to 1, so that the expected queue size is large.?Newell (1984) showed that the Poisson approximation can be disastrous, and the qcueneing system with a superposition arrival process should be analyzed more carefully. The superposition of point processes has been widely discussed since the original investigation by Cox and Smith (1954). Surveys or reviews have appeared by Cox (1962) and C'inlar (1972). The emphasis of much of the early work has been either on the Poisson nature of a large numberllll 2

of superpositions, or on the distribution of counts of events in superpositions. Lawrance (197 3) studied the distributions and deenden the dependency of the intervals between events. Cherry (1972) considered the problem of superposing two independent renewal processes and two Markov renewal processes. He applied his results to describe the joint departure process of two indcependlentl M/G/1 queues and a classic problem in machine repair and maintenance. For more details, see Cherry and Disney (1973, 1983) and Disney (1975). Kshirsagar and Becker (1981) generalized some of the results in Cox and Smith (1954) to the superposition of Markov Renewal processes. In particular, the interval between two successive visits to a particular state and the asymptotic variance of the number of visits to a state in the superposed process are considered. However, none of these authors have dealt with the extension of the fundamental concepts of renewal processes, namely renewal functions. renewal equations, and the Key Renewal Theorem to the superposition of renewal processes. The Key Renewal Theorem for ordinary renewal processes is useful in studying the behavior of the process remote from the time origin or when it is in equilibrium. A generalization of the Key Renewal Theorem isus therefore useful i stud te asymptotic behavior of the process formed by superposing independent renewal processes. A detailed study of the extension of ordinary renewal functions, renewal equations, and the Key Renewal Theorem to the superposition of independent renewal processes is given in this paper. In this paper, we fix the number of renewal processes, 7). and study the asymptotic behavior of the superposition process when the time t is large. In particular, we define the S-renewal functions and the S-renewal equations. The S-renewal function is defined to be the suml of the ordinary renewal functions of the component renewal processes. The S-renewal equation is derived by conditioning on the time of the first event which occurs in the superposition process. The solution of the S-renewal equations is derived in Section 2, and in Section 3 by letting t - oo, we derive the Key.Superposition, Renewal Theorem. Just like the orldinallry K Renewal Theorem, the Key Superposition Renewal Theorem is useful in studying the asymptotic behavior of the superposition process. In particular, we study its application to the calculation of the excess life, current life and the total life in the superposition process. We also apply the Key Superposition Renewal Theorem to the study of (C=I Gi)/IM/1/1 queueing systems. Numerical studies are carried out to compare various characteristics of the (Ei1 G7I;)/A/1/1 with that of the Al/Ill/1/1 systems. 3

The S-renewal function, S-renewal equation and the Key superpositon theorem we derive in this paper is a continuous state space version of the Markov renewal function, Markov renewal equation and the limit theorems given in Chapter 10 of Cinlar (1975). In a Markov renewal process, the transition state space is a countable set. In the superposition of renewal )processes case, the state space is the set of all possible ages of the processes at the time when an exvent occurs in the superposition process. This paper is organized as follows: In Section 2 of this paper, we generalize the definitions of renewal functions and renewal integral equations associated with ordinary renewal processes to the S-renewal functions and S-renewal equations of p independent renewal processes. The solution of this S-renewal equation is presented. In Section 3, we study the asymptotic behavior of the solution of the S-renewal equations and apply it to various exanmples. This leads to the generalization of the Ordinary Key Renewal Theorem to the Key Superplositionl Renewal Theorem. Theorems stated in Sections 2 and 3 are proved in Section 4. The Central Limit Theorem for the superposition process will be proved in Section 5. In addition, the asymptotic results for the renewal function associated with ordinary renewal processes will be extended to the S-renewal function of the superposition process. 2 S-Renewal Functions and S-Renewal Equations In this section, the definitions of the S-renewal function and the S-renewal equation for the superposition of renewal processes are given. The solution of the S-renewal equation is derived. Suppose that there are p independent ordinary renewal processes in operation simultaneously. Let Fi, i = 1,2,...,p, be the probability distribution functions for the successive interevent times of the ith process. Consider the sequence of events formed by superposing the individual processes. At the time when an event occurs in the superposition process, one of the processes. say I)ocess i, probabilistically starts over. In addition, the others have age D1,... D_1,, D-+. D,. respectively, where the Dj s are random variables. Suppose that at time 0. the processes have age d1,...,dp respectively. Let d = (d1,2,...,d) and N(t,d) be the number of events that 4

occur in the superposition of these p renewal processes during the time interval (0, t]. Then p NV(t,d) -= Z N i(t). (2.1) i=1 {Nd'(t);t > O} is an ordinary renewal process with initial age d-, 1 < i < p. It is also a delayed renewal process such that the successive occurrence times between events hlave a common distribution function Fi. The initial delay distribution function is Fit, some of the d- s may be zero, and Fd(t) _ Fi(t + d-) - Fj(d,) F,'t (t) F(d)F(d)(2.2) 1 -F (di) provided that Fi(t) < 1 for all t > 0. Here Fd'(t)= P(X=' < t) = P(X. ( t + di | X.~ > di). Xd' is the initial time to the first renewal of the ith process, and X- has a distribution function Fi. Before the S-renewal function for the superposition process {N(t,d);t > O} is defined, let us define the concept of the convolution of any two increasing functions. Let A and B be nondecreasing functions, continuous from the right, with A(0) = B(0) = 0. Define the convolution of A and B, denoted A4 * B, by A B(t) B(t - s) dA(s), t > 0. (2.3) Jo The expected number of events that occur in the time interval (0, t] is given by p H(t,d) = ~(N(td))= E (Nd'(t)) 1=1 p p po p = Hid(t) = d F. d (Fi)(t) = Fd [l + Hi(t)]. (2.4) i=1 i=1 j=0 i=l where (Fi)o(t) = 1 and Fdt * (F/)o(t) Fdt(t) for all t. (Fi,)(t) (Fi)j-1 * Fi(t) is the j-fold convolution of the distribution function Fi. H.d(t) is the expected number of renewals in the delayed renewal process {N(.l (t);t > 0} in the time interval (0,t]. Hi(t) = El(Fi) (t) is the renewal function associated with the distribution Fi. Define H(t, d) to be the S-renewal function of the superposition process {N(t, d), t > 0}. H(t, d) is finite for all finite t and di, i = 1,....,, because the Hi(t)s are. Theorem 2.1 H(t,d) = h(t,d) + I(H(t.d)) (2..5) 5

where P t P I( t)) H( t, d)) (-.,u(i, s,d)) I (1 - F (s))dF(.s). (2.6) - u(i, s,d) = (s+ dr,s+ d2,...,s + di_,0, s + di+l...,s + dp) and h(t,d) = 1 - J(1 -'()). i=1 Proof: Conditioning on the time T1(d) at which the first event occurs in the process \;(t, d), and counting the expected number of events that occur thereafter, 0 0if s > t ~[N(t,d) I Ti(d)= Xdi =s] = (2.7) 1 + H(t -.s,u(i,s,,d)) if s < t In words, no events occur in (0, t] if the first event of the superposition process occurs aftel time t. On the other hand, if Tl(d) = Xd' = s < t, then one event occurs at time s, and on the average, H(t - s, u(i,s, d)) additional events will occur during the time interval (s., t]. At time s, the ith process probabilistically starts over, and the others now have ages s + dr, j = 1,2,., i - 1,i + 1,...,p. An application of the law of total probability yields P rt H(t,d) = P(T (d)< t) + H(t - s,u(i.s,d))dP(T,(d)= <.s). (2.8) Now p P(Ti(d) < t) = 1- P(Xd' > t; = 1,...,p) = 1- I(1 - F:d (t)) h(t,d), (2.9) 2=1 and for s < t, P(T1(d)= X' s) = P(X' < XXy-d < s; j = 1,..., j$ i):x II ( - -= / _ (1F- d(xz))dFI(Fx). (2.10) It follows that dP'(T1(d) = K~d s<) = 7l (1 - F'(s))dF(s). (2.11) j= l,ji This completes the proof of the theorem. D Let Tn(d) be the random time of the nth event in the superposition process NV(t. d). Let 6

6i(Tn(d)) be the age of the ith delayed renewal process Nld'(t) at time T,7(d). Defining H(/.d) 0 if t < 0 and 6(T,(d)) = (((T,,(d)),...,6p(T(d))), we have I(H(t,d)) = (N(t- Tl(d),6(Ti(d)))). (2.12) I(H(t, d)) is therefore the expected number of events that occur in the random interval (0. t - Tl(d)] of the superposition process N(t,6(Tl(d))). The integral equation derived in Theorem (2.1) is called an S-renewal equation for the superpostion of p independent renewal processes. It is an extension of the renewal integral equation associated with an ordinary renewal equation to the superposition of p independent renewal processes. More generally, we consider integral equation of the form P _t P A(t,d) = a(t,d) + E A(t - s,u(i,s,d)) (1 - F (s))dF'(.) i= ~ j=i,jfi = a(t, d) + ~(A(t - Tl(d),6(Tl(d)))) (2.13) where a is a known function of p + 1 variables and a(t,d) = 0 if t < 0. The solution of this integral equation is given in the Theorem (2.2) below. We first define some notation. Let S = {1,2,...,p} and Sj = {1.2,... j - 1.j + I.....}. We consider partitions of the set Sj into two disjoint sets 7ri and 7rs. 7ri is a subset of S, with i elements. Let aij be the set of all partitions of Sj. Also, we can partition the set S into two disjoint set 7rw and 7rC. 7ri is a subset of S with i elements. Let a- be the set of all partitions of {1,2,...,p} into the two sets 7ri and 7r. Theorem 2.2 Suppose a is a function of p+ 1 variables and it satisfies the following properties: 1. a(t,d) = O for t < 0, 2. For every finite T > 0, there exists a finite constant KT such that sup I a(t,d) < KTr for all dl,...,dp > O. and it is uniformly bounded in the other variables. 7

Then, there exists one and only one function A with the following properties. 1. For every finite T > 0, there exists a finite constant CT such that sup I A(t, d) i< CT for all d,..., dp > 0. O<t<T 2. A satisfies the S-renewal equation (2.13). This function is 00 A(t, d) = a(t, d) + ~(a(t- T,(d), 6(T,(d)))) (2.14) n=l By conditioning on all the different ways of obtaining n events in the svuperposition process N(t,d), we have p-i A(t,d) = a(t,d) + EUi(a(t,d)) (2.15) i=O where U,(a(td)) =. t f () n dH. st dH (Tr. (2.16) 3=1 oi, kE-rj i times f(6) a(t - Tr,) [1 (1- Fl(r)) 17 (1 - Fk(T- k)), (2.17) IE~~~rr + kE r 7j r+dk if k E i, = (61,...,6p) and bk -= - sk ifk c i (2.18) 0 if k -= j The proof of the theorem will be given in Section 4. Here, we offer some explanatory comments. In the solution of the S-renewal equation above, i + 1, i = 0, 1,..., p - 1, is equal to the number of processes having had at least one event occur by time Tn(d) = r. WTij is the set of component processes having had at least one event occur by time T,(d) = T. 7jt is the set of component processes whose first event occurs after time T,(d). j is the component process giving the nzth event in the superposition process iV(t,d). au is the set of all possible ways in which the above conditions hold. 6k is the current age of the kth process, k = 1, 2....p, at time T,(d) = r. 8

For k E rij, I 7er, and 5k < r, [n1er (1 -F ())][IkL (1-Fk(r - )) k()] (r) is the probability that the following events happen simultaneously: An event occurs in the superposition process at (sk -dsk, Ski, this event comes from the kth component process. Also, no event occurs in the kth process in the time interval (sk,r]. An event occurs in the superposition process at (r - dr, r], this event comes from the jth component process. The first event of the Ith process occurs at time > r. When p = 2, the solution of the S-renewal equation is given by A(tdi,d2) = a(t,di,d2)+ ~ a(t- r,O,r + d2)(1- Fd2(r))dHP (r) + j a(t-r r + d l,0)(1 - F1(r))dH2(r) + j a(t - T,0,r - s)(1 - F(T - s)) dH2(s) dHI1(T) + a(tt - 7r,r - s,0)(1 - F,(r - s))dH1(ds)dH2 (r). (2.19) Jo Jo In the special case that the function a(t,d) has a product form, the solution of the S-renewal equation also has a product form. In addition, as t -- oc there is a Key Renewal Theorem for the process N(t, d). Corollary 2.3 For i = 1,2,...,p, let Fi be the distribution function of a positive random variable with mean yL{. Suppose that gi, i = 1,2,...,p, is directly Riemann intelgravble and P g(t + d&) a(t,d) i 1-(a) I(2.20) i - Fi(di) Let A be the solution of the S-renewal equation (2.13).'Then A(t,d) (F ( di + * H.(t) (2.21) Furthermore, if Fi, i = 1,2,...,p, is not arithmetic, then {Y[[i- | gi(x ) if wi <, re, i = l,..., lim 4(t, d)= (2.22) t —* TI 0 otherwise 9

Proof: The proof is straightforward but tedious. Substitute Expression (2.20) into Equation (2.15) in Theorem (2.2) above and simplify. It is easily checked that ti(a(t, d)) = z[ j [ g(t + [dll1) gj(t -S - ) (j j Otjl It71 - F1(d1) kE7 =r -(t + d i ) [f l *4Hi(t)]H (2.23) ~- o[*n - F ](d 4',+1 kE 1iT+l Hence A(t,d) f gt d) +) Fg( Jd) + [l i- F1() 1- F1(d1) *, Hk) i=0 a,+l I 1', Finally, from the ordinary IKey Renewal Theorem, if F, i = 1,2...p, is not arithmetic. theii Vr ( A d ) Hd(1 ) d xj y d< if ^ < K lim [ I,d) + g * (2.25) L. 1- Fid) 0 if+ gi This completes the proof of Equation (2.22) and Corollary (2.3). D Examples: (1) When p = 2 and a(t, dd2) W= 1, we have after some algebra, A(t,dl, d2) 1 + Hll(t) + H2(t). (2) When a(t, d) = 1, it is easily checked that the solution of the S-renewal equation corresponding to a is given by A(t, d) = 1 + tP Hi' (t). (3) When a(t, d) n ( 1 - Fid'(t)), we can apply Corollary (2.3) with g-(t) = 1- Fi(t) to find the solution of the S-renewal equation. It is easily checked that A(t,d) = 1. (4) When a(t, d) = h(t, d) = - - (t)) we can use the linearity property of integrals and the results of exanmples (2) and (3) above to obtain A(t,d)= H(t,d) = EZp Hd'(t). Corollary (2.3) tells us that as t - oc, A(t,d) is independent of the initial age d, i = 1,2,...,p, of the component processes. In other words, in the limit as t - oc, the effect of the initial age di of the process N.d (t) disappears. In the next section, the above corollary is used to calculate the limiting remaining life of the superposition process N\(t, d). 10

3 Key Superposition Renewal Theorem and Applications In this section, it will be shown that under some regularity conditions on a(t, d), we can generalize the ordinary Key Renewal Theorem to the Key Superposition Renewal Theorem. We will see in the theorem below that lim A(t,d) is independent of the initial ages di, 1 < i < p, of the (-00 component processes. Before the theorem is given, we need the following two definitions. Definition 3.1 Let g be a function defined on R7I. For every positive 6 and m, ni = 1,2,..., i = 1,2,...,m, let m,,nz,....7lm m = min{g(x,x2,...,Xm) (ni - 1)6 < xi < n,6; i = 1,2,...,m}, mnn2,..n = max{g(XiX2... Xm): (11 - 1)^ < xi < n-i; i = 1,2., n1}, 7m (X, m OC r(6) = 6bZm 2l,n2. and (6) = 6"m1 Z,n2,....,n n 1=1 n,=l i==l 1n = 1 Then g is said to be directly Rienmann integrable if both series a(6) and 5(b6) converge absolutely for every positive 6, and the difference 5(6) - a(6) goes to 0 as 6 - 0. Definition 3.2 Let a be a function defined on RT+'. For every positive h and k = 1, 2..... let minlla(x,yl,...,yp) if (k - 1)h < x < kh ck(yl,...,yp), (3.1) 0 otherwise maxa(x, yi,...,-yp) if (k - 1)h < x < kh ck(yi,....Yp) =- (3.2) 0 otherwise For i = 1,2,...,p, let Fi be the distribution function of a positive randoim variable with finite mean ui. Define a 1 x p random vector D such that D = (D1,... Dil,0, Di +,.., Dp) with probability -/ D1, D2,..., Dp are independent random variables and Di follows the limiting curlren.t life distribution of Fi, i = 1,...,p. This means that for z > 0, P(Di > z) = (1- Fz(y))dy (3.3) 11

Also, let a(h) = h (ck(D)) and a(h) = h E ~(ct(D)). k=1 k1= Then a is said to be directly Riemann integrable with respect to (F, D) = ((F1, D1),....( F,. D,)) if both series ao(h) and ~(h) converge absolutely for every positive h, and the difference a( h)-o( h) goes to 0 as h - 0. Theorem 3.3 (Key Superposition Renewal Theorem for p independent processes) For i = 1,2,...,p, let Fi be the distribution function of a positive random variable with finite mean pi. Suppose that 1. a(t,d) = 0 for t negative, 2. For every finite T > 0, there exists a finite constant cT such that sup | a(t,d) \1<;T for all dl,...,dp > 0. O<t<T 3. A is the solution of the S-renewal equation (2.13). 4. The function p bj(tdl,...,djl,dj+l,...,dp) = a(t,dl,...,djl,O,dj+l,,...,dp) (J (1- F(dJ)) i=1,iZJ defined on 7+ is directly Riemann integrable for all j = 1,2,...,p. 5. The function a is directly Rieimann integrable with respect to (F, D) = ((F1, D1),...,, L), D )). If Fi, i = 1,...,p, is rnot arithmtetic and L = [ -, then t-i { D-' ~(a(D1.... Di_l, 0Di+....Dp))dx if it < xo lim A(t,d) i- L t — cO [0 if i = o { - ~ (a(xr,D)) dx if p < oc - < 1 o (3.4) [ O if p- = o 12

Proof: The proof will be given in Section 4. From Corollary (2.3) and the Key Superposition Renewal Theorem, we can conclude that as t -- oo. A(t, d) is independent of the initial ages d;, i = 1, 2,...,p, of the component processes. All we need to do is to average the initial age by the corresponding limiting current life distribution of the individual independent component processes. Applications Example 1: Consider the ('i=1 GIi)/AM/1/1 queue, this is a queueing system with an arrival process which is the superposition of p independent renewal processes. There is no waiting room in this system. A customer that arrives and finds the server busy leaves the system and never returns. Assume that at time t = 0, the server is busy and the ages of the renewal processes are dl, d2,..., d. Part (a): Let A(t,d) be the probability that the server is busy at time t. By the memorylessness property of the exponential distribution and the independence of the service times, at time t = 0, the residual service time X of the customer being served at that time has the same exponential distribution as any service time. Conditioning on the time T1 of the first arrival to the system, we have 1 if T1 > t and X > t A(t,d) = 0 if T1 > t and X< t (3.5) A(t - s, u(i,s,d)) if T1 = s < t and I1 = i where Ij is an indicator function such that Ij = i if the jth arrival comes from the ith process. A(t,d) satisfies the S-renewal equation with p a(t,d) = P('T, > t,X > t)= e-t' I(l - Fi(t)) (3.6) i=1 where 1/a is the mean service time. By the Key Superposition Renewal Theorem, we have 13

A el e~2 e3 elo 0.1 0.060 0.039 0.028 0.008 0.2 0.111 0.070 0.049 0.014 0.3 0.157 0.094 0.064 0.018 0.4 0.194 0.110 0.075 0.021 0.5 0.224 0.125 0.082 0.023 0.6 0.247 0.133 0.087 0.024 0.7 0.262 0.137 0.089 0.025 0.8 0.270 0.138 0.090 0.025 0.9 0.271 0.138 0.090 0.026 Table 3.1: Proportion of error when a = 1 in Example 1(a) lim A(t,d) t i — — a[Jo e -Fi(x))( EI J 1- (1- Fx(+y'I))- n d l) 4 i- -x(1 - F(x)) dy dx (3_ 7) = 1,j3i J = 1,j Expression (3.7) gives us the limiting probability that the server is busy at timle t when t is large. This is independent of the initial conditions of the system. In the special case when 1- exp -I —)1 if- > 1 Fi(x) - G(x)= - A p P- (3.8) I0 otherwise for all i E {1, 2,..., p}, the total arrival rate to the system is A < 1. Equation (3.7) simplifies to Lp p - e-at(l - Gp())( - Gp(x + y)ddy dx L (A)-j a A(j - ))P = A e-ax 1-I dxU +- ~ -ap = Ap ) (1 - A)a + x -= -r(-1)i 1 - I 1 - (1 - A e + (1 - A)a )+ Ae —' (:3.9) i=O a j1 = dx~ (I As expected, Expression (3.9) converges to La = A/(A + a) as p - oc. Let ep = (L, - L, )/La. e, is the proportion of error for thle Poisson approxilmatioll as definled ill Albinl (1982). FromIII 14

Table (3.1) above, the percentage error could be as large as 13.8% when p = 2. This suggests that the Poisson approximation is not appropriate for p small. The Key Superposition Renewal Theorem is necessary to obtain the exact solution in the analysis of ('=S G;)/AM/1/1 systems. Part (b): Let B(t,d) be the probability that the first customer arriving after time t finds the server busy. Again, conditioning on the time T1 of the first arrival to the system, we have 1 if T1 > t and X > Ti B(t,d) = (< if T1 > t and X < T1 (3.10) B(t - s,u(i,s,d)) if T = s <t, and I = i B(t,d) satisfies the S-renewal equation with a(t,d) = P(X > T1 > t) = eat [(1 - F (t)) - ( - F( ) -a dx. (311) i — 1 i - 1 By the Key Superposition Renewal Theorem, we have lim B(t,d) t-oo If [ Je (1 - rF ( x))( f (1- Fj(x + j )) ) i= ] i l,J )))( 1 Fl-i ja- ( ae-(1 - Fix(zF( )))( fi dy~) dx ]3.2) In the special case when F(x) = Gp(x) for all i {1,2,...,p}, equation (3.12) simplifies to (1- Aa+A)2l e. (3.13) PLet A(td1 be the probaby that X = 1 gen a ati( ai (- A+ th e *P = A e - ax I x o I - ( A)a + A ((I - A)a + A)23 As expected,'m converges to m^,, = [A/(A + a)]2 as p o oo. Let ep = (??ip - iii,F,/. froin Table (3.2) below, the percentage error could be as large as 17.5% when p = 2. Example 2: Consider the superposition of two independent renewal processes. Define tOe process X(t) such that X~t) = i, Z = 1,2, if at time t, the last event came from the ith process. Let A~t, di, d2) be the probability that X(t) = 1 given that at time t = 0, the ages of the renewal processes are dl and d2 respectively. Conditional on the time T1 of the first arrival, A(t,d1, d2 ) satisfies the S-renewal equation with a(t,dl,d2) = P(T > t)I(d1 < d2) =[(1- F'(t))](dl < d2) (3.14) 15

A E1 62 (3 610 0.1 -0.154 -0.213 -0.195 -0.068 0.2 -0.046 -0.136 -0.131 -0.044 0.3 0.057 -0.066 -0.075 -0.025 0.4 0.154 -0.004 -0.028 -0.011 0.5 0.242 0.049 0.011 0.000 0.6 0.318 0.093 0.042 0.009 0.7 0.382 0.128 0.067 0.015 0.8 0.430 0.155 0.086 0.020 0.9 0.461 0.175 0.100 0.024 Table 3.2: Proportion of error when a = 1 in Example l(b) where I 1 if di < d2 I(d1 < 12)= (3.15) 0 otherwise By the Key Superposition Renewal Theorem, we have lim A(t, dl,d2) = - ( 2( dyd = P(R2 > R) (3.16) t —oo Jo l 1 Jl 2 where Ri, i = 1,2. is the limiting current life distribution of the ith process. Example 3: Limiting Distributions of the Remaining Life and the Current Life Let t (d) be the remaining life at time t of the process N(t, d). For any fixed z > 0, set A. (t,d) = P({t(d) > z). Conditioning on the time T1 of occurrence of the first event in the process N(t. d). we can derive the S-renewal equation for A4(t,d). In this case, a~(t,d) = IiP( I - F'(t + )). Let gz (t) = 1 - Fi(t + z). az(t, d), therefore, has the product form specified in Corollary (2.3). It follows from that corollary lin P(-t (d) > z) = J(- (1 - Fi(x))dx), (3.17) t -- Ti which is the product of the individual limiting remaining life distributions of the component processes. This is as expected, because the p renewal processes are independent. The same 16

argument in Karlin and Taylor (1975) page 193 can be used to show that the limiting distribution of the current life for the superposition of independent renewal processes is also given by Equation (3.17). Example 4: Limiting Distribution of the Total Life Let Pt(d) be the total life at time t of the process N(t,d). For a fixed z > 0, set A:(t,d) P(3t(d) > z). Again, we can condition on the time T1(d) of occurrence of the first event in the process N(t,d) to derive an integral equation. A,(t,d) satisfies the S-renewal equation with p a:(t,d) = I( - F.'(max(t, z))). (3.18) i=1 By Theorem (3.3), if tl,...,/p < oc so that = - < oc, then lim P(pt(d) > z) (3.19) t —00 E -, (1 - F(ma( Fi((max(x z) ))dy ~ (1- Fj(max(x,z) y [)) jdydx i= = 1 31i, 1 J = E - / X -(1- F()) [ j ( Fy) dyJ dx] = - xdG(x) where G{X)= 1 _-E/(1i-=F1)) n [ ( F8 dfir'x (3- 2Fj) G()- (l - Fl(x)) dr (3.20) Accordingly, we have established the limiting distribution of the total life is lim P(3t(d) < z)= j xdG(x) = B(z). (3.21) A similar argument from Karlin and Taylor (1975) page 195 can be used to show that the mean limiting total life is at least as big as the mean interval time in the superposition process.( t, d). This fact is consistent with the analogous result for ordinary renewal processes. 4 Proof of Theorems Proof of Theorem 2.2: We first verify that A specified by equation (2.15) fulfills the reclquisite boundedness properties. Using standard renewal theory, Hi is nondecreasing and finite. It 17

follows that /o Hi,(t) - F/, * [1 + H1(t)] - Fj (t) + j.F,(t - s) dHi(s) < 1 + Hi(t) < oc for all t. (4.1) Hence, for every T, we have sup IA(t,d) I ~ T[l + 2E...] ] l. [ i dnHk ()] dH (T)] 0<t<T - i=0 j=l o,3,~, keTrr, i times = T [1+ EEE] [II Hk(T)] dH i(r)] i=0 j=l aj -ckE'ri = [T I + Ed[H Hk (T)11 1=0 o',+i kE rr +1 = T I(1 + Hi'(T)) = CT <. (4.2) i=1 establishing that the Expression (2.15) satisfies property (1) of the theorem. Next we want to show that Expression (2.15) solves the S-renewal equation. Conditional on 1. the time Tl(d) of the first event that occurs in the process N(t,d), and 2. 6i(T1(d)), i = 1,...,p, the age of the ith component process Nd'(t) at time T1(d), we have rT(d) = Tl(d) + Tn_ ((T (d))) (4.3) and 6(T,(d)) = (bl(Tn-(6(Tl(d)))),..., p(Tn-il((Tl(d))))) = b(T,-1i(b(T(d)))). (4.4) In words, knowing T1(d) and -(T1(d)), i = 1,...,p, then the times of n events in the process N(t,d) are equal to Tl(d) plus the times of n - 1 events in the process N(t/,(Tl(d))). Also. the age of the ith component process at the time of n events, Tn(d), is the same as the age of the delayed process {N6 (T(d)) (t); t > 0} at the times of n7 - 1 events. It follows that for all n > 1, S(A(t- T,(d),6(Tn(d)))) =~[~(A(t - Tn(d),6(T,,(d))) | Tl(d),6(T1(d)))] = 5[5(A(t- rT(d)- T _1(6(Tp(d))),6(T-l(,6(rTl(d)))) r Tl(d),6(T(d)))]. (4.5) 18

We can now solve the S-renewal equation by successive approximations, and we use equality (4.5) to simplify each step in the approximation to obtain A(t,d) = a(t, d) + c(A(t - T (d), 6(Tl(d)))) = a(t, d) + ~(a(t - T1(d),6(T1(d)))) + S[~(A(t - T1(d) - T((6(T1(d))), (T1(6(Ti(d)))) I Ti(d), (T1(d)))] = a(t,d) + ~(a(t - T,(d),6(Tl(d)))) + ~(A(t - T2(d),6(T2(d)))) n- I = a(t,d) + (a(t - Tj(d),6(Tj(d)))) + C(A(t - T,(d),6(Tn(d)))). (4.6) j=1 Next we want to show that lim I ~(A(t - T,(d),6(Tn(d)))) I= 0 (4.7) 7n -oo for every fixed t. Let In(N(t,d)) be the indicator function such that In(N(t,d)) is equal to j if the nth event of the superposition process comes from the jth component process. Observe that by conditioning on 1. i+ 1, 0 < i < min{7n - l,p - 1} = p, the number of processes lhaving had at least one event occur by time T,(d), 2. In(N(t,d)) = j, j = 1,2,...p 3. For each i = 0,...,J, and j = 1,2,...,p, (a) 7ri C {1,..., j - l1,j + 1,...,p} and lTr-i I-i= (b) Ndk(Tn(d)) = mk if k + {j} 0 otherwise (c) mk = n -- i1, and mk > 0; k = 1,...,p, kE ir U{j} + dk if k E 7Tr (d) T,(d) = T, and Sk(T,(d)) = - = T - ak if k E 7ij 0 if = j 19

we have I ~(A (t - Tn(d), (Tn,(d)))) P p t'T T I fj=l EEa, f( d k* (Fk)mk(Sk))d *(Fj) i=0 on kE 7r2 i times ct E E E(H Fk * (Fk)mk( ))dFJ F) i=O j=l rij inj keTrij ctE( 1 F*(Fk)mk(t))] (4.8) i=o a+i + 1On kEt+l where -i = {(tm3..,m7p): m7j + j 3 t m = 1 - i - 1, k2k > O, k = 1,...,/>}k kEr2',3 i+l = {(7i,'...,mp) i: k = nr- i —, mk, k = l,...,p}, kEri+ l and fA(6) = A(t- Tr,) l (1- Fdl()) I (1 - Fk(T - k)). IE7c kE,irz For i = 0,1,...,1p, E E ( n F * (Fk)k(t)) n I Hk (t) <. (4.9) n=i+l +- kEtril kE7r,+l This means that Eon (nlkET,+ FFk * (Fk)mk(t)) is the nth term of a finite series and hence converges to 0 as n - oo. Expression (4.8) is now bounded by the sum of a finite number of terms, each of which converges to 0 as'n - oc. This completes the proof of Expression (4.7). Letting n - o in Equation (4.6), we have Result (2.14) and ~(a(t - Tr,(d),6(TTn(d)))) (4.10) n=l = LtE z t -...J f(5)[ E I ( dF n* (Fk)k(sk))dFJ * (Fj)iT(r).,j=l( o a o " - n=i+l. Ik^Eri2 i times 20

Finally, observe that E [ I dFk *(Fk)mk(Sk)]dF **(Fj)mj(r) = I dHk (sk)dHd (r).(4.11) n=i+1 Si' kEri kE 7r, This completes the proof of the theorem. F Proof of Theorem 3.1: Key Superposition Renewal Theorem The proof is a direct extension of the proof of the ordinary Key Renewal Theorem given in Feller (1971) or C'inlar (1975). It is carried out in two steps. Step 1: Let f c(d) if O < L < x < U < oci a(x,d) = <, (4.12) | 0 otherwise where c(d) is a function independent of x. Since the function a is independent of the first variable, it follows that 1T = r which is independent of T. Let I(t) be the indicator function defined by IA(t) = 1 if t E A and 0 otherwise. Observe that 1. lim a(t,d) = lim c(d)I{<t<u}(t) = 0. t- oo t- - - 2. We know that Fdf is a nondecreasing function such that Fd i(o) lim -^ Fd(T) = 1, i.e., given any e > 0, there exists To(E) such that for r > To(E) and VI C {1,2,...,1}, we have 1- Fd'() < Lc u < (4.13) l- () (U - L) | [ (4Il:a where a = max | aj 1. Also, by Proportion (3.5.1) part (iii) in Ross (1983), given any l<_i,j<p e > 0, there exists t,,() such that for all t > t,(e) and Vkc {1,2,....p}, _ ( + 1)(tU - L) Hk(t - L)- Hk (t-U) < (4.14) 21

3. For i = 0,1,...,p- 2 and t > max(Tr,~) + U, t (c)), P j jT Jo 6)[ 1n0 dHk (Sk)]dHJ r) times j= -L Fkedk d - -( j=l, [ ( Fk(r Sk))dHk (sk)Jr d = C Z | 7j | [H (t - L) - H (t- U)] j=l j=113 < | a| E il~ )( -L)= E( + 1) (4.1T) Since e can be made arbitrarily small provided that t is large enough, it follows that when i = O, 1,...,p- 2, — tlim EJ f( r F dHk(sk)]dHj (r) =. (4.16) j=l,, k6 Ern, i times 4. Next observe that by Proposition (3.5.1) part (iii) in Ross (1983), we have - J (a(x,D))dx 1 Jo - -where y =.., yj-,Yj+, p-i times where yj = (yl,..., cy_i,0, yj+-,... yp). 5. Let s = (S,..,p) and v(j r, s) = (r -,.. r 1 - S( k))- k(sk)(+ J(T). For i = p- 1, II uiiA d k Hi] d^ ^ (4.18); times p-i times 22

It is easily deduced from condition (4) of this Theorem and by the extension of the proof for Ordinary Key Renewal Theorem to higher dimensions that 1im... c(v(j,-,s)) 1I ((1- Fk( r-k))dlHk (.k) k=1,k#j p-i times = j1... C(yj) n (k (4.19) k=l, kAj k p-i times Since t - L > r t - U, hence r -o as t oo and lim E -..L f - )(6)[ 1] dH (S)dH (k ) (r) = 1 S(a(x,D))dx. t-00 L^ ^ J J__J^ 4^J J^ J i times Step 2: Let a(x, yl,.. yp) be a function that satisfies the conditions stated in the theorem. For fixed h > 0 and k = 1,2,..., let a(x, Y1,..., yp) = Zck(Yl,.., Yp)I[(k-1)h,kh)(x) (4.20) k-1 and cO Ci(x,y1,...,yp) =;E k(l,...,Yp)I[(k-t)/h,k)(x) (4.21) k=1 where Ck(Y1,-... y,p) and ck(yl,... yp) are defined in Equations (3.1) and (3.2). Then a (y,.'.yp) < a(yl,...,yp) ~< U(yl,., Y ). By step 1 and condition (4) of the theorem, it is easily shown that if A(t, d) and A(t, d) are the solutions of the S-renewal equations corresponding to ga and a, then lim A(t,d) = ~Z(ck(D)) = - ( ~a(x,D)) dx (4.22) t —s,~ / ck=l /1 and - 1h C0 1 o lim A(t,d)= - (k((xD)) ((D)). (4.23) /.t k=-l, But A(t,d) < A(t,d) < A(t,d) and hence all limit values of A(t,d) lie between - ~(k(D)) k;= 00 andh - (ckk(D)). By condition (5) of the theorem, it follows that / k=1 1 -- c l t lim A(t,d) = - j ~(a(xD))dx. (4.24) 23

5 Asymptotic Results of N(t, d) and H(t, d) In this section, we extend some of the asymptotic results for ordinary delayed renewal process to the superposition of p renewal processes. Let N(t; p) = N(t,,...,0) be the counting process associated with the superposition of p independent renewal processes Ni(t), i = 1,2....p, each of these processes restarted at time t = 0. The next theorem tells us that N(t;p) is asymptotically normally distributed as t - oo. Theorem 5.1 Central Limit Theorem for Superposition of p Renewal Processes For i = 1,...,p, let u and a, assumned finite, represent the mean and variance of an intera ri val time of the i th renewal process Ni(t). Then P 1 N(t; p) - t 1im { i1'^ <Y} J< ye - e-22d. (5.1) lim 2 } t P 722 J-r00 t f4 \ hProof: The proof is straightforward. By the Central Limit Theorem for ordinary renewal processes [Karlin and Taylor (1975)], we have for i = 1,2,...,p, N-(t -,) - as t -oo. (5.2) [/t /_t~ Since all the component processes are independent, N(t;p) = ZNi(t) N (t -,t 3i (.5. 3) i=\ z2l ^=1 2 =l hti = D Let T, be the time of occurrence of the nth event in the superposition process N(t;p). The theorem above can now be used to show that Tn is also asymptotically normal as n, o. Theorem 5.2 Let T, be the time of occurrence of the nth event in the superposition procc.s.s N(t;p). The asymptotic Result (5.1) can be inverted to show that as n - oc, 24n.'"' ( _)3 (5.4) i=1 / 1=1 hi 2=1 i 24

Proof: First, observe the equivalence of the sets of events P > t} if and only if {N(t;p) = Ni,(t)< ni}. z=1 Write n = - a2 // 2 P 3 ) t-1 ~yn.n -Z- (5.5) so that - t -- (E —n - /E-. (5.6) z =1 i =l /~i Then p1 1 N(t; p) - t n - t5P((Tn>t) = P(N(t;p) <n)= < ) (57),-7 - (.2p r tZ- tZ- i=1 Ui' =1 i By Expressions (5.5) and (5.6) above, P P 2 P -2 P 1/2 ( ) / t.i1: = - Yn 1 ]+ Y n-~ i — j (-. I ) ~ ]~/i i;=1 Lz=1 = Now fix y, = y and let n -- o. Then P 2 p -1/2 M-Yn Il+Ynn / =-y. (5-9) t —-001/2 tr { i=1 Hi /i=1 i i Furthermore, by Expression (5.5), t, oo as n - oc. Hence by Theorem (5.1) above, f- n/ Ei=__ _ _ _ 1 >i lim P( > ) = lim P(Tn > t) = -.. 5.1) no \1 P Pi= 1 ]ti 3 i=1 /] c 27, D The following theorem is an extension of Proposition (3.5.1) in Ross (1983). The proof of the theorem is straightforward. Theorem 5.3 Let 11 be the meal ilterarrival time for the sulperpositino pioceSs V(t,d). 25

1. With probability 1, lim' (' -. t- oo t 2. i H(t, d) 1 2. lim = - t-Coo t tl 3. If Fi. i = 1,2,...,p, are not arithmetic, then h lim (H(t + h, d) - H(t, d)) - t —o, /L 4. For i = 1,2,...,p, let Fi be nonarithnetic distributions with finite variance oa. Then we have lim (H(t,d) — ) = 2 t-0co tz 2 2-2 This is an asymptotic expansion of H(t,d). Proof: Use Proposition (3.5.1) in Ross (1983). F Remarks: Theorem (5.3) also holds when the component processes are dependent. References [1] Albin, S. L. (1982) On Poisson approximations for superpostion arrival processes ill queues. Management Science, vol. 28, no. 2, 126-137. [2] Albin, S. L. (1984) Approximating a point process by a renewal process, II: Superposition arrival processes to queues. Operarions Research, vol. 32, no. 5. 1133-1162. [3] Cherry, W. P. (1972) The superposition of two independent Markov renewal processes. Ph. D. Dissertation, Department of Industrial and Operations Engineering, Untiversity of Michigan. [4] Cherry, W. P. and Disney, R. L. (1973) Some properties of a process occurring in the superposition of two independent renewal processes. Proc. XX Interi nation(alI.eeetiyg, Thf Institute of Management Sciences, ed. E. Schifler. Tel Aviv, Israel, 517-520. [5] Cherry, W. P. and Disney. R. L. (1983) The superposition of two independent Mlarkov renewal processes, Zastos Mat., XVII, 567-602. 26

UNIVERSITY OF MICHIGAN 3 9015 04735 3373 [6] Cinlar, E. (1972) Superposition of point processes. In Stochastic Point Processes, ed. P. A. W. Lewis. Wiley-Interscience, New York, 546-606. [7] Cinlar, E. (1975) Introduction to Stochastic Processes. Prentice-Hall. [8] Cox, D. R. (1962) Renewal Theory. John Wiley, New York. [9] Cox, D. R. and Smith, WV. L. (1954) On the superposition of renewal processes. Bionletrika, 41, 91-99. [10] Disney, R. L. (1975) Random flow in queueing networks. A.I.I.E. Transact., 7, 268-288. [11] Feller, W. (1971) An Introduction to Probability Theory and Its Applications. Volume II. Second Edition, John Wiley & Sons. [12] Karlin, S and Taylor, H. M. (1975) A first course in Stochastic Processes. Second Edition, Academic Press. [13] Kshirsagar A. M. and Becker M. (1981) Superposition of Markov renewal processes. South African Statist. J., 15, 13-30. [14] Lawrance, A. J. (1973) Dependency of intervals between events in superposition process. J. R. Statist. Soc. B 35, 306-315. [15] Newell, G. F. (1984) Approximations for superposition arrival processes in queues. Management Science, vol 30, no. 5, 623-632. [16] Ross, S. M. (1983) Stochastic Processes. Wiley, New York. [17] Whitt, W. (1982) Approximating a point process by a renewal process, I: Two basic methods. Operations Research, vol. 30, no. 1, 125-147. 27