]>
In the introduction to renewal processes, we noted that the arrival time process and the counting process are inverses, in a sense. The arrival time process is the partial sum process for a sequence of independent, identically distributed variables (the interarrival times). Thus, it seems reasonable that the fundamental limit theorems for partial sum processes (the law of large numbers and the central limit theorem theorem), should have analogs for the counting process. That is indeed the case, and the purpose of this section is to explore the limiting behavior of renewal processes. The main results that we will study, known appropriately enough as renewal theorems, are important for other stochastic processes, particularly Markov chains.
Thus, consider a renewal process with interarrival distribution and mean , with the assumptions and basic notation established in the introductory section. When , we let . When , we let denote the standard deviation of the interarrival distribution.
Suppose that . Show that with probability 1. Thus, is the limiting average rate of arrivals per unit time.
The purpose of this paragraph is to show that the counting variable is asymptotically normal. Thus, suppose that and are finite, and let
Show that the distribution of converges to the standard normal distribution as .
The Elementary Renewal Theorem states that the basic limit in the law of large numbers above holds in mean, as well as with probability 1. That is, the limiting mean average rate of arrivals is :
The elementary renewal theorem is of fundamental importance in the study of the limiting behavior of Markov chains. The proof, sketched in the following exercises, is not nearly as easy as one might hope (recall that convergence with probability 1 does not imply convergence in mean).
Show that .
For the next part of the proof, we will truncate the arrival times, and use the basic comparison method. For , let
and consider the renewal process with the sequence of interarrival times . We will use the standard notation developed in the introductory section..
Show that .
This section gives the deepest and most useful of the limit theorems in renewal theory. The proofs are rather complicated and are omitted. Suppose that the renewal process is aperiodic. The renewal theorem states that, asymptotically, the expected number of renewals in an interval is proportional to the length of the interval; the proportionality constant is . Specifically, for every ,
The renewal theorem is also known as Blackwell's theorem in honor of David Blackwell. The key renewal theorem is an integral version of the renewal theorem. Suppose again that the renewal process is aperiodic and suppose that is a decreasing function from to with . Then
The key renewal theorem can be extended to a more general class of functions known as directly Riemann integrable functions. The name, of course, refers to Georg Riemann. See Stochastic Processes by Sheldon Ross for more details.
Use the renewal theorem to prove the elementary renewal theorem:
Conversely, the elementary renewal theorem almost implies the renewal theorem. Assume that exists for each .
Show that the key renewal theorem implies the renewal theorem: apply the key renewal theorem to where .
Conversely, the renewal theorem implies the key renewal theorem.
Recall that the Poisson process, the most important of all renewal processes, has interarrival times that are exponentially distributed with rate parameter . Thus, the interarrival distribution function is for and the mean interarrival time is .
Verify each of the following directly:
Suppose that is a sequence of Bernoulli trials with success parameter . Recall that is a sequence of independent, identically distributed indicator variables with . We have studied a number of random processes derived from :
Consider the renewal process with interarrival sequence . Thus, is the mean interarrival time, and is the counting process. Verify each of the following directly:
Consider the renewal process with interarrival sequence . Thus, the mean interarrival time is . and the number of arrivals in the interval is for . Verify each of the following directly: