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 first inter-renewal interval to be statistically identical to the others. In this section, we correct that defect by allowing the epoch at which the first renewal occurs to be arbitrarily 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 first 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 first renewal. What we shall discover is intuitively satisfying — both the time-average behavior and, in essence, the limiting ensemble behavior are not affected by the distribution of the first renewal epoch. It might be somewhat surprising, however, to find that this irrelevance of the distribution of the first renewal epoch holds even when the mean of the first renewal epoch is infinite.

To be more precise, we let \(\left\{X_{i} ; i \geq 1\right\}\) be a set of independent nonnegative random variables. \(X_{1}\) has a given distribution function \(\mathrm{G}(x)\), whereas \(\left\{X_{i} ; i \geq 2\right\}\) are identically distributed with a given distribution function \(\mathrm{F}(x)\). Thus a renewal process is a special case of a delayed renewal process for which \(G(x)=F(x)\). Let \(S_{n}=\sum_{i=1}^{n} X_{i}\) be the \(n\)th renewal epoch. We first show that the SLLN still holds despite the deviant behavior of \(X_{1}\).

Lemma 4.8.1

Let \(\left\{X_{i} ; i \geq 2\right.\) be IID with a mean \(\overline{X}\) satisfying \(\mathrm{E}[|X|]<\infty\) and let \(X_{1}\) be a rv, independent of \(\left\{X_{i} ; i \geq 2\right\}\). Let \(S_{n}=\sum_{i=1}^{n} X_{i}\). Then \(\lim S_{n} / n=\overline{X}\) WP1.

Proof

Note that

\(\frac{S_{n}}{n}=\frac{X_{1}}{n}+\frac{\sum_{i=2}^{n} X_{i}}{n}\)

Since \(X_{1}\) is finite WP1, the first term above goes to 0 WP1 as \(n \rightarrow \infty\). The second term goes to \(\overline{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) \geq n\}\) if and only if \(\left.\left\{S_{n} \leq t\right\}\right)\). \(\{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 \(\lim _{t \rightarrow \infty} N(t)=\infty\) with probability 1 and \(\lim _{t \rightarrow \infty} \mathrm{E}[N(t)]=\infty\).

Proof

Conditioning on \(X_{1}=x\), we can write \(N(t)=1+N^{\prime}(t-x)\) where \(N^{\prime}\{t ; t \geq 0\}\) is the ordinary renewal counting process with inter-renewal intervals \(X_{2}, X_{3}, \ldots\). From Lemma 4.3.1, \(\lim _{t \rightarrow \infty} N^{\prime}(t-x)=\infty\) with probability 1, and \(\lim _{t \rightarrow \infty} \mathrm{E}\left[N^{\prime}(t-x)\right]=\infty\). Since this is true for every finite \(x>0\), and \(X_{1}\) is finite 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 \(X_{2}, X_{3}, \ldots\), have distribution function F and finite mean \(\overline{X}=\int_{x=0}^{\infty}[1-\mathrm{F}(x)] d x\). Then

\[\lim _{t \rightarrow \infty} \frac{N(t)}{t}=\frac{1}{\overline{X}} \quad W P 1\label{4.98} \]

Proof

Using Lemma 4.8.1, the conditions for Theorem 4.3.2 are fulfilled, 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 renewal 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 \(X_{1}\) with some distribution function \(G(t)\). Define \(N_{o}\left(t-X_{1}\right)\) as the number of renewals that occur in the interval \(\left(X_{1}, t\right]\). Conditional on any given sample value \(x\) for \(X_{1}\), \(\left\{N_{o}(t-x) ; t-x>0\right\}\) is an ordinary renewal counting process and thus, given \(X_{1}=x, \lim _{t \rightarrow \infty} \mathrm{E}\left[N_{o}(t-x)\right] /(t-x)=1/\overline{X}\). Since \(N(t)=1+N_{o}\left(t-X_{1}\right)\) for \(t>X_{1}\), we see that, conditional on \(X_{1}=x\),

\[\lim _{t \rightarrow \infty} \frac{\mathrm{E}\left[N(t) \mid X_{1}=x\right]}{t}=\lim _{t \rightarrow \infty} \frac{\mathrm{E}\left[N_{o}(t-x)\right]}{t-x} \frac{t-x}{t}=\frac{1}{\overline{X}}\label{4.99} \]

Since this is true for every finite sample value \(x\) for \(X_{1}\), we we have established the following theorem:

Theorem 4.8.2 (Elementary Delayed Renewal Theorem)

If \(\left\{X_{i} ; i \geq 2\right\}\) are non-arithmetic, then, for all \(\delta>0\),

\[\lim _{t \rightarrow \infty} \frac{\mathrm{E}[N(t+\delta)-N(t)]}{\delta}=\frac{1}{\overline{X}}\label{4.102} \]

If \(\left\{X_{i} ; i \geq 2\right\}\) are arithmetic with span \(\lambda\) and mean \(\overline{X}\) and \(X_{1}\) is arithmetic with span \(m \lambda\) for some positive integer \(m\), then

\[\lim _{i \rightarrow \infty} \operatorname{Pr}\{\text { renewal at } t=i \lambda\}=\frac{\lambda}{\overline{X}}\label{4.103} \]

Delayed Renewal-reward Processes

We have seen that the distribution of the first renewal epoch has no effect 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 \(X_{2}, X_{3}, \ldots\) have the distribution function F. Let \(Z(t)=t-S_{N(t)}\), let \(\tilde{X}(t)=S_{N(t)+1}-S_{N(t)}\), and let \(R(t)=\mathcal{R}(Z(t)\), \(\widetilde{X}(t))\) be a reward function. Assume that

\(\mathrm{E}\left[\mathrm{R}_{n}\right]=\int_{x=0}^{\infty} \int_{z=0}^{x} \mathcal{R}(z, x) d z \ d \mathrm{F}(x)<\infty\)

Then, with probability one,

\[\lim _{t \rightarrow \infty} \frac{1}{t} \int_{\tau=0}^{t} R(\tau) d \tau=\frac{\mathrm{E}\left[\mathrm{R}_{n}\right]}{\overline{X}_{2}} \text { for } n \geq 2\label{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 _{t \rightarrow \infty} \mathrm{E}[R(t)]=\frac{\mathrm{E}\left[\mathrm{R}_{n}\right]}{\overline{X}_{2}}\label{4.105} \]

Transient Behavior of Delayed Renewal Processes

Let \(m(t)=\mathrm{E}[N(t)]\) for a delayed renewal process. As in (4.51), we have

\[m(t)=\sum_{n=1}^{\infty} \operatorname{Pr}\{N(t) \geq n\}=\sum_{n=1}^{\infty} \operatorname{Pr}\left\{S_{n} \leq t\right\}\label{4.106} \]

For \(n \geq 2\), \(S_{n}=S_{n-1}+X_{n}\) where \(X_{n}\) and \(S_{n-1}\) are independent. From the convolution equation (1.12),

\[\operatorname{Pr}\left\{S_{n} \leq t\right\}=\int_{x=0}^{t} \operatorname{Pr}\left\{S_{n-1} \leq t-x\right\} d \mathrm{F}(x) \quad \text { for } n \geq 2\label{4.107} \]

For \(n=1\), \(\operatorname{Pr}\left\{S_{n} \leq t\right\}=\mathrm{G}(t)\). Substituting this in \ref{4.106} and interchanging the order of integration and summation,

\[\begin{aligned}
m(t) &=\mathrm{G}(t)+\int_{x=0}^{t} \sum_{n=2}^{\infty} \operatorname{Pr}\left\{S_{n-1} \leq t-x\right\} d \mathrm{F}(x) \\
&=\mathrm{G}(t)+\int_{x=0}^{t} \sum_{n=1}^{\infty} \operatorname{Pr}\left\{S_{n} \leq t-x\right\} d \mathrm{F}(x) \\
&=\mathrm{G}(t)+\int_{x=0}^{t} m(t-x) d \mathrm{F}(x) ; \quad t \geq 0
\end{aligned}\label{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 \ref{4.108} that arises from breaking up \(S_{n}\) as the sum of \(X_{1}\) and \(\widehat{S}_{n-1}\) where \(\widehat{S}_{n-1}=X_{2}+\cdots+X_{n}\). Letting \(\widehat{m}(t)\) be the expected number of renewals in time \(t\) for an ordinary renewal process with interarrival distribution F, a similar argument to that above, starting with \(\operatorname{Pr}\left\{S_{n} \leq t\right\}=\int_{0}^{t} \operatorname{Pr}\left\{\widehat{S}_{n-1} \leq t-x\right\} d \mathrm{G}(x)\) yields

\[m(t)=\mathrm{G}(t)+\int_{x=0}^{t} \widehat{m}(t-x) d \mathrm{G}(x)\label{4.109} \]

This equation brings out the effect of the initial renewal interval clearly, and is useful in computation if one already knows \(\widehat{m}(t)\).

Frequently, the most convenient way of dealing with \(m(t)\) is through transforms. Following the same argument as that in (4.54), we get \(L_{m}(r)=(1 / r) L_{\mathrm{G}}(r)+L_{m}(r) L_{\mathrm{F}}(r)\). Solving, we get

\[L_{m}(r)=\frac{L_{\mathrm{G}}(r)}{r\left[1-L_{\mathrm{F}}(r)\right]}\label{4.110} \]

We can find \(m(t)\) from \ref{4.110} by finding 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 / L_{\mathrm{F}}^{\prime}(0)=1 / \overline{X}_{2}\), which is not surprising in terms of Blackwell’s theorem. We can also expand numerator and denominator of \ref{4.110} in a power series, as in (4.55). The inverse transform, corresponding to (4.56), is

\[m(t)=\frac{t}{\overline{X}}+\frac{\mathrm{E}\left[X_{2}^{2}\right]}{2 \overline{X}}-\frac{\overline{X}_{1}}{\overline{X}}+\epsilon(t) \quad \text { for } t \rightarrow 0, \label{4.111} \]

where \(\lim _{t \rightarrow \infty} \epsilon(t)=0\).

Equilibrium Process

Consider an ordinary non-arithmetic renewal process with an inter-renewal interval \(X\) of distribution \(\mathrm{F}(x)\). We have seen that the distribution of the interval from \(t\) to the next renewal approaches \(\mathrm{F}_{Y}(y)=(1 / \mathrm{E}[X]) \int_{0}^{y}[1-\mathrm{F}(x)] d x\) as \(t \rightarrow \infty\). 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 first renewal is equal to the residual life distribution \(\mathrm{F}_{Y}(x)\) above and subsequent inter-renewal intervals should have the original distribution \(\mathrm{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 / \overline{X}\) is a solution to \ref{4.108} if \(\mathrm{G}(t)=\mathrm{F}_{Y}(t)\). Substituting \((t-x) / \overline{X}\) for \(m(t-x)\), the right hand side of \ref{4.108} is

\(\frac{\int_{0}^{t}[1-\mathrm{F}(x)] d x}{\overline{X}_{2}}+\frac{\int_{0}^{t}(t-x) d \mathrm{~F}(x)}{\overline{X}}=\frac{\int_{0}^{t}[1-\mathrm{F}(x)] d x}{\overline{X}}+\frac{\int_{0}^{t} \mathrm{~F}(x) d x}{\overline{X}}=\frac{t}{\overline{X}},\)

where we have used integration by parts for the first equality. This particular delayed renewal process is called the equilibrium process, since it starts off in steady state, and thus has no transients.