4.1: Introduction to Renewal Processes
- Page ID
- 44614
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 specified in three standard ways, first, by the joint distributions of the arrival epochs \(S_{1}, S_{2}, \ldots\), second, by the joint distributions of the interarrival times \(X_{1}, X_{2}, \ldots\), 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 \(X_{i}\), since they are IID. Each arrival epoch \(S_{n}\) is simply the sum \(X_{1}+X_{2}+\cdots+X_{n}\) of \(n\) IID rv’s. The characterization of greatest interest in this chapter is the renewal counting process, \(\{N(t) ; t>0\}\). Recall from \ref{2.2} and \ref{2.3} that the arrival epochs and the counting rv’s are related in each of the following equivalent ways.
\[\left\{S_{n} \leq t\right\}=\{N(t) \geq n\} ; \quad\left\{S_{n}>t\right\}=\{N(t)<n\}\label{4.1} \]
The reason for calling these processes renewal processes is that the process probabilistically starts over at each arrival epoch, \(S_{n}\). That is, if the nth arrival occurs at \(S_{n}=\tau\), then, counting from \(S_{n}=\tau\), the \(j^{\mathrm{t} h}\) subsequent arrival epoch is at \(S_{n+j}-S_{n}=X_{n+1}+\cdots+X_{n+j}\). Thus, given \(S_{n}=\tau,\{N(\tau+t)-N(\tau) ; t \geq 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 equivalent 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.
Suppose a recurrent finitestate Markov chain with transition matrix \([P]\) starts in state \(i\) at time 0. Then on the first 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 \(P_{i j}\), and, given a return to \(i\) at time \(n\), the probability of state \(j\) at time \(n+1\) is \(P_{i j}\). In the same way, for any \(m>0\),
\[\operatorname{Pr}\left\{X_{1}=j, \ldots, X_{m}=k \mid X_{0}=i\right\}=\operatorname{Pr}\left\{X_{n+1}=j, \ldots, X_{n+m}=k \mid X_{n}=i\right\}\label{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 infinite set of states in Chapter 5. At the same time, \ref{4.2} does not quite justify viewing successive returns to state \(i\) as a renewal process. The problem is that the time of the first 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.
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 \(X_{1}, X_{2}, \ldots\), 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 define a new counting process, \(\left\{N^{r}(t) ; t>0\right\}\), 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 \(\left\{N^{r}(t) t>0\right\}\) 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 first subsequent arrival to an empty system, at say epoch \(S_{1}^{r}>0\), the subsequent customer interarrival intervals are independent of the arrivals in \(\left(0, S_{1}^{r}\right)\) and are identically distributed to those earlier arrivals. The service times after \(S_{1}^{r}\) are also IID from those earlier. Finally, the conditions that cause queueing starting from the arrival to an empty system at \(t=S_{1}^{r}\) are the same as those starting from the arrival to an empty system at \(t=0\).
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 \(\left\{N^{r}(t) ; t>0\right\}\). 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 \(X_{n}^{r}\) of \(\left\{N^{r}(t) ; t>0\right\}\). Second, the general renewal results developed in this chapter can be applied to the distribution on \(X_{n}^{r}\) to understand the overall behavior of the queueing system.
Throughout our study of renewal processes, we use \(\bar{X}\) and \(\mathrm{E}[X]\) interchangeably to denote the mean inter-renewal interval, and use \(\sigma_{X}^{2}\) or simply \(\sigma^{2}\) to denote the variance of the inter-renewal interval. We will usually assume that \(\bar{X}\) is finite, but, except where explicitly stated, we need not assume that \(\sigma^{2}\) is finite. This means, first, that \(\sigma^{2}\) need not be calculated (which is often difficult if renewals are embedded into a more complex process), and second, since modeling errors on the far tails of the inter-renewal distribution typically affect \(\sigma^{2}\) more than \(\bar{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, \(\mathrm{E}[N(t)]<\infty\) for all \(t>0\). It is then also clear that \(N(t) / t\), which is interpreted as the time-average renewal rate over \((0, t]\), is also a rv with finite expectation.
One of the major results about renewal theory, which we establish shortly, concerns the behavior of the rv’s \(N(t) / t\) as \(t \rightarrow \infty\). For each sample point \(\omega \in \Omega\), \(N(t, \omega) / t\) is a nonnegative number for each \(t\) and \(\{N(t, \omega) ; t>0\}\) is a sample path of the counting renewal process, taken from \((0, t]\) for each \(t\). Thus \(\lim _{t \rightarrow \infty} N(t, \omega) / t\), if it exists, is the time-average renewal rate over \((0, \infty)\) for the sample point \(\omega\).
The strong law for renewal processes states that this limiting time-average renewal rate exists for a set of \(\omega\) that has probability 1, and that this limiting value is \(1 / \bar{X}\). We shall often refer to this result by the less precise statement that the time-average renewal rate is \(1 / \bar{X}\). This result is a direct consequence of the strong law of large numbers (SLLN) for IID rv’s. In the next section, we first 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 \(\mathrm{E}[N(t) / t]\) also approaches \(1 / \bar{X}\) as \(t \rightarrow \infty\). 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 final major theoretical result of the chapter is Blackwell’s theorem, which shows that, for appropriate values of \(\delta\), the expected number of renewals in an interval \((t, t+\delta]\) approaches \(\delta / \bar{X}\) as \(t \rightarrow \infty\). We shall thus interpret \(1 / \bar{X}\) as an ensemble-average renewal rate. This rate is the same as the above time-average renewal rate. We shall see the benefits 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.
1Renewal processes are often defined in a slightly more general way, allowing the interarrival intervals \(X_{i}\) to include the possibility \(1>\operatorname{Pr}\left\{X_{i}=0\right\}>0\). All of the theorems in this chapter are valid under this more general assumption, as can be verified by complicating the proofs somewhat. Allowing \(\operatorname{Pr}\left\{X_{i}=0\right\}>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 definition here, thus showing that the added generality is not worth much.
2There 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 simplifies the notation. The process is defined in terms of the IID inter-renewal intervals \(X_{1}, X_{2}, \ldots\) The first renewal epoch is at \(S_{1}=X_{1}\), and this is the point at which \(N(t)\) changes from 0 to 1.
3Readers who accept without question that \(\left\{N^{r}(t) t>0\right\}\) is a renewal process should be proud of their probabilistic intuition, but should also question exactly how such a conclusion can be proven.