Chapter 4 RENEWAL PROCESSES 4.1 Introduction Recall that a renewal process is an arrival process in which the interarrival intervals are positive,1 independent and identically distributed (IID) random variables (rv’s). Renewal processes (since they are arrival processes) can be speciﬁed in three standard ways, ﬁrst, by the joint distributions of the arrival epochs S1 , S2 , . . . , second, by the joint distributions of the interarrival times X1 , X2 , . . . , and third, by the joint distributions of the counting rv’s, N (t) for t > 0. Recall that N (t) represents the number of arrivals to the system in the interval (0, t]. The simplest characterization is through the interarrival times Xi , since they are IID. Each arrival epoch Sn is simply the sum X1 + X2 + · · · + Xn of n IID rv’s. The characterization of greatest interest in this chapter is the renewal counting process, {N (t); t > 0}. Recall from (2.2) and (2.3) that the arrival epochs and the counting rv’s are related in each of the following equivalent ways. {Sn ≤ t} = {N (t) ≥ n}; {Sn > t} = {N (t) < n}. (4.1) The reason for calling these processes renewal processes is that the process probabilistically starts over at each arrival epoch, Sn . That is, if the nth arrival occurs at Sn = τ , then, counting from Sn = τ , the j th subsequent arrival epoch is at Sn+j − Sn = Xn+1 + · · · + Xn+j . Thus, given Sn = τ , {N (τ + t) − N (τ ); t ≥ 0} is a renewal counting process with IID interarrival intervals of the same distribution as the original renewal process. This interpretation of arrivals as renewals will be discussed in more detail later. The major reason for studying renewal processes is that many complicated processes have randomly occurring instants at which the system returns to a state probabilistically equiva 1 Renewal processes are often deﬁned in a slightly more general way, allowing the interarrival intervals Xi to include the possibility 1 > Pr{Xi = 0} > 0. All of the theorems in this chapter are valid under this more general assumption, as can be veriﬁed by complicating the proofs somewhat. Allowing Pr{Xi = 0} > 0 allows multiple arrivals at the same instant, which makes it necessary to allow N (0) to take on positive values, and appears to inhibit intuition about renewals. Exercise 4.3 shows how to view these more general renewal processes while using the deﬁnition here, thus showing that the added generality is not worth much. 156 4.1. INTRODUCTION 157 lent to the starting state. These embedded renewal epochs allow us to separate the long term behavior of the process (which can be studied through renewal theory) from the behavior within each renewal period. Example 4.1.1 (Visits to a given state for a Markov chain). Suppose a recurrent ﬁnitestate Markov chain with transition matrix [P ] starts in state i at time 0. Then on the ﬁrst return to state i, say at time n, the Markov chain, from time n on, is a probabilistic replica 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 the same way, for any m > 0, Pr{X1 = j, . . . , Xm = k | X0 = i} = Pr{Xn+1 = j, . . . , Xn+m = k | Xn = i} . (4.2) Each subsequent return to state i at a given time n starts a new probabilistic replica of the Markov chain starting in state i at time 0, . Thus the sequence of entry times to state i can be 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 a countably inﬁnite set of states in Chapter 5. At the same time, (4.2) does not quite justify viewing successive returns to state i as a renewal process. The problem is that the time of the ﬁrst entry to state i after time 0 is a random variable rather than a given time n. This will not be a major problem to sort out, but the resolution will be more insightful after developing some basic properties of renewal processes. Example 4.1.2 (The G/G/m queue:). The customer arrivals to a G/G/m queue form a renewal counting process, {N (t); t > 0}. Each arriving customer waits in the queue until one of m identical servers is free to serve it. The service time required by each customer is a rv, IID over customers, and independent of arrival times and servers. The system is assumed to be empty for t < 0, and an arrival, viewed as customer number 0, is assumed at time 0. The subsequent interarrival intervals X1 , X2 , . . . , are IID. Note that N (t) for each t > 0 is the number of arrivals in (0, t], so arrival number 0 at t = 0 is not counted in N (t).2 We deﬁne a new counting process, {N r (t); t > 0}, for which the renewal epochs are those particular arrival epochs in the original process {N (t); t > 0} at which an arriving customer sees an empty system (i.e., no customer in queue and none in service).3 We will show in Section 4.5.3 that {N r (t) t > 0} is actually a renewal process, but give an intuitive explanation here. Note that customer 0 arrives at time 0 to an empty system, and given a ﬁrst subsequent arrival to an empty system, at say epoch S1r > 0, the subsequent customer interarrival intervals are independent of the arrivals in (0, S1r ) and are identically distributed to those earlier arrivals. The service times after S1r are also IID from those earlier. Finally, the conditions that cause queueing starting from the arrival to an empty system at t = S1r are the same as those starting from the arrival to an empty system at t = 0. 2 There is always a certain amount of awkwardness in ‘starting’ a renewal process, and the assumption of an arrival at time 0 which is not counted in N (t) seems strange, but simpliﬁes the notation. The process is deﬁned in terms of the IID inter-renewal intervals X1 , X2 , . . . . The ﬁrst renewal epoch is at S1 = X1 , and this is the point at which N (t) changes from 0 to 1. 3 Readers who accept without question that {N r (t) t > 0} is a renewal process should be proud of their probabilistic intuition, but should also question exactly how such a conclusion can be proven. 158 CHAPTER 4. RENEWAL PROCESSES In most situations, we use the words arrivals and renewals interchangably, but 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 {N r (t); t > 0}. The reason for being interested in {N r (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 Xnr of {N r (t); t > 0}. Second, the general renewal results developed in this chapter can be applied to the distribution on Xnr to understand the overall behavior of the queueing system. Throughout our study of renewal processes, we use X and E [X] interchangeably to denote 2 or simply σ 2 to denote the variance of the the mean inter-renewal interval, and use σX inter-renewal interval. We will usually assume that X is ﬁnite, but, except where explicitly stated, we need not assume that σ 2 is ﬁnite. This means, ﬁrst, that σ 2 need not be calculated (which is often diﬃcult if renewals are embedded into a more complex process), and second, since modeling errors on the far tails of the inter-renewal distribution typically aﬀect σ 2 more than 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 t becomes large. As might appear to be intuitively obvious, and as is proven in Exercise 4.1, N (t) is a rv (i.e., not defective) for each t > 0. Also, as proven in Exercise 4.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 ﬁnite expectation. One of the major results about renewal theory, which we establish shortly, concerns the behavior of the rv’s N (t)/t as t → 1. For each sample point ω ∈ ≠, N (t, ω)/t is a nonnegative number for each t and {N (t, ω); t > 0} is a sample path of the counting renewal process, taken from (0, t] for each t. Thus limt→1 N (t, ω)/t, if it exists, is the time-average renewal rate over (0, 1) for the sample point ω. The strong law for renewal processes states that this limiting time-average renewal rate exists for a set of ω that has probability 1, and that this limiting value is 1/X. We shall often refer to this result by the less precise statement that the time-average renewal rate is 1/ X. This result is a direct consequence of the strong law of large numbers (SLLN) for IID rv’s. In the next section, we ﬁrst state and prove the SLLN for IID rv’s and then establish the strong law for renewal processes. Another important theoretical result in this chapter is the elementary renewal theorem, which states that E [N (t)/t] also approaches 1/X as t → 1. Surprisingly, this is more than a trival consequence of the strong law for renewal processes, and we shall develop several widely useful results such as Wald’s equality, in establishing this theorem. The ﬁnal major theoretical result of the chapter is Blackwell’s theorem, which shows that, for appropriate values of δ, the expected number of renewals in an interval (t, t + δ] approaches δ/X as t → 1. We shall thus interpret 1/X as an ensemble-average renewal rate. This rate is the same as the above time-average renewal rate. We shall see the beneﬁts of being able to work with both time-averages and ensemble-averages. There are a wide range of other results, ranging from standard queueing results to results that are needed in all subsequent chapters. 4.2. THE STRONG LAW OF LARGE NUMBERS AND CONVERGENCE WP1 4.2 159 The strong law of large numbers and convergence WP1 The concept of a sequence of rv’s converging with probability 1 (WP1) was introduced brieﬂy in Section 1.5.6. We discuss this type of convergence more fully here and establish some conditions under which it holds. Next the strong law of large numbers (SLLN) is stated for IID rv’s (this is essentially the result that the partial sample averages of IID rv’s converge to the mean WP1). A proof is given under the added condition that the rv’s have a ﬁnite fourth moment. Finally, in the following section, we state the strong law for renewal processes and use the SLLN for IID rv’s to prove it. 4.2.1 Convergence with probability 1 (WP1) Recall that a sequence {Zn ; n ≥ 1} of rv’s on a sample space ≠ is deﬁned to converge WP1 to a rv Z on ≠ if n o Pr ω ∈ ≠ : lim Zn (ω) = Z(ω) = 1, n→1 i.e., if the set of sample sequences {Zn (ω); n ≥ 1} that converge to Z(ω) has probability 1. This becomes slightly easier to understand if we deﬁne Yn = Zn −Z for each n. The sequence {Yn ; n ≥ 1} then converges to 0 WP1 if and only if the sequence {Zn ; n ≥ 1} converges to Z WP1. Dealing only with convergence to 0 rather than to an arbitrary rv doesn’t cut any steps from the following proofs, but it simpliﬁes the notation and the concepts. We start with a simple lemma that provides a useful condition under which convergence to 0 WP1 occurs. We shall see later how to use this lemma in an indirect way to prove the SLLN. Lemma 4.2.1. Let {Yn ; n ≥ 1} be a sequence of rv’s, each with ﬁnite expectation. If P1 E [|Y n |] < 1, then Pr{ω : limn→1 Yn (ω) = 0} = 1. n=1 Proof: For any α, 0 < α < 1 and any integer m ≥ 1, the Markov inequality says that Pr ( m X n=1 |Yn | > α ) P Pm E[ m n=1 |Yn |] n=1 E [|Yn |] ≤ = . α α (4.3) P Pm+1 Since |Yn | is non-negative, m n=1 |Yn | > α implies that n=1 |Yn | > α. Thus the left side of (4.3) is nondecreasing in m and we can go to the limit lim Pr m→1 Now let Am = {ω : Pm ( m X n=1 n=1 |Yn (ω)| |Yn | > α ) ≤ P1 n=1 E [|Yn |] α . > α}. As seen above, the sequence {Am ; m ≥ 1} is 160 CHAPTER 4. RENEWAL PROCESSES nested, A1 ⊆ A2 · · · , so from property (1.9) of the axioms of probability,4 (m ) n[1 o X lim Pr |Yn | > α = Pr Am m→1 m=1 n=1 n X1 o = Pr ω : |Yn (ω)| > α , n=1 (4.4) P1 where we have used the fact that for any given ω, n=1 |Yn (ω)| > α if and only if Pm n=1 |Yn (ω)| > α for some m ≥ 1. Combining (4.3) with (4.4), ( ) P1 1 X n=1 E [|Yn |] . Pr ω : |Yn (ω)| > α ≤ α n=1 P Looking at the complementary set and assuming α > 1 n=1 E [|Yn |], ( ) P1 1 X E [|Yn |] . Pr ω : |Yn (ω)| ≤ α ≥ 1 − n=1 α n=1 (4.5) P For any ω such that 1 n=1 |Yn (ω)| ≤ α, we see that {|Yn (ω)|; n ≥ 1} is simply a sequence of non-negative numbers with a ﬁnite sum. Thus the individual numbers in that sequence must approach 0, i.e., limn→1 |Yn (ω)| = 0 for each such ω. It follows then that ( ) 1 n o X Pr ω : lim |Yn (ω)| = 0 ≥ Pr ω : |Yn (ω)| ≤ α . n→1 n=1 Combining this with (4.5), P1 n o E [|Yn |] Pr ω : lim |Yn (ω)| = 0 ≥ 1 − n=1 . n→1 α This is true for all α, so Pr{ω : limn→1 |Yn | = 0} = 1, and thus Pr{ω : limn→1 Yn = 0} = 1. It is instructive to recall Example 1.5.1, illustrated in Figure 4.1, where {Yn ; n ≥ 1} con verges in probability but does not converge with probability one. P Note that E [Yn ] = 1/(5j+1 − 1) for n ∈ [5j , 5j+1 ). Thus limn→1 E [Yn ] = 0, but 1 n=1 E [Yn ] = 1. Thus this sequence does not satisfy the conditions of the lemma. This helps explain how the conditions in the lemma exclude such sequences. Before proceeding to the SLLN, we want to show that convergence WP1 implies convergence in probability. We give an incomplete argument here with precise versions both in Exercise 4.5 and Exercise 4.6. Exercise 4.6 has the added merit of expressing the set {ω : limn Yn (ω) = 0} explicitly in terms of countable unions and intersections of simple events involving ﬁnite sets of the Yn . This representation is valid whether or not the conditions of the lemma are satisﬁed and shows that this set is indeed an event. 4 This proof probably appears to be somewhat nitpicking about limits. The reason for this is that the argument is quite abstract and it is diﬃcult to develop the kind of intuition that ordinarily allows us to be somewhat more casual. 4.2. THE STRONG LAW OF LARGE NUMBERS AND CONVERGENCE WP1 161 1 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 1 5 25 Figure 4.1: Illustration of a sample path of a sequence of rv’s {Yn ; n ≥ 0} where, for each j ≥ 0, Yn = 1 for an equiprobable choice of n ∈ [5j , 5j+1 ) and Yn = 0 otherwise. Assume that {Yn ; n ≥ 1} is a sequence of rv’s such that limn→1 (Yn ) = 0 WP1. Then for any ≤ > 0, each sample sequence {Yn (ω); n ≥ 1} that converges to 0 satisﬁes |Yn | ≤ ≤ for all suﬃciently large n. This means (see Exercise 4.5) that limn→1 Pr{|Yn | ≤ ≤} = 1. Since this is true for all ≤ > 0, {Yn ; n ≥ 0} converges in probability to 0. 4.2.2 Strong law of large numbers (SLLN) We next develop the strong law of large numbers. We do not have the mathematical tools to prove the theorem in its full generality, but will give a fairly insightful proof under the additional assumption that the rv under discussion has a ﬁnite 4th moment. The theorem has a remarkably simple and elementary form, considering that it is certainly one of the most important theorems in probability theory. Most of the hard work in understanding the theorem comes from understanding what convergence WP1 means, and that has already been discussed. Given this understanding, the theorem is relatively easy to understand and surprisingly easy to prove (assuming a 4th moment). Theorem 4.2.1 (Strong Law of Large Numbers (SLLN )). For each integer n ≥ 1, let Sn = X1 + · · · + Xn , where X1 , X2 , . . . are IID rv’s satisfying E [|X|] < 1. Then æ Ω Sn (ω) Pr ω : lim = X = 1. (4.6) n→1 n £ § Proof (for the case where X = 0 and E X 4 < 1): £ § £ § Assume that X = 0 and E X 4 < 1. Denote E X 4 by ∞. For any real number x, if 2 2 4 2 4 |x| ≤ 1,£ then £ . 4 §Thus x ≤ 1 + x for all x. It follows § x ≤ 1,£ and § if |x| > 21, then x < x 2 2 4 σ = E X ≤ 1 + E X . Thus σ is ﬁnite if E X is. Now let Sn = X1 + · · · + Xn where X1 , . . . , Xn are IID with the distribution of X. £ § E Sn4 = E [(X1 + · · · + Xn )(X1 + · · · + Xn )(X1 + · · · + Xn )(X1 + · · · + Xn )] √ √ ! n !√ n ! n n X X X X = E Xi  Xj  Xk X`  i=1 = n X n X n X n X i=1 j=1 k=1 `=1 j=1 k=1 E [Xi Xj Xk X` ] , `=1 162 CHAPTER 4. RENEWAL PROCESSES where we have multiplied out the product of sums to get a sum of n4 terms. For each i, 1 ≤ i ≤£n, there is a term in this sum with i = j = k = `. For each such term, § E [Xi Xj Xk X` ] = E X 4 = ∞. There are n such terms £ 4 §(one for each choice of i, 1 ≤ i ≤ n) and they collectively contribute n∞ to the sum E Sn . Also, for each i, k = 6 i, there is a term with j = i and ` = k. For each of these n(n − 1) terms, E [Xi Xi Xk Xk ] = σ 4 . There are another n(n − 1) terms with j 6= i and k = i, ` = j. Each such term contributes σ 4 to the sum. Finally, for each i 6= j, there is a term with ` = i and k = j. Collectively all of these terms contribute 3n(n − 1)σ 4 to the sum. Each of the remaining terms is 0 since at least one of i, j, k, ` is diﬀerent from all the others, Thus we have £ § E Sn4 = n∞ + 3n(n − 1)σ 4 . Now consider the sequence of rv’s {Sn4 /n4 ; n ≥ 1}. ∑Ø 4 Ø∏ 1 1 X X ØS Ø n∞ + 3n(n − 1)σ 4 E ØØ n4 ØØ = < 1, n n4 n=1 n=1 where we have used the facts that the series P 2 n≥1 1/n and the series P 3 n≥1 1/n converge. Using Lemma 4.2.1 applied to {Sn4 /n4 ; n ≥ 1}, we see that limn→1 Sn4 /n4 = 0 WP1. For each ω such that limn→1 Sn4 (ω)/n4 = 0, the nonnegative fourth root of that sequence of nonnegative numbers also approaches 0. Thus limn→1 |Sn /n| = 0 WP1. The above proof assumed that E [X] = 0. It can be extended trivially to the case of an arbitrary ﬁnite X by replacing X in the proof with X − X. A proof using the weaker 2 < 1 will be given in Section 7.9.1. condition that σX The technique that was used at the end of this proof provides a clue about why the con cept of convergence WP1 is so powerful. The technique showed that if one sequence of rv’s ({Sn4 /n4 ; n ≥ 1}) converges to 0 WP1, then another sequence (|Sn /n|; n ≥ 1}) also converges WP1. We will formalize and generalize this technique in Lemma 4.3.2 as a major step toward establishing the strong law for renewal processes. 4.3 Strong law for renewal processes To get an intuitive idea why N (t)/t should approach 1/X for large t, consider Figure 4.2. For any given sample function of {N (t); t > 0}, note that, for any given t, N (t)/t is the slope of a straight line from the origin to the point (t, N (t)). As t increases, this slope decreases in the interval between each adjacent pair of arrival epochs and then jumps up at the next arrival epoch. In order to express this as an equation, note that t lies between the N (t)th arrival (which occurs at SN (t) ) and the (N (t) + 1)th arrival (which occurs at SN (t)+1 ). Thus, for all sample points, N (t) N (t) N (t) ≥ > . SN (t)+1 SN (t) t (4.7) 4.3. STRONG LAW FOR RENEWAL PROCESSES Slope = Slope = N (t) t 163 N (t) SN (t) ✘ ❅ ✘✘✘ ✘ ❄ ✘ ✘ SN (t)+1 ❅ ❘✘✘✘ ❅ ❆ ✘ ✘ ❆❆ ✘✘✘ ✘✘ ✘ t ✘ ✘ N (t) 0 SN (t)+1 Slope = N (t) S1 SN (t) (t) and SNN(t)+1 for the same sample point. Note that for the given sample point, N (t) is the number of arrivals up to and including t, and thus SN (t) is the epoch of the last arrival before or at time t. Similarly, SN (t)+1 is the epoch of the ﬁrst arrival strictly after time t. Figure 4.2: Comparison of a sample function of N (t)/t with N (t) SN (t) We want to show intuitively why the slope N (t)/t in the ﬁgure approaches 1/X as t → 1. As t increases, we would guess that N (t) increases without bound, i.e., that for each arrival, another arrival occurs eventually. Assuming this, the left side of (4.7) increases with increasing t as 1/S1 , 2/S2 , . . . , n/Sn , . . . , where n = N (t). Since Sn /n converges to X WP1 from the strong law of large numbers, we might be brave enough or insightful enough to guess that n/Sn converges to 1/X. We are now ready to state the strong law for renewal processes as a theorem. Before proving the theorem, we formulate the above two guesses as lemmas and prove their validity. Theorem 4.3.1 (Strong Law for Renewal Processes). For a renewal process with mean inter-renewal interval X < 1, limt→1 N (t)/t = 1/X WP1. Lemma 4.3.1. Let {N (t); t > 0} be a renewal counting process with inter-renewal rv’s {Xn ; n ≥ 1}. Then (whether or not X < 1), limt→1 N (t) = 1 WP1 and limt→1 E [N (t)] = 1. Proof of Lemma 4.3.1: Note that for each sample point ω, N (t, ω) is a nondecreasing real-valued function of t and thus either has a ﬁnite limit or an inﬁnite limit. Using (4.1), the probability that this limit is ﬁnite with value less than any given n is lim Pr{N (t) < n} = lim Pr{Sn > t} = 1 − lim Pr{Sn ≤ t} . t→1 t→1 t→1 Since the Xi are rv’s, the sums Sn are also rv’s (i.e., nondefective) for each n (see Section 1.3.7), and thus limt→1 Pr{Sn ≤ t} = 1 for each n. Thus limt→1 Pr{N (t) < n} = 0 for each n. This shows that the set of sample points ω for which limt→1 N (t(ω)) < n has probability 0 for all n. Thus the set of sample points for which limt→1 N (t, ω) is ﬁnite has probability 0 and limt→1 N (t) = 1 WP1. Next, E [N (t)] is nondecreasing in t, and thus has either a ﬁnite or inﬁnite limit as t → 1. For each n, Pr{N (t) ≥ n} ≥ 1/2 for large enough t, and therefore E [N (t)] ≥ n/2 for such t. Thus E [N (t)] can have no ﬁnite limit as t → 1, and limt→1 E [N (t)] = 1. The following lemma is quite a bit more general than the second guess above, but it will be useful elsewhere. This is the formalization of the technique used at the end of the proof of the SLLN. 164 CHAPTER 4. RENEWAL PROCESSES Lemma 4.3.2. Let {Zn ; n ≥ 1} be a sequence of rv’s such that limn→1 Zn = α WP1. Let f be a real valued function of a real variable that is continuous at α. Then lim f (Zn ) = f (α) WP1. n→1 (4.8) Proof of Lemma 4.3.2: First let z1 , z2 , . . . , be a sequence of real numbers such that limn→1 zn = α. Continuity of f at α means that for every ≤ > 0, there is a δ > 0 such that |f (z) − f (α)| < ≤ for all z such that |z − α| < δ. Also, since limn→1 zn = α, we know that for every δ > 0, there is an m such that |zn − α| ≤ δ for all n ≥ m. Putting these two statements together, we know that for every ≤ > 0, there is an m such that |f (zn )−f (α)| < ≤ for all n ≥ m. Thus limn→1 f (zn ) = f (α). If ω is any sample point such that limn→1 Zn (ω) = α, then limn→1 f (Zn (ω)) = f (α). Since this set of sample points has probability 1, (4.8) follows. Proof of Theorem 4.3.1, Strong law for renewal processes: Since Pr{X > 0} = 1 for a renewal process, we see that X > 0. Choosing f (x) = 1/x, we see that f (x) is continuous at x = X. It follows from Lemma 4.3.2 that lim n→1 n 1 = Sn X WP1. From Lemma 4.3.1, we know that limt→1 N (t) = 1 with probability 1, so, with probability 1, N (t) increases through all the nonnegative integers as t increases from 0 to 1. Thus N (t) n 1 = lim = n→1 Sn t→1 SN (t) X lim WP1. Recall that N (t)/t is sandwiched between N (t)/SN (t) and N (t)/SN (t)+1 , so we can complete the proof by showing that limt→1 N (t)/SN (t)+1 = 1/X. To show this, lim t→1 N (t) n n+1 n 1 = lim = lim = n→1 Sn+1 n+1 SN (t)+1 n→1 Sn+1 X WP1. We have gone through the proof of this theorem in great detail, since a number of the techniques are probably unfamiliar to many readers. If one reads the proof again, after becoming familiar with the details, the simplicity of the result will be quite striking. The theorem is also true if the mean inter-renewal interval is inﬁnite; this can be seen by a truncation argument (see Exercise 4.8). As explained in Section 4.2.1, Theorem 4.3.1 also implies © the corresponding™ weak law of large numbers for N (t), i.e., for any ≤ > 0, limt→1 Pr |N (t)/t − 1/X| ≥ ≤ = 0). This weak law could also be derived from the weak law of large numbers for Sn (Theorem 1.5.3). We do not pursue that here, since the derivation is tedious and uninstructive. As we will see, it is the strong law that is most useful for renewal processes. Figure 4.3 helps give some appreciation of what the strong law for N (t) says and doesn’t say. The strong law deals with time-averages, limt→1 N (t, ω)/t, for individual sample points ω; 4.3. STRONG LAW FOR RENEWAL PROCESSES 165 these are indicated in the ﬁgure as horizontal averages, one for each ω. It is also of interest to look at time and ensemble-averages, E [N (t)/t], shown in the ﬁgure as vertical averages. Note that N (t, ω)/t is the time-average number of renewals from 0 to t, whereas E [N (t)/t] averages also over the ensemble. Finally, to focus on arrivals in the vicinity of a particular time t, it is of interest to look at the ensemble-average E [N (t + δ) − N (t)] /δ. Given the strong law for N (t), one would hypothesize that E [N (t)/t] approaches 1/X as t → 1. One might also hypothesize that limt→1 E [N (t + δ) − N (t)] /δ = 1/X, subject to some minor restrictions on δ. These hypotheses are correct and are discussed in detail in what follows. This equality of time-averages and limiting ensemble-averages for renewal processes carries over to a large number of stochastic processes, and forms the basis of ergodic theory. These results are important for both theoretical and practical purposes. It is sometimes easy to ﬁnd time averages (just like it was easy to ﬁnd the time-average N (t, ω)/t from the strong law of large numbers), and it is sometimes easy to ﬁnd limiting ensemble-averages. Being able to equate the two then allows us to alternate at will between time and ensemble-averages. Ensemble Average at t Time and ensemble Average over (0, τ ) (1/δ)E [N (t + δ) − N (t)] N (t,ω1 ) t ✲ Time Ave. at ω1 0 N (t,ω2 ) t ✲ Time Ave. at ω2 0 N (t,ω3 ) t 0 ✲ Time Ave. at ω3 τ t Figure 4.3: The time average at a sample point ω, the time and ensemble average from 0 to a given τ , and the ensemble-average in an interval (t, t + δ]. Note that in order to equate time-averages and limiting ensemble-averages, quite a few con ditions are required. First, the time-average must exist in the limit t → 1 with probability one and also have a ﬁxed value with probability one; second, the ensemble-average must approach a limit as t → 1; and third, the limits must be the same. The following example, for a stochastic process very diﬀerent from a renewal process, shows that equality between time and ensemble averages is not always satisﬁed for arbitrary processes. Example 4.3.1. Let {Xi ; i ≥ 1} be a sequence of binary IID random variables, each taking the value 0 with probability 1/2 and 2 with probability 1/2. Let {Mn ; n ≥ 1} be the product process in which Mn = X1 X2 · · · Xn . Since Mn = 2n if X1 to Xn each take the value 2 (an event of probability 2−n ) and Mn = 0 otherwise, we see that limn→1 Mn = 0 with probability 1. Also E [Mn ] = 1 for all n ≥ 1. Thus the time-average exists and equals 0 with probability 1 and the ensemble-average exists and equals 1 for all n, but the two are diﬀerent. The problem is that as n increases, the atypical event in which Mn = 2n has a 166 CHAPTER 4. RENEWAL PROCESSES probability approaching 0, but still has a signiﬁcant eﬀect on the ensemble-average. Further discussion of ensemble averages is postponed to Section 4.6. Before that, we brieﬂy state and discuss the central limit theorem for counting renewal processes and then introduce the notion of rewards associated with renewal processes. Theorem 4.3.2 (Central Limit Theorem (CLT) for N (t)). Assume that the interrenewal intervals for a renewal counting process {N (t); t > 0} have ﬁnite standard deviation σ > 0. Then ( ) N (t) − t/X lim Pr < α = Φ(α). (4.9) −3/2 √ t→1 σX t Ry where Φ(y) = −1 √12π exp(−x2 /2)dx. This says that the distribution function of N (t) tends to the Gaussian distribution with −3/2 √ t. mean t/X and standard deviation σX ✟✟ ✟ ✻  ❍ ✛✟ ✟ ✲❄ ❍❍ α√n σ n ✟ ✟ ❅ ■ X ✟ ✟ ❅√ ✟ α n σ ✟✟ ✟ ✟✟ ✟ 1 ✟ Slope = X ✟ nX t ✟✟ E [Sn ] Figure 4.4: Illustration of the central limit theorem (CLT) for renewal processes. A given integer n is shown on the vertical axis, and the corresponding mean, E [Sn ] = nX is shown on the horizontal axis. The horizontal line with arrows at height n indicates α standard deviations from E [Sn ], and the vertical line with arrows indicates the distance below (t/X). The theorem can be proved by applying Theorem 1.5.2 (the CLT for a sum of IID rv’s) to Sn and then using the identity {Sn ≤ t} = {N (t) ≥ n}. The general idea is illustrated in Figure 4.4, but the details are somewhat tedious, and can be found, for example, in [16]. We simply outline the argument here. For any real α, the CLT states that © √ ™ Pr Sn ≤ nX + α nσ ≈ Φ(α), Rα where Φ(α) = −1 √12π exp(−x2 /2) dx and where the approximation becomes exact in the limit n → 1. Letting √ t = nX + α nσ, and using {Sn ≤ t} = {N (t) ≥ n}, Pr{N (t) ≥ n} ≈ Φ(α). (4.10) 4.4. RENEWAL-REWARD PROCESSES; TIME-AVERAGES 167 Since t is monotonic in n for ﬁxed α, we can express n in terms of t, getting √ t ασ n t n = − ≈ − ασt1/2 (X)−3/2 . X X X Substituting this into (4.10) establishes the theorem for −α, which establishes the theorem since α is arbitrary. The omitted details involve handling the approximations carefully. 4.4 Renewal-reward processes; time-averages There are many situations in which, along with a renewal counting process {N (t); t > 0}, there is another randomly varying function of time, called a reward function {R(t); t > 0}. R(t) models a rate at which the process is accumulating a reward. We shall illustrate many examples of such processes and see that a “reward” could also be a cost or any randomly varying quantity of interest. The important restriction on these reward functions is that R(t) at a given t depends only on the location of t within the inter-renewal interval containing t and perhaps other random variables local to that interval. Before deﬁning this precisely, we start with several examples. Example 4.4.1. (Time-average residual life) For a renewal counting process {N (t), t > 0}, let Y (t) be the residual life at time t. The residual life is deﬁned as the interval from t until the next renewal epoch, i.e., as SN (t)+1 − t. For example, if we arrive at a bus stop at time t and buses arrive according to a renewal process, Y (t) is the time we have to wait for a bus to arrive (see Figure 4.5). We interpret {Y (t); t ≥ R0} as a reward function. The timet average of Y (t), over the interval (0, t], is given by5 (1/t) 0 Y (τ )dτ . We are interested in the limit of this average as t → 1 (assuming that it exists in some sense). Figure 4.5 illustrates a sample function of a renewal counting process {N (t); t > 0} and shows the residual life Y (t) for Rthat sample function. Note that, for a given sample function {Y (t) = y(t)}, the t integral 0 y(τ ) dτ is simply a sum of isosceles right triangles, with part of a ﬁnal triangle at the end. Thus it can be expressed as Z 0 t n(t) 1X 2 y(τ )dτ = xi + 2 i=1 Z t y(τ )dτ, τ =sn(t) where {xi ; 0 < i < 1} is the set of sample values for the inter-renewal intervals. Since this relationship holds for every sample point, we see that the random variable Rt Y (τ )dτ can be expressed in terms of the inter-renewal random variables Xn as 0 Z t τ =0 5 Rt Y (τ )dτ = Z t N (t) 1X 2 Xn + Y (τ )dτ. 2 n=1 τ =SN (t) Y (τ )dτ is a rv just like any other function of a set of rv’s. It has a sample value for each sample 0 function of {N (t); t > 0}, and its distribution function could be calculated in a straightforward but tedious way. For arbitrary stochastic processes, integration and diﬀerentiation can require great mathematical sophistication, but none of those subtleties occur here. 168 CHAPTER 4. RENEWAL PROCESSES N (t) ✛ X2 ✲ X1 S1 S2 S3 S4 S5 S6 X5 ❅ ❅ ❅Y (t) X2 X4 ❅ ❅ ❅ X6 ❅ ❅ X1 ❅ ❅ ❅ ❅ ❅ X3 ❅ ❅ ❅ ❅ ❅ t ❅ ❅❅ ❅ ❅ ❅ ❅ S1 S2 S3 S4 S5 S6 Figure 4.5: Residual life at time t. For any given sample function of the renewal process, the sample function of residual life decreases linearly with a slope of −1 from the beginning to the end of each inter-renewal interval. Although the ﬁnal term above can be easily evaluated for a given SN (t) (t), it is more convenient to use the following bound: Z N (t) N (t)+1 1 X 2 1 t 1 X X ≤ Y (τ )dτ ≤ Xn2 . t τ =0 2t n=1 n 2t n=1 (4.11) The term on the left can now be evaluated in the limit t → 1 (for all sample functions except a set of probability zero) as follows: PN (t) 2 PN (t) 2 n=1 Xn n=1 Xn N (t) lim = lim . (4.12) t→1 t→1 2t N (t) 2t Consider each term on the right side of (4.12) separately. For the ﬁrst term, recall that PN (t) limt→0 N (t) = 1 with probability 1. Thus as t → 1, n=1 Xn2 /N (t) goes through the Pk same set of values as n=1 Xn2 /k as k → 1. Thus, using the SLLN, Pk PN (t) 2 2 £ § n=1 Xn n=1 Xn lim = lim = E X2 WP1. t→1 k→1 N (t) k The second term on the right side of (4.12) is simply N (t)/2t. By the strong law for renewal processes, limt→1 N (t)/2t = 1/(2E [X]) WP1. Thus both limits exist WP1 and £ § PN (t) 2 E X2 n=1 Xn lim = WP1. (4.13) t→1 2t 2E [X] The right hand term of (4.11) is handled almost the same way: £ § PN (t)+1 2 PN (t)+1 2 E X2 Xn Xn N (t) + 1 N (t) n=1 n=1 lim = lim = . t→1 t→1 2t N (t) + 1 N (t) 2t 2E [X] (4.14) 4.4. RENEWAL-REWARD PROCESSES; TIME-AVERAGES 169 Combining these two results, we see that, with probability 1, the time-average residual life is given by lim t→1 Rt τ =0 £ § Y (τ ) dτ E X2 = . t 2E [X] (4.15) 2 2 Note that this time-average depends on the second moment of X; this is X + σ 2 ≥ X , so the time-average residual life is at least half the expected inter-renewal interval (which is not surprising). On the other hand, the second moment of X can be arbitrarily large (even inﬁnite) for any given value of E [X], so that the time-average residual life can be arbitrarily large relative to E [X]. This can be explained intuitively by observing that large interrenewal intervals are weighted more heavily in this time-average than small inter-renewal intervals. Example 4.4.2. As an example of the eﬀect of improbable but large inter-renewal intervals, let X take on the value £ ≤§ with probability 1 − ≤ and value 1/≤ with probability ≤. Then, for small ≤, E [X] ∼ 1, E X 2 ∼ 1/≤, and the time average residual life is approximately 1/(2≤) (see Figure 4.6). 1/≤ ❅ ❅ ❅ ❅ ❅Y (t) ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✛ ✲ 1/≤ ❅❅❅❅❅❅ ❅❅❅❅❅❅❅❅❅ ✲≤✛ Figure 4.6: Average Residual life is dominated by large interarrival intervals. Each large interval has duration 1/≤, and the expected aggregate duration between successive large intervals is 1 − ≤ Example 4.4.3. (time-average Age) Let Z(t) be the age of a renewal process at time t where age is deﬁned as the interval from the most recent arrival before (or at) t until t, i.e., Z(t) = t − SN (t) . By convention, if no arrivals have occurred by time t, we take the age to be t (i.e., in this case, N (t) = 0 and we take S0 to be 0). As seen in Figure 4.16, the age process, for a given sample function of the renewal process, is almost the same as the residual life process—the isosceles right triangles are simply turned around. Thus the same analysis as before can be used to show that the time average of Z(t) is the same as the time-average of the residual life, lim t→1 Rt τ =0 £ § Z(τ ) dτ E X2 = t 2E [X] WP1. (4.16) 170 CHAPTER 4. RENEWAL PROCESSES ° ° Z(t)° ° ° ° ° ° ° ° ° °° ° ° ° ° t ° ° ° ° ° S1 S2 S3 S4 ° ° ° S5 S6 Figure 4.7: Age at time t: For any given sample function of the renewal process, the sample function of age increases linearly with a slope of 1 from the beginning to the end of each inter-renewal interval. e (t) be the duration of the inter-renewal Example 4.4.4. (time-average Duration) Let X e interval containing time t, i.e., X(t) = XN (t)+1 = SN (t)+1 − SN (t) (see Figure 4.8). It is e (t) = Z(t) + Y (t), and thus the time-average of the duration is given by clear that X lim t→1 Rt τ =0 £ § e (τ ) dτ X E X2 = t E [X] WP1. (4.17) Again, long intervals are heavily weighted in this average, so that the time-average duration is at least as large as the mean inter-renewal interval and often much larger. ✛ e X(t) X5 ✲ t S1 S2 S3 S4 S5 S6 e (t) = XN (t) of the inter-renewal interval containing t. Figure 4.8: Duration X 4.4.1 General renewal-reward processes In each of these examples, and in many other situations, we have a random function of e (t)) whose value at time t depends only on where t is in the time (i.e., Y (t), Z(t), or X e (t) of the current current inter-renewal interval (i.e., on the age Z(t) and the duration X inter-renewal interval). We now investigate the general class of reward functions for which the reward at time t depends at most on the age and the duration at t, i.e., the reward e (t)) of the age and duration at t. R(t) at time t is given explicitly as a function6 R(Z(t), X 6 This means that R(t) can be determined at any t from knowing Z(t) and X(t). It does not mean that R(t) must vary as either of those quantities are changed. Thus, for example, R(t) could depend on only one of the two or could even be a constant. 4.4. RENEWAL-REWARD PROCESSES; TIME-AVERAGES 171 For the three examples above, the function R is trivial. That is, the residual life, Y (t), is e (t) − Z(t) and the age and duration are given directly. given by X Rt We now ﬁnd the time-average value of R(t), namely, limt→1 1t 0 R(τ ) dτ . As in examples 4.4.1 to 4.4.4 above, we ﬁrst want to look at the accumulated reward over each inter-renewal period separately. Deﬁne Rn as the accumulated reward in the nth renewal interval, Z Sn Z Sn e (τ )] dτ. Rn = R(τ ) d(τ ) = R[Z(τ ), X (4.18) Sn−1 Sn−1 For residual life (see Example 4.4.1), Rn is the area of the nth isosceles right triangle in Figure 4.5. In general, since Z(τ ) = τ − Sn−1 , Z Sn Z Xn Rn = R(τ −Sn−1 , Xn ) dτ = R(z, Xn ) dz. (4.19) Sn−1 z=0 Note that Rn is a function only of Xn , where the form of the function is determined by R(Z, X). From this, it is clear that {Rn ; n ≥ 1} is essentially7 a set of IID random variables. For residual life, R(z, Xn ) = Xn − z, so the integral in (4.19) is Xn2 /2, as calculated by inspection before. In general, from (4.19), the expected value of Rn is given by Z 1 Z x E [Rn ] = R(z, x) dz dFX (x). (4.20) x=0 z=0 Rt Breaking 0 R(τ ) dτ into the reward over the successive renewal periods, we get Z t Z S1 Z S2 Z SN (t) Z t R(τ ) dτ = R(τ ) dτ + R(τ ) dτ + · · · + R(τ ) dτ + R(τ )dτ 0 0 S1 N (t) = X n=1 Rn + Z SN (t)−1 SN (t) t R(τ ) dτ. (4.21) SN (t) The following theorem now generalizes the results of Examples 4.4.1, 4.4.3, and 4.4.4 to general renewal-reward functions. Theorem 4.4.1. Let {R(t); t > 0} ≥ 0 be a nonnegative renewal-reward function for a renewal process with expected inter-renewal time E [X] = X < 1. If E [Rn ] < 1, then with probability 1 Z 1 t E [Rn ] lim R(τ ) dτ = . (4.22) t→1 t τ =0 X Proof: Using (4.21), the accumulated reward up to time t can be bounded between the accumulated reward up to the renewal before t and that to the next renewal after t, Rt PN (t) PN (t)+1 Rn n=1 Rn τ =0 R(τ ) dτ . (4.23) ≤ ≤ n=1 t t t 7 One can certainly deﬁne functions R(Z, X) for which the integral in (4.19) is inﬁnite or undeﬁned for some values of Xn , and thus Rn becomes a defective rv. It seems better to handle this type of situation when it arises rather than handling it in general. 172 CHAPTER 4. RENEWAL PROCESSES The left hand side of (4.23) can now be broken into PN (t) n=1 Rn t = PN (t) Rn N (t) . N (t) t n=1 (4.24) Each Rn is a given function of Xn , so the Rn are IID. As t → 1, N (t) → 1, and, thus, as we have seen before, the strong law of large numbers can be used on the ﬁrst term on the right side of (4.24), getting E [Rn ] with probability 1. Also the second term approaches 1/X by the strong law for renewal processes. Since 0 < X < 1 and E [Rn ] is ﬁnite, the product of the two terms approaches the limit E [Rn ] /X. The right-hand inequality of (4.23) is handled in almost the same way, PN (t)+1 n=1 Rn t PN (t)+1 Rn N (t) + 1 N (t) . N (t) + 1 N (t) t n=1 = (4.25) It is seen that the terms on the right side of (4.25) approach limits as before and thus the term on the left approaches E [Rn ] /X withRprobability 1. Since the upper and lower t bound in (4.23) approach the same limit, (1/t) 0 R(τ ) dτ approaches the same limit and the theorem is proved. The restriction to nonnegative renewal-reward functions in Theorem 4.4.1 is slightly ar tiﬁcial. The same result holds for non-positive reward functions simply by changing the directions of the inequalities in (4.23). Assuming that E [Rn ] exists (i.e., that both its positive and negative parts are ﬁnite), the same result applies in general by splitting an arbitrary reward function into a positive and negative part. This gives us the corollary: Corollary 4.4.1. Let {R(t); t > 0} be a renewal-reward function for a renewal process with expected inter-renewal time E [X] = X < 1. If E [Rn ] exists, then with probability 1 lim t→1 1 t Z t R(τ ) dτ = τ =0 E [Rn ] . X (4.26) Example 4.4.5. (Distribution of Residual Life) Example 4.4.1 treated the time-average value of the residual life Y (t). Suppose, however, that we would like to ﬁnd the time-average distribution function of Y (t), i.e., the fraction of time that Y (t) ≤ y as a function of y. The approach, which applies to a wide variety of applications, is to use an indicator function (for a given value of y) as a reward function. That is, deﬁne R(t) to have the value 1 for all t such that Y (t) ≤ y and to have the value 0 otherwise. Figure 4.9 illustrates this function e (t), we for a given sample path. Expressing this reward function in terms of Z(t) and X have e (t)) = R(t) = R(Z(t), X ( 1; 0; e − Z(t) ≤ y X(t) . otherwise Note that if an inter-renewal interval is smaller than y (such as the third interval in Figure 4.9), then R(t) has the value one over the entire interval, whereas if the interval is greater 4.4. RENEWAL-REWARD PROCESSES; TIME-AVERAGES ✛y✲ 0 ✛y✲ ✲ X3 ✛ S1 S2 S3 173 ✛y✲ S4 Figure 4.9: Reward function to ﬁnd the time-average fraction of time that {Y (t) ≤ y}. For the sample function in the ﬁgure, X1 > y, X2 > y, and X4 > y, but X3 < y than y, then R(t) has the value one only over the ﬁnal y units of the interval. Thus Rn = min[y, Xn ]. Note that the random variable min[y, Xn ] is equal to Xn for Xn ≤ y, and thus has the same distribution function as Xn in the range 0 to y. Figure 4.10 illustrates this in terms of the complementary distribution function. From the ﬁgure, we see that Z 1 Z y E [Rn ] = E [min(X, y)] = Pr{min(X, y) > x} dx = Pr{X > x} dx. (4.27) x=0 x=0 ✛ ✒ ✲ ° ° Pr{min(X, y) > x} ° ✠ Pr{X > x} x y Figure 4.10: Rn for distribution of residual life. Rt Let FY (y) = limt→1 (1/t) 0 R(τ ) dτ denote the time-average fraction of time that the residual life is less than or equal to y. From Theorem 4.4.1 and Eq.(4.27), we then have Z E [Rn ] 1 y FY (y) = = Pr{X > x} dx WP1. (4.28) X X x=0 As a check, note that this integral is increasing in y and approaches£ 1 as § y → 1. Note also that the expected value of Y , calculated from (4.28), is given by E X 2 /2X, in agreement with (4.15). The same argument can be applied to the time-average distribution of age (see Exercise 4.12). The time-average fraction of time, FZ (z), that the age is at most z is given by Z 1 z FZ (z) = Pr{X > x} dx WP1. (4.29) X x=0 In the development so far, the reward function R(t) has been a function solely of the age and duration intervals, and the aggregate reward over the nth inter-renewal interval is a function only of Xn . In more general situations, where the renewal process is embedded in some more complex process, it is often desirable to deﬁne R(t) to depend on other aspects of the process as well. The important thing here is for {Rn ; n ≥ 1} to be an IID sequence. How to achieve this, and how it is related to queueing systems, is described in Section 4.5.3. Theorem 4.4.1 clearly remains valid if {Rn ; n ≥ 1} is IID. This more general type 174 CHAPTER 4. RENEWAL PROCESSES of renewal-reward function will be required and further discussed in Sections 4.5.3 to Rss7 where we discuss Little’s theorem and the M/G/1 expected queueing delay, both of which use this more general structure. Limiting time-averages are sometimes visualized by the following type of experiment. For some given large time t, let T be a uniformly distributed random variable over R t (0, t]; T is independent of the renewal-reward process under consideration. Then (1/t) 0 R(τ ) dτ is the expected value (over T ) of R(T ) for a given sample path of {R(τ ); τ >0}. Theorem 4.4.1 states that in the limit t → 1, all sample paths (except a set of probability 0) yield the same expected value over T . This approach of viewing a time-average as a random choice of time is referred to as random incidence. Random incidence is awkward mathematically, since the random variable T changes with the overall time t and has no reasonable limit. It also blurs the distinction between time and ensemble-averages, so it will not be used in what follows. 4.5 Random stopping trials Visualize performing an experiment repeatedly, observing independent successive sample outputs of a given random variable (i.e., observing a sample outcome of X1 , X2 , . . . where the Xi are IID). The experiment is stopped when enough data has been accumulated for the purposes at hand. This type of situation occurs frequently in applications. For example, we might be required to make a choice from several hypotheses, and might repeat an experiment until the hy potheses are suﬃciently discriminated. If the number of trials is allowed to depend on the outcome, the mean number of trials required to achieve a given error probability is typically a small fraction of the number of trials required when the number is chosen in advance. Another example occurs in tree searches where a path is explored until further extensions of the path appear to be unproﬁtable. The ﬁrst careful study of experimental situations where the number of trials depends on the data was made by the statistician Abraham Wald and led to the ﬁeld of sequential analysis (see [21]). We study these situations now since one of the major results, Wald’s equality, will be useful in studying E [N (t)] in the next section. Stopping trials are frequently useful in the study of random processes, and in particular will be used in Section 4.7 for the analysis of queues, and again in Chapter 7 as central topics in the study of Random walks and martingales. An important part of experiments that stop after a random number of trials is the rule for stopping. Such a rule must specify, for each sample path, the trial at which the experiment stops, i.e., the ﬁnal trial after which no more trials are performed. Thus the rule for stopping should specify a positive, integer valued, random variable J, called the stopping time, or stopping trial, mapping sample paths to this ﬁnal trial at which the experiment stops. We view the sample space as including the set of sample value sequences for the never-ending sequence of random variables X1 , X2 , . . . . That is, even if the experiment is stopped at the end of the second trial, we still visualize the 3rd, 4th, . . . random variables as having sample 4.5. RANDOM STOPPING TRIALS 175 values as part of the sample function. In other words, we visualize that the experiment continues forever, but that the observer stops watching at the end of the stopping point. From the standpoint of applications, the experiment might or might not continue after the observer stops watching. From a mathematical standpoint, however, it is far preferable to view the experiment as continuing. This avoids confusion and ambiguity about the meaning of IID rv’s when the very existence of later variables depends on earlier sample values. The intuitive notion of stopping a sequential experiment should involve stopping based on the data (i.e., the sample values) gathered up to and including the stopping point. For example, if X1 , X2 , . . . , represent the succesive changes in our fortune when gambling, we might want to stop when our cumulative gain exceeds some ﬁxed value. The stopping trial n then depends on the sample values of X1 , X2 , . . . , Xn . At the same time, we want to exclude from stopping trials those rules that allow the experimenter to peek at subsequent values before making the decision to stop or not.8 This leads to the following deﬁnition. Deﬁnition 4.5.1. A stopping trial (or stopping time9 ) J for a sequence of rv’s X1 , X2 , . . . , is a positive integer-valued rv such that for each n ≥ 1, the indicator rv I{J=n} is a function of {X1 , X2 , . . . , Xn }. The last clause of the deﬁnition means that any given sample value x1 , . . . , xn for X1 , . . . , Xn uniquely determines whether the corresponding sample value of J is n or not. Note that since the stopping trial J is deﬁned to be a positive integer-valued rv, the events {J = n} and {J = m} for m < n are disjoint events, so stopping at trial m makes it impossible to also stop at n for a given sample path. Also the union of the events {J = n} over n ≥ 1 has probability 1. Aside from this ﬁnal restriction, the deﬁnition does not depend on the probability measure and depends solely on the set of events {J = n} for each n. In many situations, it is useful to relax the deﬁnition further to allow J to be a possibly-defective rv. In this case the question of whether stopping occurs with probability 1 can be postponed until after specifying the disjoint events {J = n} over n ≥ 1. Example 4.5.1. Consider a Bernoulli process {Xn ; n ≥ 1}. A very simple stopping trial for this process is to stop at the ﬁrst occurrence of the string (1, 0). Figure 4.11 illustrates this stopping trial by viewing it as a truncation of the tree of possible binary sequences. The event {J = 2}, i.e., the event that stopping occurs atStrial 2, is the event {X1 =1, X2 =0}. Similarly, the event {J = 3} is {X1 =1, X2 =1, X3 =0} {X1 =0, X2 =1, X3 =0}. The dis jointness of {J = n} and {J = m} for n 6= m is represented in the ﬁgure by terminating the tree at each stopping node. It can be seen that the tree never dies out completely, and in fact, for each trial n, the number of stopping nodes is n − 1. However, the probability that stopping has not occurred by trial n goes to zero exponentially with n, which ensures that J is a random variable. 8 For example, poker players do not take kindly to a player who attempts to withdraw his bet when someone else wins the hand. Similarly, a statistician gathering data on product failures should not respond to a failure by then recording an earlier trial as a stopping time, thus not recording the failure. 9 Stopping trials are more often called stopping times or optional stopping times in the literature. In our ﬁrst major application of a stopping trial, however, the stopping trial is the ﬁrst trial n at which a renewal epoch Sn exceeds a given time t . Viewing this trial as a time generates considerable confusion. 176 CHAPTER 4. RENEWAL PROCESSES r 1 0 r r 1 0 1 0 r r s r s r s r r r r s r s r s r r✘ Figure 4.11: A tree representing the set of binary sequences, with a stopping rule viewed as a pruning of the tree. The particular stopping rule here is to stop on the ﬁrst occurrence of the string (1, 0). The leaves of the tree (i.e., the nodes at which stopping occurs) are marked with large dots and the intermediate nodes (the other nodes) with small dots. Note that each leaf in the tree has a one-to-one correspondence with an initial segment of the tree, so the stopping nodes can be unambiguously viewed either as leaves of the tree or initial segments of the sample sequences. Representing a stopping rule by a pruned tree can be used for any discrete random sequence, although the tree becomes quite unwieldy in all but trivial cases. Visualizing a stopping rule in terms of a pruned tree is useful conceptually, but stopping rules are usually stated in other terms. For example, we shortly consider a stopping trial for the interarrival intervals of a renewal process as the ﬁrst n for which the arrival epoch Sn satisﬁes Sn > t for some given t > 0. 4.5.1 Wald’s equality An important question that arises with stopping trials P is to evaluate the sum SJ of the random variables up to the stopping trial, i.e., SJ = Jn=1 Xn . Many gambling strategies and investing strategies involve some sort of rule for when to stop, and it is important to understand the rv SJ (which can model the overall gain or loss up to that trial). Wald’s equality is very useful in helping to ﬁnd E [SJ ]. Theorem 4.5.1 (Wald’s equality). Let {Xn ; n ≥ 1} be a sequence of IID rv’s, each of mean X. If J is a stopping trial for {Xn ; n ≥ 1} and if E [J] < 1, then the sum SJ = X1 + X2 + · · · + XJ at the stopping trial J satisﬁes E [SJ ] = XE [J] . Proof: Note that Xn is included in SJ = indicator function I{J≥n} = 1. Thus SJ = PJ 1 X n=1 n=1 Xn (4.30) whenever n ≤ J, i.e., whenever the Xn I{J≥n} . (4.31) 4.5. RANDOM STOPPING TRIALS 177 This includes Xn as part of the sum if stopping hasSnot occurred before trial n. The event S {J ≥ n} is the complement of {J < n} = {J = 1} · · · {J = n − 1}. All of these latter events are determined by X1 , . . . , Xn−1 and are thus independent of Xn . It follows that Xn and {J < n} are independent and thus Xn and {J ≥ n} are also independent.10 Thus £ § £ § E Xn I{J≥n} = XE I{J≥n} . We then have hX1 i E [SJ ] = E Xn I{J≥n} n=1 X1 £ § = E Xn I{J≥n} Xn=1 £ § 1 = XE I{J≥n} (4.32) n=1 = XE [J] . (4.33) The interchange of expectation and inﬁnite sum in (4.32) is obviously valid for a ﬁnite sum, and is shown in Exercise 4.18 to be valid for an inﬁnite sum if E [J] < 1. The example below shows that Wald’s equality £can be §invalid when E [J] = 1. The ﬁnal step above comes from P1 the observation that E I{J≥n} = Pr{J ≥ n}. Since J is a positive P1 integer rv, E [J] = n=1 Pr{J ≥ n}. One can also obtain the last step by using J = n=1 I{J≥n} (see Exercise 4.13). What this result essentially says in terms of gambling is that strategies for when to stop betting are not really eﬀective as far as the mean is concerned. This sometimes appears obvious and sometimes appears very surprising, depending on the application. Example 4.5.2 (Stop when you’re ahead in coin tossing). We can model a (biased) coin tossing game as a sequence of IID rv’s X1 , X2 , . . . where each X is 1 with probability p and −1 with probability 1 − p. Consider the possibly-defective stopping trial J where J is the ﬁrst n for which Sn = X1 + · · · + Xn = 1, i.e., the ﬁrst trial at which the gambler is ahead. We ﬁrst want to see if J is a rv, i.e., if the probability of eventual stopping, say θ = Pr{J < 1}, is 1. We solve this by a frequently useful trick, but will use other more systematic approaches in Chapters 5 and 7 when we look at this same example as a birthdeath Markov chain and then as a simple random walk. Note that Pr{J = 1} = p, i.e., S1 = 1 with probability p and stopping occurs at trial 1. With probability 1 − p, S1 = −1. Following S1 = −1, the only way to become one ahead is to ﬁrst return to Sn = 0 for some n > 1, and, after the ﬁrst such return, go on to Sm = 1 at some later trial m. The probability of eventually going from -1 to 0 is the same as that of going from 0 to 1, i.e., θ. Also, given a ﬁrst return to 0 from -1, the probability of reaching 1 from 0 is θ. Thus, θ = p + (1 − p)θ2 . 10 This can be quite confusing initially, since (as seen in the example of Figure 4.11) Xn is not necessarily independent of the event {J = n}, nor of {J = n + 1}, etc. In other words, given that stopping has not occurred before trial n, then Xn can have a great deal to do with the trial at which stopping occurs. However, as shown above, Xn has nothing to do with whether {J < n} or {J ≥ n}. 178 CHAPTER 4. RENEWAL PROCESSES This is a quadratic equation in θ with two solutions, θ = 1 and θ = p/(1 − p). For p > 1/2, the second solution is impossible since θ is a probability. Thus we conclude that J is a rv. For p = 1/2 (and this is the most interesting case), both solutions are the same, θ = 1, and again J is a rv. For p < 1/2, the correct solution11 is θ = p/(1 − p). Thus θ < 1 so J is a defective rv. For the cases where p ≥ 1/2, i.e., where J is a rv, we can use the same trick to evaluate E [J], E [J] = p + (1 − p)(1 + 2E [J]). The solution to this is E [J] = 1 1 = . 2(1 − p) 2p − 1 We see that E [J] is ﬁnite for p > 1/2 and inﬁnite for p = 1/2. For p > 1/2, we can check that these results agree with Wald’s equality. In particular, since SJ is 1 with probability 1, we also have E [SJ ] = 1. Since X = 2p − 1 and E [J] = 1/(2p − 1), Wald’s equality is satisﬁed (which of course it has to be). For p = 1/2, we still have SJ = 1 with probability 1 and thus E [SJ ] = 1. However X = 0 so XE [J] has no meaning and Wald’s equality breaks down. Thus we see that the restriction E [J] < 1 in Wald’s equality is indeed needed. These results are tabulated below. p> 1 2 p= 1 2 p< 1 2 Pr{J < 1} p 1−p 1 1 E [J] 1 1 1 2p−1 . It is surprising that with p = 1/2, the gambler can eventually become one ahead with probability 1. This has little practical value, ﬁrst because the required expected number of trials is inﬁnite, and second (as will be seen later) because the gambler must risk a potentially inﬁnite capital. 4.5.2 Applying Wald’s equality to m(t) = E [N (t)] Let {Sn ; n ≥ 1} be the arrival epochs and {Xn ; n ≥ 1} the interarrival intervals for a renewal process. For any given t > 0, let J be the trial n for which Sn ﬁrst exceeds t. Note that n is speciﬁed by the sample values of {X1 , . . . , Xn } and thus J is a possibly-defective stopping trial for {Xn ; n ≥ 1}. Since n is the ﬁrst trial for which Sn > t, we see that Sn−1 ≤ t and Sn > t. Thus N (t) is n − 1 and n is the sample value of N (t) + 1. Since this is true for all sample sequences, J = N (t) + 1. Since N (t) is a non-defective rv, J is also, so J is a stopping trial for {Xn ; n ≥ 1}. 11 This will be shown when we view this example as a birth-death Markov chain in Chapter 5. 4.5. RANDOM STOPPING TRIALS 179 We can then employ Wald’s equality to obtain £ § E SN (t)+1 = XE [N (t) + 1] = X[m(t) + 1]. £ § E SN (t)+1 m(t) = − 1. X (4.34) (4.35) As is often the £ case with § Wald’s equality, this provides a relationship between two quantities, m(t) and E SN (t)+1 , that are both unknown. This £ will be § used in proving the elementary renewal theorem by upper and lower bounding E SN (t)+1 . The lower bound is easy, since § £ E SN (t)+1 ≥ t, and thus m(t) ≥ t/X − 1. It follows that m(t) 1 1 ≥ − . t t X (4.36) £ § We derive an upper bound on E SN (t)+1 in the next section. First, however, as a san tity check, consider Figure 4.12 which illustrates (4.35) for the case where each Xn is a deterministic rv where Xn = X with probability 1. ✏ ✏ ✏✏ ✏ ✏✏ ✏✏ m(t) ✏ Slope = X1 ✏✏ ✏ ✏✏ ✏✏ ✏ ✏✏ ✏✏ ✏ t ✏ £ § £ 0 E SN (t) t m(t) + 1 E SN (t)+1 § Figure 4.12: Illustration of (4.34) for the special case where X is deterministic. Note that m(t), as a function of t, is then the illustrated staircase function. On each increment § £ of t by X, m(t) increases by one. Then m(t) + 1 and E SN (t)+1 are two sides of a right triangle of slope 1/X, yielding (4.34). It might be puzzling why we used N (t)+1 rather than N (t) as a stopping trial for the epochs {Si ; i ≥ 1} in this application of Wald’s equality. To understand this, assume for example that N (t) = n. When an observer sees the sample values of S1 , . . . , Sn , with Sn < t, the observer typically cannot tell (on the basis of S1 , . . . , Sn alone) whether any other arrivals will occur in the interval (Sn , t]. In other words, N (t) = n implies that Sn ≤ t, but Sn < t does not imply that N (t) = n. On the other hand, still assuming N (t) = n, an observer seeing S1 , . . . , Sn+1 knows that N (t) = n. Any stopping trial (for an arbitrary sequence of rv’s {Sn ; n ≥ 1}) can be viewed as an experiment where an observer views sample values s1 , s2 , . . . , in turn until the stopping rule is satisﬁed. The stopping rule does not permit either looking ahead or going back to change an earlier decision. Thus the rule: stop at N (t)+1 (for the renewal epochs {Sn ; n ≥ 1}) means stop at the ﬁrst sample value si that exceeds t. Stopping at the ﬁnal sample value sn ≤ t is not necessarily possible without looking ahead to the following sample value. 180 CHAPTER 4. RENEWAL PROCESSES 4.5.3 Stopping trials, embedded renewals, and G/G/1 queues The above deﬁnition of a stopping trial is quite restrictive in that it refers only to a single sequence of rv’s. In many queueing situations, for example, there is both a sequence of interarrival times {Xi ; i ≥ 1} and a sequence of service times {Vi ; i ≥ 0}. Here Xi is the interarrival interval between customer i − 1 and i, where an initial customer 0 is assumed to arrive at time 0, and X1 is the arrival time for customer 1. The service time of customer 0 is then V0 and each Vi , i > 0 is the service time of the corresponding ordinary customer. Customer number 0 is not ordinary in the sense that it arrives at the ﬁxed time 0 and is not counted in the arrival counting process {N (t); t > 0}. Example 4.5.3 (G/G/1 queues:). Consider a G/G/1 queue (the single server case of the G/G/m queue described in Example 4.1.2). We assume that the customers are served in First-Come-First-Served (FCFS) order.12 Both the interarrival intervals {Xi ; i ≥ 1} and the service times {Vi ; i ≥ 0} are assumed to be IID and the service times are assumed to be independent of the interarrival intervals. Figure 4.13 illustrates a sample path for these arrivals and departures. s3 s✛ 2 Arrivals 1 0 ✛ ✛ 0 x1 s✛ 1 x2 ✲✛ w2q 2 ✲✛ v0 w1q ✲✛ x3 3 ✲✛ v1 v3 ✲ ✲✛ v2 ✲ ✲ Departures ✲ ✛ x2 + wq = wq + v1✲ 2 1 Figure 4.13: Sample path of arrivals and departures from a G/G/1 queue. Customer 0 arrives at time 0 and enters service immediately. Customer 1 arrives at time s1 = x1 . For the case shown above, customer 0 has not yet departed, i.e., x1 < v0 , so customer 1 is queued for the interval w1q = v0 − x1 before entering service. As illustrated, customer 1’s system time (queueing time plus service time) is w1 = w1q +v1 . Note that the sample path of arrivals in the ﬁgure is one plus the sample path of the arrival counting process {N (t); t > 0}, since the counting process, by convention, does not count the initial arrival at time 0. Customer 2 arrives at s2 = x1 + x2 . For the case shown above, this is before customer 1 departs at v0 + v1 . Thus, customer 2’s wait in queue is w2q = v0 + v1 − x1 − x2 . As illustrated above, x2 +w2q is also equal to customer 1’s system time, so w2q = w1q +v1 −x2 . Customer 3 arrives when the system is empty, so it enters service immediately with no wait in queue, i.e., w3q = 0. The ﬁgure illustrates a sample path for which X1 < V0 , so arrival number 1 waits in queue for W1q = V0 − X1 . If X1 ≥ V0 , on the other hand, then customer one enters service immediately, i.e., customer one ‘sees an empty system.’ In general, then W1q = max(V0 − X1 , 0). In the same way, as illustrated in the ﬁgure, if W1q > 0, then customer 2 12 For single server queues, this is sometimes referred to as First-In-First-Out (FIFO) service. 4.5. RANDOM STOPPING TRIALS 181 waits for W1q + V1 − X2 if positive and 0 otherwise. This same formula works if W1q = 0, so W2q = max(W1q + V1 − X2 , 0). In general, it can be seen that Wiq = max(Wiq−1 + Vi−1 − Xi , 0). (4.37) This equation will be analyzed further in Section 7.2 where we are interested in queueing delay and system delay. Here our objectives are simpler, since we only want to show that the subsequence of customer arrivals i for which the event {Wiq = 0} is satisﬁed form the renewal epochs of a renewal process. To do this, ﬁrst observe from (4.37) (using induction if desired) that Wiq is a function of (X1 , . . . , Xi ) and (V0 , . . . , Vi−1 ). Thus, if we let J be the smallest i > 0 for which Wiq = 0, then IJ=i is a function of (X1 , . . . , Xi ) and (V0 , . . . , Vi−1 ). We now interrupt the discussion of G/G/1 queues with the following generalization of the deﬁnition of a stopping trial. Deﬁnition 4.5.2 (Generalized stopping trials). A generalized stopping trial J for a sequence of pairs of rv’s (X1 , V1 ), (X2 , V2 ) . . . , is a positive integer-valued rv such that, for each n ≥ 1, the indicator rv I{J=n} is a function of X1 , V1 , X2 , V2 , . . . , Xn , Vn . Wald’s equality can be trivially generalized for these generalized stopping trials. Theorem 4.5.2 (Generalized Wald’s equality). Let {(Xn , Vn ); n ≥ 1} be a sequence of pairs of rv’s, where each pair is independent and identically distributed (IID) to all other pairs. Assume that each Xi has ﬁnite mean X. If J is a stopping trial for {(Xn , Vn ); n ≥ 1} and if E [J] < 1, then the sum SJ = X1 + X2 + · · · + XJ satisﬁes E [SJ ] = XE [J] . (4.38) The proof of this will be omitted, since it is the same as the proof of Theorem 4.5.1. In fact, the deﬁnition of stopping trials could be further generalized by replacing the rv’s Vi by vector rv’s or by a random number of rv’s , and Wald’s equality would still hold.13 For the example of the G/G/1 queue, we take the sequence of pairs to be {(X1 , V0 ), (X2 , V1 ), . . . , }. Then {(Xn , Vn−1 ; n ≥ 1} satisﬁes the conditions of Theorem 4.5.2 (assuming that E [Xi ] < 1). Let J be the generalized stopping rule specifying the number of the ﬁrst arrival to ﬁnd an empty queue. Then the theorem relates E [SJ ], the expected time t > 0 until the ﬁrst arrival to see an empty queue, and E [J], the expected number of arrivals until seeing an empty queue. It is important here, as in many applications, to avoid the confusion created by viewing J as a stopping time. We have seen that J is the number of the ﬁrst customer to see an empty queue, and SJ is the time until that customer arrives. There is a further possible timing confusion about whether a customer’s service time is determined when the customer arrives or when it completes service. This makes no diﬀer ence, since the ordered sequence of pairs is well-deﬁned and satisﬁes the appropriate IID condition for using the Wald equality. 13 In fact, J is sometimes deﬁned to be a stopping rule if I{J≥n} is independent of Xn , Xn+1 , . . . for each n. This makes it easy to prove Wald’s equality, but quite hard to see when the deﬁnition holds, especially since I{J=n} , for example, is typically dependent on Xn (see footnote 7). 182 CHAPTER 4. RENEWAL PROCESSES As is often the case with Wald’s equality, it is not obvious how to compute either quantity in (4.38), but it is nice to know that they are so simply related. It is also interesting to see that, although successive pairs (Xi , Vi ) are assumed independent, it is not necessary for Xi and Vi to be independent. This lack of independence does not occur for the G/G/1 (or G/G/m) queue, but can be useful in situations such as packet networks where the interarrival time between two packets at a given node can depend on the service time (the length) of the ﬁrst packet if both packets are coming from the same node. Perhaps a more important aspect of viewing the ﬁrst renewal for the G/G/1 queue as a stop ping trial is the ability to show that successive renewals are in fact IID. Let X2,1 , X2,2 , . . . be the interarrival times following J, the ﬁrst arrival to see an empty queue. Conditioning on J = j, we have X2,1 =Xj+1 , X2,2 =Xj+2 , . . . ,. Thus {X2,k ; k ≥ 1} is an IID sequence with the original interarrival distribution. Similarly {(X2,k , V2,k ); k ≥ 1} is a sequence of IID pairs with the original distribution. This is valid for all sample values j of the stopping trial J. Thus {(X2,k , V2,k ); k ≥ 1} is statistically independent of J and (Xi , Vi ); 1 ≤ i ≤ J. The argument above can be repeated for subsequent arrivals to an empty system, so we have shown that successive arrivals to an empty system actually form a renewal process.14 One can deﬁne many diﬀerent stopping rules for queues, such as the ﬁrst trial at which a given number of customers are in the queue. Wald’s equality can be applied to any such stopping rule, but much more is required for the stopping trial to also form a renewal point. At the ﬁrst time when n customers are in the system, the subsequent departure times depend partly on the old service times and partly on the new arrival and service times, so the required independence for a renewal point does not exist. Stopping rules are helpful in understanding embedded renewal points, but are by no means equivalent to embedded renewal points. Finally, nothing in the argument above for the G/G/1 queue made any use of the FCFS service discipline. One can use any service discipline for which the choice of which customer to serve at a given time t is based solely on the arrival and service times of customers in the system by time t. In fact, if the server is never idle when customers are in the system, the renewal epochs will not depend on the service descipline. It is also possible to extend these arguments to the G/G/m queue, although the service discipline can aﬀect the renewal points in this case. 4.5.4 Little’s theorem Little’s theorem is an important queueing result stating that the expected number of cus tomers in a queueing system is equal to the product of the arrival rate and the expected time each customer waits in the system. This result is true under very general conditions; we use the G/G/1 queue with FCFS service as a speciﬁc example, but the reason for the greater generality will be clear as we proceed. Note that the theorem does not tell us how 14 Confession by author: For about 15 years, I mistakenly believed that it was obvious that arrivals to an empty system in a G/G/m queue form a renewal process. Thus I can not expect readers to be excited about the above proof. However, it is a nice example of how to use stopping times to see otherwise murky points clearly. 4.5. RANDOM STOPPING TRIALS 183 to ﬁnd either the expected number or expected wait; it only says that if one can be found, the other can also be found. s1 ✛ w0 ✛ ✲ s2 a(τ ) ✛ w1 s3 ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣♣♣♣♣♣♣ sr1 t ✛ w3 ✲ w2 ✲ ✲ d(τ ) 0 sr2 Figure 4.14: Sample path of arrivals, departures, and system waiting times for a G/G/1 queue with FCFS service. The upper step function is the number of customer arrivals, including the customer at time 0 and is denoted a(τ ). Thus a(τ ) is a sample path of A(τ ) = N (τ ) + 1, i.e., the arrival counting process incremented by 1 for the initial arrival at τ = 0. The lower step function, d(τ ) is a sample path for D(τ ), which is the number of departures (including customer 0) up to time τ . For each i ≥ 0, wi is the sample value of the system waiting time Wi for customer i. Note that Wi = Wiq + Vi . The ﬁgure also shows the sample values sr1 and s2r of the ﬁrst two arrivals that see an empty system (recall from Section 4.5.3 that the subsequence of arrivals that see an empty system forms a renewal process.) Figure 4.14 illustrates a sample path for a G/G/1 queue with FCFS service. It illustrates a sample path a(t) for the arrival process A(t) = N (t) + 1, i.e., the number of customer arrivals in [0, t], speciﬁcally including customer number 0 arriving at t = 0. Similarly, it illustrates the departure process D(t), which is the number of departures up to time t, again including customer 0. The diﬀerence, L(t) = A(t) − D(t), is then the number in the system at time t. Recall from Section 4.5.3 that the subsequence of customer arrivals for t > 0 that see an empty system form a renewal process. Actually, we showed a little more than that. Not only are the inter-renewal intervals, Xir = Sir − Sir−1 IID, but the number of customer arrivals in each inter-renewal interval are IID, and the interarrival intervals and service times between inter-renewal intervals are IID. The sample values, sr1 and s2r of the ﬁrst two renewal epochs are shown in the ﬁgure. R Sr The essence of Little’s theorem can be seen by observing that 0 1 L(τ ) dτ in the ﬁgure is the area between the upper and lower step functions, integrated out to the ﬁrst time that the two step functions become equal (i.e., the system becomes empty). For the sample value in the ﬁgure, this integral is equal to w0 + w1 + w2 . In terms of the rv’s, Z 0 S1r N (S1r )−1 L(τ ) dτ = X Wi . (4.39) i=0 The same relationship exists in each inter-renewal interval, and in particular we can deﬁne 184 CHAPTER 4. RENEWAL PROCESSES Ln for each n ≥ 1 as Ln = Z r )−1 N (Sn r Sn r Sn−1 L(τ ) dτ = X Wi . (4.40) r i=N (Sn −1 ) The interpretation of this is far simpler than the notation. The arrival step function and the departure step function in Figure 4.14 are separated whenever there are customers in the system (the system is busy) and are equal whenever the system is empty. Renewals occur when the system goes from empty to busy, so the nth renewal is at the beginning of the nth busy period. Then Ln is the area of the region between the two step functions over the nth busy period. By simple geometry, this area is also the sum of the customer waiting times over that busy period. Finally, since the interarrival intervals and service times in each busy period are IID with respect to those in each other busy period, the sequence L1 , L2 , . . . , is a sequence of IID rv’s. The function L(τ ) has the same behavior as a renewal reward function, but it is slightly more general, being a function of more than the age and duration of the renewal counting process {N r (t); t > 0} at t = τ . However the fact that {Ln ; n ≥ 1} is an IID sequence lets us use the same methodology to treat L(τ ) as was used earlier to treat renewal-reward functions. We now state and prove Little’s theorem. The proof is almost the same as that of Theorem 4.4.1, so we will not dwell on it. Theorem 4.5.3 (Little). For a FCFS G/G/1 queue in which the expected inter-renewal interval is ﬁnite, the limiting time-average number of customers in the system is equal, with probability 1, to a constant denoted as L. The sample-path-average waiting time per customer is also equal, with probability 1, to a constant denoted as W . Finally L = ∏W where ∏ is the customer arrival rate, i.e., the reciprocal of the expected interarrival time. Rt Proof: Note that for any t > 0, 0 (L(τ ) dτ can be expressed as the sum over the busy periods completed before t plus a residual term involving the busy period including t. The residual term can be upper bounded by the integral over that complete busy period. Using this with (4.40), we have N r (t) X n=1 Ln ≤ Z τ =0 N r (t)+1 N (t) t L(τ ) dτ ≤ X i=0 Wi ≤ X Ln . (4.41) n=1 Assuming that the expected inter-renewal interval, E [X r ], is ﬁnite, we can divide both sides of (4.41) by t and go to the limit t → 1. From the same argument as in Theorem 4.4.1, Rt PN (t) L(τ ) dτ E [Ln ] i=0 Wi lim = lim τ =0 = with probability 1. (4.42) t→1 t→1 t t E [X r ] The equality on the right shows that the limiting time average of L(τ ) exists with probability 1 and is equal to L = E [Ln ] /E [X r ]. The quantity on the left of (4.42) can now be broken up as waiting time per customer multiplied by number of customers per unit time, i.e., PN (t) PN (t) N (t) i=0 Wi i=0 Wi lim = lim lim . (4.43) t→1 t→1 t→1 t N (t) t 4.5. RANDOM STOPPING TRIALS 185 From (4.42), the limit on the left side of (4.43) exists (and equals L) with probability 1. The second limit on the right also exists with probability 1 by the strong law for renewal processes, applied to {N (t); t > 0}. This limit is called the arrival rate ∏, and is equal to the reciprocal of the mean interarrival interval for {N (t)}. Since these two limits exist with probability 1, the ﬁrst limit on the right, which is the sample-path-average waiting time per customer, denoted W , also exists with probability 1. Reviewing this proof and the development of the G/G/1 queue before the theorem, we see that there was a simple idea, expressed by (4.39), combined with a lot of notational complexity due to the fact that we were dealing with both an arrival counting process {N (t); t > 0} and an embedded renewal counting process {N r (t); t > 0}. The diﬃcult thing, mathematically, was showing that {N r (t); t > 0} is actually a renewal process and showing that the Ln are IID, and this was where we needed to understand stopping rules. Recall that we assumed earlier that customers departed from the queue in the same order in which they arrived. From Figure 4.15, however, it is clear that FCFS order is not required for the argument. Thus the theorem generalizes to systems with multiple servers and arbitrary service disciplines in which customers do not follow FCFS order. In fact, all that the argument requires is that the system has renewals (which are IID by deﬁnition of a renewal) and that the inter-renewal interval is ﬁnite with probability 1. A(τ ) ✛ ✛ ✛ 0 W1 W2 ✲ W3 ♣♣ ♣♣ ♣♣ ✲ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣ ♣ ♣ ♣ ♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ✲ S1 t Figure 4.15: Arrivals and departures in a non-FCFS systems. The server, for example, could work simultaneously (at a reduced rate) on all customers in the system, and thus complete service for customers with small service needs before completing earlier arrivals with greater service needs. Note that the jagged right edge of the diagram does not represent number of deparatures, but this is not essential for the argument. For example, if higher priority is given to customers with small service times, then it is not hard to see that the average number of customers in the system and the average waiting time per customer will be decreased. However, if the server is always busy when there is work to be done, it can be seen that the renewal times are unaﬀected. Service discipines will be discussed further in Section 5.6. The same argument as in Little’s theorem can be used to relate the average number of customers in a single server queue (not counting service) to the average wait in the queue (not counting service). Renewals still occur on arrivals to an empty system, and the integral of customers in queue over a busy period is still equal to the sum of the queue R t waiting times. q Let Lq (t) be the number in the queue at time t and let L = limt→1 (1/t) 0 Lq (τ )dτ be the 186 CHAPTER 4. RENEWAL PROCESSES q time-average queue wait. Letting W be the sample-path-average waiting time in queue, q q L = ∏W . (4.44) The same argument can also be applied to the service facility of a single server queue. The time-average of the number of customers in the server is just the fraction of time that the server is busy. Denoting this fraction by ρ and the expected service time by V , we get ρ = ∏V . 4.5.5 (4.45) Expected queueing time for an M/G/1 queue For our last example of the use of renewal-reward processes, we consider the expected queueing time in an M/G/1 queue. We again assume that an arrival to an empty system occurs at time 0 and renewals occur on subsequent arrivals to an empty system. At any given time t, let Lq (t) be the number of customers in the queue (not counting the customer in service, if any) and let R(t) be the residual life of the customer in service. If no customer is in service, R(t) = 0, and otherwise R(t) is the remaining time until the current service is completed. Let U (t) be the waiting time in queue that would be experienced by a customer arriving at time t. This is often called the unﬁnished work in the queueing literature and represents the delay until all the customers currently in the system complete service. Thus the rv U (t) is equal to R(t), the residual life of the customer in service, plus the service times of each of the Lq (t) customers currently waiting in the queue. Lq (t) U (t) = X VN (t)−i + R(t), (4.46) i=1 where N (t) − i is the customer number of the ith customer in the queue at time t. Since Lq (t) is a function only of the interarrival times in (0, t) and the service times of the customers that have already been served, we see that for each sample value Lq (t) = `, the rv’s Ve1 , . . . , Ve` each have the service time distribution FV . Thus, taking expected values, E [U (t)] = E [Lq (t)] E [V ] + E [R(t)] . (4.47) Figure 4.16 illustrates how to ﬁnd the time-average of R(t). Viewing R(t) as a reward ❅ ✻❅ ❅ ❅ ❅ R(t) ❅ ❅ V1 ❅ ❅ ❅ ❅ ❅ ❅ t ❅ ❅ ❅ ❅ ❄ ✛ V1 ✲✛ V2 ✲✛ V3 ✲ 0 ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ S1r Figure 4.16: Sample value of the residual life function of customers in service. function, we can ﬁnd the accumulated reward up to time t as the sum of triangular areas. 4.5. RANDOM STOPPING TRIALS 187 R r First, consider R(τ )dτ from 0 to SN r (t) , i.e., the accumulated reward up to the ﬁnal r renewal epoch in [o, t]t. Note that SN r (t) is not only a renewal epoch for the renewal r process, but also an arrival epoch for the arrival process; in particular, it is the N (SN r (t) )th r arrival epoch, and the N (SN r (t) ) − 1 earlier arrivals are the customers that have received r service up to time SN r (t) . Thus, Z r SN r (t) r N (SN r (t) )−1 X R(τ ) dτ = 0 i=0 N (t) 2 XV Vi2 i ≤ . 2 2 i=0 R Sr r We can similarly upper bound the term on the right above by 0 N (t)+1 R(τ ) dτ . We also Rt know (from going through virtually the same argument several times) that (1/t) τ =0 R(τ )dτ will approach a limit15 with probability 1 as t → 1, and that the limit will be unchanged r r if t is replaced with SN r (t) or SN r (t)+1 . Thus, taking ∏ as the arrival rate, lim t→1 Rt 0 R(τ ) dτ = lim t→1 t £ § ∏E V 2 Vi2 A(t) = 2A(t) t 2 PA(t) i=1 WP1. We will see in the next section that the time average above can be replaced with a limiting ensemble-average, so that £ § ∏E V 2 lim E [R(t)] = . (4.48) t→1 2 The next section also shows that there is a limiting ensemble-average form of (4.44), showing q that limt→1 E [Lq (t)] = ∏W . Substituting this plus (4.48) into (4.47), we get £ § ∏E V 2 q lim E [U (t)] = ∏E [V ] W + . (4.49) t→1 2 Thus E [U (t)] is asymptotically independent of t. It is now important to distinguish between q E [U (t)] and W . The ﬁrst is the expected unﬁnished work at time t, which is the queueing delay that a customer would incur by arriving at t; the second is the sample-path-average expected queueing delay. For Poisson arrivals, the probability of an arrival in (t, t + δ] is independent of all earlier arrivals and service times, so it is independent of U (t)16 . Thus, in the limit t → 1, each arrival faces an expected delay limt→1 E [U (t)], so limt→1 E [U (t)] q must be equal to W . Substituting this into (4.49), we obtain the celebrated PollaczekKhinchin formula, £ § ∏E V 2 q W = (4.50) . 2(1 − ∏E [V ]) 15 In fact, one could simply take the limit without bringing in the renewal process, since it is clear by now that the renewal process justiﬁes the limit with probability 1. 16 This is often called the PASTA property, standing for Poisson arrivals see time-averages. This holds with great generality, requiring only that time-averages exist and that the parameters of interest at a given time t are independent of future arrivals. At the same time, this property is somewhat vague, so it should be used to help the intuition rather than to prove theorems. 188 CHAPTER 4. RENEWAL PROCESSES This delay has some of the peculiar features of residual life, and in particular, if £ queueing § E V 2 = 1, the limiting expected queueing delay is inﬁnite even when the expected service time is less than the expected interarrival interval. £ § In trying to visualize why the queueing delay is so large when E V 2 is large, note that while a particularly long service is taking place, numerous arrivals are coming into the system, and all are being delayed by this single long service. In other words, the number of new customers held up by a long service is proportional to the length of the service, and the amount each of them are held up is also proportional to the length of the service. This visualization is rather crude, but does serve to explain the second moment of V in (4.50). This phenomenon is sometimes called the “slow truck eﬀect” because of the pile up of cars behind a slow truck on a single lane road. For a G/G/1 queue, (4.49) is still valid, but arrival times are no longer independent of U (t), q so that typically E [U (t)] = 6 W . As an example, suppose that the service time is uniformly distributed between 1−≤ and 1+≤ and that the interarrival interval is uniformly distributed q between 2 − ≤ and 2 + ≤. Assuming that ≤ < 1/2, the system has no queueing and W = 0. On the other hand, for small ≤, limt→1 E [U (t)] ∼ 1/4 (i.e., the server is busy half the time with unﬁnished work ranging from 0 to 1). 4.6 Expected number of renewals The purpose of this section is to evaluate E [N (t)], denoted m(t), as a function of t > 0 for arbitrary renewal processes. We ﬁrst ﬁnd an exact expression, in the form of an integral equation, for m(t). This can be easily solved by Laplace transform methods in special cases. For the general case, however, m(t) becomes increasingly messy for large t, so we then ﬁnd the asymptotic behavior of m(t). Since N (t)/t approaches 1/X with probability 1, we might expect m(t) to grow with a derivative m0 (t) that asymptotically approaches 1/X. This is not true in general. Two somewhat weaker results, however, are true. The ﬁrst, called the elementary renewal theorem (Theorem 4.6.1), states that limt→1 m(t)/t = 1/X. The second result, called Blackwell’s theorem (Theorem 4.6.2), states that, subject to some limitations on δ > 0, limt→1 [m(t+δ)−m(t)] = δ/X. This says essentially that the expected renewal rate approaches steady state as t → 1. We will ﬁnd a number of applications of Blackwell’s theorem throughout the remainder of the text. The exact calculation of m(t) makes use of the fact that the expectation of a nonnegative random variable is deﬁned as the integral of its complementary distribution function, m(t) = E [N (t)] = 1 X n=1 Pr{N (t) ≥ n} . Since the event {N (t) ≥ n} is the same as {Sn ≤ t}, m(t) is expressed in terms of the distribution functions of Sn , n ≥ 1, as follows. m(t) = 1 X n=1 Pr{Sn ≤ t} . (4.51) 4.6. EXPECTED NUMBER OF RENEWALS 189 Although this expression looks fairly simple, it becomes increasingly complex with increasing t. As t increases, there is an increasing set of values of n for which Pr{Sn ≤ t} is signiﬁcant, and Pr{Sn ≤ t} itself is not that easy to calculate if the interarrival distribution FX (x) is complicated. The main utility of (4.51) comes from the fact that it leads to an integral equation for m(t). Since Sn = Sn−1 + Xn for each n ≥ 1 (interpreting S0 as 0), and since Xn and Sn−1 are independent, we can use the convolution equation (1.11) to get Pr{Sn ≤ t} = Z t x=0 Pr{Sn−1 ≤ t − x} dFX (x) for n ≥ 2. Substituting this in (4.51) for n ≥ 2 and using the fact that Pr{S1 ≤ t} = FX (t), we can interchange the order of integration and summation to get m(t) = FX (t) + Z 1 X t x=0 n=2 = FX (t) + Z 1 X t x=0 n=1 = FX (t) + Z t x=0 Pr{Sn−1 ≤ t − x} dFX (x) Pr{Sn ≤ t − x} dFX (x) m(t − x)dFX (x) ; t ≥ 0. (4.52) An alternative derivation is given in Exercise 4.22. This integral equation is called the renewal equation. The following alternative form is achieved by integration by parts.17 m(t) = FX (t) + Z t τ =0 4.6.1 FX (t − τ ) dm(τ ) ; t ≥ 0. (4.53) Laplace transform approach If we assume ≥ 0 has a density fX (x), and that this density has a Laplace transform18 R 1 that X −sx LX (s) = 0 fX (x)e dx, then we can take the Laplace transform of both sides of (4.52). Note that the ﬁnal term in (4.52) is the convolution of m with fX , so that the Laplace transform of m(t) satisﬁes Lm (s) = LX (s) + Lm (s)LX (s). s Solving for Lm (s), Lm (s) = 17 LX (s) . s[1 − LX (s)] (4.54) A mathematical subtlety £ with § the Stieltjes integrals (4.52) and (4.53) will be discussed in Section 4.7.3. Note that LX (s) = E e−sX = gX (−s) where g is the MGF of X. Thus the argument here could be carried out using the MGF. We use the Laplace transform since the mechanics here are so familiar to most engineering students 18 190 CHAPTER 4. RENEWAL PROCESSES Example 4.6.1. As a simple example of how this can be used to calculate m(t), suppose fX (x) = (1/2)e−x + e−2x for x ≥ 0. The Laplace transform is given by LX (s) = 1 1 (3/2)s + 2 + = . 2(s + 1) s + 2 (s + 1)(s + 2) Substituting this into (4.54) yields Lm (s) = (3/2)s + 2 4 1 1 = 2+ . − s2 (s + 3/2) 3s 9s 9(s + 3/2) We can solve for m(t), t ≥ 0, by taking the inverse Laplace transform, m(t) = 4t 1 − exp[−(3/2)t] + . 3 9 The procedure in this example can be used for any inter-renewal density fX (x) for which the Laplace transform is a rational function, i.e., a ratio of polynomials. In such cases, Lm (s) will also be a rational function. The Heaviside inversion formula (i.e., factoring the denominator and expressing Lm (s) as a sum of individual poles as done above) can then be used to calculate m(t). In the example above, there was a second order pole at s = 0 leading to the linear term 4t/3 in m(t), there was a ﬁrst order pole at s = 0 leading to the constant 1/9, and there was a pole at s = −3/2 leading to the exponentially decaying term. We now show that a second order pole at s = 0 always occurs when LX (s) is a rational function. To see this, note that LX (0) is just the integral of fX (x), which is 1; thus 1−LX (s) has a zero at s = 0 and Lm (s) has a second order pole at s = 0. To evaluate the residue for this second order we recall that the ﬁrst and second derivatives of LX (s) at s = 0 £ pole, § are −E [X] and E X 2 respectively. £Expanding LX (s) in a power series around s = 0 then § 2 2 yields LX (s) = 1 − sE [X] + (s /2)E X plus terms of order s3 or higher. This gives us √ £ § ! £ § 1 − sX + (s2 /2)E X 2 + · · · 1 1 E X2 § = Lm (s) = 2 £ + (4.55) 2 − 1 + ··· . s s X − (s/2)E [X 2 ] + · · · s2 X 2X The remaining terms are the other of Lm (s) with their residues. RFor values of s with R poles −sx R <(s) ≥ 0, we have |LX (s)| = | fX (x)e dx| ≤ fX (x)|e−sx |dx ≤ fX (x)dx = 1 with strict inequality except for s = 0. Thus LX (s) cannot have any poles on the imaginary axis or the right half plane, and 1 − LX (s) cannot have any zeros there other than the one at s = 0. It follows that all the remaining poles of Lm (s) are strictly in the left half plane. This means that the inverse transforms for all these remaining poles die out as t → 1. Thus the inverse Laplace transform of Lm (s) is £ § E X2 t m(t) = + 2 − 1 + ≤(t) X 2X t σ2 1 = + for t ≥ 0, (4.56) 2 − 2 + ≤(t) X 2X where limt→1 ≤(t) = 0. 4.6. EXPECTED NUMBER OF RENEWALS 191 We have derived (4.56) only for the special case in which fX (x) has a rational Laplace trans form. For this case, (4.56) implies both the elementary renewal theorem (limt→1 m(t)/t = 1/X) and also Blackwell’s theorem (limt→1 [m(t + δ) − m(t)] = δ/X). We will interpret the 2 meaning of the constant term σ 2 /(2X ) − 1/2 in Section 4.8. 4.6.2 The elementary renewal theorem Theorem 4.6.1 (The elementary renewal theorem). Let {N (t); t > 0} be a renewal counting process with mean inter-renewal interval X . Then limt→1 E [N (t)] /t = 1/X. Discussion: We have already seen that m(t) = E [N (t)] is ﬁnite for all t > 0 (see Exercise 4.2). The theorem is proven by establishing a lower and upper bound to m(t)/t and showing that each approaches 1/E [X] as t → 1. The key element for each bound is (4.35), repeated below, which comes from the Wald equality. £ § E SN (t)+1 m(t) = − 1. (4.57) X Proof: The lower bound to£ m(t)/t§comes by recognizing that SN (t)+1 is the epoch of the ﬁrst arrival after t. Thus E SN (t)+1 > t. Substituting this into (4.57), m(t) 1 1 > − . t t E [X] Clearly this lower bound approaches 1/E [X] as t → 1. The upper bound, which is more diﬃcult19 and might be omitted on a ﬁrst reading, is established by ﬁrst truncating X(t) and then applying (4.57) to the truncated process. For an arbitrary constant b > 0, let X̆i = min(b, Xi ). Since these truncated random variables h i are IID, they form a related renewal counting process {N̆ (t); t > 0} with m̆(t) = E N̆ (t) and S̆n = X̆1 + · · · + X̆n . Since X̆i ≤ Xi for all i, we see that S̆n ≤ Sn for all n. Since {Sn ≤ t} = {N (t) ≥ n}, it follows that N̆ (t) ≥hN (t) and i thus m̆(t) ≥ m(t). Finally, in the truncated process, S̆N̆ (t)+1 ≤ t + b and thus E S̆N̆ (t)+1 ≤ t + b. Thus, applying (4.57) to the truncated process, h i E S N̆ (t)+1 m(t) m̆(t) 1 t+b h i − h i. = ≤ ≤ t t t tE X̆ tE X̆ Next, choose b = 19 √ t. Then m(t) 1 1 ≤ h i + √ h i. t E X̆ t E X̆ The diﬃculty here, and the reason for using a truncation argument, comes from the fact that the residual life, SN (t)+1£− t§at t might be arbitrarily large. We saw in Section 4.4 that the time-average residual life is inﬁnite if E X 2 is inﬁnite. Figure 4.6 also illustrates why residual life can be so large. 192 CHAPTER 4. RENEWAL PROCESSES h i R h i √ b Note ﬁnally that E X̆ = 0 [1−FX (x)] dx. Since b = t, we have limt→1 E X̆ = E [X], completing the proof. Note that this theorem (and its proof) have not assumed ﬁnitehvariance. It can also be seen i that the theorem holds when E [X] is inﬁnite, since limt→1 E X̆ = 1 in this case. Recall that N [t, ω]/t is the average number of renewals from 0 to t for a sample function ω, and m(t)/t is the average of this over ω. Combining with Theorem 4.3.1, we see that the limiting time and ensemble-average equals the time-average renewal rate for each sample function except for a set of probability 0. Another interesting question is to determine the expected renewal rate in the limit of large t without averaging from 0 to t. That is, are there some values of t at which renewals are more likely than others for large t? If the inter-renewal intervals have an integer distribution function (i.e., each inter-renewal interval must last for an integer number of time units), then each renewal epoch Sn must also be an integer. This means that N (t) can increase only at integer times and the expected rate of renewals is zero at all non-integer times. An obvious generalization of integer valued inter-renewal intervals is that of inter-renewals that occur only at integer multiples of some real number d > 0. Such a distribution is called an arithmetic distribution. The span of an arithmetic distribution is the largest number ∏ such that this property holds. Thus, for example if X takes on only the values 0, 2, and 6, its distribution is arithmetic with span ∏ = 2. Similarly, if X takes on only the values 1/3 and 1/5, then the span is ∏ = 1/15. The remarkable thing, for our purposes, is that any inter-renewal distribution that is not an arithmetic distribution leads to a uniform expected rate of renewals in the limit of large t. This result is contained in Blackwell’s renewal theorem, which we state without proof.20 . Recall, however, that for the special case of an inter-renewal density with a rational Laplace transform, Blackwell’s renewal theorem is a simple consequence of (4.56). Theorem 4.6.2 (Blackwell). If a renewal process has an inter-renewal distribution that is non-arithmetic, then for each δ > 0, lim [m(t + δ) − m(t)] = t→1 δ . E [X] (4.58) If the inter-renewal distribution is arithmetic with span ∏, then lim [m(t+∏) − m(t)] = t→1 ∏ . E [X] (4.59) Eq. (4.58) says that for non-arithmetic distributions, the expected number of arrivals in the interval (t, t + δ] is equal to δ/E [X] in the limit t → 1. Since the theorem is true for arbitrarily small δ, the theorem almost seems to be saying that m(t) has a derivative for large t, but this is not true. One can see the reason by looking at an example where X can take on only the values 1 and π. Then no matter how large t is, N (t) can only increase at discrete points of time of the form k + jπ where k and j are nonnegative integers. Thus 20 See Theorem 1 of Section 11.1, of [8]) for a proof 4.7. RENEWAL-REWARD PROCESSES; ENSEMBLE-AVERAGES 193 dm(t)/dt is either 0 or 1 for all t. As t gets larger, the jumps in m(t) £ become both §smaller in magnitude and more closely spaced from one to the next. Thus m(t + δ) − m(t) /δ can approach 1/E [X] as t → 1 for any ﬁxed δ (as the theorem says), but as δ gets smaller, the convergence in £t gets slower. For § the above example (and for all discrete non-arithmetic distributions), m(t + δ) − m(t) /δ does not approach21 1/E [X] for any t as δ → 0. For an arithmetic renewal process with span ∏, the asymptotic behavior of m(t) as t → 1 is much simpler. Renewals can only occur at multiples of ∏, and since simultaneous renewals are not allowed, either 0 or 1 renewal occurs at each time k∏. Thus for any k. we have Pr{Renewal at ∏k} = m(∏k) − m(∏(k−1)), (4.60) where, by convention, we take m(0) = 0. Thus (4.59) can be restated as lim Pr{Renewal at k∏} = k→1 ∏ . X (4.61) The limiting behavior of m(t) is discussed further in the next section. 4.7 Renewal-reward processes; ensemble-averages Theorem 4.4.1 showed that if a renewal-reward process has an expected inter-renewal in terval X and an expected inter-renewal reward E [Rn ], then the time-average reward is E [Rn ] /X with probability 1. In this section, we explore the ensemble average, E [R(t)], as a function of time t. It is easy to see that E [R(t)] typically changes with t, especially for small t, but a question of major interest here is whether E [R(t)] approaches a constant as t → 1. In more concrete terms, if the arrival times of busses at a bus station forms a renewal process, then the waiting time for the next bus, i.e., the residual life, starting at time t, can be represented as a reward function R(t). We would like to know if the expected waiting time depends critically on t, where t is the time since the renewal process started, i.e., the time since a hypothetical bus number 0 arrived. If E [R(t)] varies signiﬁcantly with t, even as t → 1, it means that the choice of t = 0 as the beginning of the initial interarrival interval never dies out as t → 1. Blackwell’s renewal theorem (and common sense) tell us that there is a large diﬀerence between arithmetic inter-renewal times and non-arithmetic inter-renewal times. For the arithmetic case, all renewals occur at multiples of the span ∏. Thus, for example, the expected waiting time (i.e., the expected residual life) decreases at rate 1 from each multiple of ∏ to the next, and it increases with a jump equal to the probability of an arrival at each multiple of ∏. For this reason, we usually consider various reward functions only at multiples of ∏. We would guess, then, that E [R(n∏)] approaches a constant as n → 1. For the non-arithmetic case, on the other hand, the expected number of renewals in any small interval of length δ becomes independent of t as t → 1, so we might guess that 21 This must seem like mathematical nitpicking to many readers. However, m(t) is the expected number of renewals in (0, t], and how m(t) varies with t, is central to this chapter and keeps reappearing. 194 CHAPTER 4. RENEWAL PROCESSES E [R(t)] approaches a limit as t → 1. We would also guess that these asymptotic ensemble averages are equal to the appropriate time averages from Section 4.4. The bottom line for this section is that under very broad conditions, the above guesses are essentially correct. Thus the limit as t → 1 of a given ensemble-average reward can usually be computed simply by ﬁnding the time-average and vice-versa. Sometimes time-averages are simpler, and sometimes ensemble-averages are. The advantage of the ensemble-average approach is both the ability to ﬁnd E [R(t)] for ﬁnite values of t and to understand the rate of convergence to the asymptotic result. The following subsection is restricted to the arithmetic case. We will derive the joint distribution function of age and duration for any given time t, and then look at the limit as t → 1. This leads us to arbitrary reward functions (such as residual life) for the arithmetic case. We will not look speciﬁcally at generalized reward functions that depend on other processes, but this generalization is quite similar to that for time-averages. The non-arithmetic case is analyzed in the remainder of the subsections of this section. The basic ideas are the same as the arithmetic case, but a number of subtle mathematical limiting issues arise. The reader is advised to understand the arithmetic case ﬁrst, since the limiting issues in the non-arithmetic case can then be viewed within the intuitive context of the arithmetic case. 4.7.1 Age and duration for arithmetic processes Let {N (t); t > 0} be an arithmetic renewal counting process with inter-renewal intervals X1 , X2 , . . . and arrival epochs S1 , S2 , . . . , where Sn = X1 + · · · + Xn . To keep the notation as uncluttered as possible, we take the span to be one and then scale to an arbitrary ∏ later. Thus each Xi is a positive integer-valued rv. Recall that the age Z(t) at any given t > 0 is Z(t) = t − SN (t) (where by convention S0 = 0) e (t) is X e (t) = SN (t)+1 (t) − SN (t) . Since arrivals occur only at integer and the duration X times, we initially consider age and duration only at integer times also. If an arrival occurs at integer time t, then SN (t) = t and Z(t) = 0. Also, if S1 > t, then N (t) = 0 and Z(t) = t (i.e., the age is taken to be t if no arrivals occur up to and including time t). Thus, for integer t, Z(t) is an integer-valued rv taking values from [0, t]. Since SN (t)+1 > t, it follows e (t) is an integer-valued rv satisfying X e (t) > Z(t). Since both are integer valued, that X e (t) must exceed Z(t) by at least 1 (or by ∏ in the more general case of span ∏). X e (t) = k for given i < t, it is necessary and suﬃcient In order to satisfy Z(t) = i and X to have an arrival epoch at t − i followed by an interarrival interval of length k, where e (t) = k, it is necessary and suﬃcient that k > t, i.e., that the k ≥ i + 1. For Z(t) = t and X ﬁrst inter-renewal epoch occurs at k > t. Theorem 4.7.1. Let {Xn ; n ≥ 1} be the interarrival intervals of an arithmetic renewal process with unit span. Then the the joint PMF of the age and duration at integer time 4.7. RENEWAL-REWARD PROCESSES; ENSEMBLE-AVERAGES 195 t ≥ 1 is given by pZ(t),Xe (t) (i, k) = ( pX (k) for i = t, k > t qt−i pX (k) for 0 ≤ i < t, k > i . 0 otherwise (4.62) where qj = Pr{arrival at time j}. The limit as t → 1 for any given 0 ≤ i < k is given by lim integer t→1 pZ(t),Xe (t) (i, k) = pX (k) . X (4.63) Proof: The idea is quite simple. For the upper part of (4.62), note that the age is t if and only there are no arrivals in (0, t], which corresponds to X1 = k for some k > t. For the middle part, the age is i for a given i < t if and only if there is an arrival at t − i and the next arrival epoch is after t, which means that the corresponding interarrival interval k exceeds i. The probability of an arrival at t−i, i.e., qt−i , depends only on the arrival epochs up to and including time t − i, which should be independent of the subsequent interarrival time, leading to the product in the middle term of (4.62). To be more precise about this independence, note that for i < t, qt−i = Pr{arrival at t − i} = X n≥1 pSn (t − i). (4.64) Given that Sn = t − i, the probability that Xn+1 = k is pX (k). This is the same for all n, establishing (4.62). For any ﬁxed i, k with i < k, note that only the middle term in (4.62) is relevant as t → 1. Using Blackwell’s theorem (4.61) to take the limit as t → 1, we get (4.63) The probabilities in the theorem, both for ﬁnite t and asymptotically as t → 1, are illus trated in Figure 4.17. The product form of the probabilities in (4.62) (as illustrated in the e (t) are independent, but this is incorrect ﬁgure) might lead one to think that Z(t) and X e because of the constraint that X (t) > Z(t). It is curious that in the asymptotic case, (4.63) e (t) = k, the age is equally likely to have any integer value shows that, for a given duration X from 0 to k − 1, i.e., for a given duration, the interarrival interval containing t is uniformly distributed around t. The marginal PMF for Z(t) is calculated below using (4.62). pZ(t) (i) = c ( FX (i) for i = t qt−i FcX (i) for 0 ≤ i < t . 0 otherwise (4.65) 196 3 CHAPTER 4. RENEWAL PROCESSES pX (5) pXr(4) r r 1 pX (3) r r Z(3) 2 1 0 0 pX (2) r r i pX (1) r r 1 k 2 r 3 r r 4 e X(3) r r r 5 r q1 r q2 r q3 6 a) Case where t = 3. 3 q pX (4) q r q q q pX (3) r r Z(1) 2 pX (2) r r i 1 pX (1) r r 0 0 1 k 2 r 3 r r 4 e X(1) q q q q q q q q q 5 1/X 1/X 1/X 1/X b) Asymptotic case where t → 1 e (t) and Z(t) in an arithmetic renewal Figure 4.17: Joint PMF, pXe (t)Z(t) (k, i) of X process with span 1. In part a), t = 3 and the PMF at each sample point is the product of two terms, qt−i = Pr{Arrival at t − i} and pX (k). Part b) is the asymptotic case where t → 1. Here the arrival probabilities become uniform. e (t) can be calculated where FcX (i) = pX (i+1) + pX (i+2) + · · · . The marginal PMF for X directly from (4.62), but it is simpliﬁed somewhat by recognizing that qj = m(j) − m(j − 1). (4.66) Substituting this into (4.62) and summing over age, pX(t) e (k) = £ § ( pX (k) m(t) − m(t−k) pX (k) m(t) £ § pX (k) m(t) + 1 for k < t for k = t . (4.67) for k > t The term +1 in the expression for k > t corresponds to the uppermost point for the given k in Figure 4.17a. This accounts P for the possibility of no arrivals up to time t. It is not immediately evident that k pX(t) e (k) = 1, but this can be veriﬁed from the renewal equation, (4.52). Blackwell’s theorem shows that the arrival probabilities tend to 1/X as t → 1, so the limiting marginal probabilities for age and duration become lim integer t→1 pZ(t) (i) = lim p e (k) integer t→1 X (t) = FcX (i) . X k pX (k) . X (4.68) (4.69) e (t) can also be found for all t from (4.62) and (4.63) The expected value of Z(t) and X respectively, but they don’t have a particularly interesting form. The asymptotic values as t → 1 are more simple and interesting. The asymptotic expected value for age is derived 4.7. RENEWAL-REWARD PROCESSES; ENSEMBLE-AVERAGES 197 below from (4.68).22 lim integer t→1 E [Z(t)] = X i = = = i lim integer t→1 pZ(t) (i) 1 1 1 j−1 1 X X 1 XX i pX (j) = i pX (j) X i=1 j=i+1 X j=2 i=1 1 1 X j(j − 1) pX (j) 2 X j=2 £ § E X2 1 − . 2 2X (4.70) £ § This limiting ensemble average age has the same dependence on E X 2 as the time average in (4.16), but, perhaps surprisingly, it is reduced from that amount by 1/2. To understand this, note that we have only calculated the expected age at integer values of t. Since arrivals occur only at integer values, the age for each sample function must increase with unit slope as t is increased from one integer to the next. The expected age thus also increases, and then at the next integer value, it drops discontinuously due to the probability of an arrival at that next integer. Thus the limiting value of E [Z(t)] has a saw tooth shape and the value at each discontinuity is the lower side of that discontinuity. Averaging this asymptotic £ 2§ expected age over a unit of time, the average is E X /2X, in agreement with (4.16). £ § As with the time average, the limiting expected age is inﬁnite if E X 2 = 1. However, for each t, Z(t) ≤ t, so E [Z(t)] < 1 for all t, increasing without bound as t → 1 The asymptotic expected duration is derived in a similar way, starting from (4.69) lim integer t→1 h i X e (t) = E X k = lim integer t→1 X k2 pX (k) k X kpX(t) e (k) = £ § E X2 X . (4.71) This agrees with the time average in (4.17). The reduction by 1/2 seen in (4.70) is not present here, since as t is increased in the interval [t, t+1), X(t) remains constant. Since the asymptotic ensemble-average age diﬀers from the time-average age in only a trivial way, and the asymptotic ensemble-average duration is the same as the time-average duration, it might appear that we have gained little by this exploration of ensemble averages. What we have gained, however, is a set of results that apply to all t. Thus they show how (in principle) these results converge as t → 1. 22 Finding the limiting expectations from the limiting PMF’s requires interchanging a limit with an ex pectation. This can be justiﬁed (in both (4.70) and (4.71)) by assuming that X has a ﬁnite second moment and noting that all the terms involved are positive, that Pr{arrival at j} ≤ 1 for all j, and that pX (k) ≤ 1 for all k. 198 CHAPTER 4. RENEWAL PROCESSES 4.7.2 Joint age and duration: non-arithmetic case Non-arithmetic renewal processes are mathematically more complicated than arithmetic re newal processes, but the concepts are the same. We start by looking at the joint probability of the age and duration, each over an incremental interval. (see Figure 4.18 (a)). ✲ ° ° Z(t) ° ° z+δ A ° z ° x ° x−δ ° ° ✲ ° ° Z(t) ° z+δ ° ° B °T ✛ z °° ° ° ° e (t) X (a) ✲ t ✲ ✲ ✲ ✲ e (t) X (b) Figure 4.18: Part (a): The incremental square region A of sample values for Z(t) e (t) whose joint probability is speciﬁed in (4.73). The square is assumed to be and X inside the indicated semi-inﬁnite trapezoidal region, i.e., to satisfy 0 ≤ z < z+δ ≤ t and z+2δ ≤ x. e (t) to ﬁnd the marginal Part (b): Summing over discrete sample regions of X probability Pr{z ≤ Z(t) < z+δ} = Pr{T } + Pr{B}, where T is the triangular area and B the set of indicated squares. e (t) Theorem 4.7.2. Consider an arbitrary renewal process with age Z(t) and duration X at any given time t > 0. Let A be the event \ e (t) ≤ x}, A = {z ≤ Z(t) < z+δ} {x−δ < X (4.72) where 0 ≤ z < z+δ ≤ t and z+2δ ≤ x. Then £ §£ § Pr{A} = m(t−z) − m(t−z−δ) FX (x) − FX (x−δ) . If in addition the renewal process is non-arithmetic, £ § FX (x) − FX (x−δ) lim Pr{A} = . t→1 X (4.73) (4.74) Proof: Note that A is the box illustrated in Figure 4.18 (a) and that under the given e (t) > Z(t) for all sample points in A. Recall that Z(t) = t − SN (t) and conditions, X e (t) = SN (t)+1 − SN (t) = XN (t)+1 , so A can also be expressed as X A = {t−z−δ < SN (t) ≤ t − z} \ {x − δ < XN (t)+1 ≤ x}. (4.75) 4.7. RENEWAL-REWARD PROCESSES; ENSEMBLE-AVERAGES 199 We now argue that A can also be rewritten as A= 1 n o [ \ {t−z−δ < Sn ≤ t − z} {x − δ < Xn+1 ≤ x} . (4.76) n=1 To see this, ﬁrst assume that the event in (4.75) occurs. Then N (t) must have some positive sample value n, so (4.76) occurs. Next assume that the event in (4.76) occurs, which means that one of the events, say the nth, in the union occurs. Since Sn+1 = Sn + Xn+1 > t, we see that n is the sample value of SN (t) and (4.75) must occur. To complete the proof, we must ﬁnd Pr{A}. First note that A is a union of disjoint events. That is, although more than one arrival epoch might occur in (t−z−δ, t−z], the following arrival epoch can exceed t for only one of them. Thus Pr{A} = 1 X n=1 n o \ Pr {t−z−δ < Sn ≤ t − z} {x − δ < Xn+1 ≤ x} . (4.77) For each n, Xn+1 is independent of Sn , so n o \ Pr {t−z−δ < Sn ≤ t − z} {x − δ < Xn+1 ≤ x} © ™£ § = Pr t−z−δ < Sn ≤ t − z FcX (x) − FcX (x−δ . Substituting this into (4.77) and using (4.51) to sum the series, we get £ §£ § Pr{A} = m(t−z) − m(t−z−δ) FX (x) − FX (x−δ) . This establishes (4.73). Blackwell’s theorem then establishes (4.74). It is curious that Pr{A} has such a simple product expression, where one term depends only on the function m(t) and the other only on the distribution function FX . Although the theorem is most useful as δ → 0, the expression is exact for all δ such that the square region A satisﬁes the given constraints (i.e., A lies in the indicated semi-inﬁnite trapezoidal region). 4.7.3 Age Z(t) for ﬁnite t: non-arithmetic case In this section, we ﬁrst use Theorem 4.7.2 to ﬁnd bounds on the marginal incremental probability of Z(t). We then ﬁnd the distribution function, FZ(t) (z), and the expected value, E [Z(t)] of Z(t). Corollary 4.7.1. For 0 ≤ z < z+δ ≤ t, the following bounds hold on Pr{z ≤ Z(t) < z+δ}. £ § Pr{z ≤ Z(t) < z+δ} ≥ m(t−z) − m(t−z−δ) FcX (z+δ) (4.78) § c £ Pr{z ≤ Z(t) < z+δ} ≤ m(t−z) − m(t−z−δ) FX (z). (4.79) Proof*: As indicated in Figure 4.18 (b), Pr{z ≤ Z(t) < z+δ} = Pr{T } + Pr{B}, where T is the triangular region, \ e T = {z ≤ Z(t) < z+δ} {Z(t) < X(t) ≤ z+δ}, 200 CHAPTER 4. RENEWAL PROCESSES and B is the rectangular region B = {z ≤ Z(t) < z+δ} \ e (t) > z+δ}. {X It is easy to ﬁnd Pr{B} by summing the probabilities in (4.73) for the squares indicated in Figure 4.18 (b). The result is £ § Pr{B} = m(t−z) − m(t−z−δ) FcX (z+δ). (4.80) Since Pr {T } ≥ 0, this establishes the lower bound in (4.78). We next need an upper bound to Pr{T } and start by ﬁnding an event that includes T . \ e T = {z ≤ Z(t) < z + δ} {Z(t) < X(t) ≤ z + δ} i [h \ = {t − z − δ < Sn ≤ t − z } {t − Sn < Xn+1 ≤ z + δ } n≥1 ⊆ i [h \ {t − z − δ < Sn ≤ t − z } {z < Xn+1 ≤ z + δ } , n≥1 where the inclusion follows from the fact that Sn ≤ t − z for the event on the left to occur, and this implies that z ≤ t − Sn . Using the union bound, we then have hX i£ § Pr{T } ≤ Pr{{t − z − δ < Sn ≤ t − z} FcX (z) − FcX (z + δ) n≥1 §£ § £ = m(t−z) − m(t−z−δ) FcX (z) − FcX (z + δ) . Combining this with (4.80), we have (4.79). The following corollary uses Corollary 4.7.1 to determine the distribution function of Z(t). The rather strange dependence on the existence of a Stieltjes integral will be explained after the proof. Rt Corollary 4.7.2. If the Stieltjes integral t−z FcX (t − τ ) dm(τ ) exists for given t > 0 and 0 < z < t, then Z t Pr{Z(t) ≤ z} = FcX (t − τ ) dm(τ ). (4.81) t−z Proof: First, partition the interval [0, z) into a given number ` of increments, each of size δ = z/`. Then Pr{Z(t) < z} = `−1 X k=0 Pr{kδ ≤ Z(t) < kδ + δ} . Applying the bounds in 4.78 and 4.79 to the terms in this sum, Pr{Z(t) < z} ≥ Pr{Z(t) < z} ≤ `−1 h X ° ° ¢i m t − kδ) − m t − kδ − δ FcX (kδ + δ) k=0 `−1 h X k=0 ° ¢ ° ¢i ° ¢ m t − kδ − m t − kδ − δ FcX kδ . (4.82) (4.83) 4.7. RENEWAL-REWARD PROCESSES; ENSEMBLE-AVERAGES These are, respectively, lower and upper Riemann sums for the Stieltjes integral Thus, if this Stieltjes integral exists, then, letting δ = z/` → 0, Z Pr{Z(t) < z} = t t−z 201 Rz 0 FcX (t−τ ) dm(τ ). FcX (t − τ ) dm(τ ). This is a convolution and thus the Stieltjes integral exists unless m(τ ) and FcX (t − τ ) both have a discontinuity at some τ ∈ [0, z] (see Exercise 1.12). If no such discontinuity exists, then Pr{Z(t) < z} cannot have a discontinuity at z. Thus, if the Stieltjes integral exists, Pr{Z(t) < z} = Pr{Z(t) ≤ z}, and, for z < t, FZ(t) (z) = Z t t−z FcX (t − τ ) dm(τ ). The above argument showed us that the values of z at which the Stieltjes integral in (4.81) fails to exist are those at which FZ(t) (z) has a step discontinuity. At these values we know that FZ(t) (z) (as a distribution function) should have the value at the top of the step (thus including the discrete probability that Pr{Z(t) = z}). In other words, at any point z of discontinuity where the Stieltjes integral does not exist, FZ(t) (z) is the limit23 of FZ(t) (z+≤) as ≤ > 0 approaches 0. Another way of expressing this is that for 0 ≤ z < t, FZ(t) (z) is the limit of the upper Riemann sum on the right side of (4.83). The next corollary uses an almost identical argument to ﬁnd E [Z(t)]. As we will see, the Stieltjes integral fails to exist at those values of t at which there is a discrete positive probability of arrival. The expected value at these points is the lower Riemann sum for the Stieltjes integral. Corollary 4.7.3. If the Stieltjes integral E [Z(t)] = FcX (t) + Rt 0 Z 0 t FcX (t − τ ) dm(τ ) exists for given t > 0, then (t − τ )FcX (t − τ ) dm(τ ). (4.84) Proof: Note that Z(t) = t if and only if X1 > t, which has probability FcX (t). For the other possible values of Z(t), we divide [0, t) into ` equal intervals of length δ = t/` each. Then E [Z(t)] can be lower bounded by E [Z(t)] ≥ FcX (t) + ≥ FcX (t) + 23 `−1 X k=0 `−1 X k=0 kδ Pr{kδ ≤ Z(t) < kδ + δ}} £ § kδ m(t−kδ) − m(t−kδ−δ) FcX (kδ + δ). This seems to be rather abstract mathematics, but as engineers, we often evaluate functions with step discontinuities by ignoring the values at the discontinuities or evaluating these points by adhoc means. 202 CHAPTER 4. RENEWAL PROCESSES where we used 4.78 for the second step. Similarly, E [Z(t)] can be upper bounded by E [Z(t)] ≤ FcX (t) + `−1 X (kδ + δ)Pr{kδ ≤ Z(t) < kδ + δ}} k=0 `−1 X £ § ≤ FcX (t) + (kδ + δ) m(t−kδ) − m(t−kδ−δ) FcX (kδ). k=0 where we used 4.79 for the second step. These provide lower and upper Riemann sums to the Stieltjes integral in (4.81), completing the proof in the same way as the previous corollary. 4.7.4 Age Z(t) as t → 1: non-arithmetic case Next, for non-arithmetic renewal processes, we want to ﬁnd the limiting values, as t → 1, for FZ(t) (z) and E [Z(T )]. Temporarily ignoring any subtleties about the limit, we ﬁrst view dt dm(t) as going to X as t → 1. Thus from (4.81), 1 lim Pr{Z(t) ≤ z} = t→1 X Z 0 z FcX (τ )dτ. (4.85) If X has a PDF, this simpliﬁes further to lim fZ(t) (z) = t→1 1 fX (z). X (4.86) Note that this agrees with the time-average result in (4.29). Taking these limits carefully requires more mathematics than seems justiﬁed here, especially since the result uses Black well’s theorem, which was not proven here. Thus we state (without proof) another theorem, equivalent to Blackwell’s theorem, called the key renewal theorem, that simpliﬁes taking this type of limit. Essentially Blackwell’s theorem is easier to interpret, but the key renewal theorem is often easier to use. Theorem 4.7.3 (Key renewal theorem). Let r(x) ≥ 0 be a directly Riemann integrable function, and let m(t) = E [N (t)] for a non-arithmetic renewal process. Then Z t Z 1 1 lim r(t − τ )dm(τ ) = r(x)dx. (4.87) t→1 τ =0 X 0 We ﬁrst explain what directly Riemann integrable means. If r(x) is nonzero only over ﬁnite limits, say [0, b], then direct Riemann integration means the same thing as ordinary Riemann integration (as learned in elementary calculus). However, if r(x) is nonzero over [0, 1), then the ordinary Riemann integral (if it exists) is the result of integrating from 0 to b and then taking the limit as b → 1. The direct Riemann integral (if it exists) is the result of taking a Riemann sum over the entire half line, [0, 1) and then taking the limit as the grid becomes ﬁner. Exercise 4.25 gives an example of a simple but bizarre function that is Riemann integrable but not directly Riemann integrable. If r(x) ≥ 0 can be upper 4.7. RENEWAL-REWARD PROCESSES; ENSEMBLE-AVERAGES 203 bounded by a decreasing Riemann integrable function, however, then, as shown in Exercise 4.25,r(x) must be directly Riemann integrable. The bottom line is that restricting r(x) to be directly Riemann integrable is not a major restriction. Next we interpret the theorem. If m(t) has a derivative, then Blackwell’s theorem would suggest that dm(t)/dt → (1/X) dt, which leads to (4.87) (leaving out the mathematical details). On the other hand, if X is discrete but non-arithmetic, then dm(t)/dt can be intuitively viewed as a sequence of impulses that become smaller and more closely spaced as t → 1. Then r(t) acts like a smoothing ﬁlter which, as t → 1, smoothes these small impulses. The theorem says that the required smoothing occurs whenever r(t) is directly Riemann integrable. The theorem does not assert that the Stieltjes integral exists for all t, but only that the limit exists. For most applications to discrete inter-renewal intervals, the Stieltjes integral does not exist everywhere. Using the key renewal theorem, we can ﬁnally determine the distribution function and expected value of Z(t) as t → 1. These limiting ensemble averages are, of course, equal to the time averages found earlier. Theorem 4.7.4. For any non-arithmetic renewal process, the limiting distribution function and expected value of the age Z(t) are given by Z 1 z c lim FZ(t) (z) = FX (x) dx. (4.88) t→1 X 0 £ § Furthermore, if E X 2 < 1, then £ § E X2 lim E [Z(t)] = . (4.89) t→z 2X Proof: For any given z > 0, let r(x) = FcX (x) for 0 ≤ x ≤ z and r(x) = 0 elsewhere. Then (4.81) becomes Z t Pr{Z(t) ≤ z} = r(t − τ ) dm(τ ). 0 Taking the limit as t → 1, lim Pr{Z(t) ≤ z} = Z t lim r(t − τ ) dm(τ ) t→1 t→1 0 Z Z 1 1 1 z c = r(x) dx = FX (x) dx, (4.90) X 0 X 0 where in (4.90) we used the fact that FcX (x) is decreasing to justify using (4.87). This establishes (4.88). To establish (4.89), we again use the key renewal theorem, but here we £let r(x) = x FcX (x). § c 2 Exercise 4.25 shows that x FX (x) is directly Riemann integrable if E X < 1. Then, taking the limit of (4.84 and then using (4.87), we have Z t c lim E [Z(t)] = lim FX (t) + r(t − τ ) dm(τ ) t→1 t→1 0 Z Z 1 1 1 1 c = r(x) dx = xFX (x) dx. X 0 X 0 Integrating this by parts, we get (4.89). 204 4.7.5 CHAPTER 4. RENEWAL PROCESSES Arbitrary renewal-reward functions: non-arithmetic case If we omit all the mathematical precision from the previous three subsections, we get a very simple picture. We started with (4.72), which gave the probability of an incremental e (t)) plane for given t. We then converted various sums over square region A in the (Z(t), X an increasingly ﬁne grid of such regions into Stieltjes integrals. These integrals evaluated the distribution and expected value of age at arbitrary values of t. Finally, the key renewal theorem let us take the limit of these values as t → 1. In this subsection, we will go through the same procedure for an arbitrary reward function, e say £ R(t) §= R(Z(t), X (t)), and show how to ﬁnd E [R(T )]. Note that Pr{Z(t) ≤ z} = E IZ(t)≤z is a special case of E [R(T )] where R(t) is chosen to be IZ(t)≤z . Similarly, ﬁnding the distribution function at a given argument for any rv can be converted to the expectation of an indicator function. Thus, having a methodology for ﬁnding the expectation of an arbitrary reward function also covers distribution functions and many other quantities of interest. We will leave out all the limiting arguments here about converting ﬁnite incremental sums of areas into integrals, since we have seen how to do that in treating Z(t). In order to make this general case more transparent, we use the following shorthand for A when it is incrementally small: Pr{A} = m0 (t − z)fX (x) dx dz, (4.91) where, if the derivatives exist, m0 (τ ) = dm(τ )/dτ and fX (x) = dFX (x)/dx. If the derivatives do not exist, we can view m0 (τ ) and fX (x) as generalized functions including impulses, or, more appropriately, view them simply as shorthand. After using the shorthand as a guide, we can put the results in the form of Stieltjes integrals and verify the mathematical details at whatever level seems appropriate. n o e We do this ﬁrst for the example of the distribution function of duration, Pr X(t) ≤ x0 , where we ﬁrst assume that x0 ≤ t. As illustrated in Figure 4.19, the corresponding reward e e function R(t) is 1 in the triangular region where X(t) ≤ x0 and Z(t) < X(t). It is 0 elsewhere. ✲t ° ♣♣ ♣♣ ♣♣♣ ° ♣ ♣♣♣ ° Z(t) ° ♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ° e ♣ ♣ ° ♣♣ ♣♣ ♣♣ ♣♣ ♣♣≤♣♣ ♣♣x♣♣ 0 ♣♣ X(t) ♣ ♣ ♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ° ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣ ° ♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ♣♣♣ ° ♣ ° ✲ e (t) x0 X ° ° ° ° ° ° ° ° ° ° ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ e X(t) > x0 ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ e (t) x0 X Figure 4.19: Finding FXe (t) (x0 ) for x0 ≤ t and for x0 > t. ♣♣✲ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ♣♣ ✲ 4.7. RENEWAL-REWARD PROCESSES; ENSEMBLE-AVERAGES Z x0 Z x0 n o e (t) ≤ x0 Pr X = m0 (t − z)fX (x) dx dz x=z Zz=0 x0 £ § = m0 (t−z) FX (x0 ) − FX (z) dz z=0 Z t £ § = FX (x0 ) m(t) − m(t−x0 ) − FX (t−τ ) dm(τ ). 205 (4.92) t−x0 n o e > x0 . As shown in the For the opposite case, where x0 > t, it is easier to ﬁnd Pr X(t) e ﬁgure, this is the region where 0 ≤ Z(t) ≤ t and X(t) > x0 . There is a subtlety here in that the incremental areas we are using are only valid n for Z(t) < t. If the o age is equal to t, then e no renewals have occured in (0, t], so that Pr X (t) > x0 ; Z(t) = t = FcX (x0 ). Thus Z n o c e Pr X (t) > x0 = FX (x0 ) + t− z=0 Z 1 x=x0 m0 (t − z)fX (x) dx dz = FcX (x0 ) + m(t)FcX (x0 ). (4.93) As a sanity test, the renewal equation, (4.53), can be used to show that the sum of (4.92) and (4.93) at x0 = t is equal to 1 (as they must be if the equations are correct). n o e We can now take the limit, limt→1 Pr X(t) ≤ x0 . For any given x0 , (4.92) holds for suﬃciently large t, and the key renewal theorem can be used since the integral has a ﬁnite range. Thus, Z x0 n o i 1h e lim Pr X(t) ≤ x0 = x0 FX (x0 ) − FX (x) dx t→1 X 0 Z x0 h i 1 = FX (x0 ) − FX (x) dx X 0 Z x0 h i 1 c = FcX (x) − dFX (x0 ) dx. (4.94) X 0 It is easy to see that the right side of (4.94) is increasing from 0 to 1 with increasing x0 , i.e., it is a distribution function. After this example, it is now straightforward to write down the expected value of an arbitrary renewal-reward function R(t) whose sample value at Z(t) = z and X(t) = x is denoted by R(z, x). We have Z 1 Z t Z 1 E [R(t)] = R(t, x) dFX (x) + R(z, x) dFX (x) dm(t − z). (4.95) x=t z=0 x=z The ﬁrst term above arises from the subtlety discussed above for the case where Z(t) = t. The second term is simply the integral over the semi-inﬁnite trapezoidal area in Figure 4.19. The analysis up to this point applies to both the arithmetic and nonarithmetic cases, but we now must assume again that the renewal process is nonarithmetic. If the inner integral, 206 CHAPTER 4. RENEWAL PROCESSES R1 i.e., x=z R(z, x) dFX (x), as a function of z, is directly Riemann integrable, then not only can the key renewal theorem be applied to this second term, but also the ﬁrst term must approach 0 as t → 1. Thus the limit of (4.95) as t → 1 is Z Z 1 1 1 lim E [R(t)] = R(z, x) dFX (x) dz. (4.96) t→1 X z=0 x=z This is the same expression as found for the time-average renewal reward in Theorem 4.4.1. Thus, as indicated earlier, we can now equate any time-average result for the nonarithmetic case with the corresponding limiting ensemble average, and the same equations have been derived in both cases. h i e As a simple example of (4.96), let R(z, t) = x. Then E [R(t)] = E X(t) and h i e (t) = lim E X t→1 = Z 1Z 1 Z 1 Z x 1 x dFX (x) dz = x dz dFX (x) X z=0 x=z x=0 z=0 £ § Z E X2 1 1 2 x dFX (x) = . X x=0 X (4.97) After calculating the integral above by interchanging the £ order § of integration, we can go 2 back and assert that the key renewalh theorem applies if E X is ﬁnite. If it is inﬁnite, then i e it is not hard to see that limt→1 E X(t) is inﬁnite also. It has been important, and theoretically reassuring, to be able to ﬁnd ensemble-averages for nonarithmetic renewal-reward functions in the limit of large t and to show (not surprisingly) that they are the same as the time-average results. The ensemble-average results are quite tricky, though, and it is wise to check results achieved that way with the corresponding time-average results. 4.8 Delayed renewal processes We have seen a certain awkwardness in our discussion of Little’s theorem and the M/G/1 delay result because an arrival was assumed, but not counted, at time 0; this was necessary for the ﬁrst inter-renewal interval to be statistically identical to the others. In this section, we correct that defect by allowing the epoch at which the ﬁrst renewal occurs to be arbi trarily distributed. The resulting type of process is a generalization of the class of renewal processes known as delayed renewal processes. The word delayed does not necessarily imply that the ﬁrst renewal epoch is in any sense larger than the other inter-renewal intervals. Rather, it means that the usual renewal process, with IID inter-renewal times, is delayed until after the epoch of the ﬁrst renewal. What we shall discover is intuitively satisfying — both the time-average behavior and, in essence, the limiting ensemble behavior are not aﬀected by the distribution of the ﬁrst renewal epoch. It might be somewhat surprising, however, to ﬁnd that this irrelevance of the distribution of the ﬁrst renewal epoch holds even when the mean of the ﬁrst renewal epoch is inﬁnite. To be more precise, we let {Xi ; i≥1} be a set of independent nonnegative random variables. X1 has a given distribution function G(x), whereas {Xi ; i ≥ 2} are identically distributed 4.8. DELAYED RENEWAL PROCESSES 207 with a given distribution function F(x). Thus a renewal P process is a special case of a delayed renewal process for which G(x) = F(x). Let Sn = ni=1 Xi be the nth renewal epoch. We ﬁrst show that the SLLN still holds despite the deviant behavior of X1 . Lemma 4.8.1. Let {Xi ; i ≥ 2 be IID with aPmean X satisfying E [|X |] < 1 and let X1 be a rv, independent of {Xi ; i ≥ 2}. Let Sn = ni=1 Xi . Then lim Sn /n = X WP1. Prrof: Note that Pn Xi Sn X1 = + i=2 . n n n Since X1 is ﬁnite WP1, the ﬁrst term above goes to 0 WP1 as n → 1. The second term goes to X, proving the lemma (which is thus a trivial variation of the SLLN). Now, for the given delayed renewal process, let N (t) be the number of renewal epochs up to and including time t. This is still determined by the fact that {N (t) ≥ n} if and only if {Sn ≤ t}). {N (t); t > 0} is then called a delayed renewal counting process. The following simple lemma follows from lemma 4.3.1. Lemma 4.8.2. Let {N (t); t > 0} be a delayed renewal counting process. Then limt→1 N (t) = 1 with probability 1 and limt→1 E [N (t)] = 1. Proof: Conditioning on X1 = x, we can write N (t) = 1 + N 0 (t − x) where N 0 {t; t ≥ 0} is the ordinary renewal counting process with inter-renewal intervals X2 , X3 , . . . . From Lemma 4.3.1, limt→1 N 0 (t − x) = 1 with probability 1, and limt→1 E [N 0 (t − x)] = 1. Since this is true for every ﬁnite x > 0, and X1 is ﬁnite with probability 1, the lemma is proven. Theorem 4.8.1 (Strong Law for Delayed Renewal Processes). Let N (t); t > 0 be the renewal counting process for a delayed renewal process where the inter-renewal intervals R1 X2 , X3 , . . . , have distribution function F and ﬁnite mean X = x=0 [1 − F(x)] dx. Then N (t) 1 = t→1 t X lim WP1. (4.98) Proof: Using Lemma 4.8.1, the conditions for Theorem 4.3.2 are fulﬁlled, so the proof follows exactly as the proof of Theorem 4.3.1. . Next we look at the elementary renewal theorem and Blackwell’s theorem for delayed re newal processes. To do this, we view a delayed renewal counting process {N (t); t > 0} as an ordinary renewal counting process that starts at a random nonnegative epoch X1 with some distribution function G(t). Deﬁne No (t − X1 ) as the number of renewals that occur in the interval (X1 , t]. Conditional on any given sample value x for X1 , {No (t − x); t−x > 0} is an ordinary renewal counting process and thus, given X1 = x, limt→1 E [No (t − x)] /(t − x) = 1/X. Since N (t) = 1 + No (t − X1 ) for t > X1 , we see that, conditional on X1 = x, E [N (t) | X1 =x] E [No (t − x)] t − x 1 = lim = . (4.99) t→1 t t−x t X Since this is true for every ﬁnite sample value x for X1 , we we have established the following theorem: lim t→1 208 CHAPTER 4. RENEWAL PROCESSES Theorem 4.8.2 (Elementary Delayed Renewal Theorem). For a delayed renewal pro cess with E [Xi ] = X for i ≥ 2, lim t→1 E [N (t)] 1 = . t X (4.100) The same approach gives us Blackwell’s theorem. Speciﬁcally, if {Xi ; i≥2} is a sequence of IID non-arithmetic rv’s, then, for any δ > 0, Blackwell’s theorem for ordinary renewal processes implies that lim t→1 E [No (t − x + δ) − No (t − x)] 1 = . δ X (4.101) Thus, conditional on any sample value X1 = x, limt→1 E [N (t+δ) − N (t) | X1 =x] = δ/X. Taking the expected value over X1 gives us limt→1 E [N (t + δ) − N (t)] = δ/X. The case in which {Xi ; i≥2} are arithmetic with span ∏ is somewhat more complicated. If X1 is arithmetic with span ∏ (or a multiple of ∏), then the ﬁrst renewal epoch must be at some multiple of ∏ and ∏/X gives the expected number of arrivals at time i∏ in the limit as i → 1. If X1 is non-arithmetic or arithmetic with a span other than a multiple of ∏, then the eﬀect of the ﬁrst renewal epoch never dies out, since all subsequent renewals occur at multiples of ∏ from this ﬁrst epoch. We ignore this rather ugly case and state the following theorem for the nice situations. Theorem 4.8.3 (Blackwell for Delayed Renewal). If {Xi ; i≥2} are non-arithmetic, then, for all δ > 0, lim t→1 E [N (t + δ) − N (t)] 1 = . δ X (4.102) If {Xi ; i ≥ 2} are arithmetic with span ∏ and mean X and X1 is arithmetic with span m∏ for some positive integer m, then lim Pr{renewal at t = i∏} = i→1 4.8.1 ∏ . X (4.103) Delayed renewal-reward processes We have seen that the distribution of the ﬁrst renewal epoch has no eﬀect on the time or ensemble-average behavior of a renewal process (other than the ensemble dependence on time for an arithmetic process). This carries over to reward functions with almost no change. In particular, the generalized version of Theorem 4.4.1 is as follows: Theorem 4.8.4. Let {N (t); t > 0} be a delayed renewal counting process where the interrenewal intervals X2 , X3 , . . . have the distribution function F. Let Z(t) = t − SN (t) , let e e (t)) be a reward function. Assume that X(t) = SN (t)+1 − SN (t) , and let R(t) = R(Z(t), X Z 1 Z x E [Rn ] = R(z, x) dz dF(x) < 1 . x=0 z=0 4.8. DELAYED RENEWAL PROCESSES 209 Then, with probability one, 1 lim t→1 t Z t R(τ )dτ = τ =0 E [Rn ] for n ≥ 2. X2 (4.104) We omit the proof of this since it is a minor variation of that of theorem 4.4.1. Finally, the equivalence of time and limiting ensemble averages holds as before, yielding lim E [R(t)] = t→1 4.8.2 E [Rn ] . X2 (4.105) Transient behavior of delayed renewal processes Let m(t) = E [N (t)] for a delayed renewal process. As in (4.51), we have m(t) = 1 X n=1 Pr{N (t) ≥ n} = 1 X n=1 Pr{Sn ≤ t} . (4.106) For n ≥ 2, Sn = Sn−1 + Xn where Xn and Sn−1 are independent. From the convolution equation (1.12), Pr{Sn ≤ t} = Z t x=0 Pr{Sn−1 ≤ t − x} dF(x) for n ≥ 2. (4.107) For n = 1, Pr{Sn ≤ t} = G(t). Substituting this in (4.106) and interchanging the order of integration and summation, m(t) = G(t) + = G(t) + = G(t) + Z t 1 X x=0 n=2 Z t X 1 x=0 n=1 Z t x=0 Pr{Sn−1 ≤ t − x} dF(x) Pr{Sn ≤ t − x} dF(x) m(t − x)dF(x) ; t ≥ 0. (4.108) This is the renewal equation for delayed renewal processes and is a generalization of (4.52). It is shown to have a unique solution in [8], Section 11.1. There is another useful integral equation very similar to (4.108) that arises from breaking up Sn as the sum of X1 and Sbn−1 where Sbn−1 = X2 + · · · +Xn . Letting m(t) b be the expected number of renewals in time t for an ordinary renewal process with interarrival distribution F, o Rt n b a similar argument to that above, starting with Pr{Sn ≤ t} = 0 Pr Sn−1 ≤ t − x dG(x) yields m(t) = G(t) + Z t x=0 m(t b − x)dG(x). (4.109) 210 CHAPTER 4. RENEWAL PROCESSES This equation brings out the eﬀect of the initial renewal interval clearly, and is useful in computation if one already knows m(t). b Frequently, the most convenient way of dealing with m(t) is through transforms. Following the same argument as that in (4.54), we get Lm (r) = (1/r)LG (r) + Lm (r)LF (r). Solving, we get Lm (r) = LG (r) . r[1 − LF (r)] (4.110) We can ﬁnd m(t) from (4.110) by ﬁnding the inverse Laplace transform, using the same procedure as in Example 4.6.1. There is a second order pole at r = 0 again, and, evaluating the residue, it is 1/L0F (0) = 1/X 2 , which is not surprising in terms of Blackwell’s theorem. We can also expand numerator and denominator of (4.110) in a power series, as in (4.55). The inverse transform, corresponding to (4.56), is £ § E X22 t X1 m(t) = + − + ≤(t) for t → 0, (4.111) X 2X X where limt→1 ≤(t) = 0. 4.8.3 The equilibrium process Consider an ordinary non-arithmetic renewal process with an inter-renewal interval X of distribution F(x). We have seen that Rthe distribution of the interval from t to the next y renewal approaches FY (y) = (1/E [X]) 0 [1 − F(x)]dx as t → 1. This suggests that if we look at this renewal process starting at some very large t, we should see a delayed renewal process for which the distribution G(x) of the ﬁrst renewal is equal to the residual life distribution FY (x) above and subsequent inter-renewal intervals should have the original distribution F(x) above. Thus it appears that such a delayed renewal process is the same as the original ordinary renewal process, except that it starts in “steady state.” To verify this, we show that m(t) = t/X is a solution to (4.108) if G(t) = FY (t). Substituting (t − x)/X for m(t − x), the right hand side of (4.108) is Rt Rt Rt Rt F(x)dx t 0 [1 − F(x)]dx 0 (t − x)dF(x) 0 [1 − F(x)]dx + = + 0 = , X2 X X X X where we have used integration by parts for the ﬁrst equality. This particular delayed renewal process is called the equilibrium process, since it starts oﬀ in steady state, and thus has no transients. 4.9 Summary Sections 4.1 to 4.7 developed the central results about renewal processes that frequently appear in subsequent chapters. The chapter starts with the strong law for renewal processes, showing that the time average rate of renewals, N (t)/t, approaches 1/X with probability 4.10. EXERCISES 211 1 as t → 1. This, combined with the strong law of large numbers, is the basis for most subsequent results about time-averages. Section 4.4 adds a reward function R(t) to the underlying renewal process. These reward functions are deﬁned to depend only on the inter-renewal interval containing t, and are used to study many surprising aspects of renewal processes such as residual life, age, and duration. For all sample paths of a renewal process (except a subset of probabiity 0), the time-average reward for a given R(t) is a constant, and that constant is the expected aggregate reward over an inter-renewal interval divided by the expect length of an inter-renewal interval. The next topic, in Section 4.5 is that of stopping trials. These have obvious applications to situations where an experiment or game is played until some desired (or undesired) outcome (based on the results up to and including the given trial) occurs. This is a basic and important topic in its right, but is also needed to understand both how the expected renewal rate E [N (t)] /t varies with time t and how renewal theory can be applied to queueing situations. Finally, we found that stopping rules were helpful in understanding G/G/1 queues, especially Little’s theorem, and to derive an understand the Pollaczek-Khinchin expression for the expected delay in an M/G/1 queue. This is followed, in Section 4.6, by an analysis of how E [N (t)] /t varies with t. This starts by using Laplace transforms to get a complete solution of the ensemble-average, E [N (t)] /t, as a function of t, when the distribution of the inter-renewal interval has a rational Laplace transform. For the general case (where the Laplace transform is irrational or non-existant), the elementary renewal theorem shows that limt→1 E [N (t)] /t = 1/X. The fact that the time-average (WP1) and the limiting ensemble-average are the same is not surprising, and the fact that the ensemble-average has a limit is not surprising. These results are so fun damental to other results in probability, however, that they deserve to be understood. Another fundamental result in Section 4.6 is Blackwell’s renewal theorem, showing that the distribution of renewal epochs reach a steady state as t → 1. The form of that steady state depends on whether the inter-renewal distribution is arithmetic (see (4.59)) or nonarithmetic (see (4.58)). Section 4.7 ties together the results on rewards in 4.4 to those on ensemble averages in 4.6. Under some very minor restrictions imposed by the key renewal theorem, we found that, for non-arithmetic inter-renewal distributions, limt→1 E [R(t)] is the same as the time-average value of reward. Finally, all the results above were shown to apply to delayed renewal processes. For further reading on renewal processes, see Feller,[8], Ross, [16], or Wolﬀ, [22]. Feller still appears to be the best source for deep understanding of renewal processes, but Ross and Wolﬀ are somewhat more accessible.

Renewal Processes

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock