Chapter 3RENEWAL PROCESSES3.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}. (3.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 3.3 shows how to view these more generalrenewal processes while using the definition here, thus showing that the added generality is not worth much.1063.1. INTRODUCTION 107lent 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 3.1.1. Consider a 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 customer isa rv, IID over customers, and independent of arrival times and servers. We define a newrenewal counting process, {N0(t); t ≥ 0}, for which the renewal ep ochs are those particulararrival epochs in the original process {N(t); t > 0} at which an arriving customer sees anempty system2(i.e., no customer in queue and none in service). To make the time originprobabilistically identical to the renewal epochs in this new renewal process, we assumethat a customer arrives to an empty queue at time 0, but does not count as an arrival in(0, t]. There are two renewal counting processes, {N(t); t > 0} and {N0(t); t ≥ 0} in thisexample, and the renewals in the second process are those particular customer arrivals thatarrive to an empty system. In most situations, we use the words arrivals and renewalsinterchangably. For this type of example, the word arrival is used for the counting process{N(t); t > 0} and the word renewal is used for {N0(t); t > 0}.Throughout our study of renewal processes, we use X and E [X] interchangeably to denotethe mean inter-renewal interval, and use σ2to denote the variance of the inter-renewalinterval. We will usually assume that X is finite, but, except where explicitly stated, weneed not assume that σ2is finite. This means, first, that σ2need not be calculated (whichis often difficult if renewals are embedded into a more complex process), and second, sincemo deling errors on the far tails of the inter-renewal distribution typically affect σ2morethan X, the results are relatively robust to these kinds of modeling errors.Much of this chapter will be devoted to understanding the behavior of N(t) and N(t)/t as tbecomes large. As might appear to be intuitively obvious, and as is proven in Exercise 3.1,N(t) is a rv (i.e., not defective). Also, as proven in Exercise 3.2 E [N(t)] < 1 for all t > 0.It is then also clear that N(t)/t, which is interpreted as the time-average renewal rate over(0,t], is also a rv with finite expectation.One of the major results about renewal theory, which we establish shortly, is that, withprobability 1, the family of random variables, {N(t)/t; t > 0}, has a limiting value,limt→1N(t)/t, equal to 1/ X. This result is called the strong law of large numbers forrenewal processes. We shall often refer to it by the less precise statement that the time-average renewal rate is 1/ X. This result is an analog (and direct consequence) of the stronglaw of large numbers, Theorem 1.6.Another important result is the elementary renewal theorem, which states that E[N(t)/t]also approaches 1/X as t → 1. It seems surprising that this does not follow easily from thestrong law for renewal processes, but in fact it doesn’t, and we shall develop several widelyuseful results such as Wald’s equality, in establishing this theorem. The final major result2Readers who accept without question that {N0(t) t > 0} is a renewal process here should feel happyabout their probabilistic intuition, but should be concerned about a certain degree of carelessness. We returnlater to provide a sound argument why {N0(t) t > 0} is indeed a renewal process.108 CHAPTER 3. RENEWAL PROCESSESis Blackwell’s theorem, which shows that, for appropriate values of δ, the expected numberof renewals in an interval (t, t + δ] approaches δ/X as t → 1. We shall thus interpret1/X as an ensemble-average renewal rate. This rate is the same as the above time-averagerenewal rate. We shall see the benefits of being able to work with both time-averages andensemble-averages.3.2 Strong law of large numbers for renewal processesTo get an