Blackwell's Renewal Theorem and Local Renewal Rates

Renewal Rates in Fixed Windows

The long-run renewal rate describes average growth over a time interval whose length increases. A different question asks how many renewals to expect in a window of fixed width that moves farther and farther into the future. Blackwell’s renewal theorem answers this local question: under its hypotheses, the expected count approaches the window width divided by the mean interarrival time. The local statement is stronger than a cumulative growth rate, and arithmetic interarrivals require special care.

Let \(X_1,X_2,\ldots\) be independent, identically distributed, strictly positive random variables on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). They are the interarrival times, with common distribution \(F\) and finite mean \(\mu=\mathbb{E}[X_1]\), where \(0<\mu<\infty\). Define the renewal epochs by \(S_0=0\) and \(S_n=X_1+\cdots+X_n\) for \(n\ge1\). The renewal count is \(N(t)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le t\}}\) for \(t\ge0\).

Definition: The renewal measure \(U\) assigns to a measurable set \(B\subseteq[0,\infty)\) the value \(U(B)=\sum_{n\ge0}\mathbb{P}(S_n\in B)\). It includes the initial epoch \(S_0=0\). For \(t\ge0\) and \(h>0\), \(U((t,t+h])\) is the expected number of renewals in the interval open at its left endpoint and closed at its right endpoint.

The endpoint convention matters when renewal epochs can have atoms. Since \(S_0=0\), it contributes nothing to \(U((t,t+h])\) for \(t\ge0\). The same interval contains exactly the epochs counted by \(N(t+h)-N(t)\).

Proposition: For every \(t\ge0\) and \(h>0\), \(\mathbb{E}[N(t+h)-N(t)]=U((t,t+h])\).

Proof. For each outcome, \(N(t+h)-N(t)=\sum_{n\ge1}\mathbf{1}_{\{t<S_n\le t+h\}}\): the difference counts precisely the epochs in the stated interval, including the right endpoint and excluding the left. Taking expectations and using monotone convergence for the increasing partial sums of nonnegative indicators gives \(\mathbb{E}[N(t+h)-N(t)]=\sum_{n\ge1}\mathbb{P}(t<S_n\le t+h)\). The term \(n=0\) in \(U((t,t+h])\) is zero, so this sum is \(U((t,t+h])\). \(\square\)

Call the interarrival law arithmetic with span \(d>0\) if \(X_1\) is almost surely in \(\{d,2d,3d,\ldots\}\) for a maximal such \(d\). If there is no \(d>0\) with this property, call it nonarithmetic. In the arithmetic case all renewal epochs lie on the lattice \(\{0,d,2d,\ldots\}\). This lattice can make local counts depend on the location of the window, even far from time zero.

Theorem (Blackwell’s renewal theorem): Suppose the interarrivals are strictly positive and independent with common distribution \(F\), and \(0<\mu=\mathbb{E}[X_1]<\infty\). If \(F\) is nonarithmetic, then for every fixed \(h>0\), \(U((t,t+h])\to h/\mu\) as \(t\to\infty\). If \(F\) is arithmetic with span \(d\), then for every positive integer \(m\), \(U((t,t+md])\to md/\mu\) as \(t\to\infty\). In the arithmetic case, a limit of \(h/\mu\) is not asserted for arbitrary widths \(h\) that are not integer multiples of \(d\). This is a standard theorem; its proof is developed in the later material on lattice and nonarithmetic proofs of Blackwell’s theorem.

The limit \(h/\mu\) has the units and interpretation of a rate multiplied by a duration: the long-run event rate is \(1/\mu\), so a window of width \(h\) has limiting expected count \(h/\mu\). The theorem holds for each fixed width; it does not say that the width may vary with \(t\). Nor does it state that individual intervals have exactly this expected count at finite times.

Three Local-Rate Calculations

Worked Example: Exponential Interarrivals

Suppose the interarrivals have the exponential distribution with rate \(2\), so their density is \(2e^{-2x}\) for \(x>0\). Find the expected number of renewals in \((1,7/4]\), and compare it with Blackwell’s limit.

The mean interarrival time is \(\mu=1/2\). The sum \(S_n\) of \(n\) exponential interarrivals has density \(2^n x^{n-1}e^{-2x}/(n-1)!\) for \(x>0\). This follows by induction: convolution with the density \(2e^{-2x}\) changes the density for \(n\) into \(2^{n+1}e^{-2x}\int_0^x y^{n-1}\,dy/(n-1)!=2^{n+1}x^ne^{-2x}/n!\). Summing the densities of \(S_n\), for \(n\ge1\), gives the renewal density \(\sum_{n\ge1}2^n x^{n-1}e^{-2x}/(n-1)!=2e^{-2x}\sum_{k\ge0}(2x)^k/k!=2\). Thus \(U((1,7/4])=\int_1^{7/4}2\,dx=2(7/4-1)=3/2\). The interval width is \(h=7/4-1=3/4\), and Blackwell’s value is \(h/\mu=(3/4)/(1/2)=3/2\). Here the local expectation equals the limit exactly, not just asymptotically.

Check: The density integrates to \(2(3/4)=3/2\) over the interval, and the theorem gives \((3/4)/(1/2)=3/2\) as well. The exponential law is nonarithmetic, as its continuous density is not concentrated on any lattice.

Worked Example: Deterministic Interarrivals and a Window-Width Trap

Let every interarrival equal \(1\). Then \(\mu=1\), the span is \(d=1\), and the renewal epochs are the nonnegative integers. For the width \(h=2\), every interval \((t,t+2]\) contains exactly two integers when \(t\ge0\): if \(t\) is an integer, they are \(t+1,t+2\); if it is not, the interval still contains exactly two integers. Therefore \(U((t,t+2])=2\) for every \(t\ge0\), agreeing with \(h/\mu=2/1=2\).

Now take the non-lattice-multiple width \(h=1/2\). For every positive integer \(n\), the interval \((n,n+1/2]\) contains no integer, so its renewal measure is \(0\). The interval \((n-1/2,n]\) contains the integer \(n\) at its right endpoint, so its renewal measure is \(1\). Both left endpoints tend to infinity as \(n\to\infty\), but the corresponding values differ. Hence the local renewal measure has no limit for this width.

Check: The lattice theorem applies to width \(2=2d\) and predicts \(2/\mu=2\), which is the exact count. It does not assert a limit for width \(1/2\); the two sequences of windows verify why that restriction is needed.

Worked Example: Two-Point Lattice Interarrivals

Let each interarrival be \(1\) or \(2\), each with probability \(1/2\). Find the limiting expected number of renewals in \((n,n+2]\) as the integer \(n\) tends to infinity.

The mean is \(\mu=(1)(1/2)+(2)(1/2)=3/2\). The law is arithmetic with span \(d=1\), so width \(2=2d\) is covered by the lattice form of Blackwell’s theorem. To check the prediction directly, define \(u_k=U(\{k\})\) for integers \(k\ge0\), and set \(u_k=0\) for \(k<0\). Since the interarrivals are positive, at most one renewal epoch on any sample path can equal \(k\). We have \(u_0=1\), and for \(k\ge1\), conditioning on the last interarrival gives \(u_k=\tfrac12u_{k-1}+\tfrac12u_{k-2}\). In particular, \(u_1=1/2\) and \(u_2=(1/2)(1/2)+(1/2)(1)=3/4\).

The recurrence has solution \(u_k=\tfrac23+\tfrac13(-\tfrac12)^k\) for \(k\ge0\). Indeed, the constant term satisfies the recurrence because \(\tfrac12(\tfrac23)+\tfrac12(\tfrac23)=\tfrac23\); the geometric term satisfies it because \(r^2=\tfrac12r+\tfrac12\) at \(r=-1/2\). At \(k=0\) the formula gives \(2/3+1/3=1\), and at \(k=1\) it gives \(2/3-1/6=1/2\), so the recurrence and initial values establish the formula for all \(k\). For integer \(n\), the interval \((n,n+2]\) contains the renewal epochs \(n+1\) and \(n+2\), so \(U((n,n+2])=u_{n+1}+u_{n+2}\to\tfrac23+\tfrac23=\tfrac43\). Blackwell’s prediction is \(h/\mu=2/(3/2)=4/3\).

Check: The recurrence gives \(u_2=3/4\), while the formula gives \(2/3+(1/3)(1/4)=2/3+1/12=3/4\). The limiting two-point sum is \(4/3\), matching the independently evaluated value \(2/(3/2)=4/3\).

Local Limits and Cumulative Growth

The renewal function is \(U([0,t])=1+\mathbb{E}N(t)\). For finite-mean interarrivals, the elementary renewal theorem gives \(U([0,t])/t\to1/\mu\). This cumulative statement concerns the average growth up to time \(t\). Blackwell’s theorem instead concerns the increment \(U((t,t+h])\) over a window of fixed width. A limit for the cumulative function divided by \(t\) does not, by itself, imply a limit for its fixed-width increments: controlling a function’s average slope at large scales does not control every short interval.

Common mistake: infer a local limit from the cumulative rate. For deterministic interarrivals equal to \(1\), the cumulative renewal measure satisfies \(U([0,t])=\lfloor t\rfloor+1\), so \(U([0,t])/t\to1=1/\mu\). It would be wrong to conclude that every interval of width \(1/2\) has renewal measure \(1/2\). In fact, \((n,n+1/2]\) has measure \(0\), while \((n-1/2,n]\) has measure \(1\). The correction is to check the arithmetic hypothesis and the width: the lattice theorem gives the stated local limit for widths that are integer multiples of the span, while nonarithmetic interarrivals allow every fixed positive width.

For applications, the local theorem turns a renewal-count question into a simple asymptotic calculation when its hypotheses fit. For instance, a window of width \(h\) has limiting expected count \(h/\mu\), and the limiting expected count per unit width is \(1/\mu\). The word “limiting” is essential: the finite-time count can depend on the initial epoch and the interarrival law, and lattice effects can persist in windows that do not align with the span. Always state the interval endpoints, determine whether the law is arithmetic, and compare the chosen width with its span before applying the result.

Check Your Understanding

Use the interval convention \((t,t+h]\) in each question.

State the hypotheses and conclusion of Blackwell’s theorem for nonarithmetic interarrivals.
A renewal process has mean interarrival time \(4\). What is the limiting expected count in a fixed window of width \(3\), when Blackwell’s theorem applies?
For deterministic interarrivals equal to \(2\), which positive integer-multiple window widths are covered by the lattice theorem?
Explain why a cumulative renewal rate of \(1/\mu\) does not imply that every short window has expected count equal to its width divided by \(\mu\).
For interarrivals \(1\) or \(2\) with equal probabilities, write the recurrence for \(u_k=U(\{k\})\) and compute \(u_2\).

Blackwell's Renewal Theorem and Local Renewal Rates

What You'll Learn