New Better Than Used in Expectation Processes Department C.Y. Teresa Lam of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 90-16 Revised August 1990 Revised November 1990

New Better Than Used in Expectation Processes C. Y. Teresa Lam Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 Abstract In this paper, we study the new better than used in expectation and new worse than used in expectation properties of Markov renewal processes. We show that a Markov renewal process belongs to a more general class of stochastic processes encountered in reliability or maintenance applications. We present sufficient conditions such that the first passage times of these processes are new better than used in expectation. The results are applied to the study of shock and repair models, random repair time processes, inventory, and queueing models. NBUE AND NWUE PROCESSES; INCREASING MARKOV RENEWAL PROCESSES; FIRST PASSAGE TIMES; QUEUEING; RANDOM REPAIR TIME PROCESSES; SHOCK AND REPAIR MODELS; INVENTORY 1 Introduction First passage times of appropriate stochastic processes have often be used to represent times to failure of devices or systems which are subject to shocks and wear, random repair time, and random interruptions during their operation. The life distribution properties of these processes have therefore been widely investigated in the reliability and maintenance literature. Conditions under which the first passage times have increasing failure rate (IFR), increasing failure rate average (IFRA), new better than used (NBU) and new better than used in expectation (NBUE) 1

properties have been studied. It is well known that IFR = IFRA => NBU => NBUE for life distributions. IFR characterization of birth and death processes, nonnegative diffusion processes, pure jump processes, Levy wear processes and Markov chains were presented in Keilson (1979), Dermari, Ross and Schechner (1983), Abdel-Hameed (1984a, b), and Brown and Chaganty (1983) respectively. IFRA properties of Markov jump processes, Poisson shock models and Markov chains were considered by Shaked and Shanthikumar (1987), Ohi and Nishida (1983), Brown and Chaganty (1983) and references there. Marshall and Shaked (1979), and Block and Savits (1981) studied multidimensional IFRA processes. Marshall and Shaked (1983, 1986), and Shanthikumar (1984) considered processes with NBU first passage times. Shock models with NBUE survival were discussed in Block and Savits (1978). Karasu and Ozekici (1989) studied new better than used in expectation (NBUE) and new worse than used in expectation (NWUE) properties of increasing Markov processes and Markov chains. In this paper, we consider the NBUE and NWUE properties of Markov renewal processes. This extends the results in Karasu and Ozekici (1989). We introduce a general class of stochastic processes and show that Markov renewal processes are special cases. The class of stochastic processes considered here is closely related to those discussed by Marshall and Shaked (1983), and Shanthikumar (1984). In their papers, they presented conditions such that the first passage times of their processes are NBU. However, as illustrated by an example in Section 2 of this paper, not all NBUE stochastic processes which are used to represent times to failures of certain devices are also NBU. This motivates us to look at a weaker characterization of stochastic processes encountered in reliability or maintenance applications. In Section 3 of this paper, we consider sufficient conditions such that an increasing Markov renewal process is NBUE or NWUE. The results will then be generalized to characterize the NBUE and NWUE properties of a general Markov renewal process. In Section 4, we introduce the general class of stochastic processes of interest to us, and show that under some conditions, these stochastic processes are NBUE. The results in Sections 3 and 4 are applied to study shock and repair models, random repair processes, inventory and queueing models. 2

2 An Motivating Example In this example, we show that not all NBUE processes are also NBU. The set of NBU processes are therefore strictly included in the set of NBUE processes. Consider a stochastic process Z = {Z(t); t > 0} with state space S C R+. R+ here represents the set of all nonnegative real numbers. Z(0) = 0 with probability 1. Let T,(Z) be its first passage time to level x E 5, i.e., T,(Z) = inft > 0: Z(t) > x}. (2.1) T,(Z) is said to have NBU (respectively, new worse than used (NWU)) distribution if P(TT(Z) > t + s | Tr(Z) > t) < (respectively, >)P(T,(Z) > s) (2.2) for all t,s > 0. Tr(Z) is said to have NBUE (respectively, NWUE) distribution if E(Tx(Z) - t T,(Z) > t) < (respectively, >)~(Tx(Z)) (2.3) or J P(Tr(Z) > t + s) ds < (respectively, >)P(Tr(Z) > t) J P(T~(Z) > s)ds (2.4) for all t > 0. The process Z is said to be NBU (respectively, NWU, NBUE, NWUE) if the first passage times T,(Z) have NBU (respectively, NWU, NBUE, NWUE) distributions for all x E S. Assume that {Z(t); t > 0} is a Markov process with state space S = {0, 1,2, 3} and Z(0) = 0 with probability 1. Suppose the process can jump from state 0 to state 3 with probability p or to state 1 with probability 1 - p. Furthermore, the process jumps from state i to state i + 1 with probability 1, i = 1,2. Assume that the sojourn times of the process in each state are exponential with mean 1 and let T be the first passage time of the process to a state greater than 2. Obviously, P(T > t) = pe-t + (1 - p)e-t(l + t + ) = e-[1 + (1 - p)t + (1 - p)], (2.5) ~(T) = o P(T > t) dt = p + 3(1 - p) = 3 - 2p, (2.6) [oo) 3

and 2 | P(T > t + s) dt = e3[3 - 2p + 2s(1 p) + -(1 - )]. (2.7) J[0,oo) 2 It is easily shown that if p = 0.5, then for all s > 0, ~(T) - E(T - T > s) > 0. However, P(T > 0.5) = 0.7961 and P(T > 1.5 i T > 1) = 0.8015. Hence Z is NBUE but not NBU. The Markov process considered here can be used to model the performance of certain electronic devices. The states 0, 1, 2 and 3 can be used to represent perfect, minor damage, major damage and failure conditions of the unit. The device either fails soon after it is used (fails upon the initial surge of current) or deteriorate gradually until it fails. A similar example to the one given here was also studied by Marshall and Shaked (1983) to show that Markov process with positive skip (sample paths with positive jumps greater than 1) need not be NBU. Z(t) here usually represent the state of a device, and the device fails if the state exceeds a certain level x. The first passage time to level x is therefore the lifetime of a device. However, Z(t) here can also represent the virtual waiting time or work-backlog of a queueing system, inventory level in a warehouse, or the content in a dam. 3 NBUE and NWUE properties of Markov Renewal Processes In this section, we first consider the NBUE and NWUE properties of increasing Markov renewal processes. The results will then be extended to more general Markov renewal processes. It will be shown that a general Markov renewal process can be used to model the accumulated damage to a device that is subjected to both shocks and repairs. Consider a Markov renewal process (X,S) = {X,Sn; n E {0, 1,2,...}} with state space S C {0,1,2,...} and So = 0. Let Z = {Z(t),t > 0} be the semi-Markov process associated with (X,S). This means that S1,S2,... are the successive jump times of Z and X1,X2,... are the successive states visited by Z. Assume that P(supn S, < oo) = 0. Let the family of probabilities Q = {Q(ij,t): i,j E St > 0} be the semi-Markov kernel over S. Assume that EjEsQ(i,j,oo) = 1 for each i E S. Here, Q(i,j,t) is the probability that knowing the 4

current state is i, the next transition state is to state j and the sojourn time in the current state is less than or equal to t. (X,S) is an increasing Markov renewal process (or Z is an increasing semi-Markov process) if Q(i, j, t) = 0 for all i > j and t 0. The embedded process X is then an increasing Markov chain with transition probability Q(i,j,oo) = Q(i,j). Let F(i, t) = ZjEs Q(i, j, t), i.e., it is the distribution of the occupation time during each visit to state i. If Q(i,j) = 0 for some pair (i,j), then Q(i,j,t) = 0 for all t and define Q(i,j,t)/Q(i,j) = 1. With this convention, we define for all i,j E S and t > 0, G(ij,t)- Q(ij)' (3.1) For each pair (i,j), the function t - G(i, j, t) is the distribution function of the occupation time in state i given the next state will be in state j. Let Tax(Z) be the first passage time of the process Z starting from state a at time t = 0 to state x E S. For i,j E S, let 00 R(i,j,t) = E Qn(i,j,t) (3.2) n=O be the Markov renewal function. Hence, R(i, j, t) is the expected number of visits to state j in the finite interval [0, t]. Write Pt(i,j) = P(Z(t) = j I Z(0) = Xo = i) (3.3) and U(i,j,t) = [ o Ij(Z(s))ds I Xo = i = [ P(i,j)ds (3.4) where Ij(k) = 1 or 0 according as k = j or k $ j. Note that U(i,j,t) is called the potential function of Z and it represents the expected time spent in state j during [O,t] by the process starting at i. Furthermore, U(i,j) = U(i,j,oo) = ~[ Ij(Z(s))ds Xo = i = [ Ps(i,j)d. (3.5) Starting at state i, U(i,j) is the total expected time spent in j. From Cinlar (1975a), U(i,j) = R(i,j)m(j) = R(i,j, oo)m(j) (3.6) where m(j) is the mean sojourn time in state j. For notational convenience, we define the cumulative potential matrix, {U(i, j);i,j E S}, by U(ij) = U(i,k). (3.7) k<j 5

Pt(i,j) and R(i,j) are defined similarly. Let N(t) be the number of transitions of the process in the interval (O,t]. Then for all i,j,k E S and t > 0, we have P(XN(t)+l = kXN(t) =j I Xo = i) 00 = ZP(Xn+i = k,Xn = j,N(t)= n IXo = i) n=O oo = P(Xn+l = kc,Xn = j,Sn <_ t < Sn+i I Xo = i) n=O 00oo = o| Qn(i, j ds)P(Xn+l = k, Sn+l - Sn > t - X = ) 00oo = E t] Q(ij, ds)[Q(j,k) - Q(j,k,t - s)] (3.8) =[O 0,t] = R(ij, ds)[Q(jk) - Q(j, kt - s)]. (3.9) Expression (3.9) follows from (3.8) by the monotone convergence theorem. Furthermore, P(XN(t) = Xo = i = R(i,j, ds)[l - F(j,t - s)]. (3.10) The interchange of the summation and integral signs is again justified by the monotone convergence theorem. It follows that R(ij, ds)[Q(j,k) - Q(j,k,t - s)] qi(j, k, t) = P(XN(t)+l = k | XN(t) =, Xo = i) = [O' ] R(i,j, ds)[l - F(j,t - s)] (3.11) Let Mj be the sojourn time of the process in state j, j E S, Wi(j, k, t) = ~(Mj)Ik(j)+ E U(b, k)qi(j, b, t) (3.12) bES and Wi(j,x, t) = W( j, k, t). (3.13) k<x Wi(j,x,t) - Ek<x (Mj)Ik(j) is the expected time of the process (X,S) spent in states below or equal to x during the time interval [SN(t)+l,oo ) given that Xo = i and XN(t) = j. In the case when G(i,j,t) = Q(i,j,t)/Q(i,j) = G(i,t) independent of j for all i,j E S and t > 0, we 6

have F(i,t) = G(i,t), qi(jk,t) = Q(j,k), Wi(j,k,t) = U(j, k) and Wi(j,x,t) = U(j,x) for all i,j,k,x E S and t > 0. Increasing Markov chains and Markov processes are both special cases of increasing Markov renewal processes. A review of the literature in the characterization (PF, densities, IFR, IFRA, NBU) of first passage times of increasing Markov chains and Markov processes are given in Karasu and Ozekici (1989). Furthermore, in their paper, they showed that an increasing Markov process and its the embedded Markov chain are NBUE (NWUE) if U(i,j) and R(i,j) are decreasing (increasing) in i on i < j for all j E S respectively. In the theorems and corollaries below, we study conditions under which an increasing Markov renewal process is NBUE or NWUE. Theorem 3.1 Suppose 1. (X, S) is an increasing Markov renewal process, 2. the sojourn time in state i, Mi, is NBUE for all i E S, 3. U(i,j) > Wi(k,j, t) for all i < k < j, i,j E S and t > O. Then (X, S) is an NBUE Markov renewal process. Proof: By condition (1) of the Theorem, for all t > O, a, x E S and a < x, P(Ta(Z) > t I Xo = a) = P(Z(t) < x I Xo = a) =: P(Z(t) = k Xo = a) = Pt(a,x). a<k<x (3.14) Z or (X, S) is NBUE if p = Pt(a,x) | P.(a x) ds - l Pt+,(a, x) ds > 0. (3.15)'0ooo)'0ooo) Note that Pt+s(a, x) ds = U(a,x) - U(a, x, t) (3.16) [o,oo) 7

is the expected amount of time the process stayed in the set {j E S: a < j < x} in the time interval [t, oo) given that the process starts from state a at the time origin. Furthermore, Pt+sa, x)ds J[ oso ) E= yo P(Z(t + s) = kI Xo = a) ds a<k<x [ )(I) = o ]J yP(Z(t +s) = k Z(t) = u,Xo = a)Pt(a, u)ds a<k<x a,)Z uES = Pt(a,u) / P(Z(t + s) = k I Z(t)= u,Xo = a) a<u<x u<k<x,_ ) (3.17) ds and Pt(a, x) | J[0oo ) P,(a,x)ds= Z Pt(a,u)U(a,x). a<u<x (3.18) For a < u < k < x, J P(Z(t + s) = k I Z(t) = u,Xo = a)ds = [ Ik(Z(s + t))ds I XN(t) = u,Xo = a. (3.19) Equation (3.19) gives the expected time spent in state k during the [t, oo) given that the process starts from state a at time 0 and is in state u at time t. Conditional on XN(t)+l = b E S, Equation (3.19) becomes + [ \ Ik(Z(s)) ds | XN(t) = u,Xo = a],SN( t)+ I ) + [J( SN+l 00) Ik(Z(s))ds I XN(t) = u,X a] 4= t[ t Ik(Z(s)))d XN(t) =u,Xo = a] [t,S N( )+ ) ) + E [s Ik(Z(s)) ds I XN(t)+ = b, XN(t) =, Xo = a]qa(u, b,t). (3.20) bES N( t)+ 1,o) Since SN(t)+l is a stopping time for the semi-Markov process Z and it is semi-regenerative, this means that ~[| f l m IIk(Z(s)) ds I XN(t)+l = b,XN(t) =, Xo = a] [ SN(Lt)+ ) I (,) = E [f Ik(Z(s)) ds | Xo = b] = U(b, k). (3.21) 8

Furthermore, for a < u < k, ~[ \ WIk(Z(s))ds | XN(t) = uXo = a,N(t) = n,SN(t) = s 9 t,SN(t)+I) d ) Ik(u)~[Mu - (t - s) I Mu > (t - )] (3.22) < Ik(u)E[Mu]. (3.23) Equation (3.23) follows from Equation (3.22) because Mu is NBUE. Now partially unconditioning both sides of (3.23) with respect to N(t) = n and SN(t) = s, we have ~\ [SN ) Ik(Z(s))ds I XN(t) = u, Xo = a] Ik(u)[M (3.24) Hence, for a, x E S, p > E Pt(a,u)[U(a, x)- lW(u,x,t)] > (3.25) a<u<x by condition (3) of the Theorem. (X, S) is therefore NBUE. o In the case when G(i, j, t) = G(i, t) independent of j for all i,j E S and t > 0, Condition (3) of the theorem can be replaced by U(i,j) > U(k,j) for all i < k < j, i,j E S. Corollary 3.2 If (X, S) satisfies conditions (1) and (2) of Theorem 3. 1 and in addition, G(i,j, t) = G(i,t) is independent of j for all i,j E S and t > 0, m(i) is decreasing in i and R(i,j) is decreasing in i E S for i < j and j E S, then (X, S) is an NBUE Markov renewal process. Proof: The proof is the same as the proof of Corollary 4.7 for increasing Markov process in Karasu and Ozekici (1989). ~ From Theorem 3.4 of Karasu and Ozekici (1989), if R(i,j) is decreasing in i E S for i < j and j E 5, then the increasing Markov chain X is NBUE. Hence, provided all conditions in Corollary 3.2 hold, the NBUE property of embedded Markov chain X is inherited by the Markov Renewal process (X, S) Obviously, the NWUE characterization of an increasing Markov renewal process can be carried out in a similar fashion. In particular, we have the following theorem. 9

Theorem 3.3 Suppose 1. (X, S) is an increasing Markov renewal process, 2. the sojourn time in state i, Mi, is NWUE for all i E S, 3. U(i,j) < Wi(k,j,t) for all i < k < j, i,j S and t > 0. Then (X, S) is an NWUE Markov renewal process. Corollary 3.4 If(X, S) satisfies conditions (1) and (2) of Theorem 3.3 and in addition, G(i,j, t) = G(i,t) independent of j for all i,j E S and t > 0, m(i) is increasing in i and R(i,j) - R(i,I) is increasing in i E S for all i < j and l,j E S with I < j, then (X,S) is an NWUE Markov renewal process. Proof: The proof is the same as the proof of Corollary 4.9 for increasing Markov process in Karasu and Ozekici (1989). o Again, provided that the conditions in Corollary 3.4 hold, the NWUE property of the increasing Markov chain X is inherited by (X, S). Consider a device that is subjected to shocks and assume that the amount of damage to the device at time t can be modeled by an increasing Markov renewal process, (X, S), with discrete state space S. The device fails when the accumulated damage exceeds x and Z(0) = a < x. The survival function H = 1 - H of the device is given by 00 H(t) = PkP(N(t) = k) (3.26) k=O where N(t) is the number of shocks that occur in the interval (0, t] and Pk = 1 - Pk is the probability of surviving k shocks. Provided that the conditions in Theorem 3.1 hold, the distribution function H is NBUE, i.e., H(t) JI H(s)(s)d H(s)ds. (3.27) [o,oo) [,oo) Furthermore, Pk = Qk(a,j). (3.28) j<x 10

The same argument used in the proof of Theorem 3.4 in Karasu and Ozekici (1989) applies to show that if R(i,j) is decreasing in i E S for i < j and j E S, then Pk is an NBUE sequence, i.e., for j = 0,1,2,..., 00 00 PJEPk E P- (3.29) k=O k=j The shock model considered here is a special case of the shock model discussed in Block and Savits (1978). More generally, let (X, S) be a Markov renewal process (not necessarily increasing) with state space S and semi-Markovian kernel Q. Let Z be the associated semi-Markov process, and define Z(t) = sup{Z(s); 0 < s < t}, (3.30) in other words, Z(t) is the maximum level the process Z has ever attained during [0,t]. We adjoin a distinguished state A to the state space and define XOO = A, S00 = oo. For a subset A of S, define N = inf{n > 1: Xn E A}. Set N = oo if no such N exists. Then FA(i,j,t) = P(XN = j, N < t | Xo = i) (3.31) is the probability that, starting from state i, the process Z enters A for the first time at state j E A and this happens at or before t. For i E S, let Ai = {i,i + 1,i + 2,...}. Then, for all j E Ai and t > 0, Q(i,j,t) = FA,(i,j,t) (3.32) is the probability that the first transition of Z is to state j and this happens before t. From Cinlar (1975b), Z is an increasing semi-Markov process, and Q is the corresponding semiMarkovian kernel. As noted in Cinlar (1975b), FA satisfies the equation FA(i,j,t) = Q(i,j,t)k, ds)F(k,- ) (3.33) where QA(i,k,t) = 0 if k E A and QA(i,k,t) = Q(ik,t) if k E A for all i,k E S, t > 0. This is a Markov renewal equation with defective semi-Markov kernel QA. From Cinlar (1969), it is not difficult to show that the solution of Equation (3.33) exists and is unique. More specifically, for all i,j E S and t > 0, FA(i,j,t):= i7o RA(ik,ds)Q(k,j,t - s) (3.34) k$, 11

where RA(i, j, t) = n= oQn(i,j,t). Now for all a < x, if Tax(Z) is the first passage time of the process Z starting from state a at time t = 0 to state x E S, then P(Tax(Z) > t I Xo = a) = P(Tax(Z) > t I Z(O) = a). (3.35) It follows immediately that Z is NBUE (respectively, NWUE) if and only if the increasing semi-Markov process Z is NBUE (respectively, NWUE). Consider a device that is subjected to both shocks and repairs. Assume that the amount of damage to the device at time t can be modeled by a Markov renewal process, (X, ), with discrete state space S. If Z(Sn) < Z(S,), the device is said to be under repair at time Sn. On the other hand, if Z(Sn) > Z(S;), then at epoch Sn, a shock with magnitude Z(Sn) - Z(S-) affects the device and causes damage. The device fails when the total damage exceeds x and Z(O) = a < x. The survival function H of the device is again given by Equation (3.26) where N(t) is now the number of events that occur during the interval (0, t] in the increasing Markov renewal process Z and Pk = Ej<XQk(a,j). Provided that all the conditions in Theorem (3.1) hold for the increasing semi-Markov process Z, the distribution function H is again NBUE. 4 General NBUE processes The stochastic processes considered in this section are very general. They include Markov renewal processes, shock models considered by Esary, Marshall and Proschan (1973), A-Hameed and Proschan (1975), and Block and Savits (1978), and NBU processes studied by Marshall and Shaked (1983), and Shanthikumar (1984). Let (An, Yn)5 be a sequence of (not necessarily independent and identically distributed) random variables. Suppose Yn are all nonnegative, Sn = t=Yi, n = 1,2,... and So = 0. Let N(t) = sup{n Sn <K t}. We say that {N(t); t > 0} is a point process associated with the sequence (An, Yn)', and at time Sn, an event of magnitude An occurs. For fixed al,..., aj (some of the ai s may be negative) and yl,...,yj (all the yi s are nonnegative), define the sequence (hj((a, y), i = 1,...., j;.)) and ho(.) of deterministic nonnegative real valued functions on R+. 12

Consider the stochastic process {Z(t); t > 0} defined by Z(t) = ho(t) if N(t) = 0 (4.1) Z(t) = (4.1) hN(t)((Ai, Y), i = 1, 2,..., N(t); t - SN(t)) if N(t) > 1 This means that the process moves deterministically between events. The deterministic pattern between events is determined by the location and magnitude of earlier events. In particular, in the time interval [Sj,Sj+i), the function hj governs the behavior of the process. Note that the process Z stays nonnegative. However, unlike Marshall and Shaked (1983), and Shanthikumar (1984), we are not restricting the process to jump an amount An at time Sn. An increasing Markov renewal process is a special case of the general stochastic process introduced here. In particular, it satisfies the following conditions. (An)' is a sequence of discrete random variables taking values on S. Assume Ao = a with probability 1 and for all n > 1, P(An = j I An.1 = i) = Q(i,j). Y(0) = 0 and for n > 1, P(Yn < t I An- = i) = F(i,t). For all n > 1, P(An = j,Yn < t I An-1 = i) = Q(i,j,t). ho(t) = a for all t > 0. For j = 1,2,... and t > 0, hj((Ai,Yi), i = 0,1,...., j; t) = Aj. Before we state sufficient conditions such that the process Z is NBUE, let us define some notations. For each m E {0,1,2,...}, let Sm = Em+L l Yi and Nm(t) = sup{n: Sm < t}. Define the stochastic processes {Zm(t);t > 0} and {Wm(t);t > 0} by Zm(t) Z(Sm+) ho(t) if No(t) = 0 h m+Nm,(t)((AiYi),i = 1,2,..., m + Nm(t); t - S()) otherwise (4.2) and Wm(t) = > ho(t) if Nm(t) = 0 hN,(t)((Am+i,Ym+i),i = 1,2,... Nm(t); t - Sm(t)) if Nm(t) > 1 Observe that Zm is obtained from Z by shifting the origin to Sm. Wm is defined in the same way as Z, but with the sequence (Am+i,Ym+i)i. Also, for t > 0, let Z(t) = maxo<u<t Z(u) and Wm(t) = maxo<<t Wm(u). Z and Wm are therefore transformations of Z and Wm which trace their historical maximum. Let H(Z, t) represents the history of the process Z upto time t. For each x E S, define r, = inf{t: ho(t) > x; t > 0}. Set r7 = oo if no such 7, exists. For 13

n= 1,2,..., define Y t Yn if Yn <_ r Y 1_ (4.4) Tr if Yn > Tx Furthermore, from Shanthikumar (1984), a stochastic process {X(t); t > 0} stochastically dominates a process {Y(t); t > O} (X >st Y) if for every nondecreasing functional f E[f(X)] > E[f(Y)] (4.5) whenever the expectations exist. For Theorem 4.1 below and the examples in this section, we will assume (An, Yn)' is a sequence of independent random variables. Theorem 4.1 Suppose 1. (An,Yn)~ is a sequence of independent random variables. 2. Z(O) = ho(O) = 0 with probability 1. 3. For every realization (ai, yi)' of (Ai, Yi)', we have for all t > 0, (a) hl((al, Yl); t) ho(t), (b) hm+j((ai,yi),i = 1,...,m+j; t) > h((am+i,,ym+i,),i = 1,...,j;t), m = 0,1,2,..., j= 1,2,..., (c) P(hj((Am+i,Ym+l),(am+i,ym+),i = 2,...,j;t) > p I Ym+i > s) > P(hj((Am+l,Ym+l),(am+,m+, i),i = 2,...,j;t) > p), p,s > O, m = 0,1,..., j= 1,2,.... 4. For each x E S and n = 1,2,..., Yn' is NBUE, i.e., ~(YnZ - s Y' > s) < ~(Yn) whenever O < s < /r. 5. j[P(Wm(t) < x)dt <J P(Z(t) < x)dt for all x E S and m = 0,1,2,.... Then {Z(t);t > 0} is an NBUE process. 14

Remarks: 1. Conditions (3(a)) and (3(b)) require Zm(t) > Wm(t) with probability 1 for all t > 0. In most applications, this condition is easily verified. Some examples are given below. Furthermore, we have Z(Sm) > Wm(O) = Z(O) = ho(O). Hence, if Z(t) represents the accumulated damage of a device at time t and events mean repair, this means that a used device cannot be repaired to a better condition than a new one. 2. Condition (3(c)) in the Theorem is weaker than Condition (iv) of Theorem 3.2 in Shanthikumar (1984) for NBU processes. In his paper, he required that P(hj((Am+l,Ym+l),(am+, ym+i), i = 2,...,j;t) > p I Ym+l = si) > P(hj((Am+i,Ym+l),(am+i, ym+),i = 2,...,j;t) > p IYm+l = 52), whenever si > s2, t,p,l1,s2 > 0, m = 0,1,..., j = 1,2,.... 3. Note that if ho(t) = 0 for all t > 0 and Y, is NBUE, n = 1,2,..., then Condition (A) of the theorem holds. Also, if Yn is NBU, n = 1,2,..., then it is trivially true that Y, is also NBU for all x E S. Hence, Yn is NBUE. 4. If (An,,Y,)0 is a pair of renewal sequences, then Z and Wm are the same process distributionally. Condition (5) of Theorem 4.1 always holds. If Wm >st Z, m = 0,1,2,..., then P(Wm(t) < x) < P(Z(t) < x) for all x E S and t > 0. Condition (5) of Theorem 4.1 follows. Section 4 of Shanthikumar (1984) discussed situations such that Wm >st Z holds for independent non-renewal sequences. If Tx(Wm) and Tx(Z) are respectively the first passage times of the processes Wm and Z to level x E S, then Condition (5) of the theorem implies that E(Tx(Wm)) < ~(Tx(Z)) for all x E S. Before the proof of Theorem 4.1 is given, let us look at some examples of the stochastic process Z encountered in applications. Example 1: A random repair time process Suppose (An,Yn)w is a pair of renewal sequences. Let Z(t) represents the wear and repair 15

process of an equipment at time t. Assume that wear starts at 0 at time 0 and the rate of wear, r, is constant independent of time. At time Sn (n > 0), the equipment is repaired and the process Z is set to level max{Z(S-) - An,min{Z(S ), a}} and a > 0. This means that once the equipment is used, it is not possible to repair it to perfect condition. In this example, we have 1. ho(t) = rt, r > O, t > O, 2. hj((A,Yij),i = 1,2,...,j;t) = max{Z(S7j) - Aj,min{Z(S7),a}} + rt, j = 1,2,..., t> 0. Now, provided that Yn is NBU for all n = 1,2,..., it is easily verified that all conditions in Theorem 4.1 are satisfied and Z is therefore NBUE. In general, let a(x,t) be a nonnegative real valued function defined on R+ x R+. Assume that at time S,n the equipment is repaired to level max{Z(Sn)- An, min{Z(Sn), a(Z(S), Sn)}} which depends on both level and age of the equipment. In particular, Z is still NBUE when a(x,t) is monotonically increasing in both x and t. Furthermore, we can also assume the rate of wear to be both level and age dependent (Shanthikumar (1984)), i.e., dZ() = r(Z(t),t), Sn-i < t < Sn,, n = 1,2,... dt r(x, t) here is a nonnegative real valued function defined on R+ x 3+ and it increases on t. Example 2: Inventory model Let Z(t) represents the net inventory level of an item at time t in a warehouse of finite capacity x > 0. Assume Z(O) = 0. At time t, the items are consumed at rate r(Z(t)) > 0 depending on the net inventory position at that time. This means that dZ(t) = -r(Z(t)), Sn-1 < t < Sn n = 1,2,.... dt Assume backlogging is permitted. Z(t) is therefore negative if the backorder level at time t is positive. Furthermore, items are replenished at time S,. The number of items received at time Sn is equal to max{An,-Z(Sn )}, the maximum of the positive random variable An and the backorder level at that time. Let Z+(t) = max{0,Z(t)}. Z+(t) is therefore the on-hand inventory level at time t. Assume that 16

1. (AnY,n) is a pair of renewal sequence. 2. Y, is NBUE, n = 1, 2,..., i.e., given that there is no shipment of items in the last certain period of time, the expected additional time until the next shipment is less than or equal to the expected time between shipments. 3. P(An > p I Yn > s) > P(An > p), n = 1,2,..., p, s > 0. Then from Theorem 4.1, the first passage time of on-hand inventory to level x E S (the time taken to fill up an empty warehouse) is NBUE. Z + is still NBUE even if we assume that the maximum number of backorder permitted is b > 0 (or Z(t) > -b for all t > 0). Example 3: Queueing model Let (A,,Yn)~ be a non-renewal sequence of independent random variables. Let Z(t) represents the work-backlog or the virtual waiting time in a queueing system at time t. Assume Z(0) = 0. At time t, the service rate is r(Z(t)) > 0 depending on the work-backlog at that time. Suppose the nth customer arrives at time Sn increases the work-backlog by An to Z(Sn) + An. Assume that An+1 >~st An, Yn >~t Yn+', and Yn is NBUE, n = 1,2,.... Also, P(An > p I Yn > s) > P(An > p), n = 1, 2,..., p, s > 0. Then from Shanthikumar (1984), Conditions (1) and (2) above implies that Wm >st Z, m = 0,1,2,.... It follows from Theorem 4.1 that the first passage time of the work-backlog to level x E S is NBUE. Proof of Theorem 4.1: For z E S and m = 0,1,2,..., let T; = TX(Wm)- Y+1. (4.6) Consider the conditional expectation E(T(Z) - t I T,(Z) > t,N(t) = m,H(Z, Sm)) = C(T(Z) - S - (t - Sm) I T(Z)- Sm > t- SmN(t) = m,H(Z,Sm)) = (TX(Zm)- (t- Sm) I T(Zm) > t - Sm,N(t) = m,H(Z,Sm)) (4.7) < E(T(Wm)- (t - Sm) I Tx(Wm) > t - SmYm+i > t - Sm > 0) (4.8) = ~(T; I TX(Wm) > t-SmYm+i > t-Sm > 0) 17

+ (Ym+l - (t - Sm) I Tr(Wm) > t - Sm,Ym+1 > t - Sm > 0) = E(T I Ym+1 > t - S 0) + (Y+ -(tS ) I| > t - Sm ) (4.9) < E(T;) + E(YM+l) (4.10) = (TX(Wm)) < ~(TX(Z)). (4.11) Conditions (1), (3(a)) and (3(b)) of the theorem lead (4.7) into (4.8). Note that 1. E(T; I Ym+l > t - Sm > 0) < E(T*) by Conditions (1) and (3(c)) of the theorem, 2. ~(Y+ - (t - S) I Ym+i > t- Sm >_ 0) < ~(Ym+1) because Ym+i and Sm are independent and Y+I is NBUE. Equation (4.10) therefore follows from (4.9). Finally, (4.11) follows from Condition (5) of the theorem. Now partially unconditioning both sides of (4.11) with respect to the history and m (including the case m = 0), we have ~(T(Z) - t I T,(Z) > t) < ~(Tx(Z)). (4.12) C References [1] A-Hameed, M. S. and Proschan, F. (1975) Shock models with underlying birth process. J. Appl. Prob. 12, 18-28. [2] Abdel-Hameed, M. (1984a) Life distribution properties of devices subject to a Levy wear process. Math. Oper. Res. 9, 606-614. [3] Abdel-Hameed, M. (1984b) Life distribution properties of devices subject to a pure jump damage process. J. Appl. Prob. 21, 816-825. [4] Block, H. W. and Savits, T. H. (1978) Shock models with NBUE survival. J. Appl. Prob. 15, 621-628. 18

[5] Block, H. W. and Savits, T. H. (1981) Multidimensional IFRA processes. Ann. Prob. 9, 162-166. [6] Brown, M. and Chaganty, N. R. (1983) On the first passage time distribution for a class of Markov chains. Ann. Prob. 11, 1000-1008. [7] Cinlar, E. (1969) Markov renewal theory. Adv. Appl. Prob. 1, 123-187. [8] Cinlar, E. (1975a) Introduction to stochastic processes., Prentice-Hall, Inc., Englewood Cliffs, New Jersey. [9] Cinlar, E. (1975b) Markov renewal theory: A survey. Management Science 21, 727-752. [10] Derman, C., Ross, S. M. and Scheckner, Z. (1983) A note on first passage times in birth and death and non-negative diffusion processes. Naval Res. Logist. Quart. 30, 283-285. [11] Esary, J. D., Marshall, A. W. and Proschan, F. (1973) Shock models and wear processes. Ann. Prob. 1, 627-650. [12] Karasu, I and Ozekici, S. (1989) NBUE and NWUE properties of increasing Markov processes. J. Appl. Prob. 26, 827-834. [13] Keilson, J. (1979) Markov Chain Models - Rarity and Exponentially. Springer-Verlag, New York. [14] Marshall, A. M. and Shaked, M. (1979) Multivariate shock models for distributions with increasing hazard rate average. Ann. Prob. 7, 343-358. [15] Marshall, A. M. and Shaked, M. (1983) New better than used processes. Adv. Appl. Prob. 15, 601-615. [16] Marshall, A. M. and Shaked, M. (1986) NBU processes with general state space. Math. Operat. Res. 11, 95-109. [17] Ohi, F. and Nishida, T. (1983) Another proof of IFRA property of S. M. Ross' generalized Poisson shock models. Math. Japan. 28, 117-123. 19

[18] Shaked, M. and Shanthikumar, J. G. (1987) IFRA properties of some Markov jump processes with general state space. Math. Operat. Res. 12, 562-568. [19] Shanthikumar, J. G. (1984) Processes with new better than used first passages times. Adv. Appl. Prob. 16, 667-686. 20

UNIVERSITY OF MICHIGAN 90 1 11111047327781 305 04732 7781