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].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 characterizationof 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-1Renewal processes are often defined in a slightly more general way, allowing the interarrival intervals Xito include the p ossibility 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.2185.1. INTRODUCTION 219lent 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). Suppose a recurrent finite-state Markov chain with transition matrix [P ] starts in state i at time 0. Then on the firstreturn to state i, say at time n, the Markov chain, from time n on, is a probabilistic replicaof 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 the sameway, 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 time ofthe first entry to state i after time 0 is a random variable rather than a given time n. Thiswill not be a major problem to sort out, but the resolution will be more insightful afterdeveloping 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 waits in the queue untilone of m identical servers is free to serve it. 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).2We define a new counting process, {Nr(t); t > 0}, for which the renewal epochs are thoseparticular arrival epochs in the original 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 conditions that cause queueing starting from the arrival to an empty system at t = Sr1are the same as those starting from the arrival to an empty system at t = 0.2There is always a certain amount of awkwardness in ‘starting’ a renewal process, and the assumption ofan arrival at time 0 which is not counted in N(t) seems strange, but simplifies the notation. The process isdefined in terms of the IID inter-renewal intervals X1, X2, . . . . The first renewal epoch is at S1= X1, andthis is the point at which N (t) changes from 0 to 1.3Readers who accept without question that {Nr(t) t > 0} is a renewal process should be proud of theirprobabilistic intuition, but should also question exactly how such a conclusion can be proven.220 CHAPTER 5. RENEWAL PROCESSESIn most situations, we use the words arrivals and renewals interchangably, but for thistype of example, the word arrival is used for the counting process {N(t); t > 0} and theword renewal is used for {Nr(t); t > 0}. The reason for being interested in {Nr(t); t >0} is that it allows us to analyze very complicated queues such as this in two stages.First, {N(t); t > 0} lets us analyze the distribution of the inter-renewal intervals