From Lattice Renewals to Integer Renewal Mass
Blackwell’s renewal theorem gives a local, rather than merely long-run average, description of renewals. In the lattice case, renewals can occur only at regularly spaced points. The relevant quantity is the probability mass assigned by the renewal measure to each such point. This tutorial proves that, when the lattice span is maximal and the interarrival mean is finite, this mass approaches the span divided by the mean.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_n)_{n\ge1}\) be independent, identically distributed, strictly positive interarrival times with finite mean \(\mu=\mathbb{E}X_1\). Define \(S_0=0\) and \(S_n=X_1+\cdots+X_n\) for \(n\ge1\). The renewal count is \(N(t)=\max\{n\ge0:S_n\le t\}\), and the renewal measure is \(U(B)=\sum_{n\ge0}\mathbb{P}(S_n\in B)\) for sets \(B\) of times. Strictly positive interarrivals ensure that at most one renewal epoch can equal any fixed time.
Maximality matters: it rules out a smaller repeating lattice. After scaling, the interarrival variable \(Y\) is positive integer-valued, has finite mean \(m=\mathbb{E}Y=\mu/h\), and its possible values have greatest common divisor \(1\). The lattice renewal theorem is the assertion that \(u_k\) tends to \(1/m=h/\mu\).
The Renewal Recurrence and the Residual-Life Chain
Write \(f_j=\mathbb{P}(Y=j)\), so \(\sum_{j\ge1}f_j=1\). For integer \(k\ge0\), let \(u_k\) be the renewal mass after scaling, meaning \(u_k=\sum_{n\ge0}\mathbb{P}(Y_1+\cdots+Y_n=k)\), where the sum for \(n=0\) is \(0\). Because each \(Y_i\) is positive, the partial sums are strictly increasing; therefore \(u_k\) is also the probability that some renewal occurs at integer time \(k\).
Proof. At \(k=0\), only the epoch with index \(n=0\) contributes, so \(u_0=1\). For \(k\ge1\), condition on the first interarrival \(Y_1=j\). A renewal at \(k\) requires \(1\le j\le k\), followed by a renewal at \(k-j\) in the process formed by the remaining independent interarrivals. The probability of that latter event is \(u_{k-j}\). Summing over the disjoint possible values of \(Y_1\) gives $$ u_k=\sum_{j=1}^{k}f_j u_{k-j}. $$ This proves the recurrence, including the case \(k-j=0\), which accounts for a renewal at \(k\) that is the first renewal after time zero. \(\square\)
To obtain the limit, track the time remaining until the next renewal. Let \(R_n\) be the smallest nonnegative integer \(r\) such that \(n+r\) is a renewal epoch, with time zero included among the epochs. Thus \(R_n=0\) exactly when \(n\) is a renewal epoch. The state space is \(C=\{r\ge0:\mathbb{P}(Y>r)>0\}\). From a positive state \(r\), the chain moves to \(r-1\). From state zero, a fresh interarrival begins, so the next state is \(Y-1\). Independence of successive interarrivals makes \((R_n)_{n\ge0}\) a Markov chain.
Proof of the theorem. First consider the residual-life chain started at \(R_0=0\). It is irreducible on \(C\): from zero, if \(r\in C\), then \(\mathbb{P}(Y>r)>0\), so there is positive probability to jump to some state at least \(r\), and then descend deterministically to \(r\). Every state in \(C\) descends to zero. The first return time to zero, starting from zero, is exactly \(Y\), so its mean is \(m<\infty\); the chain is positive recurrent. Its possible return times to zero are precisely the possible values of \(Y\). Their greatest common divisor is \(1\), so the chain is aperiodic.
Define \(\pi_r=\mathbb{P}(Y>r)/m\) for \(r\in C\). The integer tail-sum identity gives \(\sum_{r\ge0}\mathbb{P}(Y>r)=\mathbb{E}Y=m\), so these values form a probability distribution. To check stationarity, the probability entering state \(r\) in one step comes either from \(r+1\), by deterministic descent, or from zero, by a new interarrival of length \(r+1\). Thus, interpreting absent states as having zero mass, $$ \sum_{s\in C}\pi_s\,\mathbb{P}(R_{n+1}=r\mid R_n=s) =\pi_{r+1}+\pi_0 f_{r+1} =\frac{\mathbb{P}(Y>r+1)+\mathbb{P}(Y=r+1)}{m} =\pi_r. $$ The same calculation applies at \(r=0\). In particular, the stationary mass at zero is \(\pi_0=1/m\).
By the stated countable-state convergence theorem, \(\mathbb{P}_0(R_k=0)\to\pi_0=1/m\). Since \(R_k=0\) exactly when \(k\) is a renewal epoch and at most one epoch can equal \(k\), \(\mathbb{P}_0(R_k=0)=u_k\). Hence \(u_k\to1/m=h/\mu\), proving the point-mass limit. Finally, \((t,t+h]\) contains exactly one multiple of \(h\), namely \(h\lceil t/h\rceil\); as \(t\to\infty\), its index tends to infinity. Therefore \(U((t,t+h])=u_{\lceil t/h\rceil}\to h/\mu\). \(\square\)
Worked Examples
Worked Example: Interarrivals of One or Two Units
Suppose the scaled interarrival \(Y\) equals \(1\) or \(2\), each with probability \(\tfrac12\). Find the renewal masses and their limit.
The probabilities are \(f_1=f_2=\tfrac12\), with all other \(f_j=0\). They sum to \(1\), and the greatest common divisor of \(1\) and \(2\) is \(1\). The mean is \(m=1\cdot\tfrac12+2\cdot\tfrac12=\tfrac32\). The recurrence gives \(u_0=1\), \(u_1=\tfrac12u_0=\tfrac12\), and, for \(k\ge2\), \(u_k=\tfrac12u_{k-1}+\tfrac12u_{k-2}\).
The characteristic equation is \(r^2=\tfrac12r+\tfrac12\), or \(2r^2-r-1=0\), whose roots are \(1\) and \(-\tfrac12\). Hence \(u_k=C+D(-\tfrac12)^k\). The initial values require \(C+D=1\) and \(C-\tfrac12D=\tfrac12\). Subtracting gives \(\tfrac32D=\tfrac12\), so \(D=\tfrac13\) and \(C=\tfrac23\).
Check: The formula gives \(u_0=\tfrac23+\tfrac13=1\) and \(u_1=\tfrac23-\tfrac16=\tfrac12\). Both roots satisfy the recurrence’s characteristic equation, so the formula satisfies the recurrence at every \(k\ge2\). Its limit is \(\tfrac23\), which equals \(1/m=1/(\tfrac32)=\tfrac23\).
Worked Example: Interarrivals on an Even Lattice
Suppose the original interarrival \(X_1\) equals \(2\) or \(4\), each with probability \(\tfrac12\). Find the limiting renewal mass at a lattice point.
The maximal span is \(h=2\), since both possible values are multiples of \(2\), while their scaled values \(1\) and \(2\) have greatest common divisor \(1\). The mean is \(\mu=2\cdot\tfrac12+4\cdot\tfrac12=3\). In scaled units the interarrival is \(Y=1\) or \(2\), each with probability \(\tfrac12\), so the recurrence from the first example applies. For instance, \(u_2=\tfrac12u_1+\tfrac12u_0=\tfrac12\cdot\tfrac12+\tfrac12\cdot1=\tfrac34\); the closed form gives \(\tfrac23+\tfrac13(\tfrac14)=\tfrac34\) as well.
Check: The point-mass limit is \(1/\mathbb{E}Y=1/(\tfrac32)=\tfrac23\). In original time units it is \(h/\mu=2/3\), the same value. In particular, \(U((4,6])=u_3\) and tends to \(\tfrac23\) as the interval is translated farther out along the even lattice.
Worked Example: Three Possible Interarrival Lengths
Let \(h=1\) and suppose \(Y\) has probabilities \(\mathbb{P}(Y=1)=\tfrac12\), \(\mathbb{P}(Y=2)=\tfrac13\), and \(\mathbb{P}(Y=3)=\tfrac16\). Compute the first renewal masses and identify their limit.
The probabilities sum to \(\tfrac12+\tfrac13+\tfrac16=1\), and the support has greatest common divisor \(1\). The mean is \(m=1\cdot\tfrac12+2\cdot\tfrac13+3\cdot\tfrac16=\tfrac12+\tfrac23+\tfrac12=\tfrac53\). The recurrence gives \(u_0=1\), \(u_1=\tfrac12\), and $$ u_2=\tfrac12u_1+\tfrac13u_0=\tfrac14+\tfrac13=\tfrac7{12}. $$ It then gives $$ u_3=\tfrac12u_2+\tfrac13u_1+\tfrac16u_0 =\tfrac7{24}+\tfrac16+\tfrac16 =\tfrac{15}{24}=\tfrac58. $$
Check: At time \(3\), renewal can occur through one interarrival of length \(3\), two interarrivals with lengths \(1,2\) in either order, or three interarrivals of length \(1\). The probabilities sum to \(\tfrac16+2(\tfrac12\cdot\tfrac13)+(\tfrac12)^3=\tfrac4{24}+\tfrac8{24}+\tfrac3{24}=\tfrac{15}{24}=\tfrac58\), agreeing with the recurrence. The theorem gives \(u_k\to1/m=1/(\tfrac53)=\tfrac35\).
Interpreting the Limit and Avoiding a Span Error
The renewal mass at one distant lattice point tends to \(h/\mu\), but this does not say that the renewal count itself approaches a finite value. The count \(N(t)\) grows with \(t\); the local statement concerns its increments over a fixed interval. Because \((t,t+h]\) contains exactly one lattice point for every real \(t\), its expected number of renewals is \(U((t,t+h])\), which tends to \(h/\mu\). The open-left, closed-right convention avoids counting a lattice endpoint twice when adjacent intervals are used.
Common mistake. In the even-lattice example, using \(1/\mu=1/3\) as the limit loses the span factor. The scaled interarrival has mean \(\mathbb{E}Y=\mu/h=3/2\), so its renewal mass tends to \(1/(\tfrac32)=\tfrac23\). Equivalently, in original units the theorem gives \(h/\mu=2/3\), not \(1/3\). The span cannot be omitted unless the lattice has first been scaled to unit spacing.
The greatest-common-divisor condition is also essential. If the scaled interarrival were always even, renewals could occur only at even integer times; the renewal mass at odd times would be zero, so it could not converge to a positive common limit across all integers. Choosing the maximal span rescales that example so that the scaled support has greatest common divisor \(1\).
Check Your Understanding
Use the recurrence and the theorem’s hypotheses to justify each answer.
- If \(X_1\) equals \(3\) or \(6\), each with probability \(\tfrac12\), identify the maximal span, the scaled mean, and the limiting point mass.
- For the interarrival law with probabilities \(\tfrac12,\tfrac13,\tfrac16\) at \(1,2,3\), compute \(u_4\) from the recurrence and verify it by listing the compositions of \(4\).
- Why does \(U((t,t+h])\) contain the mass of exactly one lattice point, including when \(t/h\) is an integer?
- Which hypothesis of the lattice theorem fails if the scaled interarrival is always \(2\), and what happens to renewal masses at odd integers?
- Explain why the residual-life chain has return-time mean \(\mathbb{E}Y\), and why its stationary mass at zero is the renewal-mass limit.