Worked Renewal Counts with Mixed Interarrival Laws

Renewal Counts at a Fixed Time

A renewal count at time $t$ is built from the renewal epochs that have occurred by $t$. For discrete interarrival laws, an epoch can land exactly at the observation time, so the convention at the boundary can change both the count and its distribution. This tutorial works through two useful cases: interarrivals taking one of two positive values, and exponentially distributed interarrivals.

Let $X_1,X_2,\ldots$ be independent, identically distributed, strictly positive random variables on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. They are the interarrival times. Define $S_0=0$ and $S_n=X_1+\cdots+X_n$ for $n\ge1$. The renewal count used here includes an epoch at the observation time:

Definition: For $t\ge0$, let $N(t)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le t\}}$, the number of renewals in the interval $(0,t]$. The $n$th epoch probability is $U_n(t)=\mathbb{P}(S_n\le t)$. Since the interarrivals are strictly positive, the epochs are strictly increasing.

For a two-point law bounded below by $a>0$, at most $\lfloor t/a\rfloor$ renewals can occur by time $t$, so the count is a finite sum. For exponential interarrivals there is no positive lower bound, but the count is still finite almost surely; the calculation below also proves its expectation is finite. In either case, expressing the count as a sum of indicators gives the useful identity $\mathbb{E}N(t)=\sum_{n\ge1}U_n(t)$. For an infinite sum, this follows by applying the monotone convergence theorem to the increasing partial sums of the indicators.

Two Possible Interarrival Times

Theorem (Epoch probabilities for a two-point law): Suppose $X_k=a$ with probability $p$ and $X_k=b$ with probability $1-p$, where $0<a<b$ and $0<p<1$. For every integer $n\ge1$, $$ U_n(t)=\sum_{\substack{0\le j\le n\\na+(b-a)j\le t}} \binom{n}{j}p^{\,n-j}(1-p)^j. $$ An empty sum has value $0$. Consequently, $$ \mathbb{E}N(t)=\sum_{n=1}^{\lfloor t/a\rfloor}U_n(t). $$

Proof. In the first $n$ interarrivals, let $J$ be the number that equal $b$. If $J=j$, then the other $n-j$ interarrivals equal $a$, and $S_n=(n-j)a+jb=na+(b-a)j$. There are $\binom{n}{j}$ arrangements of those $j$ long interarrivals; each arrangement has probability $p^{n-j}(1-p)^j$ by independence. The events corresponding to different arrangements are disjoint, so $J=j$ has probability $\binom{n}{j}p^{n-j}(1-p)^j$. The event $S_n\le t$ consists exactly of the values of $j$ satisfying $na+(b-a)j\le t$. Summing their probabilities proves the formula for $U_n(t)$. Also $S_n\ge na$, so $U_n(t)=0$ whenever $n>t/a$. Summing the finitely many epoch probabilities gives the stated expectation identity. $\square$

Worked Example: Two-Point Interarrivals at Time Three

Suppose each interarrival is $1$ or $2$, each with probability $\tfrac12$. Find the epoch probabilities and the distribution and expectation of $N(3)$, using the convention $S_n\le3$.

The minimum interarrival is $1$, so at most three renewals can occur. For $n=1$, both possible interarrivals are at most $3$, giving $U_1(3)=1$. For $n=2$, the total is at most $3$ unless both interarrivals equal $2$. The four equally likely ordered pairs have totals $2,3,3,4$, so $U_2(3)=\tfrac34$. For $n=3$, the total is at most $3$ only when all three interarrivals equal $1$, so $U_3(3)=(\tfrac12)^3=\tfrac18$. For $n\ge4$, $S_n\ge4>3$, so $U_n(3)=0$.

To obtain the count distribution, $N(3)=1$ exactly when $S_2>3$, which requires two consecutive interarrivals of $2$; its probability is $\tfrac14$. The event $N(3)=3$ requires $S_3\le3$, which occurs only for the sequence $(1,1,1)$; its probability is $\tfrac18$. The remaining probability is $1-\tfrac14-\tfrac18=\tfrac58$, so $N(3)=2$ with probability $\tfrac58$. Thus $$ \mathbb{E}N(3)=1\cdot\tfrac14+2\cdot\tfrac58+3\cdot\tfrac18 =\tfrac14+\tfrac{10}{8}+\tfrac38=\tfrac{15}{8}. $$ Check: Summing the epoch probabilities gives $U_1(3)+U_2(3)+U_3(3)=1+\tfrac34+\tfrac18=\tfrac{15}{8}$, the same expectation.

Why the Boundary Convention Matters

The count $N(t)$ includes renewals at $t$, because its defining event is $S_n\le t$. A different, also well-defined count is $N_{<}(t)=\sum_{n\ge1}\mathbf{1}_{\{S_n<t\}}$, which excludes epochs exactly at $t$. These counts agree whenever the probability of an epoch at $t$ is zero, as happens for exponential interarrivals. They need not agree for a two-point law.

Worked Example: An Epoch Exactly at the Observation Time

Use the same two-point law, with values $1$ and $2$ each of probability $\tfrac12$, but observe at $t=2$. Find the count distribution and expectation under both boundary conventions.

For $N(2)$, the first renewal always occurs by time $2$, so $U_1(2)=1$. Two renewals occur by time $2$ only if both interarrivals equal $1$, an event with probability $\tfrac12\cdot\tfrac12=\tfrac14$. Three renewals are impossible because $S_3\ge3>2$. Therefore $\mathbb{P}(N(2)=1)=1-\tfrac14=\tfrac34$, $\mathbb{P}(N(2)=2)=\tfrac14$, and $\mathbb{E}N(2)=\tfrac34+2\cdot\tfrac14=\tfrac54$. The epoch-probability sum checks this: $U_1(2)+U_2(2)=1+\tfrac14=\tfrac54$.

For the strict count $N_{<}(2)$, the first renewal is strictly before $2$ only when $X_1=1$, with probability $\tfrac12$. A second renewal cannot be strictly before $2$, since $S_2\ge2$. Hence $N_{<}(2)=1$ with probability $\tfrac12$ and $N_{<}(2)=0$ with probability $\tfrac12$, giving $\mathbb{E}N_{<}(2)=\tfrac12$. The difference is due to equality: the sequence $(1,1)$ has $S_2=2$, so that second epoch is counted by $N(2)$ but not by $N_{<}(2)$.

Common mistake. Replacing $S_n\le t$ with $S_n<t$ without changing the stated convention gives the wrong answer at an atom. In the example, the incorrect strict calculation would report $\mathbb{E}N(2)=\tfrac12$. The defined count includes the epoch at $2$, and its correct expectation is $\tfrac54$. Before using an epoch formula, check whether its inequality matches the requested count.

Exponential Interarrivals

Theorem (Exponential epoch probabilities and expected count): Suppose the interarrivals are independent and each has the exponential distribution with rate $\lambda>0$, meaning $\mathbb{P}(X_k>x)=e^{-\lambda x}$ for $x\ge0$. For $t\ge0$ and $n\ge1$, $$ U_n(t)=1-e^{-\lambda t}\sum_{k=0}^{n-1}\frac{(\lambda t)^k}{k!}, \qquad \mathbb{E}N(t)=\lambda t. $$

Proof. The density of $X_k$ is $f(x)=\lambda e^{-\lambda x}$ for $x>0$. We first derive the density of $S_n$. For $n=1$, it is $f_1(s)=\lambda e^{-\lambda s}$. If $S_n$ has density $f_n(s)=\lambda^n s^{n-1}e^{-\lambda s}/(n-1)!$, independence gives, for $s>0$, $$ f_{n+1}(s)=\int_0^s f_n(u)\lambda e^{-\lambda(s-u)}\,du =\frac{\lambda^{n+1}e^{-\lambda s}}{(n-1)!}\int_0^s u^{n-1}\,du =\frac{\lambda^{n+1}s^ne^{-\lambda s}}{n!}. $$ By induction this is the density of $S_n$ for every $n\ge1$. Integrating it from $0$ to $t$, or integrating by parts repeatedly, gives $$ \mathbb{P}(S_n\le t)=1-e^{-\lambda t}\sum_{k=0}^{n-1}\frac{(\lambda t)^k}{k!}. $$ For the expected count, put $x=\lambda t$. The same formula can be written $U_n(t)=e^{-x}\sum_{k=n}^{\infty}x^k/k!$, since $\sum_{k=0}^{\infty}x^k/k!=e^x$. All terms are nonnegative, so Tonelli's theorem permits reversing the order of summation: $$ \mathbb{E}N(t)=\sum_{n=1}^{\infty}U_n(t) =e^{-x}\sum_{k=1}^{\infty}\sum_{n=1}^{k}\frac{x^k}{k!} =e^{-x}\sum_{k=1}^{\infty}\frac{kx^k}{k!} =xe^{-x}\sum_{r=0}^{\infty}\frac{x^r}{r!}=x=\lambda t. $$ This calculation also establishes that the count has finite expectation. Since a nonnegative integer-valued random variable with finite expectation cannot be infinite with positive probability, $N(t)$ is finite almost surely. For $t=0$, all the epoch probabilities and the expected count are $0$, consistent with the formulas. $\square$

Worked Example: Exponential Interarrivals at Time One-Half

Let each interarrival be exponential with rate $\lambda=2$, and observe at $t=\tfrac12$. Compute the first three epoch probabilities and the expected count.

Here $\lambda t=2\cdot\tfrac12=1$. Substitution into the epoch formula gives $$ U_1(\tfrac12)=1-e^{-1},\qquad U_2(\tfrac12)=1-e^{-1}(1+1)=1-2e^{-1}, $$ and $$ U_3(\tfrac12)=1-e^{-1}(1+1+\tfrac12)=1-\tfrac52e^{-1}. $$ For the next epoch, the same substitution gives $U_4(\tfrac12)=1-e^{-1}(1+1+\tfrac12+\tfrac16)=1-\tfrac83e^{-1}$. The expected count is $\lambda t=2\cdot\tfrac12=1$. It is not obtained by stopping the epoch-probability sum after three or four terms: the exponential law allows arbitrarily many renewals in any positive time interval.

Check: With $x=1$, the nonnegative-series calculation gives $$ \sum_{n=1}^{\infty}U_n(\tfrac12) =e^{-1}\sum_{k=1}^{\infty}\frac{k}{k!} =e^{-1}\sum_{r=0}^{\infty}\frac{1}{r!} =e^{-1}e=1, $$ matching the direct mean $\lambda t=1$. For exponential interarrivals, $\mathbb{P}(S_n=t)=0$ at each fixed $t$, because $S_n$ has a density. Thus replacing $\le t$ by $<t$ does not change these probabilities or the expected count.

Choosing and Checking a Calculation

For a finite-time renewal-count problem, first identify the interarrival law and the exact convention for counting an epoch at $t$. For a two-point law, use the number of long interarrivals among the first $n$; this reduces the epoch event to a finite binomial sum. Since every interarrival is at least $a>0$, only $n\le\lfloor t/a\rfloor$ contributes to the expected count. For exponential interarrivals, calculate each epoch probability from the Erlang distribution, then sum the entire nonnegative series when finding the expectation.

These methods are useful both for exact calculations and for checking more elaborate approaches. Epoch probabilities describe how likely it is that at least $n$ renewals have occurred; their sum gives the expected number of renewals. The distinction between these probabilities and the full distribution of $N(t)$ is important: the event $S_n\le t$ means $N(t)\ge n$, while an exact count requires comparing successive epochs. In a discrete interarrival model, test whether equality can occur before applying either interpretation.

Check Your Understanding

Use the convention $N(t)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le t\}}$ unless a question explicitly asks for a strict count.

If interarrivals are $1$ or $3$, each with probability $\tfrac12$, compute $U_2(4)$. Does the event include the pair $(1,3)$?
For interarrivals $1$ and $2$, each with probability $\tfrac12$, what is the largest possible value of $N(\tfrac52)$?
For the same two-point law, calculate $\mathbb{E}N(1)$, and explain the role of an epoch exactly at time $1$.
For exponential interarrivals with rate $\lambda$, write $U_2(t)$ and $\mathbb{E}N(t)$ in terms of $\lambda$ and $t$.
Why is it incorrect to find an exponential renewal expectation by summing only the first three epoch probabilities?