Elementary Renewal Theorem and Long-Run Event Rate

From Mean Interarrival Time to Long-Run Rate

In a renewal process, events occur at successive epochs, and the gaps between epochs are independent copies of a common interarrival time. A basic long-run question is how many events to expect by time $t$, relative to the length of the observation period. The elementary renewal theorem answers this question using just the mean interarrival time: if that mean is finite and positive, the expected count grows asymptotically at a constant rate equal to its reciprocal.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $X_1,X_2,\ldots$ be independent and identically distributed random variables with $X_k>0$ almost surely and $0<\mu=\mathbb{E}[X_1]<\infty$. Define the $n$th renewal epoch by $S_n=\sum_{k=1}^n X_k$. For $t\ge0$, count renewals at or before $t$, excluding the initial time $S_0=0$:

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

Because the interarrivals are strictly positive, the epochs increase strictly. The endpoint convention matters at a renewal epoch: an event at exactly $t$ is included by the condition $S_n\le t$. The function $U(t)$, called the renewal function, is the expected number of renewals by time $t$.

Theorem (Elementary renewal theorem): For positive iid interarrivals with finite mean $0<\mu<\infty$, the renewal function is finite for each finite $t$, and $$ \lim_{t\to\infty}\frac{U(t)}{t}=\frac{1}{\mu}. $$ Thus the expected number of renewals per unit time approaches the reciprocal of the mean interarrival time. The proof of the general theorem is given in the later treatment devoted to proving the elementary renewal theorem.

The limit is an asymptotic statement. It does not say that $U(t)=t/\mu$ at each finite time, nor that the count itself is close to its limit without variation. It says that the ratio of the expected count to elapsed time approaches a constant. The units also agree: if time is measured in days, then $\mu$ is in days per event and $1/\mu$ is in events per day.

Why the Expected Count Is Finite

The theorem’s ratio is meaningful only if $U(t)$ is finite at finite $t$. Positive interarrivals prevent infinitely many renewals in finite time on each sample path, but that fact alone does not automatically establish a finite expectation. The following argument verifies the expectation as well.

Proposition: If $X_k$ are positive iid interarrivals, then $U(t)<\infty$ for every finite $t\ge0$.

Proof. Fix finite $t$. Since $X_1>0$ almost surely, there is a $\delta>0$ such that $p=\mathbb{P}(X_1\ge\delta)>0$: indeed, the events $\{X_1\ge 1/m\}$, for positive integers $m$, have union $\{X_1>0\}$, so at least one has positive probability. Let $r=\lfloor t/\delta\rfloor$ and $Y_k=\mathbf{1}_{\{X_k\ge\delta\}}$. If $S_n\le t$, then $\sum_{k=1}^nY_k\le r$, since $r+1$ interarrivals of size at least $\delta$ would have sum at least $(r+1)\delta>t$. Also, by summing the indicators in the definition of $N(t)$ and applying monotone convergence, $U(t)=\sum_{n\ge1}\mathbb{P}(S_n\le t)$.

If $p=1$, the event $S_n\le t$ is impossible when $n>r$, so this sum has only finitely many nonzero terms. If $0<p<1$, then $\sum_{k=1}^nY_k$ has a binomial distribution, and for $n\ge\max(1,r)$,

\mathbb{P}(S_n\le t) \le \sum_{j=0}^{r}\binom{n}{j}p^j(1-p)^{n-j} \le \left(\sum_{j=0}^{r}(1-p)^{-j}\right)n^r(1-p)^n.

For the second inequality, use $p^j\le1$, $\binom{n}{j}\le n^j\le n^r$, and $(1-p)^{n-j}=(1-p)^n(1-p)^{-j}$. The series $\sum_{n\ge\max(1,r)} n^r(1-p)^n$ converges because a polynomial times a geometric sequence with ratio strictly below $1$ is summable. The omitted initial terms are finite in number. Therefore $\sum_{n\ge1}\mathbb{P}(S_n\le t)<\infty$, proving $U(t)<\infty$. $\square$

Worked Examples

Worked Example: Deterministic Interarrivals

Suppose every interarrival is exactly $2$ time units, so $X_k=2$ almost surely. Then $\mu=2$, and $S_n=2n$. By the endpoint convention, a renewal is counted when $2n\le t$, so $N(t)=\lfloor t/2\rfloor$ and $U(t)=\lfloor t/2\rfloor$.

At $t=17/3$, the condition $2n\le17/3$ is equivalent to $n\le17/6$. Thus $N(17/3)=\lfloor17/6\rfloor=2$, and

\frac{U(17/3)}{17/3}=\frac{2}{17/3}=\frac{6}{17}.

For general $t$, $t/2-1<\lfloor t/2\rfloor\le t/2$. Dividing by $t>0$ gives $1/2-1/t<U(t)/t\le1/2$, so $U(t)/t\to1/2=1/\mu$. This example also shows the endpoint effect: at $t=6$, the renewals at $2,4,6$ are all counted, giving $N(6)=3$, not $2$.

Worked Example: Exponential Interarrivals

Suppose the interarrivals are exponential with rate $\lambda=3/2$ per unit time. Their mean is $\mu=1/\lambda=2/3$. The renewal process is the Poisson process with rate $3/2$, for which $N(t)$ has a Poisson distribution with mean $\lambda t$. Hence $U(t)=\lambda t$.

At $t=4$, the count has Poisson mean $(3/2)4=6$, so $U(4)=6$ and $U(4)/4=6/4=3/2$. The limit is already exact at every positive $t$:

\frac{U(t)}{t}=\frac{(3/2)t}{t}=\frac32=\frac{1}{2/3}=\frac{1}{\mu}.

As a check on the expectation formula, if $N(t)$ is Poisson with parameter $\lambda t$, then $\mathbb{E}[N(t)]=\sum_{k\ge1} k e^{-\lambda t}(\lambda t)^k/k! =\lambda t\, e^{-\lambda t}\sum_{j\ge0}(\lambda t)^j/j! =\lambda t$. The exact linearity here is a special feature of the Poisson process, not part of the general theorem.

Worked Example: Two-Point Interarrivals

Let each interarrival equal $1$ or $3$, each with probability $1/2$. The mean is $\mu=(1+3)/2=2$, so the predicted long-run expected rate is $1/2$. Compute $U(8)$ directly to see that the finite-time ratio need not equal the limit.

If exactly $k$ of the first $n$ interarrivals equal $3$, then $S_n=n+2k$. Therefore $S_n\le8$ holds exactly when $k\le\lfloor(8-n)/2\rfloor$. For $n=1,\ldots,8$, the probabilities $\mathbb{P}(S_n\le8)$ are, respectively,

1,\quad 1,\quad \frac78,\quad \frac{11}{16},\quad \frac{3}{16},\quad \frac{7}{64},\quad \frac{1}{128},\quad \frac{1}{256}.

For example, when $n=4$, at most two interarrivals can equal $3$, giving $(\binom40+\binom41+\binom42)/2^4=(1+4+6)/16=11/16$. When $n=5$, at most one can equal $3$, giving $(1+5)/2^5=3/16$. For $n=7$ and $n=8$, none can equal $3$, giving $1/2^7$ and $1/2^8$. For $n=1,2$ every possible sum is at most $8$, and for $n=3$ only the outcome with three interarrivals equal to $3$ is excluded, leaving $7/8$.

For $n>8$, $S_n\ge n>8$, so there are no further terms. Adding the listed probabilities gives

U(8)=1+1+\frac78+\frac{11}{16}+\frac{3}{16}+\frac{7}{64}+\frac{1}{128}+\frac{1}{256} =\frac{991}{256}, \qquad \frac{U(8)}8=\frac{991}{2048}.

This finite-time ratio differs from $1/2$. The elementary renewal theorem says that as $t$ increases without bound, the ratio approaches $1/2$; it does not assert equality at $t=8$.

A Bounded-Interarrival Case You Can Verify Directly

The general theorem permits interarrivals arbitrarily close to zero or arbitrarily large, as long as they are positive and have finite mean. In the special case where they are bounded both below and above, its expectation limit follows directly from the strong law of large numbers and bounded convergence.

Proposition: Suppose the interarrivals are iid and satisfy $0<a\le X_k\le b<\infty$ almost surely. Then $U(t)/t\to1/\mu$.

Proof. By the strong law of large numbers, $S_n/n\to\mu$ almost surely. Since $S_n\le nb$, the number of renewals tends to infinity as $t\to\infty$: specifically, $N(t)\ge\lfloor t/b\rfloor$. For sufficiently large $t$, write $m=N(t)\ge1$. The count convention implies $S_m\le t<S_{m+1}$, and therefore

\frac{S_m}{m}\le\frac{t}{m}<\frac{S_{m+1}}{m} =\frac{m+1}{m}\frac{S_{m+1}}{m+1}.

As $t\to\infty$, $m\to\infty$; both outer quantities converge almost surely to $\mu$. Thus $t/N(t)\to\mu$, and, because $\mu>0$, $N(t)/t\to1/\mu$ almost surely. Also, $S_m\ge ma$ and $S_m\le t$, so $N(t)/t\le1/a$ for $t>0$. This deterministic bound is integrable. The dominated convergence theorem now gives $\mathbb{E}[N(t)/t]\to1/\mu$, which is the stated limit because $\mathbb{E}[N(t)/t]=U(t)/t$. $\square$

This special-case proof highlights a point that matters in the general theorem. The strong law for renewal epochs, together with its inversion, gives the almost-sure rate $N(t)/t\to1/\mu$. Almost-sure convergence alone does not guarantee convergence of expectations: that step needs an additional argument controlling large values. The general elementary renewal theorem supplies the expectation limit under the weaker finite-mean assumption, without requiring a positive lower bound on the interarrivals.

Long-Run Interpretation and a Common Mistake

Suppose events represent component replacements, patient arrivals, or machine failures, and the average time between consecutive events is $\mu$. The theorem says that over a long observation period of length $t$, the expected number of events is approximately $t/\mu$. For instance, if the mean gap is $5$ hours, the long-run expected rate is $1/5$ event per hour. This is a long-run average rate; it does not mean that events occur exactly every $5$ hours, or that the count over a short interval is predictable from the mean alone.

Common mistake: treating the asymptotic rate as an exact finite-time formula. In the two-point example, $\mu=2$, so replacing $U(8)$ by $8/\mu=4$ incorrectly claims an exact count expectation. The direct calculation gives $U(8)=991/256$, not $4$, and $991/256\ne4$. The theorem concerns the limit as $t\to\infty$, not equality for a fixed $t$. A second mistake is to confuse the pathwise limit with the expected-count limit: an almost-sure limit for $N(t)/t$ does not, by itself, justify taking expectations of that limit.

Check Your Understanding

Use the endpoint convention $S_n\le t$ when answering these questions.

If every interarrival is $3$, what are $N(10)$, $U(10)$, and the limiting expected rate?
For iid positive interarrivals with finite mean $\mu=4$, what does the elementary renewal theorem say about $U(t)/t$? Does it say $U(12)=3$?
For the two-point interarrival law taking values $1$ and $3$ with equal probability, compute $\mathbb{P}(S_3\le5)$ and explain which outcomes are included.
Why does a finite-time expectation $U(t)$ exist when the interarrivals are positive iid, even if they can be arbitrarily close to zero?
In the bounded-interarrival proposition, which bound allows almost-sure convergence to be passed through the expectation?