7.3 Limit theorems for renewal processes

Renewal processes overview

Renewal processes model systems where events occur repeatedly over time, with the gaps between events being random but statistically identical. They provide the foundation for analyzing long-term, steady-state behavior in queueing systems, reliability theory, and many other applied settings.

Definition of renewal process

A renewal process is built from a sequence of independent and identically distributed (i.i.d.) non-negative random variables $X_1, X_2, \ldots$ representing the interarrival times between successive events. The $n$-th event occurs at time

$T_n = X_1 + X_2 + \cdots + X_n$

The counting process $N(t) = \sup\{n \geq 0 : T_n \leq t\}$ gives the number of renewals that have occurred by time $t$. The entire process starts at time zero, and the randomness comes solely from the i.i.d. interarrival times.

Interarrival times in renewal processes

• The interarrival times share a common distribution function $F(x) = P(X_i \leq x)$, which can be discrete or continuous.
• The mean interarrival time $\mu = E[X_i]$ plays a central role in every limit theorem that follows.
• Common modeling choices for $F$ include the exponential distribution (which makes $N(t)$ a Poisson process), as well as gamma and Weibull distributions.

Renewal function and renewal equation

The renewal function $m(t) = E[N(t)]$ is the expected number of renewals by time $t$. It satisfies the renewal equation:

$m(t) = F(t) + \int_0^t m(t - x)\, dF(x)$

This integral equation says: either the first interarrival time lands before $t$ (the $F(t)$ term), or it lands at some time $x \leq t$ and the process "restarts," contributing $m(t-x)$ additional expected renewals. The renewal equation is the starting point for deriving all the limit theorems below.

Strong law of large numbers (SLLN)

The SLLN for renewal processes pins down the long-run rate at which renewals occur. It is the most basic asymptotic result and underpins everything else in this unit.

Statement of SLLN for renewal processes

Let $N(t)$ be a renewal process whose interarrival times have finite mean $\mu = E[X_i]$. Then, with probability one:

$\lim_{t \to \infty} \frac{N(t)}{t} = \frac{1}{\mu}$

In words: the long-run average number of renewals per unit time converges almost surely to $1/\mu$.

Proof sketch of SLLN

1. By definition, $T_{N(t)} \leq t < T_{N(t)+1}$. Divide through by $N(t)$: $\frac{T_{N(t)}}{N(t)} \leq \frac{t}{N(t)} < \frac{T_{N(t)+1}}{N(t)}$
2. Since $N(t) \to \infty$ as $t \to \infty$, the classical SLLN for i.i.d. sums gives $T_n / n \to \mu$ almost surely. Both the left and right sides of the inequality therefore converge to $\mu$.
3. By the squeeze (sandwich) argument, $t / N(t) \to \mu$ a.s., so $N(t)/t \to 1/\mu$ a.s.

The key ingredients are the i.i.d. assumption, finiteness of $\mu$, and the squeeze lemma.

Applications of SLLN in renewal theory

• Queueing systems: If customers arrive according to a renewal process with mean interarrival time $\mu = 5$ minutes, the long-run arrival rate is $1/5 = 0.2$ customers per minute.
• Reliability: If a component's lifetime distribution has mean $\mu = 1000$ hours, the long-run failure rate is $1/1000$ failures per hour.

The SLLN converts distributional information (the mean) into a deterministic long-run rate, which is the basis for capacity planning and performance estimation.

Elementary renewal theorem

While the SLLN is a statement about the random variable $N(t)/t$, the elementary renewal theorem (ERT) makes the corresponding statement about its expectation.

Statement of elementary renewal theorem

Let $m(t) = E[N(t)]$ be the renewal function for interarrival times with finite mean $\mu$. Then:

$\lim_{t \to \infty} \frac{m(t)}{t} = \frac{1}{\mu}$

This looks similar to the SLLN, but the two results are logically distinct. The SLLN says the sample path ratio converges a.s.; the ERT says the ratio of expectations converges. Almost sure convergence does not automatically imply convergence of expectations (you need uniform integrability or a separate argument), so the ERT requires its own proof.

Key assumptions and conditions

• Interarrival times are i.i.d. and non-negative.
• The mean $\mu = E[X_i]$ is finite (and positive, to avoid trivialities).

No moment conditions beyond the first moment are needed.

Proof outline of elementary renewal theorem

1. Use Wald's equation: $E[T_{N(t)+1}] = \mu \cdot E[N(t) + 1] = \mu\,(m(t) + 1)$.
2. Since $T_{N(t)} \leq t < T_{N(t)+1}$, taking expectations gives $\mu\, m(t) \leq t + \mu$ (from the right inequality, after careful handling) and a matching lower bound.
3. Divide by $t$ and send $t \to \infty$. Both bounds squeeze $m(t)/t$ to $1/\mu$.

A fully rigorous proof handles the subtlety that $N(t)+1$ is a stopping time for the i.i.d. sequence, making Wald's equation applicable.

Interpretation and significance

The ERT tells you that $m(t) \approx t/\mu$ for large $t$: the expected number of renewals grows linearly in time. For example, if lightbulbs have a mean lifetime of 800 hours, you'd expect roughly $t/800$ replacements over $t$ hours.

This linear approximation is the starting point for more refined results (Blackwell, key renewal theorem) and for practical cost/performance calculations.

Blackwell's renewal theorem

Blackwell's theorem sharpens the ERT by describing the local behavior of the renewal function rather than just its global growth rate.

Formulation of Blackwell's theorem

For a non-lattice renewal process with finite mean $\mu$, and any fixed $h > 0$:

$\lim_{t \to \infty} [m(t+h) - m(t)] = \frac{h}{\mu}$

Comparison with elementary renewal theorem

• The ERT says $m(t)/t \to 1/\mu$, a statement about cumulative growth.
• Blackwell's theorem says the increment $m(t+h) - m(t) \to h/\mu$, a statement about how many renewals fall in a window of fixed width $h$ far into the future.

Blackwell's result is strictly stronger: you can recover the ERT from Blackwell's theorem (sum up increments), but not the other way around.

Proof sketch of Blackwell's theorem

1. Write $m(t+h) - m(t) = \int_0^{t+h} \bar{F}(t+h-x)\,dm(x) - \int_0^t \bar{F}(t-x)\,dm(x)$ (or use the renewal equation directly on the increment).

2. Apply the key renewal theorem (below) with $f(x) = \mathbf{1}_{[0,h]}(x)$, which is directly Riemann integrable.

3. The key renewal theorem gives the limit as $(1/\mu)\int_0^\infty \mathbf{1}_{[0,h]}(x)\,dx = h/\mu$.

So Blackwell's theorem is really a corollary of the key renewal theorem.

Implications and applications

• In reliability, Blackwell's theorem tells you that far into the future, the expected number of failures in any interval of length $h$ is approximately $h/\mu$, regardless of when you start observing.
• It justifies treating the renewal process as approximately "uniform" over short windows once enough time has passed.

Key renewal theorem

The key renewal theorem (KRT) is the most general of the classical renewal limit theorems. Both the ERT and Blackwell's theorem are special cases.

Statement of key renewal theorem

Let $m(t)$ be the renewal function for a non-lattice renewal process with finite mean $\mu$, and let $g(t)$ be a directly Riemann integrable (dRi) function. Then:

$\lim_{t \to \infty} \int_0^t g(t - x)\, dm(x) = \frac{1}{\mu} \int_0^\infty g(x)\, dx$

The integral on the left is a convolution of $g$ with the renewal measure. The theorem says this convolution "flattens out" to a constant determined by the total integral of $g$ and the renewal rate $1/\mu$.

Relationship to other renewal theorems

• ERT: Not a direct special case of the KRT (the function $g = 1$ is not dRi), but the ERT is used in proving the KRT and the two are closely linked.
• Blackwell's theorem: Set $g(x) = \mathbf{1}_{[0,h]}(x)$. This function is dRi, and $\int_0^\infty g(x)\,dx = h$, recovering $m(t+h) - m(t) \to h/\mu$.

The KRT provides a single unified tool for computing limits of renewal-type equations.

Directly Riemann integrable functions

A function $g$ is directly Riemann integrable if it is Riemann integrable on every finite interval and the upper and lower Riemann sums over a partition of $[0,\infty)$ with mesh $\delta$ converge to the same finite limit as $\delta \to 0$. In practice, a sufficient condition is:

• $g$ is bounded, non-negative, and $\int_0^\infty g(x)\,dx < \infty$.
• $g$ has at most countably many discontinuities.

Most functions you encounter in applications (indicator functions of bounded intervals, exponentially decaying functions, etc.) satisfy this condition.

Applications in stochastic processes

The KRT is the workhorse behind many asymptotic results:

• Queueing theory: Deriving the limiting distribution of waiting times and queue lengths in GI/G/1 queues.
• Reliability: Computing the long-run average cost of age-replacement or block-replacement policies.
• Insurance mathematics: Analyzing the asymptotic behavior of ruin probabilities via the Cramér-Lundberg model, where claim arrivals form a renewal process.

Whenever you need the limit of a quantity that satisfies a renewal-type integral equation, the KRT is typically the tool you reach for.

Renewal reward processes

Renewal reward processes attach a reward (or cost) to each renewal cycle, extending the basic renewal framework to handle accumulated quantities over time.

Definition and setup

A renewal reward process is defined by i.i.d. pairs $(X_n, R_n)$, where:

• $X_n$ is the length of the $n$-th cycle (interarrival time).
• $R_n$ is the reward earned during the $n$-th cycle.

The pairs $(X_n, R_n)$ are i.i.d. across cycles, but $X_n$ and $R_n$ within the same cycle may be dependent. The total reward accumulated by time $t$ is:

$R(t) = \sum_{n=1}^{N(t)} R_n$

(Some formulations also include a partial reward from the cycle in progress; the long-run result is the same.)

Renewal reward theorem

If $\mu = E[X_n] < \infty$ and $E[|R_n|] < \infty$, then with probability one:

$\lim_{t \to \infty} \frac{R(t)}{t} = \frac{E[R_n]}{E[X_n]} = \frac{\nu}{\mu}$

The corresponding result for expectations also holds: $E[R(t)]/t \to \nu/\mu$.

The intuition is clean: over a long time horizon, you complete roughly $t/\mu$ cycles, each earning on average $\nu$, so the total reward is approximately $(\nu/\mu) \cdot t$.

Proof sketch of renewal reward theorem

1. Write $R(t) = \sum_{n=1}^{N(t)} R_n$. By the SLLN for i.i.d. sums, $\sum_{n=1}^{k} R_n / k \to \nu$ a.s.
2. Therefore $R(t)/N(t) \to \nu$ a.s. as $t \to \infty$ (since $N(t) \to \infty$).
3. Multiply and divide: $R(t)/t = (R(t)/N(t)) \cdot (N(t)/t)$.
4. By the SLLN for renewal processes, $N(t)/t \to 1/\mu$ a.s.
5. The product of the two almost sure limits gives $\nu/\mu$.

Examples and applications

• Machine replacement: A machine earns revenue $R_n$ during its $n$-th lifetime $X_n$. If $E[R_n] = \$500$ and $E[X_n] = 10$ days, the long-run earning rate is $\$50$/day.
• Inventory systems: Each order cycle has a random length $X_n$ and a random holding cost $R_n$. The renewal reward theorem gives the long-run average cost per unit time.
• On-off systems: A server alternates between "on" (duration $X_n^{\text{on}}$) and "off" (duration $X_n^{\text{off}}$). Setting $R_n = X_n^{\text{on}}$ and $X_n = X_n^{\text{on}} + X_n^{\text{off}}$, the long-run fraction of time the server is on equals $E[X^{\text{on}}] / E[X^{\text{on}} + X^{\text{off}}]$.

Asymptotic behavior of renewal processes

Beyond the core limit theorems, several finer results describe how renewal processes settle into their long-run regime.

Limiting distribution of age and residual life

At time $t$, define:

• Age (backward recurrence time): $A(t) = t - T_{N(t)}$, the time since the last renewal.
• Residual life (forward recurrence time): $Y(t) = T_{N(t)+1} - t$, the time until the next renewal.

For a non-lattice renewal process with finite mean $\mu$, both $A(t)$ and $Y(t)$ converge in distribution as $t \to \infty$ to the equilibrium (or spread) distribution:

$F_e(x) = \frac{1}{\mu} \int_0^x [1 - F(u)]\, du$

This is a size-biased version of the original interarrival distribution. It's always more spread out than $F$ itself, which reflects the inspection paradox: if you arrive at a "random" time, you're more likely to land in a long cycle than a short one.

Convergence rates and conditions

• The rate at which $m(t)/t$ approaches $1/\mu$ depends on the tail of $F$. If $E[X_i^2] < \infty$, one can show $m(t) = t/\mu + (E[X_i^2]/(2\mu^2)) - 1/2 + o(1)$, giving a precise correction term.
• Exponential convergence of the age/residual life distributions to $F_e$ can be established when the interarrival distribution has a density and satisfies certain spread-out conditions.
• Stronger moment conditions (e.g., existence of the moment generating function near zero) yield sharper error bounds.

Connections to other limit theorems

• Central limit theorem for renewal processes: If $\sigma^2 = \text{Var}(X_i) < \infty$, then $\frac{N(t) - t/\mu}{\sigma t^{1/2}/\mu^{3/2}} \xrightarrow{d} \mathcal{N}(0,1)$ as $t \to \infty$. This quantifies the fluctuations of $N(t)$ around its mean.
• The CLT for renewal reward processes similarly gives the asymptotic normality of $R(t)$.
• Together, the SLLN, ERT, Blackwell, KRT, and CLT form a hierarchy: each gives progressively more detailed information about the long-run behavior of the process.

Practical implications and insights

• Queueing: The limiting results justify steady-state formulas (e.g., Little's law, Pollaczek-Khinchine formula) that assume the system has "settled down."
• Reliability: The equilibrium distribution $F_e$ is used to model the residual life of a component found in operation at a random inspection time.
• Risk assessment: The CLT provides confidence intervals for quantities like total claims or total downtime over a planning horizon, not just point estimates from the SLLN.

Understanding which theorem to apply depends on what you need: a long-run rate (SLLN/ERT), local renewal counts (Blackwell), a general renewal-type limit (KRT), or distributional information about fluctuations (CLT).