Renewal Epochs as Partial Sums
A renewal process records successive event times. Its long-run behavior begins with a basic question: how quickly do the event times themselves grow? If each gap between events has the same finite average length, then the \(n\)th event time grows approximately like \(n\) times that average. The precise statement is an almost-sure limit for the average of the first \(n\) gaps.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(X_1,X_2,\ldots\) be iid nonnegative random variables, called the interarrival times, with finite mean \(\mu=\mathbb{E}[X_1]<\infty\). Define the renewal epochs by \(S_0=0\) and \(S_n=X_1+\cdots+X_n\) for \(n\ge1\). Thus \((S_n)_{n\ge0}\) is a discrete-time process with state space \([0,\infty)\). Its natural filtration is \(\mathcal{F}_n=\sigma(X_1,\ldots,X_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). No conditioning on this filtration is needed for the limit below.
The phrase almost surely means that the set of sample paths on which the convergence holds has probability one. This is stronger than convergence in probability and different from convergence in distribution. The theorem identifies the long-run average gap along almost every realization; it does not say that each individual gap approaches \(\mu\).
Why the Strong Law Applies
The result used here is the iid strong law of large numbers, also called Kolmogorov’s strong law: if \(Y_1,Y_2,\ldots\) are iid real-valued random variables with \(\mathbb{E}|Y_1|<\infty\), then \(n^{-1}\sum_{k=1}^nY_k\to\mathbb{E}[Y_1]\) almost surely. This is a standard result of probability theory; its proof is not given here. The renewal-epoch conclusion follows by checking its hypotheses and identifying the partial sum.
Proof. First consider \(\mu=0\). Since \(X_1\ge0\) and \(\mathbb{E}[X_1]=0\), for every integer \(m\ge1\), \(\mathbb{P}(X_1\ge1/m)\le m\mathbb{E}[X_1]=0\). The event \(\{X_1>0\}\) is the union of the events \(\{X_1\ge1/m\}\), so \(\mathbb{P}(X_1=0)=1\). Each \(X_k\) has the same distribution, and a countable intersection of probability-one events has probability one. Thus all the interarrival times are zero simultaneously almost surely, and \(S_n/n=0=\mu\) for every \(n\ge1\) on that event.
Now suppose \(\mu>0\). Nonnegativity gives \(\mathbb{E}|X_1|=\mathbb{E}[X_1]=\mu<\infty\). The variables \(X_1,X_2,\ldots\) are iid by assumption, so the iid strong law applies to their partial sums. Since \(S_n=\sum_{k=1}^nX_k\), it gives \(S_n/n\to\mathbb{E}[X_1]=\mu\) almost surely. This proves the assertion in both cases. \(\square\)
The proof requires no renewal-counting argument: it concerns the epochs, which are just partial sums. In particular, it does not yet describe how many epochs fall before a given time. The finite-mean assumption supplies the finite expectation required by the strong law, while independence and identical distribution are the assumptions that let that theorem be applied to the gaps.
Worked Applications
Worked Example: Constant Interarrival Times
Suppose every interarrival time equals \(5\) with probability one: \(X_k=5\) almost surely for every \(k\). These are iid, nonnegative random variables and \(\mu=\mathbb{E}[X_1]=5\). For every \(n\ge1\), adding the \(n\) gaps gives $$ S_n=\underbrace{5+\cdots+5}_{n\ \text{terms}}=5n, \qquad \frac{S_n}{n}=\frac{5n}{n}=5. $$
Check: The formula gives \(S_1=5\) and \(S_2=10\), and the corresponding averages are \(5/1=5\) and \(10/2=5\). The average is exactly the mean gap for every \(n\), so its limit is \(5=\mu\), as the theorem predicts.
Worked Example: Two-Point Interarrival Times
Let the interarrival times be iid with \(\mathbb{P}(X_k=1)=\tfrac34\) and \(\mathbb{P}(X_k=3)=\tfrac14\). Their mean is $$ \mu=1\cdot\tfrac34+3\cdot\tfrac14 =\tfrac34+\tfrac34 =\tfrac32. $$ Define \(I_k=\mathbf{1}_{\{X_k=3\}}\). Then \(X_k=1+2I_k\), because this expression is \(1\) when \(X_k=1\) and \(3\) when \(X_k=3\). The indicators are iid Bernoulli random variables with mean \(\mathbb{E}[I_k]=\tfrac14\). Therefore $$ \frac{S_n}{n} =\frac{1}{n}\sum_{k=1}^n(1+2I_k) =1+2\frac{1}{n}\sum_{k=1}^n I_k \longrightarrow 1+2\cdot\tfrac14 =\tfrac32 \quad\text{almost surely}. $$ This is also a direct application of the renewal-epoch theorem.
Check: Taking expectations in the finite-\(n\) identity gives \(\mathbb{E}[S_n/n]=1+2(\tfrac14)=\tfrac32\) for every \(n\). This agrees with the almost-sure limit and with the direct mean calculation. The expectation check is a consistency check; the almost-sure convergence itself follows from the strong law.
Worked Example: Exponential Interarrival Times
Suppose the interarrival times are iid exponential random variables with rate \(2\), so their density is \(f(x)=2e^{-2x}\) for \(x\ge0\). The mean is computed from the density: $$ \mathbb{E}[X_1]=\int_0^\infty x\,2e^{-2x}\,dx. $$ Integration by parts gives $$ \int_0^\infty x e^{-2x}\,dx =\left[-\frac{x}{2}e^{-2x}\right]_0^\infty +\frac12\int_0^\infty e^{-2x}\,dx =0+\frac12\cdot\frac12 =\frac14. $$ Consequently \(\mathbb{E}[X_1]=2\cdot\tfrac14=\tfrac12\). Since the gaps are iid, nonnegative, and have finite mean, the epoch theorem yields $$ \frac{S_n}{n}\longrightarrow\tfrac12 \quad\text{almost surely}. $$
Check: The mean calculation uses \(\int_0^\infty e^{-2x}\,dx=[-\tfrac12e^{-2x}]_0^\infty=\tfrac12\), so the integration-by-parts value is \(\tfrac12\cdot\tfrac12=\tfrac14\), and the density factor \(2\) gives \(\tfrac12\). The asserted limit is exactly this mean gap.
Why the Assumptions Matter
Equal marginal means do not establish the renewal-epoch limit if the interarrival times are dependent. For a concrete example, take a random variable \(Y\) with \(\mathbb{P}(Y=0)=\mathbb{P}(Y=1)=\tfrac12\), and set \(X_k=Y\) for every \(k\). Each gap has mean \(\tfrac12\), but the gaps are not independent. For every \(n\), \(S_n=nY\), so \(S_n/n=Y\). The average equals \(0\) with probability \(\tfrac12\) and \(1\) with probability \(\tfrac12\); it does not converge to \(\tfrac12\) almost surely.
Common mistake. One might calculate \(\mathbb{E}[S_n/n]=\tfrac12\) for every \(n\) in this dependent example and incorrectly conclude that \(S_n/n\to\tfrac12\) almost surely. The calculation is \(\mathbb{E}[S_n/n]=\mathbb{E}[Y]=\tfrac12\), but the actual sample-path average is \(Y\), not its expectation. A constant sequence of expectations does not imply almost-sure convergence. Independence is not a cosmetic condition: it is part of the strong law being applied.
The finite-mean condition also matters if the conclusion is understood as convergence to a finite mean. For example, let the iid gaps have the Pareto distribution with \(\mathbb{P}(X_k>x)=1/x\) for \(x\ge1\), and \(X_k\ge1\). Its mean is infinite. To see what happens to the averages, fix an integer \(K\ge1\) and define \(Y_k^{(K)}=\min(X_k,K)\). For each fixed \(K\), these variables are iid and bounded, so the iid strong law applies. Also \(X_k\ge Y_k^{(K)}\), and hence, almost surely, $$ \liminf_{n\to\infty}\frac{S_n}{n} \ge \mathbb{E}[Y_1^{(K)}]. $$ The tail-integral formula for a nonnegative random variable gives $$ \mathbb{E}[Y_1^{(K)}] =\int_0^K\mathbb{P}(X_1>t)\,dt =\int_0^1 1\,dt+\int_1^K\frac{1}{t}\,dt =1+\log K. $$ The strong-law event used here has probability one for each integer \(K\); their countable intersection still has probability one. On that intersection the lower bound holds for every integer \(K\). Since \(1+\log K\) is unbounded as \(K\to\infty\), \(\liminf S_n/n=\infty\), which means \(S_n/n\to\infty\). Thus an infinite-mean example need not have a finite long-run average epoch increment.
Interpreting the Limit
The conclusion \(S_n/n\to\mu\) says that the cumulative time of the first \(n\) renewals, divided by the number of gaps, settles to the mean interarrival time along almost every sample path. Equivalently, the deviation per gap vanishes: for almost every outcome and every \(\varepsilon>0\), there is a (possibly outcome-dependent) index after which \(\left|S_n/n-\mu\right|<\varepsilon\). It does not assert that \(S_n=n\mu\), nor that \(X_n\to\mu\). The examples above show why the average of the gaps, rather than the behavior of a single gap, is the right quantity.
Check Your Understanding
For each question, distinguish the assumptions of the strong law from the conclusion about the epoch averages.
- If \(X_k=4\) almost surely for every \(k\), what are \(\mu\), \(S_n\), and the limit of \(S_n/n\)?
- For iid gaps taking values \(2\) and \(6\) with probabilities \(\tfrac34\) and \(\tfrac14\), calculate \(\mu\) and state the almost-sure limit of \(S_n/n\).
- In the example \(X_k=Y\) for all \(k\), why does \(\mathbb{E}[S_n/n]=\tfrac12\) fail to imply convergence to \(\tfrac12\) almost surely?
- Which hypotheses allow the iid strong law to be applied to \(S_n=\sum_{k=1}^nX_k\)?
- For the Pareto example, why does proving a lower bound for every integer \(K\) imply that \(S_n/n\) tends to infinity?