Asymptotic Solutions from the Key Renewal Theorem

From a Forced Equation to a Long-Time Limit

A renewal equation describes a quantity that receives a new contribution at time \(t\), together with contributions carried forward from earlier renewals. Solving the equation at every time can be harder than finding its long-time behavior. The key renewal theorem gives a direct route to that behavior: express the solution as a convolution with the renewal measure, then combine the integral of the forcing function with the mean interarrival time.

Let \(X_1,X_2,\ldots\) be independent, identically distributed, strictly positive random variables on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with distribution \(F\) and finite mean \(\mu=\mathbb{E}[X_1]\in(0,\infty)\). Define \(S_0=0\) and \(S_n=X_1+\cdots+X_n\) for \(n\ge1\). The renewal measure \(U\) is the measure on \([0,\infty)\) defined by \(U(B)=\sum_{n\ge0}\mathbb{P}(S_n\in B)\) for measurable sets \(B\). It includes an atom of mass one at zero, corresponding to \(S_0\).

Definition: For a locally bounded function \(z\) on \([0,\infty)\), its renewal convolution is \( (U*z)(t)=\int_{[0,t]}z(t-s)\,U(ds)=\sum_{n\ge0}\mathbb{E}[z(t-S_n)\mathbf{1}_{\{S_n\le t\}}]\). A forced renewal equation with forcing function \(z\) is \(g(t)=z(t)+\int_{[0,t]}g(t-x)\,F(dx)\). A function is directly Riemann integrable if its upper and lower sums on successively finer equal-width partitions converge to the same finite integral, with finite tail sums; for signed functions this condition is imposed on the absolute value as well.

The renewal measure is locally finite: for any fixed \(t\), \(U([0,t])<\infty\). Indeed, strict positivity gives some \(\varepsilon>0\) with \(p=\mathbb{P}(X_1\ge\varepsilon)>0\). To have \(S_n\le t\), the first \(n\) interarrivals can contain at most \(\lfloor t/\varepsilon\rfloor\) increments at least \(\varepsilon\). The expected number of trials before one more such increment is finite, so the expected number of renewals up to \(t\) is finite. Thus the convolution is well-defined for locally bounded \(z\).

The Convolution Representation

Proposition: Suppose \(z\) is locally bounded and \(g\) is a locally bounded solution of the forced renewal equation. Then \(g(t)=\int_{[0,t]}z(t-s)\,U(ds)\). Conversely, this convolution defines a locally bounded solution of the equation. Among locally bounded solutions, it is unique.

Proof. Write \(F^{*n}\) for the distribution of \(S_n\), with \(F^{*0}\) a unit mass at zero. Iterating the equation \(m+1\) times gives \(g(t)=\sum_{n=0}^{m}\int_{[0,t]}z(t-s)\,F^{*n}(ds)+\int_{[0,t]}g(t-s)\,F^{*(m+1)}(ds)\). This identity follows by substituting the equation for \(g\) in the final integral at each iteration; all integrals are over nonnegative renewal times no greater than \(t\).

For fixed \(t\), \(g\) is bounded on \([0,t]\), say by \(C_t\). Also \(S_n\to\infty\) almost surely: by the strong law of large numbers, \(S_n/n\to\mu>0\). Therefore \(\mathbb{P}(S_{m+1}\le t)\to0\). The absolute value of the final integral is at most \(C_t\mathbb{P}(S_{m+1}\le t)\), so it tends to zero. The finite sum converges to the integral against \(U=\sum_{n\ge0}F^{*n}\), proving the representation for any locally bounded solution.

For the converse, the measure identity \(U=F^{*0}+F*U\) follows by separating the \(n=0\) term from the sum defining \(U\). Convolving this identity with \(z\) gives \(U*z=z+F*(U*z)\), which is the forced renewal equation. All these integrals are finite on bounded time intervals by local boundedness of \(z\) and local finiteness of \(U\). Finally, the representation already proved applies to every locally bounded solution, so every such solution equals \(U*z\). This proves uniqueness. \(\square\)

The representation explains why the forcing function’s integral determines the limit: at large times, the renewal measure spreads its mass at an average rate \(1/\mu\). To use that fact precisely, the forcing function must satisfy the theorem’s integrability condition, and the interarrival law must be nonarithmetic.

Theorem (Key Renewal Theorem): Suppose the interarrivals are strictly positive and independent and identically distributed, \(0<\mu=\mathbb{E}[X_1]<\infty\), and \(F\) is nonarithmetic. If \(z\) is directly Riemann integrable, then \(\lim_{t\to\infty}(U*z)(t)=\frac{1}{\mu}\int_0^\infty z(s)\,ds\). The theorem is a standard result established in the earlier material on the Key Renewal Theorem; its proof is not repeated here.

Here, nonarithmetic means there is no \(d>0\) such that \(X_1\) belongs to \(\{0,d,2d,\ldots\}\) with probability one. For nonnegative continuous functions that are piecewise monotone and have an integrable tail, direct Riemann integrability is a standard test. The next result states exactly how the theorem answers the asymptotic question for a forced equation.

Corollary: Under the hypotheses of the Key Renewal Theorem, the locally bounded solution of \(g=z+F*g\) satisfies \(\lim_{t\to\infty}g(t)=\frac{1}{\mu}\int_0^\infty z(s)\,ds\).

Proof. The proposition gives \(g=U*z\). The hypotheses of the Key Renewal Theorem hold for \(F\) and \(z\), so applying that theorem to this representation gives the displayed limit. \(\square\)

Worked Asymptotic Calculations

Worked Example: Gamma Interarrivals and Exponential Forcing

Let each interarrival have density \(f(x)=xe^{-x}\) for \(x>0\), and let \(z(t)=e^{-3t}\) for \(t\ge0\). Find the long-time limit of the forced renewal solution.

The density integrates to one because \(\int_0^\infty xe^{-x}\,dx=1\). Its mean is \(\mu=\int_0^\infty x^2e^{-x}\,dx=2\), using integration by parts twice. The law has a density, so it is nonarithmetic. The forcing function is nonnegative, decreasing, and integrable, hence directly Riemann integrable. All hypotheses of the Key Renewal Theorem hold.

\int_0^\infty z(s)\,ds =\int_0^\infty e^{-3s}\,ds =\left[-\frac{1}{3}e^{-3s}\right]_0^\infty =\frac{1}{3}.

Therefore the solution \(g(t)=\sum_{n\ge0}\mathbb{E}[e^{-3(t-S_n)}\mathbf{1}_{\{S_n\le t\}}]\) satisfies \(\lim_{t\to\infty}g(t)=\frac{1}{2}\cdot\frac{1}{3}=\frac{1}{6}\).

Check: the theorem’s constant is the forcing integral divided by the mean, \( (1/3)/2=1/6\). The result is a long-time limit; it does not assert that the solution equals \(1/6\) at finite \(t\).

Worked Example: An Explicit Solution with Exponential Interarrivals

Let the interarrivals be exponential with rate \(2\), and take \(z(t)=te^{-t}\). Find the solution and its limit, then substitute the solution into the renewal equation.

The interarrival mean is \(\mu=1/2\), and the exponential law is nonarithmetic. The \(n\)-th renewal time, for \(n\ge1\), has density \(2^n s^{n-1}e^{-2s}/(n-1)!\). Summing these densities gives \(2e^{-2s}\sum_{k\ge0}(2s)^k/k!=2\). Thus the renewal measure is \(U(ds)=\delta_0(ds)+2\,ds\), where \(\delta_0\) is unit mass at zero. The forcing function is piecewise monotone, nonnegative, and has an integrable tail, so it is directly Riemann integrable.

Using the renewal convolution and changing variables \(u=t-s\),

\begin{aligned} g(t) &=te^{-t}+2\int_0^t (t-s)e^{-(t-s)}\,ds\\ &=te^{-t}+2\int_0^t ue^{-u}\,du\\ &=te^{-t}+2\bigl[1-(t+1)e^{-t}\bigr]\\ &=2-(t+2)e^{-t}. \end{aligned}

Also, \(\int_0^\infty te^{-t}\,dt=1\), by integration by parts. The Key Renewal Theorem gives the limit \(1/(1/2)=2\), which agrees with the explicit expression because \((t+2)e^{-t}\to0\).

Substitution check: The equation requires \(g(t)=z(t)+\int_0^t g(t-x)2e^{-2x}\,dx\). Substituting the proposed \(g\), the integral term is

\begin{aligned} \int_0^t 2e^{-2x}g(t-x)\,dx &=2(1-e^{-2t})-2e^{-t}\int_0^t(t-x+2)e^{-x}\,dx\\ &=2(1-e^{-2t})-2e^{-t}(t+1-e^{-t})\\ &=2-2(t+1)e^{-t}. \end{aligned}

Adding \(z(t)=te^{-t}\) gives \(2-(t+2)e^{-t}=g(t)\), as required. In the second line, integration gives \(\int_0^t(t-x+2)e^{-x}\,dx=t+1-e^{-t}\).

Worked Example: Why Arithmetic Interarrivals Can Oscillate

Let every interarrival equal \(1\), so \(\mu=1\), and use \(z(t)=e^{-t}\). The forcing is directly Riemann integrable and has integral \(1\), but the interarrival law is arithmetic. Calculate the renewal convolution and check whether it has a limit.

Here \(S_n=n\), so the convolution includes exactly the terms with integers \(n\ge0\) and \(n\le t\): \(g(t)=\sum_{n=0}^{\lfloor t\rfloor}e^{-(t-n)}\). Write \(t=m+r\), where \(m=\lfloor t\rfloor\) and \(0\le r<1\). Then

g(m+r)=e^{-r}\sum_{k=0}^{m}e^{-k} =e^{-r}\frac{1-e^{-(m+1)}}{1-e^{-1}}.

Along integer times \(t=m\), this tends to \(1/(1-e^{-1})\). Along times \(t=m+1/2\), it tends to \(e^{-1/2}/(1-e^{-1})\). These two limits differ because \(e^{-1/2}\ne1\), so \(g(t)\) has no limit as \(t\to\infty\). The nonarithmetic hypothesis cannot be dropped from the stated Key Renewal Theorem.

Check: At \(t=m\), the sum includes \(n=m\), whose contribution is \(1\). At \(t=m+1/2\), the largest included renewal time is still \(m\), and its contribution is \(e^{-1/2}\). This verifies the endpoint convention \(n\le t\) used in the calculation.

Using the Theorem Correctly

For a forced renewal equation, the asymptotic calculation can be organized into four checks:

Identify the renewal law.
Confirm that the interarrivals are strictly positive, have finite positive mean \(\mu\), and have a nonarithmetic distribution.

Check the forcing function.
Verify direct Riemann integrability, rather than relying only on pointwise decay. In common examples, a piecewise monotone function with an integrable tail passes this test.

Write the convolution.
Use \(g(t)=\int_{[0,t]}z(t-s)\,U(ds)\). This also provides an explicit solution when the renewal measure is known.

Compute the constant.
Evaluate \(\int_0^\infty z(s)\,ds\) and divide by \(\mu\). Check that the result agrees with any explicit expression for \(g(t)\).

A frequent mistake is to multiply by the mean instead of dividing by it. In the exponential-interarrival example, \(\mu=1/2\) and \(\int_0^\infty te^{-t}\,dt=1\). Multiplying gives the incorrect value \((1/2)\cdot1=1/2\). The theorem gives the renewal rate \(1/\mu=2\), so the correct limit is \(2\cdot1=2\). The explicit solution \(2-(t+2)e^{-t}\) confirms that value.

The conditions matter as much as the calculation. If \(\mu\) is infinite, the theorem’s finite-mean rate does not apply. If \(z\) is not directly Riemann integrable, its integral alone need not determine the convolution limit. If the renewal law is arithmetic, the example above shows that persistent oscillations can prevent a limit. Checking these hypotheses first prevents a correct-looking formula from being used outside its scope.

Check Your Understanding

For each question, state any hypothesis you use and verify the constant or expression by substitution where possible.

For nonarithmetic interarrivals with mean \(3\) and \(z(t)=e^{-2t}\), what limit does the Key Renewal Theorem give?
For exponential interarrivals of rate \(4\) and forcing \(z(t)=e^{-t}\), compute the limiting value. Which quantity is the renewal rate?
State the convolution representation of the locally bounded solution to \(g=z+F*g\), including the \(n=0\) term.
In the deterministic-unit-interarrival example, why do the sequences \(t=m\) and \(t=m+1/2\) give different limiting values?
Give two hypotheses, other than direct Riemann integrability, required for the stated nonarithmetic Key Renewal Theorem.

Asymptotic Solutions from the Key Renewal Theorem

What You'll Learn