Renewal Epochs as Sums
A renewal epoch is the time at which a specified renewal occurs. Its distribution is determined by adding the interarrival times that came before it. Independence makes that addition tractable: the law of a sum can be built from the laws of its terms, one interarrival at a time. For discrete interarrivals this gives a probability table; for continuous interarrivals it gives an integral for the density.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_k)_{k\ge1}\) be independent, identically distributed, nonnegative interarrival times with common distribution function \(F(t)=\mathbb{P}(X_1\le t)\). Define the renewal epochs by \(S_0=0\) and \(S_n=\sum_{k=1}^n X_k\) for \(n\ge1\). The distribution of \(S_n\) is the distribution of the sum of \(n\) independent copies of \(X_1\). This tutorial concerns that distribution, not the expected number of renewals up to a time.
A Recursion for the Distribution
Write \(F_n(t)=\mathbb{P}(S_n\le t)\), with \(F_0(t)=\mathbf{1}_{\{t\ge0\}}\), the distribution function of \(S_0=0\). The last interarrival \(X_n\) is independent of \(S_{n-1}\). Conditioning on its value gives a recursion valid whether the interarrival law is discrete, continuous, or a mixture of the two.
Proof. Since \(S_n=S_{n-1}+X_n\), the event \(S_n\le t\), conditional on \(X_n=x\), is the event \(S_{n-1}\le t-x\). Independence means that the conditional distribution of \(S_{n-1}\) given \(X_n=x\) is its unconditional distribution. Therefore its conditional probability is \(F_{n-1}(t-x)\). Averaging this probability over the distribution of \(X_n\) gives \(\mathbb{P}(S_n\le t)=\int_{[0,\infty)}F_{n-1}(t-x)\,dF(x)\). This argument also applies when \(S_{n-1}\) or \(X_n\) has atoms, because the integral is with respect to the full probability distribution, including its atoms. \(\square\)
For a countable discrete law, let \(p(x)=\mathbb{P}(X_1=x)\), with \(p(x)=0\) off its support. Put \(p_n(s)=\mathbb{P}(S_n=s)\). Independence and a partition according to the value of the last interarrival give the mass recursion below. Each term corresponds to one possible last value \(x\): the preceding epochs must sum to \(s-x\).
For a continuous interarrival law with density \(f\), the epoch \(S_n\) has a density \(f_n\), and the corresponding recursion is an integral. The formula requires that the interarrival law have a density; it is not a density formula for a purely discrete law.
Proof. Suppose \(S_{n-1}\) has density \(f_{n-1}\). Independence gives the joint density \(f_{n-1}(y)f(x)\) for \((S_{n-1},X_n)=(y,x)\). For any Borel set \(C\subseteq[0,\infty)\), integrate that joint density over the pairs with \(y+x\in C\). Changing variables from \(y\) to \(s=y+x\), so \(y=s-x\), gives $$ \mathbb{P}(S_n\in C)=\int_C\left(\int_0^s f_{n-1}(s-x)f(x)\,dx\right)ds. $$ The inner integral is nonnegative and finite for almost every \(s\), and this identity for every Borel set \(C\) shows that it is a density of \(S_n\). Starting with \(S_1=X_1\), which has density \(f\), induction proves the assertion for every \(n\ge2\). Nonnegativity of the interarrivals accounts for the integration limits: \(0\le x\le s\). \(\square\)
Discrete Interarrivals: Build a Probability Table
In a discrete calculation, list the possible values of \(S_n\) and add the probabilities of all combinations that produce each value. Equivalently, apply the mass recursion repeatedly. When several combinations lead to the same sum, their probabilities must be added. The table should include all possible sums, including those with probability zero if they help make the pattern clear.
Worked Example: Three Interarrivals with Two Possible Values
Suppose the interarrivals are independent and each equals \(1\) or \(3\), each with probability \(\tfrac12\). Find the distribution of \(S_3\).
The one-interarrival table has masses \(p(1)=\tfrac12\) and \(p(3)=\tfrac12\); their sum is \(\tfrac12+\tfrac12=1\). Each ordered triple has probability \((\tfrac12)(\tfrac12)(\tfrac12)=\tfrac18\), by independence. The possible sums depend on the number of interarrivals equal to \(3\): zero such values gives \(3\), one gives \(5\), two gives \(7\), and three gives \(9\). There are respectively \(1,3,3,1\) ordered triples in these four cases.
| Value of \(S_3\) | Number of triples | Probability |
|---|---|---|
| 3 | 1 | \(\tfrac18\) |
| 5 | 3 | \(\tfrac38\) |
| 7 | 3 | \(\tfrac38\) |
| 9 | 1 | \(\tfrac18\) |
Check. The probabilities sum to \(\tfrac18+\tfrac38+\tfrac38+\tfrac18=1\). Also, the mean interarrival is \(1(\tfrac12)+3(\tfrac12)=2\), so the mean of three independent interarrivals is \(3(2)=6\). Directly from the table, the mean is \(3(\tfrac18)+5(\tfrac38)+7(\tfrac38)+9(\tfrac18)=\tfrac{48}{8}=6\).
Worked Example: A Two-Step Probability Table
Now suppose each interarrival equals \(1\) with probability \(\tfrac23\) and \(2\) with probability \(\tfrac13\), independently. Find the law of \(S_2\) using the convolution sum.
The single-interarrival probabilities add to \(\tfrac23+\tfrac13=1\). For \(S_2=2\), both interarrivals must equal \(1\), so the probability is \((\tfrac23)(\tfrac23)=\tfrac49\). For \(S_2=3\), the ordered pairs are \((1,2)\) and \((2,1)\). Each has probability \((\tfrac23)(\tfrac13)=\tfrac29\), so the total is \(\tfrac29+\tfrac29=\tfrac49\). For \(S_2=4\), both must equal \(2\), giving probability \((\tfrac13)(\tfrac13)=\tfrac19\).
| Value of \(S_2\) | Contributing pairs | Probability |
|---|---|---|
| 2 | (1,1) | \(\tfrac49\) |
| 3 | (1,2), (2,1) | \(\tfrac49\) |
| 4 | (2,2) | \(\tfrac19\) |
Check. The masses sum to \(\tfrac49+\tfrac49+\tfrac19=1\). The mean of one interarrival is \(1(\tfrac23)+2(\tfrac13)=\tfrac43\), so \(\mathbb{E}[S_2]=2(\tfrac43)=\tfrac83\). From the table, \(\mathbb{E}[S_2]=2(\tfrac49)+3(\tfrac49)+4(\tfrac19)=\tfrac{8+12+4}{9}=\tfrac83\).
Continuous Interarrivals: Integrate Along the Sum
For continuous variables, the mass assigned to one exact value is usually zero, so a probability table is not the right representation. Instead, the convolution integral collects contributions from every way to write \(s\) as \(x+(s-x)\). The integration interval is determined by the supports of the two densities. Nonnegative interarrivals imply \(x\ge0\) and \(s-x\ge0\), which explains the limits \(0\) to \(s\) in the density formula.
Worked Example: Two Uniform Interarrivals
Let the independent interarrivals each have the uniform density \(f(x)=1\) for \(1\le x\le2\), and \(f(x)=0\) otherwise. Find the density and distribution function of \(S_2\).
In the convolution integral, both \(x\) and \(s-x\) must lie in \([1,2]\). Thus \(x\) must lie in the intersection \([1,2]\cap[s-2,s-1]\). When \(2\le s\le3\), this intersection is \([1,s-1]\), of length \((s-1)-1=s-2\). When \(3\le s\le4\), it is \([s-2,2]\), of length \(2-(s-2)=4-s\). Outside \([2,4]\), the intersection has length zero. Since both density values on the intersection equal \(1\), its length is the convolution integral.
Integrating this density gives the distribution function. For \(2\le s\le3\), integrate \(u-2\) from \(2\) to \(s\), obtaining \(\tfrac{(s-2)^2}{2}\). For \(3\le s\le4\), the probability accumulated by \(3\) is \(\tfrac{(3-2)^2}{2}=\tfrac12\); adding the integral of \(4-u\) from \(3\) to \(s\) gives \(\tfrac12+\tfrac12-\tfrac{(4-s)^2}{2}=1-\tfrac{(4-s)^2}{2}\). Therefore
Check. The total density integral is \(\int_2^3(s-2)\,ds+\int_3^4(4-s)\,ds=\tfrac12+\tfrac12=1\). At \(s=3\), the density formulas agree: \(3-2=4-3=1\), and the distribution function gives \(\tfrac12\) from either piece. At the support endpoints, \(F_2(2)=0\) and \(F_2(4)=1\), as required. The sum cannot be less than \(2\) or greater than \(4\), matching the support found from adding two values in \([1,2]\).
Choosing and Checking the Right Formula
The probability-table recursion and the density recursion are two versions of the same addition principle, but their assumptions differ. Use the mass formula when the interarrival law is discrete and its possible values can be listed or summed over. Use the density formula when the interarrival law has a density. If the law has both atoms and a density, the distribution-function recursion remains valid as stated; a calculation must account for both the sum over atoms and the integral over the continuous part.
Two checks are especially useful. First, the probabilities in a discrete table must sum to \(1\), and a density must integrate to \(1\). Second, the possible values of \(S_n\) must be consistent with sums of values in the support of \(X_1\). For instance, if every interarrival is between \(a\) and \(b\), with \(0\le a\le b\), then every \(S_n\) lies between \(na\) and \(nb\). A formula assigning positive probability or density outside that range has an incorrect support.
Common mistake. For the second discrete example, a tempting but incorrect calculation is to say that \(S_2=3\) has probability \(\tfrac23+\tfrac13=1\), by adding the two one-step probabilities. This ignores that \(S_2=3\) requires two interarrivals, in one of the ordered pairs \((1,2)\) or \((2,1)\). Independence gives \((\tfrac23)(\tfrac13)+(\tfrac13)(\tfrac23)=\tfrac29+\tfrac29=\tfrac49\). The convolution adds probabilities of the relevant pairs, not probabilities of single interarrival values.
Check Your Understanding
Use the support and convolution formulas to work through these questions, and check that each resulting law has total probability \(1\).
- If each interarrival is \(1\) or \(2\), each with probability \(\tfrac12\), what are the possible values and probabilities of \(S_2\)?
- For discrete interarrivals with mass function \(p\), explain why \(p_2(s)=\sum_x p(x)p(s-x)\) counts all ordered pairs with sum \(s\).
- If each interarrival is uniform on \([0,1]\), what is the support of \(S_2\), and which values of \(x\) can contribute to its density at a fixed \(s\)?
- Why does a continuous density formula require a different representation from a discrete probability table?
- In the two-uniform-interarrival example, evaluate \(F_2(\tfrac52)\) using the displayed distribution function.