Renewal Limit Theorem Problem Workshop

A Checklist for Renewal Limits

Renewal limit problems often begin with different questions: how many renewals occur in a fixed window, what is the long-run response to a forcing function, or how does an initial delay affect either answer? The calculations become more reliable when the model is first translated into a renewal measure or a renewal equation. Then the decisive checks are usually the same: the mean interarrival time must be finite, the arithmetic or nonarithmetic case must be identified, and the function used in a key renewal theorem must satisfy its integrability condition.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(X_1,X_2,\ldots\) be independent, identically distributed, strictly positive random variables with distribution \(F\) and mean \(\mu=\mathbb{E}X_1\), where \(0<\mu<\infty\). Set \(S_0=0\), \(S_n=X_1+\cdots+X_n\) for \(n\ge1\), and \(N(t)=\#\{n\ge1:S_n\le t\}\) for \(t\ge0\). Thus \(N(t)\) excludes the epoch \(S_0=0\). The renewal measure is \(U(B)=\sum_{n\ge0}\mathbb{P}(S_n\in B)\) for measurable \(B\subseteq[0,\infty)\); it includes the unit atom at zero.

Definition: The interarrival law is arithmetic with span \(d>0\) if \(d\) is the largest number for which \(\mathbb{P}(X_1\in\{d,2d,3d,\ldots\})=1\). Otherwise it is nonarithmetic. A function \(g:[0,\infty)\to\mathbb{R}\) is directly Riemann integrable if its upper and lower Riemann sums on equal-width partitions have finite limits as the mesh decreases to zero, with the tails of those sums tending to zero. In particular, a nonnegative decreasing integrable function is directly Riemann integrable.

Two standard results from renewal theory organize the calculations below. The nonarithmetic Blackwell theorem states that, if \(0<\mu<\infty\), then for every fixed \(h>0\), \(U((t,t+h])\to h/\mu\) as \(t\to\infty\). In the arithmetic case with span \(d\), the corresponding lattice limit is \(U((nd,(n+1)d])\to d/\mu\) as integers \(n\to\infty\). The key renewal theorem states that for a nonarithmetic law with \(0<\mu<\infty\) and directly Riemann integrable \(g\), \(\int_{[0,t]}g(t-s)U(ds)\to\mu^{-1}\int_0^\infty g(u)\,du\). These are standard renewal theorems; their proofs are not repeated here.

From a Forced Equation to a Limit

For a measurable forcing function \(g\), consider the renewal equation \(z(t)=g(t)+\int_{[0,t]}z(t-s)F(ds)\). Assume \(g\) is bounded on every finite interval and \(z\) is a solution with the same local boundedness. The integral accounts for the response after the first interarrival, while \(g(t)\) is the forcing applied at time \(t\). The relevant convolution is with \(U\), not just with \(F\).

Proposition: Under the preceding assumptions, the unique locally bounded solution is \(z(t)=\int_{[0,t]}g(t-s)U(ds)\). If, in addition, \(F\) is nonarithmetic, \(0<\mu<\infty\), and \(g\) is directly Riemann integrable, the key renewal theorem gives \(\lim_{t\to\infty}z(t)=\mu^{-1}\int_0^\infty g(u)\,du\).

Proof. Write \(F^{*n}\) for the distribution of \(S_n\), with \(F^{*0}\) a unit atom at zero. Iterating the equation \(m\) times gives \(z(t)=\sum_{k=0}^{m}\int_{[0,t]}g(t-s)F^{*k}(ds)+\int_{[0,t]}z(t-s)F^{*(m+1)}(ds)\). This identity follows by substituting the equation for each remaining \(z\); all integrals are over a finite time interval, where the functions are bounded. Fix \(T<\infty\), and let \(C_T\) bound \(|z(u)|\) for \(0\le u\le T\). For \(0\le t\le T\), the absolute value of the last term is at most \(C_T\mathbb{P}(S_{m+1}\le T)\).

To see that this probability tends to zero, choose \(\varepsilon>0\) such that \(p=\mathbb{P}(X_1\ge\varepsilon)>0\); such an \(\varepsilon\) exists because \(X_1>0\) almost surely. If \(S_n\le T\), at most \(r=\lfloor T/\varepsilon\rfloor\) of the first \(n\) interarrivals can be at least \(\varepsilon\). The number of such interarrivals has a binomial distribution with parameters \(n,p\). Hence \(\mathbb{P}(S_n\le T)\le\sum_{j=0}^{r}\binom{n}{j}p^j(1-p)^{n-j}\to0\); each of the finitely many terms tends to zero. Letting \(m\to\infty\) in the iterated equation proves the representation. It also proves uniqueness: the difference of two locally bounded solutions has zero forcing, and its absolute value on \([0,T]\) is bounded by \(C_T\mathbb{P}(S_{m+1}\le T)\) for every \(m\), hence is zero. The asserted limit now follows by applying the stated key renewal theorem to the representation. \(\square\)

Worked Example: An Exponential Renewal Response

Let the interarrivals be exponential with rate \(1/2\), so \(F(ds)=\tfrac12e^{-s/2}\,ds\) for \(s\ge0\) and \(\mu=2\). Take \(g(t)=e^{-t}\) for \(t\ge0\). This is decreasing, nonnegative, and integrable, so it is directly Riemann integrable. Find the limit of the solution to the forced renewal equation and check it directly.

The law is nonarithmetic: it has a density, so it cannot be supported on a lattice. For \(n\ge1\), \(S_n\) has density \((1/2)^n s^{n-1}e^{-s/2}/(n-1)!\) for \(s>0\). Summing these densities gives \(\tfrac12e^{-s/2}\sum_{k=0}^\infty (s/2)^k/k!=\tfrac12\). Thus \(U\) consists of an atom of mass \(1\) at zero and density \(1/2\) on \((0,\infty)\). The representation gives

z(t)=e^{-t}+\frac12\int_0^t e^{-(t-s)}\,ds =e^{-t}+\frac12(1-e^{-t}) =\frac12+\frac12e^{-t}.

Therefore \(z(t)\to\tfrac12\). Independently, the key renewal theorem gives \(\mu^{-1}\int_0^\infty e^{-u}\,du=\tfrac12\cdot1=\tfrac12\). Substitution checks the equation: the integral term is \(\tfrac12(1-e^{-t})\), and adding \(g(t)=e^{-t}\) returns \(\tfrac12+\tfrac12e^{-t}=z(t)\).

Window Counts: Check the Lattice Before Taking a Limit

For counts in a fixed window, use the renewal measure directly. The endpoint convention matters: \((t,t+h]\) excludes a renewal at the left endpoint and includes one at the right endpoint. In a nonarithmetic model, Blackwell’s theorem gives the limit \(h/\mu\). In a lattice model, the limit can depend on whether the window includes lattice points; applying the nonarithmetic formula without checking the support can give a false answer.

Worked Example: A Lattice Window and a Boundary Trap

Suppose \(X_n\) equals \(1\) or \(2\), each with probability \(1/2\). Each interarrival is positive, the arithmetic span is \(d=1\), and \(\mu=\tfrac12(1)+\tfrac12(2)=\tfrac32\). For every integer \(n\), the strict-left, included-right window \((n,n+1]\) contains exactly one possible lattice location, \(n+1\). The arithmetic Blackwell theorem therefore gives \(U((n,n+1])\to d/\mu=1/(\tfrac32)=\tfrac23\).

Now take windows of width \(1/2\). For integer \(n\), \((n,n+\tfrac12]\) contains no integer, so its renewal measure is zero. But \((n-\tfrac12,n]\) contains the single integer \(n\), whose renewal mass tends to \(\tfrac23\) by the lattice singleton limit. The two sequences of windows have the same width but different limiting masses. Thus a real-\(t\) limit for windows of width \(1/2\) does not exist. The issue is not arithmetic in the calculation; it is the alignment of the strict and included endpoints with the lattice.

Check: the tempting nonarithmetic calculation would give \((1/2)/\mu=(1/2)/(\tfrac32)=\tfrac13\). That value is neither the zero along integer-aligned windows nor the \(\tfrac23\) limit along windows ending at integers. The nonarithmetic hypothesis is essential.

Delayed Starts and Long-Run Window Counts

A delayed renewal process has epochs \(D+S_n\), \(n\ge0\), where \(D\ge0\) is an initial delay independent of the ordinary interarrivals. Its renewal measure is \(U_D(B)=\sum_{n\ge0}\mathbb{P}(D+S_n\in B)\). When the delay is a fixed finite constant, the late-time window calculation is the ordinary one with the window shifted by that constant. The early-time behavior can change, but the long-run Blackwell rate does not.

Worked Example: A Fixed Initial Delay

Use the exponential interarrivals from the first example, with rate \(1/2\) and mean \(2\), but start renewal epochs at \(D=3\). Compute the expected number of delayed epochs in \((t,t+2]\) for \(t\ge3\), and compare it with the Blackwell limit.

For \(t\ge3\), shifting the interval back by \(3\) gives \((t-3,t-1]\), an interval of length \(2\) entirely in nonnegative time. The shifted renewal measure has density \(1/2\) away from its atom at zero, and this open-left interval excludes zero even when \(t=3\). Consequently, the expected count is \(\int_{t-3}^{t-1}\tfrac12\,ds=\tfrac12((t-1)-(t-3))=1\). Equivalently, delayed Blackwell gives \(h/\mu=2/2=1\). The two calculations agree for every \(t\ge3\), so in particular the limit is \(1\).

At the boundary \(t=3\), the shifted interval is \((0,2]\): its renewal measure is \(\int_0^2\tfrac12\,ds=1\), with no contribution from the atom \(S_0=0\). This explicitly checks that the endpoint convention has not added the initial epoch.

Inspection Bias Is a Different Limit Question

Blackwell’s theorem concerns the expected number of renewal epochs in a fixed time window. The inspection paradox asks a different question: what interval length is seen by an observer who samples time rather than sampling renewal intervals uniformly? Longer intervals occupy more time, so they are more likely to contain the observation. If \(\mathbb{E}X_1^2<\infty\), the interval containing a typical long-run observation has the length-biased distribution, assigning an interval of length \(x\) weight proportional to \(x\). Its mean is \(\mathbb{E}X_1^2/\mu\), which exceeds \(\mu\) when \(X_1\) is nonconstant and has finite second moment.

Worked Example: Length Bias for Two Possible Intervals

Suppose renewal intervals have length \(1\) or \(3\), each with probability \(1/2\). The ordinary mean interval is \(\mu=\tfrac12(1)+\tfrac12(3)=2\). At a randomly sampled long-run time, the length-biased probabilities are proportional to length times the original probability: the weights are \(1\cdot\tfrac12=\tfrac12\) and \(3\cdot\tfrac12=\tfrac32\). Their sum is \(2\), so the observed interval has length \(1\) with probability \((\tfrac12)/2=\tfrac14\) and length \(3\) with probability \((\tfrac32)/2=\tfrac34\).

The mean length seen by the observer is \(\tfrac14(1)+\tfrac34(3)=\tfrac14+\tfrac94=\tfrac{10}4=\tfrac52\), larger than the ordinary mean \(2\). The same value follows from the moment formula: \(\mathbb{E}X_1^2=\tfrac12(1^2)+\tfrac12(3^2)=5\), so \(\mathbb{E}X_1^2/\mu=5/2\). As a further interpretation, conditional on an interval of length \(x\), a uniform observation within it has mean forward residual time \(x/2\). The mean residual time is therefore \(\tfrac14(\tfrac12)+\tfrac34(\tfrac32)=\tfrac18+\tfrac98=\tfrac54\). This is not the mean interval \(2\): it is the mean remaining portion after a time-sampled inspection.

Check: the inspection probabilities sum to \(\tfrac14+\tfrac34=1\), and the length-biased mean \(\tfrac52\) is larger than \(2\), as expected. The interval of length \(3\) is three times as likely to contain a randomly selected time as an interval of length \(1\).

Common Failure Modes

Common mistake: applying the nonarithmetic window formula on a lattice. In the lattice example, using \(h/\mu\) for \(h=\tfrac12\) gives \((\tfrac12)/(\tfrac32)=\tfrac13\). But for \(t=n\), the strict-left window \((n,n+\tfrac12]\) contains no lattice point and has renewal mass zero; for \(t=n-\tfrac12\), the window contains \(n\) and its mass tends to \(\tfrac23\). The corrected conclusion is that no single real-\(t\) limit exists for this width. The arithmeticity check must come before the limit formula.

For a forced equation, another error is to report \(\int g\) without dividing by \(\mu\). The key renewal theorem’s limit is \(\mu^{-1}\int g\); the exponential example gives \(1/2\), not \(1\). A third error is to confuse a delayed start with a change in the interarrival law. A fixed finite initial delay shifts the epochs but does not change the late-time window rate. Finally, a length-biased inspection calculation is not a Blackwell count: it weights interval lengths, rather than counting renewal epochs in a time window.

Before using a renewal limit, check the following items:

Is the interarrival mean finite and strictly positive?
Is the law arithmetic, and if so, what is its maximal span?
Are the interval endpoints strict or included, and can an endpoint carry renewal mass?
For the key renewal theorem, is the forcing function directly Riemann integrable?
Does an initial delay change only early behavior, or is the question instead about an interval seen by a time-sampled observer?

Check Your Understanding

For each question, identify the relevant renewal limit and state the assumption that makes it applicable.

If \(F\) is nonarithmetic with mean \(\mu=4\), what is the Blackwell limit for \(U((t,t+3])\)?
For arithmetic span \(d=2\) and mean \(\mu=5\), what is the limit of \(U((2n,2n+2])\)?
For \(g(t)=e^{-2t}\) and a nonarithmetic renewal law with mean \(\mu=3\), what limit does the key renewal theorem predict for the forced equation?
Why can a width-\(d/2\) window fail to have a Blackwell limit when the renewal law has span \(d\)? Specify how endpoint alignment matters.
For intervals taking values \(2\) and \(4\) with equal probabilities, compute the length-biased probability of observing an interval of length \(4\), and compare the ordinary and length-biased mean interval lengths.