From a Renewal Equation to a Convolution Series
A renewal equation expresses an unknown function in terms of its value after the first interarrival and a known forcing function. Iterating the equation separates the contributions from one renewal, two renewals, and so on. The result is a series of convolutions. To make that series a valid solution, we need to know that only finitely much renewal mass accumulates on any bounded time interval and that the remainder from repeated iteration vanishes.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \(X_1,X_2,\ldots\) be independent, identically distributed, strictly positive random variables with distribution \(F\) on \((0,\infty)\). Define \(S_0=0\) and \(S_n=X_1+\cdots+X_n\) for \(n\ge1\). For measures \(H,K\) on \([0,\infty)\), their convolution \(H*K\) is the distribution of the sum when \(H,K\) are probability measures; more generally, \((H*g)(t)=\int_{[0,t]}g(t-s)H(ds)\) for a measurable function \(g\). Write \(F^{*n}\) for the \(n\)-fold convolution of \(F\), with \(F^{*0}=\delta_0\), the unit mass at zero.
The integral includes the endpoint \(s=t\). Since \(F\) is supported on strictly positive values, its contribution at \(s=0\) is zero, while \(F^{*0}\) contributes exactly \(g(t)\). The strict positivity assumption also prevents infinitely many renewals from accumulating in a bounded interval.
Local Finiteness and the Solution Theorem
A measure is locally finite if it assigns finite mass to every bounded interval. This property is essential: for bounded \(g\), it ensures that the convolution series has finite total absolute contribution at each time.
Proof. Choose \(a>0\) such that \(p=\mathbb{P}(X_1\ge a)>0\); such an \(a\) exists because \(X_1>0\) almost surely. Let \(K=\lfloor T/a\rfloor\). If \(S_n\le T\), at most \(K\) of \(X_1,\ldots,X_n\) can be at least \(a\). If \(p=1\), then \(S_n\ge na\), so \(\mathbb{P}(S_n\le T)=0\) for \(n>K\), and the required sum is finite. If \(0<p<1\), independence gives \[ \mathbb{P}(S_n\le T) \le \sum_{j=0}^{K}\binom{n}{j}p^j(1-p)^{n-j}. \] For each fixed \(j\), \(\binom{n}{j}\le n^j\), so the sum over \(n\ge K+1\) of each term on the right is bounded by a constant times \(\sum_n n^j(1-p)^n\), which converges. Therefore \(\sum_{n\ge0}\mathbb{P}(S_n\le T)<\infty\). Since \(F^{*n}([0,T])=\mathbb{P}(S_n\le T)\), summing over \(n\) gives \(U([0,T])<\infty\). \(\square\)
Proof. Fix \(T<\infty\), and let \(M=\sup_{u\ge0}|g(u)|<\infty\). For every \(t\le T\), $$ \sum_{n=0}^{\infty}|(F^{*n}*g)(t)| \le M\sum_{n=0}^{\infty}F^{*n}([0,t]) \le M U([0,T])<\infty. $$ Thus the series converges absolutely, and its absolute value is at most \(M U([0,T])\) for all \(t\le T\); this proves finiteness and local boundedness. Separating its \(n=0\) term and using \(F*F^{*n}=F^{*(n+1)}\) gives \(z=g+F*z\). The interchange of the integral and series is justified by absolute convergence, with the same bound on each bounded interval.
For uniqueness, let \(w\) be any other locally bounded measurable solution and set \(d=w-z\). Subtracting the equations gives \(d=F*d\), hence, by repeated substitution, \(d=F^{*m}*d\) for every integer \(m\ge1\). Fix \(t\), and let \(C=\sup_{0\le u\le t}|d(u)|<\infty\). Then $$ |d(t)|\le C F^{*m}([0,t])=C\mathbb{P}(S_m\le t). $$ The lemma's argument shows that \(\mathbb{P}(S_m\le t)\to0\), since these probabilities are terms of a convergent nonnegative series. Letting \(m\to\infty\) gives \(d(t)=0\). This holds for every \(t\), proving uniqueness. \(\square\)
Discrete-Time Renewal Equations
In discrete time, suppose \(X_1,X_2,\ldots\) are independent, identically distributed positive integer-valued interarrivals, with \(f_k=\mathbb{P}(X_1=k)\) for \(k\ge1\). For sequences \(a=(a_n)\) and \(b=(b_n)\), define their convolution by \((a*b)_n=\sum_{k=0}^n a_kb_{n-k}\). Let \(u_n=\sum_{m=0}^{\infty}\mathbb{P}(S_m=n)\); this is the mass of the discrete renewal measure at \(n\). Because \(S_m\ge m\), only \(m\le n\) can contribute to \(u_n\). The discrete equation $$ z_n=g_n+\sum_{k=1}^n f_k z_{n-k} $$ therefore has the finite-at-each-index solution \(z_n=\sum_{k=0}^n u_k g_{n-k}\). Iteration proves the formula: the equation at index \(n\) uses only values with smaller indices, so induction determines each \(z_n\) uniquely. Equivalently, its convolution series has no terms from more than \(n\) renewals at index \(n\).
Worked Example: A Discrete Equation with Two Possible Interarrivals
Let \(f_1=f_2=\tfrac12\), with all other \(f_k=0\), and let the bounded forcing be \(g_n=1\) for every \(n\ge0\). The probabilities sum to \(\tfrac12+\tfrac12=1\). Find \(z_0,\ldots,z_4\) from the renewal equation.
At \(n=0\), the sum is empty, so \(z_0=1\). For \(n\ge1\), the recurrence is \(z_n=1+\tfrac12z_{n-1}+\tfrac12z_{n-2}\), where the term involving \(z_{n-2}\) is omitted when \(n=1\). Thus $$ \begin{aligned} z_1&=1+\tfrac12(1)=\tfrac32,\\ z_2&=1+\tfrac12(\tfrac32)+\tfrac12(1)=\tfrac94,\\ z_3&=1+\tfrac12(\tfrac94)+\tfrac12(\tfrac32)=\tfrac{23}{8},\\ z_4&=1+\tfrac12(\tfrac{23}{8})+\tfrac12(\tfrac94)=\tfrac{57}{16}. \end{aligned} $$ For example, the renewal masses through index four are \(u_0=1\), \(u_1=\tfrac12\), \(u_2=\tfrac34\), \(u_3=\tfrac58\), and \(u_4=\tfrac{11}{16}\). Their partial sums are \(1,\tfrac32,\tfrac94,\tfrac{23}{8},\tfrac{57}{16}\), as required by \(g_n=1\).
Check: Substituting the last two values into the recurrence at \(n=4\) gives \(1+\tfrac12(\tfrac{23}{8})+\tfrac12(\tfrac94)=1+\tfrac{23}{16}+\tfrac{18}{16}=\tfrac{57}{16}\), confirming the computed value.
Continuous-Time Examples
Worked Example: Deterministic Interarrivals and Endpoint Inclusion
Let \(F=\delta_1\), so every interarrival is exactly one time unit, and take \(g(t)=1\). Then \(F^{*n}=\delta_n\), and the solution is $$ z(t)=\sum_{n=0}^{\infty}\mathbf{1}_{\{n\le t\}}=\lfloor t\rfloor+1. $$ Here membership is tested with \(n\le t\), not \(n<t\): the renewal at the endpoint \(t=n\) is included.
At \(t=\tfrac52\), the contributing indices are \(n=0,1,2\), so \(z(\tfrac52)=3\). The equation gives \(1+z(\tfrac32)=1+2=3\), since only the interarrival \(s=1\) contributes to the integral. At \(t=2\), the contributing indices are \(0,1,2\), again giving \(z(2)=3\); the equation gives \(1+z(1)=1+2=3\). The endpoint at \(2\) is counted in the convolution series and in the equation.
Worked Example: Exponential Interarrivals and Constant Forcing
Let \(F\) have density \(e^{-s}\) for \(s>0\), and let \(g(t)=1\). For \(n\ge1\), the \(n\)-fold convolution has density \(e^{-s}s^{n-1}/(n-1)!\). This follows by induction: convolving the density for \(n\) with \(e^{-s}\) gives \(e^{-s}\int_0^s u^{n-1}/(n-1)!\,du=e^{-s}s^n/n!\). Therefore $$ (F^{*n}*g)(t)=\int_0^t e^{-s}\frac{s^{n-1}}{(n-1)!}\,ds. $$ The \(n=0\) term is \(1\). Since the terms are nonnegative, summing inside the integral is valid, and the exponential series yields $$ z(t)=1+\int_0^t e^{-s}\sum_{n=1}^{\infty}\frac{s^{n-1}}{(n-1)!}\,ds =1+\int_0^t 1\,ds=1+t. $$ At \(t=2\), the solution is \(z(2)=3\).
Check by substitution: For \(z(u)=1+u\), the convolution term at \(t=2\) is $$ \int_0^2(1+2-s)e^{-s}\,ds =3(1-e^{-2})-\bigl(1-3e^{-2}\bigr)=2. $$ Thus \(g(2)+(F*z)(2)=1+2=3=z(2)\). In general the same calculation with upper limit \(t\) gives \((F*z)(t)=t\), verifying the formula for every \(t\ge0\).
Why the Assumptions and the Zero-th Term Matter
The zero-th convolution is not optional: it represents the forcing before any renewal has occurred. A concrete incorrect calculation is to use only \(F^{*n}\) for \(n\ge1\) when \(F=\delta_1\) and \(g=1\). At \(t=\tfrac12\), that calculation gives an empty sum and hence \(z(\tfrac12)=0\). But the renewal equation at that time has no interarrival contribution, so it requires \(z(\tfrac12)=g(\tfrac12)=1\). Including \(F^{*0}=\delta_0\) corrects the series and gives \(z(t)=\lfloor t\rfloor+1\).
Strictly positive interarrivals are important for local finiteness and uniqueness. If zero-length interarrivals were permitted, take \(F=\delta_0\) and \(g(t)=1\). The equation would read \(z(t)=1+z(t)\), which has no finite solution. Correspondingly, every convolution power of \(F\) is \(\delta_0\), so the proposed renewal measure has infinite mass at zero. The assumptions identify when the convolution-series method actually produces a finite, unique solution.
Check Your Understanding
Use the convolution equation and its hypotheses to answer the following questions.
- For interarrivals with \(F=\delta_2\) and forcing \(g(t)=1\), compute \(z(\tfrac32)\) and \(z(4)\). State whether an endpoint renewal is counted at \(t=4\).
- In the discrete example, calculate \(z_2\) directly from the renewal recurrence and then from the renewal masses \(u_0,u_1,u_2\).
- Explain why \(F^{*n}([0,T])=\mathbb{P}(S_n\le T)\) tends to zero as \(n\) increases when interarrivals are strictly positive.
- Show what the continuous equation requires at \(t=0\) when \(F\) is supported on \((0,\infty)\), and identify the term in the convolution series that supplies this value.
- For \(F=\delta_0\) and \(g(t)=1\), explain why neither the proposed convolution series nor the renewal equation gives a finite solution.