Interarrival Times and Renewal Epochs

From Interarrivals to Epochs

A renewal process is built by repeatedly waiting for an interarrival time and then starting a new wait. The interarrival times describe the gaps between events; the renewal epochs describe when the events occur. Keeping these quantities distinct is essential: the first epoch is the first gap, while each later epoch accumulates all the gaps that came before it.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_n)_{n\ge1}$ be independent, identically distributed random variables taking values in $(0,\infty)$. The index $n$ is discrete, and each $X_n$ is the time between the $(n-1)$st and $n$th events. The $n$th renewal epoch is the time at which the $n$th event occurs.

Definition: Set $S_0=0$. For $n\ge1$, the $n$th renewal epoch is $S_n=X_1+\cdots+X_n$. Thus $X_n=S_n-S_{n-1}$. Since every $X_n>0$, the epochs satisfy $0=S_0<S_1<S_2<\cdots$ almost surely.

The positivity assumption means that events occur in strictly increasing time order. Independence means that the gaps are independent; identical distribution means that each gap has the same probability law. Neither property says that the epochs themselves are independent: for example, $S_2$ contains $X_1$, just as $S_1$ does.

The construction is valid for both integer-valued and continuously distributed gaps. For positive integer-valued gaps, epochs take positive integer values. For gaps with a density on $(0,\infty)$, epochs also have densities. The formulas below derive the first three laws directly from independence.

Distribution Formulas for the First Three Epochs

Theorem: Suppose $X_1,X_2,\ldots$ are iid and strictly positive. If they are positive integer-valued with $\mathbb{P}(X_1=r)=a_r$, then for $k\ge1$, $$ \mathbb{P}(S_1=k)=a_k,\qquad \mathbb{P}(S_2=k)=\sum_{r=1}^{k-1}a_r a_{k-r}, $$ and $$ \mathbb{P}(S_3=k)=\sum_{r=1}^{k-2}\sum_{s=1}^{k-r-1}a_r a_s a_{k-r-s}. $$ An empty sum is zero. If instead each $X_n$ has a density $f$ on $(0,\infty)$, then the first three epochs have densities $$ f_{S_1}(t)=f(t),\qquad f_{S_2}(t)=\int_0^t f(x)f(t-x)\,dx, $$ and $$ f_{S_3}(t)=\int_0^t\int_0^{t-x}f(x)f(y)f(t-x-y)\,dy\,dx,\qquad t>0. $$

Proof. By definition, $S_1=X_1$, so its law is the interarrival law. For the discrete case, the event $S_2=k$ is the disjoint union, over positive integers $r$ with $1\le r\le k-1$, of the events $\{X_1=r,\ X_2=k-r\}$. Independence gives each event probability $a_r a_{k-r}$; summing gives the formula. For $S_3=k$, choose the first two positive integer gaps $r,s$. The third must equal $k-r-s$, which is positive exactly when $s\le k-r-1$. The events for distinct pairs $(r,s)$ are disjoint, and independence gives probability $a_r a_s a_{k-r-s}$ for each. This proves the discrete formulas, including zero probability when there are no admissible positive gaps.

For the density formulas, independence gives joint density $f(x)f(y)$ for $(X_1,X_2)$. To find the density of their sum at $t>0$, integrate along the possible decompositions $x+(t-x)=t$, with $0<x<t$; this gives $\int_0^t f(x)f(t-x)\,dx$. For three gaps, the joint density of $(X_1,X_2,X_3)$ is $f(x)f(y)f(z)$. At a fixed sum $t$, write $z=t-x-y$; positivity requires $x>0$, $y>0$, and $x+y<t$. Integrating over that triangular region gives the stated double integral. These integrations are the change-of-variables formula for the sum, with Jacobian $1$. Hence the displayed functions are the densities of the respective sums. $\square$

These formulas are specific ways to compute the first few epoch laws, not a claim that epochs are independent. In practice, a discrete calculation enumerates possible gap combinations that reach a specified total. A continuous calculation integrates the joint density over all positive gap values with the required total.

Worked Example: A Three-Point Discrete Interarrival Law

Suppose the iid gaps satisfy $\mathbb{P}(X_n=1)=\tfrac12$, $\mathbb{P}(X_n=2)=\tfrac13$, and $\mathbb{P}(X_n=4)=\tfrac16$, with probability zero at every other value. The probabilities sum to $\tfrac12+\tfrac13+\tfrac16=1$. Find the distributions of $S_1,S_2,S_3$.

The first epoch is one gap: its masses are $\tfrac12,\tfrac13,\tfrac16$ at $1,2,4$, respectively. For $S_2$, list the possible unordered gap pairs and account for their order when the gaps differ:

\begin{aligned} \mathbb{P}(S_2=2)&=\mathbb{P}(1,1)=\tfrac14,\\ \mathbb{P}(S_2=3)&=\mathbb{P}(1,2)+\mathbb{P}(2,1)=2\cdot\tfrac12\cdot\tfrac13=\tfrac13,\\ \mathbb{P}(S_2=4)&=\mathbb{P}(2,2)+\mathbb{P}(1,3)+\mathbb{P}(3,1) =\tfrac19,\\ \mathbb{P}(S_2=5)&=\mathbb{P}(1,4)+\mathbb{P}(4,1) =2\cdot\tfrac12\cdot\tfrac16=\tfrac16,\\ \mathbb{P}(S_2=6)&=\mathbb{P}(2,4)+\mathbb{P}(4,2) =2\cdot\tfrac13\cdot\tfrac16=\tfrac19,\\ \mathbb{P}(S_2=8)&=\mathbb{P}(4,4)=\tfrac1{36}. \end{aligned}

Here the $S_2=4$ line has only the pair $(2,2)$: the gaps $(1,3)$ and $(3,1)$ have probability zero because $3$ is not an allowed gap. Thus $\mathbb{P}(S_2=4)=\tfrac19$, not an additional contribution from those pairs.

For three gaps, enumerate the possible triples by their total. At total $3$, only $(1,1,1)$ occurs, giving $\tfrac18$. At total $4$, the permutations of $(1,1,2)$ give $3\cdot\tfrac14\cdot\tfrac13=\tfrac14$. At total $5$, the permutations of $(1,2,2)$ give $3\cdot\tfrac12\cdot\tfrac19=\tfrac16$. At total $6$, the triples are $(2,2,2)$ and the three permutations of $(1,1,4)$, so the mass is $\tfrac1{27}+3\cdot\tfrac14\cdot\tfrac16=\tfrac{35}{216}$.

At total $7$, the permutations of $(1,2,4)$ give $6\cdot\tfrac12\cdot\tfrac13\cdot\tfrac16=\tfrac16$. At total $8$, the permutations of $(2,2,4)$ give $3\cdot\tfrac19\cdot\tfrac16=\tfrac1{18}$. At total $9$, the permutations of $(1,4,4)$ give $3\cdot\tfrac12\cdot\tfrac1{36}=\tfrac1{24}$. At total $10$, the permutations of $(2,4,4)$ give $3\cdot\tfrac13\cdot\tfrac1{36}=\tfrac1{36}$. At total $12$, only $(4,4,4)$ occurs, giving $\tfrac1{216}$. All other totals have probability zero.

Check: the $S_2$ masses sum to $\tfrac9{36}+\tfrac{12}{36}+\tfrac4{36}+\tfrac6{36}+\tfrac4{36}+\tfrac1{36}=1$. The $S_3$ masses, in denominator $216$, sum to $27+54+36+35+36+12+9+6+1=216$. The supports also agree with adding three allowed gaps: the smallest total is $3$, and the largest is $12$.

Worked Example: Three Epochs from Uniform Interarrivals

Let each gap have the uniform density $f(x)=1$ for $0<x<1$, and zero otherwise. Find the densities of the first three epochs. Values at the finitely many boundary points do not affect a density.

The first epoch has density $1$ on $(0,1)$. For $S_2$, the integral formula is $\int_0^t 1\,dx$ when $0<t<1$, because both gaps must lie in $(0,1)$. This gives $f_{S_2}(t)=t$. For $1\le t<2$, the first gap $x$ must satisfy $t-1<x<1$, so the allowed interval has length $2-t$. Thus $f_{S_2}(t)=2-t$ there, and the density is zero outside $(0,2)$.

For $S_3$, integrate the $S_2$ density against the last gap: $$ f_{S_3}(t)=\int_{\max(0,t-1)}^{\min(1,t)} f_{S_2}(t-x)\,dx. $$ For $0<t<1$, the limits are $0,t$, and $t-x<1$, so $$ f_{S_3}(t)=\int_0^t(t-x)\,dx=\tfrac{t^2}{2}. $$ For $1\le t<2$, split at $x=t-1$. On $0<x<t-1$, $1\le t-x<2$, so $f_{S_2}(t-x)=2-t+x$. On $t-1\le x<1$, $0<t-x\le1$, so $f_{S_2}(t-x)=t-x$. Therefore $$ f_{S_3}(t)=\int_0^{t-1}(2-t+x)\,dx+\int_{t-1}^1(t-x)\,dx =\frac{t^2-3(t-1)^2}{2}. $$ For $2\le t<3$, the integration limits are $t-2,1$; throughout this interval $1\le t-x<2$. Hence $$ f_{S_3}(t)=\int_{t-2}^1(2-t+x)\,dx=\frac{(3-t)^2}{2}. $$ It is zero outside $(0,3)$.

Check: $f_{S_2}$ integrates to $\int_0^1t\,dt+\int_1^2(2-t)\,dt=\tfrac12+\tfrac12=1$. For $S_3$, the three interval integrals are $\tfrac16,\tfrac23,\tfrac16$, respectively, and sum to $1$. The density is nonnegative on each stated interval, as also follows from its integral representation.

Worked Example: Changing the Time Unit

Suppose instead that each gap is uniform on $(0,2)$, with density $f(x)=\tfrac12$ there. This example shows explicitly how doubling the gap scale changes each epoch distribution. If $U_n=X_n/2$, then $U_n$ is uniform on $(0,1)$, and $S_n=2(U_1+\cdots+U_n)$. A scaled variable $2Y$ has density $\tfrac12 f_Y(t/2)$, because $\mathbb{P}(2Y\le t)=\mathbb{P}(Y\le t/2)$.

Consequently, $S_1$ has density $\tfrac12$ on $(0,2)$. For $S_2$, scaling the preceding triangular density gives $$ f_{S_2}(t)= \begin{cases} t/4,&0<t<2,\\ (4-t)/4,&2\le t<4,\\ 0,&\text{otherwise}. \end{cases} $$ For $S_3$, scaling each of the three uniform-$(0,1)$ intervals gives $$ f_{S_3}(t)= \begin{cases} t^2/16,&0<t<2,\\ \bigl(t^2-3(t-2)^2\bigr)/16,&2\le t<4,\\ (6-t)^2/16,&4\le t<6,\\ 0,&\text{otherwise}. \end{cases} $$ The middle expression is nonnegative on $[2,4]$: writing $u=t-2$, its numerator is $4+4u-2u^2$, which is at least $2$ for $0\le u\le2$.

Check: the $S_2$ density integrates to $\int_0^2t/4\,dt+\int_2^4(4-t)/4\,dt=\tfrac12+\tfrac12=1$. For $S_3$, substituting $t=2u$ in each integral shows that its total integral equals the total integral of the uniform-$(0,1)$ $S_3$ density, already computed as $1$. Its support $(0,6)$ is also exactly the range allowed by three gaps each in $(0,2)$.

Common Errors and a Practical Check

A frequent mistake is to treat an epoch as though it were a fresh interarrival time. In the first discrete example, $S_2=2$ requires both gaps to equal $1$, so its probability is $\tfrac12\cdot\tfrac12=\tfrac14$. The incorrect calculation $\mathbb{P}(S_2=2)=\mathbb{P}(X_1=1)=\tfrac12$ ignores the second gap. The correction is to list all positive gap combinations that produce the target total and multiply their probabilities using independence.

Another error is to omit permutations when distinct gaps can occur in different orders. For example, the total $3$ in the first discrete example can arise from $(1,2)$ or $(2,1)$, so its probability is $2\cdot\tfrac12\cdot\tfrac13=\tfrac13$. If the gaps are equal, there is only one ordered combination: $(1,1)$ contributes $\tfrac14$ to the total $2$, not twice that amount.

For continuous interarrivals, integrating over all real values without respecting positivity or the support of the density can produce incorrect bounds. In the uniform example, three gaps each lie in $(0,1)$, so $S_3$ must lie in $(0,3)$. Within that support, the possible integration limits change when $t$ crosses $1$ and $2$; those changes are why the density is piecewise defined.

A reliable calculation therefore checks three things: the sums use independent gaps, the allowed combinations or integration limits respect the gap support, and the resulting masses or density integrate to one. These checks test both the arithmetic and whether the proposed distribution accounts for every possible set of gaps.

Check Your Understanding

Use the partial-sum definition and verify each distribution by checking its support and total probability or integral.

If positive integer-valued iid gaps have masses $a_1=\tfrac12$ and $a_2=\tfrac12$, what are the possible values and probabilities of $S_2$?
For the three-point discrete law in the first example, explain why the two ordered pairs $(1,2)$ and $(2,1)$ both contribute to $\mathbb{P}(S_2=3)$.
If the interarrival density is uniform on $(0,1)$, what are the support and density of $S_2$?
Why is $S_3$ not independent of $S_1$, even though the interarrival times are independent?
For uniform-$(0,2)$ gaps, use scaling to state the support of $S_3$ and verify that its largest possible value is consistent with three gaps.

Interarrival Times and Renewal Epochs

What You'll Learn