Proving the Renewal-Function Series Formula

From a Count to a Series

The renewal function records the expected number of renewals observed by a fixed time. A count can be represented as a sum of indicators: each possible renewal contributes one if its epoch has occurred, and zero otherwise. Taking expectations then suggests a series of probabilities. The important point is to justify this passage when there are infinitely many possible renewal epochs. Because the indicators are nonnegative, the partial sums increase, and the monotone convergence theorem gives the required exchange.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_k)_{k\ge1}$ be independent, identically distributed interarrival times with $0<X_k<\infty$ almost surely. Define the $n$th renewal epoch by $S_n=X_1+\cdots+X_n$, and for $t\ge0$ define the renewal count and renewal function by

N(t)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le t\}}, \qquad U(t)=\mathbb{E}[N(t)].

The endpoint convention is part of the definition: a renewal at time exactly $t$ is counted. The indicators in the sum are nested in the sense that $S_n\le t$ implies $S_k\le t$ for every $1\le k<n$, since the interarrival times are positive.

Theorem (Renewal-function series formula): For every $t\ge0$, under the assumptions above, $$ U(t)=\sum_{n\ge1}\mathbb{P}(S_n\le t), $$ where either side is understood as a nonnegative extended real number. No finite-mean assumption on the interarrival times is required for this identity.

The equality concerns expectations and probabilities, not independence of the events $\{S_n\le t\}$. In fact, these events are nested and generally dependent. The argument uses only the representation of the count and the nonnegativity of its summands.

Proof by Increasing Partial Counts

For $m\ge1$, define the count stopped at its first $m$ possible renewals by $N_m(t)=\sum_{n=1}^{m}\mathbf{1}_{\{S_n\le t\}}$. These variables are nonnegative and increase pointwise to $N(t)$ as $m$ increases. We use the standard measure-theoretic monotone convergence theorem: if nonnegative random variables increase pointwise to a limit, then their expectations increase to the expectation of that limit. This is the only infinite-sum exchange needed here.

Proof. Fix $t\ge0$. For each finite $m$, linearity of expectation for a finite sum and the indicator identity $\mathbb{E}[\mathbf{1}_A]=\mathbb{P}(A)$ give

\mathbb{E}[N_m(t)] =\mathbb{E}\!\left[\sum_{n=1}^{m}\mathbf{1}_{\{S_n\le t\}}\right] =\sum_{n=1}^{m}\mathbb{E}[\mathbf{1}_{\{S_n\le t\}}] =\sum_{n=1}^{m}\mathbb{P}(S_n\le t).

For every outcome, $N_m(t)$ increases to $N(t)$: each term in the defining sum for $N(t)$ eventually appears in $N_m(t)$, and no term is removed. Applying monotone convergence to this increasing sequence gives $\mathbb{E}[N_m(t)]\to\mathbb{E}[N(t)]$, allowing an infinite value. The finite sums on the right increase to $\sum_{n\ge1}\mathbb{P}(S_n\le t)$, by the definition of a series with nonnegative terms. Taking the limit in the finite-$m$ equality proves the formula. $\square$

This proof does not assume that the expected count is finite. It establishes equality even if both sides are infinite. Under the stated positivity and independence assumptions, the count is finite almost surely for each fixed $t$: there is some $a>0$ with $\mathbb{P}(X_1\ge a)>0$, and independence implies that $X_k\ge a$ occurs infinitely often almost surely. Thus $S_n$ tends to infinity almost surely. A finite almost-sure count can still have infinite expectation, so the extended-value formulation remains useful.

Proposition (Finite-count approximation): For every integer $m\ge1$, $$ \mathbb{E}[N_m(t)]=\sum_{n=1}^{m}\mathbb{P}(S_n\le t), \qquad U(t)=\lim_{m\to\infty}\mathbb{E}[N_m(t)]. $$ In particular, $U(t)<\infty$ exactly when the series of epoch probabilities converges to a finite value.

Proof. The finite-sum equality was established in the theorem’s proof. Since $N_m(t)$ increases pointwise to $N(t)$, monotone convergence gives the stated limit. The finite partial sums of the nonnegative series increase to its sum, so that limit is finite exactly when the series sum is finite. $\square$

Worked Applications

Worked Example: Deterministic Interarrival Times

Suppose every interarrival time is exactly $2$, and find $U(5)$. The renewal epochs are $S_n=2n$. The endpoint test is $2n\le5$, which holds for $n=1,2$ and fails for every $n\ge3$. Therefore the series formula gives

U(5)=\sum_{n\ge1}\mathbb{P}(2n\le5) =1+1+\sum_{n\ge3}0=2.

Directly, the renewals by time $5$ occur at times $2$ and $4$, so $N(5)=2$ with probability one and $\mathbb{E}[N(5)]=2$. Both calculations agree. The exact endpoint also matters: at $t=4$, the second renewal is counted because the condition is $S_n\le t$.

Worked Example: Exponential Interarrivals

Let the interarrival times be independent exponential random variables with rate $2$, and calculate $U(1)$. Their sums $S_n$ have Erlang distributions. Equivalently, the number of renewals by time $1$ has the Poisson distribution with mean $2$. Thus, for $n\ge1$, $\mathbb{P}(S_n\le1)$ is the probability of at least $n$ events in a Poisson random variable with mean $2$. Writing $k$ for its value gives

\begin{aligned} U(1) &=\sum_{n\ge1}\mathbb{P}(S_n\le1)\\ &=e^{-2}\sum_{n\ge1}\sum_{k=n}^{\infty}\frac{2^k}{k!}\\ &=e^{-2}\sum_{k\ge1}k\frac{2^k}{k!}\\ &=2e^{-2}\sum_{k\ge1}\frac{2^{k-1}}{(k-1)!} =2. \end{aligned}

The change in summation order is valid because every term is nonnegative: for a fixed $k\ge1$, the term $2^k/k!$ appears once for each $n=1,\ldots,k$, hence $k$ times. The final series is $e^2$, by the exponential power series, so the factors $e^{-2}$ and $e^2$ cancel, leaving $2$.

Check: The Poisson mean at time $1$ is $2\cdot1=2$, matching the series calculation. This example illustrates that the formula sums probabilities for individual epochs, not probabilities of disjoint events; the events $\{S_n\le1\}$ are nested.

Worked Example: Two-Point Interarrival Times

Let each interarrival time independently equal $1$ or $2$, each with probability $\tfrac12$. Find $U(3)$. For $n=1$, either value is at most $3$, so $\mathbb{P}(S_1\le3)=1$. For $n=2$, there are four equally likely ordered pairs. The sums are $2,3,3,4$, so three meet the inclusive condition and $\mathbb{P}(S_2\le3)=\tfrac34$. For $n=3$, the sum is at most $3$ only when all three interarrivals equal $1$, giving $\mathbb{P}(S_3\le3)=\tfrac18$. For $n\ge4$, $S_n\ge n\ge4$, so the probability is zero. Therefore

U(3)=1+\frac34+\frac18=\frac{8}{8}+\frac{6}{8}+\frac{1}{8}=\frac{15}{8}.

To check this answer directly, list the eight equally likely sequences of the first three interarrivals, writing $1$ or $2$ for each value. Their renewal counts by time $3$ are: $111$ gives $3$; $112,121,122,211,212$ each give $2$; and $221,222$ each give $1$. The total count across the eight outcomes is $3+2+2+2+2+2+1+1=15$, so its average is $\tfrac{15}{8}$, as obtained from the series. The count includes an epoch exactly at time $3$, as required by the endpoint convention.

Why Nonnegativity and Endpoints Matter

The proof depends on the partial counts increasing. If summands could be negative, an infinite sum could involve cancellation, and taking limits of finite sums would need additional conditions. Here every indicator is either $0$ or $1$, so monotone convergence applies directly. Independence of the indicators is neither assumed nor needed; independence is part of the standard renewal-process setup for the interarrival times, but the expectation identity itself follows from the indicator representation and nonnegativity.

A common mistake is to replace the inclusive epoch event by a strict one. For deterministic interarrivals of length $1$ at $t=2$, using $S_n<2$ gives probability $1$ for $n=1$ and probability $0$ for $n=2$, incorrectly producing a count of $1$. With the defined count $N(2)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le2\}}$, both $S_1=1$ and $S_2=2$ are counted, and the correct value is $U(2)=2$.

Another error is to use $\mathbb{P}(N(t)\ge1)$ in place of the expected count. That probability only indicates whether at least one renewal has occurred; it does not count additional renewals. In the two-point example, $\mathbb{P}(N(3)\ge1)=1$, whereas the expected count is $\tfrac{15}{8}$. The series works because its $n$th term asks whether the $n$th renewal has occurred, so each realized renewal contributes once.

Check Your Understanding

Use the inclusive endpoint convention $S_n\le t$. For each question, identify the relevant epoch probabilities before summing.

If every interarrival time equals $3$, find $U(8)$ from the series formula and verify it from the renewal count.
For interarrivals that independently equal $1$ or $2$ with equal probabilities, calculate $\mathbb{P}(S_2\le2)$.
Explain why the renewal-function formula remains valid if the expected count is infinite.
At $t=2$, how does the answer for deterministic unit interarrivals change if the event is incorrectly written $S_n<2$?
Does the series formula require the events $\{S_n\le t\}$ to be independent? Explain which property justifies the limit.

Proving the Renewal-Function Series Formula

What You'll Learn