Computing Renewal Functions from Tail Probabilities

From Epoch Probabilities to an Expected Count

A renewal function can be computed without first finding the full distribution of the number of renewals. Instead, consider each possible renewal in turn: the first has occurred by time $t$ if its epoch is no later than $t$, the second has occurred if its epoch is no later than $t$, and so on. Adding these probabilities gives the expected count. This approach is especially useful when the distributions of the renewal epochs are easier to calculate than the probabilities of each possible count.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $X_1,X_2,\ldots$ be independent, identically distributed, strictly positive interarrival times. Define the renewal epochs by $S_0=0$ and $S_n=X_1+\cdots+X_n$ for $n\ge1$. For $t\ge0$, use the endpoint convention $N(t)=\max\{n\ge0:S_n\le t\}$: a renewal at exactly time $t$ is counted. The renewal function is $m(t)=\mathbb{E}[N(t)]$. Write $F_n(t)=\mathbb{P}(S_n\le t)$ for the distribution function of the $n$th renewal epoch.

Theorem (Tail-probability formula): Under the assumptions above, $N(t)$ is finite almost surely and has finite expectation for each finite $t\ge0$. Moreover, $$ m(t)=\sum_{n=1}^{\infty}\mathbb{P}(N(t)\ge n) =\sum_{n=1}^{\infty}\mathbb{P}(S_n\le t) =\sum_{n=1}^{\infty}F_n(t). $$

Proof. Fix $t\ge0$. Since $\mathbb{P}(X_1>0)=1$, there is an $\varepsilon>0$ with $q=\mathbb{P}(X_1\ge\varepsilon)>0$. Otherwise $\mathbb{P}(X_1\ge1/k)=0$ for every positive integer $k$, contradicting $\mathbb{P}(X_1>0)=1$. Put $r=\lfloor t/\varepsilon\rfloor$, and let $T$ be the index of the $(r+1)$st interarrival time that is at least $\varepsilon$. The indicators $\mathbf{1}_{\{X_i\ge\varepsilon\}}$ are independent Bernoulli random variables with success probability $q$. The waiting times between successive successes have tail probabilities $(1-q)^k$, $k\ge0$, and hence mean $\sum_{k\ge0}(1-q)^k=1/q$. Therefore $\mathbb{E}[T]=(r+1)/q<\infty$. By time $S_T$, at least $r+1$ interarrivals are at least $\varepsilon$, so $S_T\ge(r+1)\varepsilon>t$. Thus $N(t)<T$, proving that $N(t)$ is finite almost surely and has finite expectation.

For each outcome, the nonnegative integer $N(t)$ can be written as $\sum_{n\ge1}\mathbf{1}_{\{N(t)\ge n\}}$: exactly its first $N(t)$ indicators equal one. Taking expectations and applying monotone convergence to the increasing partial sums gives $\mathbb{E}[N(t)]=\sum_{n\ge1}\mathbb{P}(N(t)\ge n)$. Because the epochs are strictly increasing, $N(t)\ge n$ holds exactly when $S_n\le t$. Substitution gives both equalities in the formula. $\square$

The theorem turns a count problem into an epoch-distribution problem. In a calculation, find $F_n(t)$ for each relevant $n$, then sum. Strict positivity ensures the identity is meaningful and the expectation finite, but does not by itself ensure that only finitely many terms are nonzero. A lower bound on the interarrival times gives a simple finite cutoff.

Proposition (Finite cutoff): If, in addition, $X_i\ge c$ almost surely for a constant $c>0$, then $F_n(t)=0$ whenever $n> \lfloor t/c\rfloor$. Consequently, $$ m(t)=\sum_{n=1}^{\lfloor t/c\rfloor}F_n(t), $$ where the sum is zero when $\lfloor t/c\rfloor=0$.

Proof. The assumption $X_i\ge c$ gives $S_n=X_1+\cdots+X_n\ge nc$ almost surely. If $n>\lfloor t/c\rfloor$, then $n>t/c$, so $nc>t$. Hence $\mathbb{P}(S_n\le t)=0$. In the tail-probability formula, all terms after $\lfloor t/c\rfloor$ therefore vanish. If $t<c$, the upper limit is zero and every $S_n\ge c>t$, so $m(t)=0$, as the empty sum states. $\square$

Exact Calculations for Discrete Interarrivals

Worked Example: Interarrivals of One or Two Time Units

Suppose each $X_i$ equals $1$ or $2$, each with probability $\tfrac12$. Find $m(3)$, counting a renewal at time $3$. Here $X_i\ge1$, so the finite cutoff gives $n\le\lfloor3/1\rfloor=3$. The endpoint test in every term is $S_n\le3$, including equality.

For $n=1$, both possible values are at most $3$, so $F_1(3)=1$. For $n=2$, the four equally likely ordered pairs are $(1,1),(1,2),(2,1),(2,2)$. The first three have sums $2,3,3$, respectively; the last has sum $4$. Thus $F_2(3)=\tfrac34$. For $n=3$, the sum is at most $3$ only for $(1,1,1)$, which has probability $(\tfrac12)^3=\tfrac18$. Therefore $F_3(3)=\tfrac18$, and $F_n(3)=0$ for $n\ge4$, since $S_n\ge n\ge4$.

m(3)=1+\frac34+\frac18=\frac88+\frac68+\frac18=\frac{15}{8}.

Check by the count distribution: $\mathbb{P}(N(3)=1)=F_1(3)-F_2(3)=\tfrac14$, $\mathbb{P}(N(3)=2)=F_2(3)-F_3(3)=\tfrac58$, and $\mathbb{P}(N(3)=3)=F_3(3)=\tfrac18$. These probabilities sum to $\tfrac28+\tfrac58+\tfrac18=1$, and their weighted count is $1\cdot\tfrac14+2\cdot\tfrac58+3\cdot\tfrac18=\tfrac28+\tfrac{10}{8}+\tfrac38=\tfrac{15}{8}$, agreeing with the tail sum.

Worked Example: Interarrivals of One or Three Time Units

Now suppose $\mathbb{P}(X_i=1)=\tfrac23$ and $\mathbb{P}(X_i=3)=\tfrac13$. Find $m(4)$. The interarrivals satisfy $X_i\ge1$, so only $n=1,2,3,4$ can contribute. Again, equality counts: the event used for each term is $S_n\le4$.

One interarrival is always at most $4$, so $F_1(4)=1$. For two interarrivals, the only pair whose sum exceeds $4$ is $(3,3)$, with probability $(\tfrac13)^2=\tfrac19$. Thus $F_2(4)=1-\tfrac19=\tfrac89$; pairs summing exactly $4$ are included. For three interarrivals, the sum is at most $4$ only if all three equal $1$, so $F_3(4)=(\tfrac23)^3=\tfrac8{27}$. For four interarrivals, only four $1$'s fit, giving $F_4(4)=(\tfrac23)^4=\tfrac{16}{81}$. Five or more interarrivals have sum at least $5$, so their probabilities are zero.

m(4)=1+\frac89+\frac8{27}+\frac{16}{81} =\frac{81+72+24+16}{81} =\frac{193}{81}.

Check by the count distribution: The tail probabilities give $\mathbb{P}(N(4)=1)=1-\tfrac89=\tfrac19$, $\mathbb{P}(N(4)=2)=\tfrac89-\tfrac8{27}=\tfrac{16}{27}$, $\mathbb{P}(N(4)=3)=\tfrac8{27}-\tfrac{16}{81}=\tfrac8{81}$, and $\mathbb{P}(N(4)=4)=\tfrac{16}{81}$. Their sum is $\tfrac9{81}+\tfrac{48}{81}+\tfrac8{81}+\tfrac{16}{81}=1$. The expected count is $\tfrac9{81}+2\cdot\tfrac{48}{81}+3\cdot\tfrac8{81}+4\cdot\tfrac{16}{81}=\tfrac{193}{81}$, the same value.

An Infinite Sum That Can Still Be Evaluated Exactly

When interarrivals have no positive lower bound, the finite-cutoff proposition may not apply. The tail-probability formula still applies, but infinitely many epoch probabilities can be nonzero. For exponential interarrivals, the epoch distributions make that infinite sum tractable.

Worked Example: Exponential Interarrivals at a Fixed Time

Let the interarrivals be independent exponential random variables with rate $\lambda=2$, and calculate $m(1)$. For $n\ge1$, $S_n$ has the Erlang distribution with density $2^n s^{n-1}e^{-2s}/(n-1)!$ for $s\ge0$. Integrating this density gives $F_n(1)=1-e^{-2}\sum_{k=0}^{n-1}2^k/k!$. For example, direct substitution gives $F_1(1)=1-e^{-2}$, $F_2(1)=1-3e^{-2}$, and $F_3(1)=1-5e^{-2}$. The series does not stop at $n=3$.

Rearranging the Erlang expression using $\sum_{k=0}^{\infty}2^k/k!=e^2$ gives $F_n(1)=e^{-2}\sum_{k=n}^{\infty}2^k/k!$. All terms are nonnegative, so the order of summation can be exchanged by the theorem for nonnegative series. For a fixed $k\ge1$, the term $2^k/k!$ appears once for each $n=1,\ldots,k$, hence $k$ times. Therefore

\begin{aligned} m(1) &=e^{-2}\sum_{n=1}^{\infty}\sum_{k=n}^{\infty}\frac{2^k}{k!}\\ &=e^{-2}\sum_{k=1}^{\infty}k\frac{2^k}{k!}\\ &=2e^{-2}\sum_{k=1}^{\infty}\frac{2^{k-1}}{(k-1)!}\\ &=2e^{-2}e^2=2. \end{aligned}

Check: With exponential interarrivals of rate $2$, the renewal count has the Poisson distribution with mean $2$ at time $1$. The calculation from the epoch probabilities gives the same expected count, $2$.

Endpoint Conventions and a Common Mistake

The comparison $S_n\le t$ is part of the definition of the count, not a notational detail. If an epoch can equal $t$ with positive probability, replacing $\le$ by $<$ changes the answer. For instance, if every interarrival equals $1$, then $S_1=1$ and $S_2=2$. At $t=2$, the inclusive convention gives $N(2)=2$ and $m(2)=2$; a strict test would exclude the second renewal and give the wrong value $1$.

A related error is to sum the probabilities of the exact count values as if they were the tail probabilities. In the first worked example, the exact-count probabilities are $\tfrac14,\tfrac58,\tfrac18$, which sum to $1$: they form a probability distribution. Their sum is not the expected count. The expectation weights each count by its size, giving $\tfrac14+2\cdot\tfrac58+3\cdot\tfrac18=\tfrac{15}{8}$. The tail formula instead sums $\mathbb{P}(N(3)\ge n)$, namely $1+\tfrac34+\tfrac18$, and gives the same expected value. Exact-count probabilities and tail probabilities answer different questions.

In practice, the calculation is systematic: establish the endpoint convention, identify the epoch CDFs $F_n(t)$, use a lower bound on interarrivals if one gives a finite cutoff, and sum the resulting probabilities. When the sum is infinite, look for a form that permits a justified rearrangement, as in the exponential example. Finally, check the result by recovering the distribution of $N(t)$ when that distribution has only a few possible values.

Check Your Understanding

For each question, use the convention that a renewal at exactly time $t$ is counted.

If $X_i=2$ almost surely, what are $F_1(4)$, $F_2(4)$, and $m(4)$?
If $X_i$ is $1$ or $2$ with equal probabilities, which values of $n$ can contribute to $m(2)$, and what is the role of the event $S_n=2$?
Explain why $\mathbb{P}(N(t)\ge n)=\mathbb{P}(S_n\le t)$ uses the inclusive inequality.
For the interarrival law in the second worked example, use the tail probabilities there to find $\mathbb{P}(N(4)=2)$.
Why does a positive lower bound $c$ on interarrivals imply that only finitely many terms in the tail-probability sum can be nonzero?

Computing Renewal Functions from Tail Probabilities

What You'll Learn