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 \(F\) and mean interarrival time \( \mu \), with the assumptions and basic notation established in the introductory section. When \(\mu = \infty\), we let \(1 / \mu = 0\). When \(\mu \lt \infty\), we let \(\sigma\) denote the standard deviation of the interarrival distribution.
If \(\mu \lt \infty\) then \( N_t / t \to 1 / \mu \) as \( t \to \infty \) with probability 1. Thus, \( 1 / \mu \) is the limiting average rate of arrivals per unit time.
Recall that \( T_{N_t} \le t \lt T_{N_t + 1} \) for \( t \gt 0 \). Hence, if \( N_t \gt 0 \),
\[ \frac{T_{N_t}}{N_t} \le \frac{t}{N_t} \lt \frac{T_{N_t + 1}}{N_t}\]Recall that \( N_t \to \infty \) as \( t \to \infty \) with probability 1. Recall also that by the strong law of large numbers that \( T_n / n \to \mu \) as \( n \to \infty \) with probability 1. It follows that \( T_{N_t} / N_t \to \mu \) as \( t \to \infty \) with probability 1. Also, \( (N_t + 1) / N_t \to 1\) as \( t \to \infty \) with probability 1. Therefore
\[ \frac{T_{N_t + 1}}{N_t} = \frac{T_{N_t + 1}}{N_t + 1} \frac{N_t + 1}{N_t} \to \mu \]as \( t \to \infty \) with probability 1. Hence by the squeeze theorem for limits, \( t / N_t \to \mu \) as \( t \to \infty \) with probability 1.
The purpose of this paragraph is to show that the counting variable \( N_t \) is asymptotically normal. Thus, suppose that \( \mu \) and \( \sigma \) are finite, and let
\[ Z_t = \frac{N_t - t / \mu}{\sigma \sqrt{t / \mu^3}}, \quad t \gt 0 \]The distribution of \( Z_t \) converges to the standard normal distribution as \( t \to \infty \).
Let \( W_n = \frac{T_n - n \, \mu}{\sigma \sqrt{n}} \) for \( n \in \N_+ \). The distribution of \( W_n \) converges to the standard normal distribution as \( n \to \infty \), by the ordinary central limit theorem. Next, for \( z \in \R \), \( \P(Z_t \le z) = \P(T_{n(z,t)} \gt t) \) where \( n(z, t) = \lfloor t / \mu + z\,\sigma \sqrt{t / \mu^3} \rfloor \). Also, \( \P(Z_t \le z) = \P[W_{n(z,t)} \gt w(z, t)] \) where \( w(z, t) = -z / \sqrt{1 + z \, \sigma / \sqrt{t / \mu}} \). But \( n(z, t) \to \infty \) as \( t \to \infty \) and \( w(z, t) \to -z \) as \( t \to \infty \). Recall that \( 1 - \Phi(-z) = \Phi(z) \), where as usual, \( \Phi \) is the standard normal distribution function. Thus, we conclude that \( \P(Z_t \le z) \to \Phi(z) \) as \( t \to \infty \).
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 \( 1 / \mu \). The elementary renewal theorem is of fundamental importance in the study of the limiting behavior of Markov chains, but the proof is not nearly as easy as one might hope. In particular, recall that convergence with probability 1 does not imply convergence in mean, so the elementary renewal theorem does not follow from the law of large numbers in Theorem 1.
The elementary renewal theorem: \( m(t) / t \to 1 / \mu \) as \( t \to \infty \).
We first show that \( \liminf_{t \to \infty} m(t) / t \ge 1 / \mu \). Note first that this result is trivial if \( \mu = \infty \), so assume that \( \mu \lt \infty \). Next, \( N_t + 1 \) is a stopping time for the sequence of interarrival times \( \bs{X} \). Recall that \( T_{N_t + 1} \gt t \) for \( t \gt 0 \). From Wald's equation it follows that \( [m(t) + 1] \mu \gt t \). Therefore \( m(t) / t \gt 1 / \mu - 1 / t \) for \( t \gt 0 \). Hence \( \liminf_{t \to \infty} m(t) / t \ge 1 / \mu \).
Next we show that \( \limsup_{t \to \infty} m(t) / t \le 1 / \mu \). For this part of the proof, we need to truncate the arrival times, and use the basic comparison method. For \( a \gt 0 \), let
\[ X_{a,i} = \begin{cases} X_i, & X_i \le a \\ a, & X_i \gt a \end{cases} \]and consider the renewal process with the sequence of interarrival times \( \bs{X}_a = (X_{a,1}, X_{a,2}, \ldots) \). We will use the standard notation developed in the introductory section. First note that \( T_{a, N_{a,t} + 1} \le t + a \) for \( t \gt 0 \) and \( a \gt 0 \). Fromm Wald's equation again, it follows that \( [m_a(t) + 1] \mu_a \le t + a \). Therefore
\[ \frac{m_a(t)}{t} \le \left(\frac{1}{\mu_a} + \frac{a}{t\,\mu_a}\right) - \frac{1}{t}, \quad a, \; t \gt 0 \]But \( m(t) \le m_a(t) \) for \( t \gt 0 \) and \( a \gt 0 \) and therefore
\[ \frac{m(t)}{t} \le \left(\frac{1}{\mu_a} + \frac{a}{t\,\mu_a} \right) - \frac{1}{t}, \quad a, \; t \gt 0 \]Hence \( \limsup_{t \to \infty} m(t) / t \le 1 / \mu_a \) for \( a \gt 0 \). Finally, \( \mu_a \to \mu \) as \( a \to \infty \) by the monotone convergence theorem, so it follows that \( \limsup_{t \to \infty} m(t) / t \le 1 / \mu \)
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 \( 1 / \mu \). Specifically, for every \( h \gt 0 \),
\[ m(t, t + h] \to \frac{h}{\mu} \text{ as } t \to \infty \]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 \( g: [0, \infty) \to [0, \infty) \) is decreasing with \( \int_0^\infty g(t) \, dt \lt \infty \). Then
\[ \int_0^t g(t - x) \, dm(x) \to \frac{1}{\mu} \int_0^\infty g(x) \, dx \text{ as } t \to \infty \]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.
The renewal theorem implies the elementary renewal theorem:
Let \( a_n = m(n, n + 1] \) for \( n \in \N \). From the renewal theorem, \( a_n \to 1 / \mu \) as \( n \to \infty \). Therefore \( \frac{1}{n} \sum_{k=0}^{n-1} a_k \to \frac{1}{\mu} \) as \( n \to \infty \). It follows that \( m(n) / n \to 1 / \mu \) as \( n \to \infty \). But the renewal function is increasing so for \( t \gt 0 \),
\[ \frac{\lfloor t \rfloor}{t} \frac{m(\lfloor t \rfloor)}{\lfloor t \rfloor} \le \frac{m(t)}{t} \le \frac{\lceil t \rceil}{t} \frac{m(\lceil t \rceil)}{\lceil t \rceil} \]From the the squeeze theorem for limits it follows that \( m(t) / t \to 1 / \mu \) as \( t \to \infty \).
Conversely, the elementary renewal theorem almost implies the renewal theorem.
Assume that \( g(x) = \lim_{t \to \infty} [m(t + x) - m(t)] \) exists for each \( x \gt 0 \). (This assumption is the reason that the proof is incomplete.) Note that
\[ m(t + x + y) - m(t) = [m(t + x + y) - m(t + x)] + [m(t + x) - m(t)] \]Let \( t \to \infty \) to conclude that \( g(x + u) = g(x) + g(y) \) for all \( x \ge 0 \) and \( y \ge 0 \). It follows that \( g \) is increasing and \( g(x) = c\,x \) for \( x \ge 0 \) where \( c \) is a constant. Exactly as in the proof of the previous theorem, it follows that \( m(n) / n \to c \) as \( n \to \infty \). From the elementary renewal theorem, we can conclude that \( c = 1 / \mu \).
The key renewal theorem implies the renewal theorem
This result follows by apply the key renewal theorem to the function \( g_h(x) = \bs{1}(0 \le x \le h) \) where \( h \gt 0 \).
Conversely, the renewal theorem implies the key renewal theorem. The key renewal theorem can be used to find the limiting distributions of the current and remaining age.
If the renewal process is aperiodic, then
\[ \P(R_t \gt x) \to \frac{1}{\mu} \int_x^\infty \bar{F}(y) \, dy \text{ as } t \to \infty, \quad x \in [0, \infty) \]Recall that
\[ \P(R_t \gt x) = \bar{F}(t + x) + \int_0^t \bar{F}(t + x - s) \, dm(s), \quad x \in [0, \infty) \]But \( \bar{F}(t + x) \to 0 \) as \( t \to \infty \), and by the key renewal theorem, the integral converges to \( \frac{1}{\mu} \int_0^\infty \bar{F}(x + y) \, dy \). Finally a change of variables in the limiting integral gives the result.
If the renewal process is aperiodic, then
\[ \P(R_t \gt x) \to \frac{1}{\mu} \int_x^\infty \bar{F}(y) \, dy \text{ as } t \to \infty, \quad x \in [0, \infty) \]Recall that, since the renewal process is aperiodic,
\[ \P(C_t \gt x) = \bar{F}(t) + \int_0^{t - x} \bar{F}(t - s) \, dm(s), \quad x \in [0, t] \]Again, \( \bar{F}(t) \to 0 \) as \( t \to \infty \). The change of variables \( u = t - x \) changes the integral into \( \int_0^u \bar{F}(u + x - s) \, dm(s) \). By the key renewal theorem, this integral converges \( \frac{1}{\mu} \int_0^\infty \bar{F}(y + x) \, dy = \int_x^\infty \bar{F}(y + x) \, dy \).
The current and reamining life have the same limiting distribution. In particular,
\[ \lim_{t \to \infty} \P(C_t \le x) = \lim_{t \to \infty} \P(R_t \le x) = \frac{1}{\mu} \int_0^x \bar{F}(y) \, dy, \quad x \in [0, \infty) \]By the previous two exercises, the limiting right-tail distribution functions of \( R_t \) and \( C_t \) are the same. The ordinary (left-tail) limiting distribution function is
\[ 1 - \frac{1}{\mu} \int_x^\infty \bar{F}(y) \, dy = \frac{1}{\mu} \left(\mu - \int_x^\infty \bar{F}(y) \, dy \right) \]But recall that \( \mu = \int_0^\infty \bar{F}(y) \, dy \) so the result follows since \( \int_0^\infty \bar{F}(y) \, dy - \int_x^\infty \bar{F}(y) \, dy = \int_0^x \bar{F}(y) \, dy \)
The fact that the current and remaining age processes have the same limiting distribution may seem surprising at first, but there is a simple intuitive explanation. After a long period of time, the renewal process looks just about the same backward in time as forward in time. But reversing the direction of time reverses the rolls of current and remaining age.
Recall that the Poisson process, the most important of all renewal processes, has interarrival times that are exponentially distributed with rate parameter \( r \gt 0 \). Thus, the interarrival distribution function is \( F(x) = 1 - e^{-r\,x} \) for \( x \ge 0 \) and the mean interarrival time is \( \mu = 1 / r \).
Verify each of the following directly:
Suppose that \( \bs{X} = (X_1, X_2, \ldots) \) is a sequence of Bernoulli trials with success parameter \( p \in (0, 1) \). Recall that \( \bs{X} \) is a sequence of independent, identically distributed indicator variables with \( p = \P(X = 1) \). We have studied a number of random processes derived from \( \bs{X} \):
Consider the renewal process with interarrival sequence \( \bs{U} \). Thus, \( \mu = 1 / p \) is the mean interarrival time, and \( \bs{Y} \) is the counting process. Verify each of the following directly:
Consider the renewal process with interarrival sequence \( \bs{X} \). Thus, the mean interarrival time is \( \mu = p \) and the number of arrivals in the interval \( [0, n] \) is \( V_{n+1} - 1 \) for \( n \in \N \). Verify each of the following directly: