Chapter 5RENEWAL PROCESSES5.1 IntroductionRecall that a renewal process is an arrival pro cess in which the interarrival intervals arepositive,1independent and identically distributed (IID) random variables (rv’s). Renewalprocesses (since they are arrival processes) can be specified in three standard ways, first,by the joint distributions of the arrival epochs S1, S2, . . . , second, by the joint distributionsof the interarrival times X1, X2, . . . , and third, by the joint distributions of the countingrv’s, N(t) for t > 0. Recall that N(t) represents the number of arrivals to the system in theinterval (0, t]. Figure 5.1 reviews the connection between the sample values of these rv’s.rrrN(t, !) = n for Sn(!)  t < Sn+1(!)X1(!)-X2(!)-X3(!)-6tN(t, !)0 S1(!) S2(!) S3(!)Figure 5.1: A sample function of an arrival process for a given sample point ! withits arrival epochs {S1(!), S2(!), . . . }, its interarrival times {X1(!), X2(!), . . . }, and itscounting process {N(t, !); t > 0}. The sample function of the counting process is thestep function illustrated with a unit step at each arrival epoch.The simplest characterization is through the interarrival times Xi, since they are IID. Eacharrival epoch Snis simply the sum X1+ X2+ ···+ Xnof n IID rv’s. The characterization1Renewal processes are often defined in a slightly more general way, allowing the interarrival intervals Xito include the possibility 1 > Pr{Xi= 0} > 0. All of the theorems in this chapter are valid under this moregeneral assumption, as can be verified by complicating the proofs somewhat. Allowing Pr{Xi= 0} > 0allows multiple arrivals at the same instant, which makes it necessary to allow N (0) to take on positivevalues, and appears to inhibit intuition about renewals. Exercise 5.3 shows how to view these more generalrenewal processes while using the definition here, thus showing that the added generality is not worth much.2165.1. INTRODUCTION 217of greatest interest in this chapter is the renewal counting process, {N(t); t > 0}. Recallfrom (2.2) and (2.3) that the arrival epochs and the counting rv’s are related in each of thefollowing equivalent ways.{Sn t} = {N(t)  n}; {Sn> t} = {N(t) < n}. (5.1)The reason for calling these processes renewal processes is that the process probabilisticallystarts over at each arrival epoch, Sn. That is, if the nth arrival occurs at Sn= ⌧, then,counting from Sn= ⌧, the jthsubsequent arrival epoch is at Sn+j Sn= Xn+1+ ··· +Xn+j. Thus, given Sn= ⌧ , {N (⌧ + t)  N(⌧); t  0} is a renewal counting process withIID interarrival intervals of the same distribution as the original renewal pro cess. Thisinterpretation of arrivals as renewals will be discussed in more detail later.The major reason for studying renewal processes is that many complicated processes haverandomly occurring instants at which the system returns to a state probabilistically equiva-lent to the starting state. These embedded renewal epochs allow us to separate the long termbehavior of the pro cess (which can be studied through renewal theory) from the behaviorwithin each renewal period.Example 5.1.1 (Visits to a given state for a Markov chain). Assume that a recur-rent finite-state Markov chain with transition matrix [P ] starts in state i at time 0. Then onthe first return to state i, say at time n, the Markov chain, from time n on, is a probabilisticreplica of the chain starting at time 0. That is, the state at time 1 is j with probability Pij,and, given a return to i at time n, the probability of state j at time n + 1 is Pij. In thesame way, for any m > 0,Pr{X1= j, . . . , Xm= k | X0= i} = Pr{Xn+1= j, . . . , Xn+m= k | Xn= i}. (5.2)Each subsequent return to state i at a given time n starts a new probabilistic replica of theMarkov chain starting in state i at time 0, . Thus the sequence of entry times to state i canbe viewed as the arrival epochs of a renewal process.This example is important, and will form the key to the analysis of Markov chains with acountably infinite set of states in Chapter 6. At the same time, (5.2) does not quite justifyviewing successive returns to state i as a renewal process. The problem is that the timeof the first entry to state i after time 0 is a random variable rather than the given time nindicated in (5.2). This will not be a major problem to sort out, but the resolution will bemore insightful after developing some basic properties of renewal processes.Example 5.1.2 (The G/G/m queue:). The customer arrivals to a G/G/m queue forma renewal counting process, {N(t); t > 0}. Each arriving customer enters one of the mservers if the server is not busy and otherwise waits in a common queue with first-comefirst-serve service until a server becomes free. The service time required by each customeris a rv, IID over customers, and independent of arrival times and servers. The system isassumed to be empty for t < 0, and an arrival, viewed as customer number 0, is assumed attime 0. The subsequent interarrival intervals X1, X2, . . . , are IID. Note that N(t) for eacht > 0 is the number of arrivals in (0, t], so arrival numb er 0 at t = 0 is not counted in N(t).22There is always a certain amount of awkwardness in ‘starting’ a renewal process, and the assumption of218 CHAPTER 5. RENEWAL PROCESSESWe define a new counting process, {Nr(t); t > 0}, for which the renewal epochs are thosearrival epochs in the original arrival process {N(t); t > 0} at which an arriving customersees an empty system (i.e., no customer in queue and none in service).3We will showin Section 5.5.3 that {Nr(t) t > 0} is actually a renewal process, but give an intuitiveexplanation here. Note that customer 0 arrives at time 0 to an empty system, and given afirst subsequent arrival to an empty system, at say epoch Sr1> 0, the subsequent customerinterarrival intervals are independent of the arrivals in (0, Sr1) and are identically distributedto those earlier arrivals. The service times after Sr1are also IID from those earlier. Finally,the number of customers in the queue is the same function of inter-arrival intervals andservice completions for the system staring at time 0 as for any subsequent arrival to anempty system.In most situations, we use the words arrivals and renewals interchangably, but for this typeof example, the word arrival is used for the counting process {N(t); t > 0} of the actualarrivals to the queueing system and the word renewal is used for {Nr(t); t > 0}. The