Proof of the Elementary Renewal Theorem

From Renewal Epochs to Expected Counts

Knowing that the number of renewals per unit time approaches a constant on almost every sample path does not, by itself, show that the expected number of renewals per unit time approaches the same constant. The obstacle is that rare sample paths with unusually many renewals can affect an expectation even when they do not alter an almost-sure limit. The proof of the elementary renewal theorem addresses this directly: Fatou’s lemma gives one inequality, and truncating interarrivals gives a uniform-in-time count bound for the other.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_k)_{k\ge1}$ be independent, identically distributed random variables with $X_k>0$ almost surely and finite mean $\mu=\mathbb{E}X_1$. In particular, $0<\mu<\infty$. Define the $n$th renewal epoch by $S_0=0$ and $S_n=X_1+\cdots+X_n$ for $n\ge1$. The renewal count $N(t)$, a process in continuous time $t\ge0$ with values in $\{0,1,2,\ldots\}$, counts renewals at or before time $t$: $N(t)=\max\{n\ge0:S_n\le t\}$. Thus an epoch exactly at $t$ is counted. The renewal function is $U(t)=\mathbb{E}N(t)$.

Theorem (Elementary Renewal Theorem): Under the assumptions above, $U(t)$ is finite for every $t\ge0$, and $$ \lim_{t\to\infty}\frac{U(t)}{t}=\frac{1}{\mu}. $$

The epoch strong law, established in the earlier material on renewal epochs, states that $S_n/n\to\mu$ almost surely. Its inversion gives $N(t)/t\to1/\mu$ almost surely. Here is the short argument for that inversion. Since $\mu>0$, $S_n\to\infty$ almost surely, so $N(t)$ is finite and tends to infinity as $t\to\infty$. For $N(t)\ge1$, the definition gives $S_{N(t)}\le t<S_{N(t)+1}$. Divide by $N(t)$: the left side tends almost surely to $\mu$, and the right side, written as $\frac{N(t)+1}{N(t)}\frac{S_{N(t)+1}}{N(t)+1}$, also tends to $\mu$. Hence $t/N(t)\to\mu$, and $N(t)/t\to1/\mu$ almost surely.

The Lower Bound from Fatou’s Lemma

The almost-sure count limit already controls the lower limit of the expected count. Fix any sequence $t_m\to\infty$. The random variables $N(t_m)/t_m$ are nonnegative and converge almost surely to $1/\mu$. Fatou’s lemma, a standard measure-theoretic result, therefore gives

\frac{1}{\mu} =\mathbb{E}\!\left[\liminf_{m\to\infty}\frac{N(t_m)}{t_m}\right] \le \liminf_{m\to\infty}\mathbb{E}\!\left[\frac{N(t_m)}{t_m}\right].

Because the sequence $t_m\to\infty$ was arbitrary, this proves $\liminf_{t\to\infty}U(t)/t\ge1/\mu$. Fatou’s lemma does not give the reverse inequality. To obtain it, we compare the original renewal process with one having shorter, bounded interarrivals.

Truncation Gives the Upper Bound

Fix a truncation level $b>0$ and define $Y_k=\min(X_k,b)$. These are still independent and identically distributed, are positive almost surely, and satisfy $Y_k\le b$. Write $\mu_b=\mathbb{E}Y_1$. Then $0<\mu_b\le b$, and $Y_k\le X_k$ implies that the epochs formed from the $Y_k$’s occur no later than the corresponding original epochs. If $N_b(t)=\max\{n\ge0:Y_1+\cdots+Y_n\le t\}$, this gives $N(t)\le N_b(t)$ on every sample path.

We first verify that $N_b(t)$ has finite expectation, so that the calculation below is justified. Since $Y_1>0$ almost surely, there are numbers $a>0$ and $p>0$ with $\mathbb{P}(Y_1\ge a)=p$. Indeed, the events $\{Y_1\ge1/r\}$, for positive integers $r$, have union $\{Y_1>0\}$, which has probability one; at least one of them must have positive probability. Put $r_t=\lfloor t/a\rfloor+1$. By the time $r_t$ such increments of size at least $a$ have occurred, their sum exceeds $t$. Consequently the first time the partial sums of the $Y_k$’s exceed $t$ is no later than the time of the $r_t$th success in independent Bernoulli trials with success probability $p$. The latter time has finite mean $r_t/p$: it is the sum of $r_t$ waiting times, each with geometric mean $1/p$. Thus $\mathbb{E}N_b(t)<\infty$.

Proof of the truncated count bound. Let $\tau=\min\{n\ge1:Y_1+\cdots+Y_n>t\}$. Then $\tau=N_b(t)+1$, and $Y_1+\cdots+Y_\tau\le t+b$, since the sum before the last increment is at most $t$ and the last increment is at most $b$. Also, $\{\tau\ge k\}$ is determined by $Y_1,\ldots,Y_{k-1}$, so it is independent of $Y_k$. Using nonnegativity to interchange the sum and expectation, and then this independence, gives $$ \mathbb{E}\!\left[\sum_{k=1}^{\tau}Y_k\right] =\sum_{k\ge1}\mathbb{E}[Y_k\mathbf{1}_{\{\tau\ge k\}}] =\mu_b\sum_{k\ge1}\mathbb{P}(\tau\ge k) =\mu_b\mathbb{E}\tau. $$ The sum is finite in expectation because $\mathbb{E}\tau<\infty$, as just shown, and $Y_k\le b$. The pathwise bound on the stopped sum now implies $\mu_b\mathbb{E}\tau\le t+b$. Since $N_b(t)=\tau-1$, we obtain $$ \mathbb{E}N_b(t)\le\frac{t+b}{\mu_b}-1. $$ This proves the bound and justifies its use for the original count as well: $N(t)\le N_b(t)$ implies $U(t)\le\mathbb{E}N_b(t)<\infty$. $\square$

For each fixed $b$, divide the bound by $t>0$ and let $t\to\infty$. It follows that $$ \limsup_{t\to\infty}\frac{U(t)}{t}\le\frac{1}{\mu_b}. $$ As $b\to\infty$, $\min(X_1,b)$ increases to $X_1$. The standard monotone convergence theorem gives $\mu_b\uparrow\mu$, so $\limsup_{t\to\infty}U(t)/t\le1/\mu$. Together with the lower bound from Fatou’s lemma, this proves the asserted limit.

Worked Examples and Checks

Worked Example: Deterministic Interarrivals

Suppose $X_k=2$ almost surely for every $k$. Then $\mu=2$ and $S_n=2n$. Because renewals at time $t$ are included, $N(t)=\lfloor t/2\rfloor$, so $U(t)=\lfloor t/2\rfloor$. For example, at $t=17/3$, $N(t)=\lfloor17/6\rfloor=2$, and $U(t)/t=2/(17/3)=6/17$. The theorem predicts the limiting rate $1/\mu=1/2$; indeed, $\lfloor t/2\rfloor/t\to1/2$ because $t/2-1<\lfloor t/2\rfloor\le t/2$.

Check at an endpoint: At $t=4$, $S_2=4$, so $N(4)=2$. Replacing $S_n\le t$ by $S_n<t$ would incorrectly give one renewal at this time. The theorem’s limit is unchanged, but the convention matters for the count at exact renewal epochs.

Worked Example: Exponential Interarrivals

Let the $X_k$ be exponential with rate $3/2$. Their mean is $\mu=2/3$. The Poisson special case of the renewal process gives $N(t)$ a Poisson distribution with mean $(3/2)t$, and therefore $U(t)=(3/2)t$. For $t=4$, the mean count is $(3/2)\cdot4=6$, and $U(4)/4=6/4=3/2=1/\mu$. In this model the limiting relation holds exactly for every $t>0$, rather than only asymptotically.

Check: The interarrival mean gives $1/\mu=1/(2/3)=3/2$, matching the computed ratio $U(t)/t=(3/2)t/t=3/2$.

Worked Example: A Two-Point Interarrival Law

Suppose each interarrival is $1$ or $3$, each with probability $1/2$. Then $\mu=(1+3)/2=2$, so the theorem predicts $U(t)/t\to1/2$. Compute $U(4)$, counting epochs at time $4$ as renewals.

For one interarrival, $S_1\le4$ with probability $1$. For two interarrivals, the possible sums are $2,4,6$; three of the four equally likely ordered pairs have sum at most $4$, so $\mathbb{P}(S_2\le4)=3/4$. For three interarrivals, the sum is at most $4$ only when all three equal $1$, with probability $1/8$. For four interarrivals it is at most $4$ only when all four equal $1$, with probability $1/16$. For $n\ge5$, $S_n\ge n>4$, so the probability is zero. Since $N(4)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le4\}}$,

U(4)=1+\frac34+\frac18+\frac1{16} =\frac{16}{16}+\frac{12}{16}+\frac{2}{16}+\frac{1}{16} =\frac{31}{16}.

Check: The event $S_2=4$ occurs for the ordered pairs $(1,3)$ and $(3,1)$, and both are counted because the condition is $S_2\le4$. The computed ratio is $U(4)/4=31/64$; it need not equal $1/2$ at this finite time, but the theorem gives its limit as $t$ grows.

Worked Example: Checking the Truncation Bound

Let $X_k=1$ with probability $3/4$ and $X_k=5$ with probability $1/4$, independently. The mean is $\mu=(3/4)\cdot1+(1/4)\cdot5=2$. At $t=3$, the probabilities $\mathbb{P}(S_n\le3)$ are $3/4$ for $n=1$, $9/16$ for $n=2$, and $27/64$ for $n=3$. For $n\ge4$, $S_n\ge4>3$, so the probability is zero. Thus $$ U(3)=\frac34+\frac9{16}+\frac{27}{64} =\frac{48}{64}+\frac{36}{64}+\frac{27}{64} =\frac{111}{64}. $$ Now truncate at $b=2$. The truncated interarrival is $1$ with probability $3/4$ and $2$ with probability $1/4$, so $\mu_2=(3/4)\cdot1+(1/4)\cdot2=5/4$. The proved bound gives $U(3)\le(3+2)/(5/4)-1=4-1=3$. The direct value $111/64$ satisfies it, since $111/64<192/64=3$. The bound is not intended to be sharp at this particular time; its purpose is to control the limiting upper rate.

Why the Expectation Step Needs Care

A common mistake is to infer convergence of expectations directly from almost-sure convergence. That implication is false without additional control. For instance, let $Z_n=n^2$ with probability $1/n^2$ and $Z_n=0$ otherwise. For $n\ge2$, the probabilities of the events $\{Z_n\ne0\}$ sum to $\sum_{n\ge2}1/n^2<\infty$. The Borel–Cantelli lemma therefore gives $Z_n\to0$ almost surely, but $\mathbb{E}Z_n=n^2(1/n^2)=1$ for every $n\ge2$. The almost-sure limit is $0$, while the expectations do not tend to $0$.

For renewal counts, Fatou’s lemma supplies only the lower bound. The truncation argument supplies the missing upper bound by comparing with a faster process whose interarrivals cannot exceed $b$. Its bound holds for every $t$ at the same fixed $b$, and the means of the truncated interarrivals then increase to $\mu$. This is the specific control that turns the pathwise renewal rate into convergence of the expected rate; it does not assert that almost-sure convergence alone is enough.

Check Your Understanding

Use the definitions and bounds in the proof to answer each question.

Why does $S_{N(t)}\le t<S_{N(t)+1}$ lead to $N(t)/t\to1/\mu$, rather than directly to a limit for $U(t)/t$?
In the truncated process, why is $\{\tau\ge k\}$ independent of $Y_k$?
If $X_k=3$ almost surely, what is $N(10)$, and what is the limiting value of $U(t)/t$? State whether an epoch exactly at $t$ is included.
For the law taking values $1$ and $3$ with equal probabilities, why is $\mathbb{P}(S_2\le4)=3/4$, not $1$?
Which part of the proof would fail if one used only Fatou’s lemma, without the truncated count bound?