7.2 Renewal functions and equations

Definition of renewal function

The renewal function $m(t)$ gives the expected number of renewals (events) that occur in the time interval $[0, t]$. It's the central quantity in renewal theory because once you know $m(t)$, you can derive most other properties of the process.

The setup: you have a renewal process where inter-arrival times $X_1, X_2, \ldots$ are i.i.d. with common distribution $F(t) = P(X_i \leq t)$. The counting process $N(t)$ tracks how many renewals have occurred by time $t$.

Renewal function formula

The renewal function is defined as:

$m(t) = E[N(t)]$

You can express this as a sum of convolutions:

$m(t) = \sum_{n=1}^{\infty} F^{(n)}(t)$

where $F^{(n)}(t)$ is the $n$-fold convolution of $F$. The reasoning: $F^{(n)}(t) = P(S_n \leq t)$, where $S_n = X_1 + \cdots + X_n$ is the time of the $n$th renewal. Since $N(t) \geq n$ if and only if $S_n \leq t$, you get $E[N(t)] = \sum_{n=1}^{\infty} P(S_n \leq t)$.

The renewal function also satisfies the renewal equation:

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

This equation relates $m(t)$ back to the inter-arrival distribution and is the main tool for computing $m(t)$.

Properties of renewal function

• Non-negative and non-decreasing: $m(t) \geq 0$ and $m(t_1) \leq m(t_2)$ for $t_1 \leq t_2$
• Right-continuous: $\lim_{t \to t_0^+} m(t) = m(t_0)$ for all $t_0 \geq 0$
• Initial value: $m(0) = 0$, since no renewals have occurred at time zero
• Finiteness: $m(t) < \infty$ for all $t < \infty$ (this requires proof and uses the fact that inter-arrival times are positive with probability 1)
• Asymptotic behavior: $\lim_{t \to \infty} \frac{m(t)}{t} = \frac{1}{\mu}$, where $\mu = E[X_i]$ is the mean inter-arrival time. This is the elementary renewal theorem.

Derivation of renewal equation

The renewal equation is derived by conditioning on the time of the first renewal $X_1$. This is a standard technique in renewal theory: split the problem into what happens before and after the first event.

1. Let $X_1$ be the first inter-arrival time, with distribution $F$.

2. If $X_1 = x \leq t$, then one renewal has occurred at time $x$, and the process restarts. The expected number of additional renewals in the remaining time $[x, t]$ is $m(t - x)$, by the i.i.d. assumption.

3. If $X_1 > t$, no renewal occurs in $[0, t]$, contributing 0.

4. Taking expectations over $X_1$:

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

The term $F(t) = P(X_1 \leq t)$ accounts for the first renewal, and the integral captures all subsequent renewals.

Integral equation form

The renewal equation:

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

is a Volterra integral equation of the second kind. The unknown function $m(t)$ appears both on the left side and inside the integral on the right. The "driving term" is $F(t)$, and the "kernel" is $dF(x)$.

More generally, any equation of the form $Z(t) = z(t) + \int_0^t Z(t-x) \, dF(x)$ is called a renewal-type equation, and many problems in applied probability reduce to this form.

Renewal density definition

When $F$ has a density $f(t)$, you can differentiate the renewal equation to get an equation for the renewal density:

$u(t) = \frac{d}{dt} m(t)$

The renewal density $u(t)$ represents the instantaneous rate of renewals at time $t$. Formally, $u(t) \, dt \approx P(\text{a renewal occurs in } (t, t+dt])$.

Differentiating the renewal equation gives:

$u(t) = f(t) + \int_0^t u(t-x) f(x) \, dx$

This is the density form of the renewal equation, and it's often more convenient to work with than the distribution form.

Relationship to inter-arrival times

The renewal equation makes explicit how the entire renewal process is governed by the inter-arrival distribution $F(t)$. Different choices of $F$ produce very different renewal functions. For example:

• Exponential inter-arrival times (Poisson process): $m(t) = \lambda t$, perfectly linear
• Deterministic inter-arrival times ($X_i = d$ always): $m(t) = \lfloor t/d \rfloor$, a staircase function
• Heavy-tailed inter-arrival times: $m(t)$ grows more slowly for moderate $t$, though the asymptotic rate $1/\mu$ still holds

Solutions to renewal equation

Finding $m(t)$ in closed form is only possible for a few inter-arrival distributions. In most cases, you'll use transforms or numerical methods.

Laplace transform approach

This is the most powerful analytical technique. Taking the Laplace transform of the renewal equation $m(t) = F(t) + \int_0^t m(t-x) \, dF(x)$ and using the convolution property:

$m^*(s) = F^*(s) + m^*(s) \cdot f^*(s)$

where $f^*(s)$ is the Laplace transform of the density $f$, and $F^*(s) = f^*(s)/s$. Solving for $m^*(s)$:

$m^*(s) = \frac{f^*(s)}{s(1 - f^*(s))}$

Equivalently, in terms of the distribution transform:

$m^*(s) = \frac{F^*(s)}{1 - F^*(s)}$

(where $F^*(s) = \int_0^\infty e^{-st} dF(t) = f^*(s)$ is the Laplace-Stieltjes transform of $F$; be careful about which convention your course uses).

To recover $m(t)$, invert the transform using partial fractions, tables, or numerical inversion.

Example: For exponential inter-arrival times with rate $\lambda$, $f^*(s) = \lambda/(s+\lambda)$. Then:

$m^*(s) = \frac{\lambda/(s+\lambda)}{s \cdot [1 - \lambda/(s+\lambda)]} = \frac{\lambda/(s+\lambda)}{s \cdot s/(s+\lambda)} = \frac{\lambda}{s^2}$

Inverting gives $m(t) = \lambda t$, confirming the Poisson process result.

Numerical methods

When the Laplace transform can't be inverted analytically, numerical approaches are necessary:

1. Discretization: Divide $[0, t]$ into subintervals of width $\Delta$. Approximate the integral in the renewal equation by a Riemann sum, producing a system of linear equations that can be solved recursively.
2. Successive approximations: Start with $m_0(t) = F(t)$ and iterate: $m_{k+1}(t) = F(t) + \int_0^t m_k(t-x) \, dF(x)$. This converges to $m(t)$ under mild conditions.
3. Numerical Laplace inversion: Compute $m^*(s)$ at several values of $s$ and use algorithms (e.g., the Euler or Talbot method) to numerically invert.

Renewal equation in frequency domain

The renewal equation can also be analyzed via Fourier transforms, replacing $s$ with $i\omega$. The transformed equation has the same algebraic structure:

$\hat{m}(\omega) = \frac{\hat{F}(\omega)}{1 - \hat{F}(\omega)}$

This perspective is useful when studying periodic or oscillatory behavior in the renewal process, though it's less commonly used than the Laplace approach for computing $m(t)$.

Excess life and age

At any time $t$, you can ask two natural questions about the renewal process: how long until the next renewal? and how long since the last renewal? These are the excess life and age, respectively.

Forward and backward recurrence times

Let $S_{N(t)}$ be the time of the most recent renewal at or before time $t$, and $S_{N(t)+1}$ be the time of the next renewal after $t$.

• Excess life (forward recurrence time): $\gamma_t = S_{N(t)+1} - t$, the remaining time until the next renewal
• Age (backward recurrence time): $\delta_t = t - S_{N(t)}$, the time elapsed since the last renewal
• Spread (total life): $\gamma_t + \delta_t = X_{N(t)+1}$, the length of the inter-arrival interval containing $t$

The distributions of $\gamma_t$ and $\delta_t$ can be expressed using the renewal function. For the excess life:

$P(\gamma_t > x) = 1 - F(t+x) + \int_0^t [1 - F(t + x - y)] \, dm(y)$

This is obtained by conditioning on the time of the last renewal before $t$.

Limiting distributions and behavior

As $t \to \infty$, both the excess life and age converge in distribution to the equilibrium (or spread) distribution:

$\lim_{t \to \infty} P(\gamma_t \leq x) = \lim_{t \to \infty} P(\delta_t \leq x) = F_e(x) = \frac{1}{\mu} \int_0^x [1 - F(y)] \, dy$

This is called the equilibrium distribution (or integrated tail distribution). Notice that $F_e$ depends on the entire shape of $F$, not just its mean.

An important consequence: the limiting excess life is not the same as the original inter-arrival distribution. In fact, $E[\gamma_\infty] = E[X^2]/(2\mu)$, which exceeds $\mu/2$ whenever the inter-arrival times have positive variance. This is related to the inspection paradox: if you arrive at a "random" time, you're more likely to land in a long inter-arrival interval than a short one, so the interval you observe is stochastically larger than a typical inter-arrival time.

Residual life at time t

The term "residual life" is often used interchangeably with excess life $\gamma_t$ in the renewal theory context. In reliability theory, it takes on a more specific meaning: the remaining lifetime of a component that has survived to time $t$.

For a single component (not yet renewed), the residual life distribution is:

$P(X - t > x \mid X > t) = \frac{1 - F(t + x)}{1 - F(t)}$

This is the conditional survival probability and connects to the hazard rate $h(t) = f(t)/[1 - F(t)]$. In a renewal process with replacements, the residual life $\gamma_t$ accounts for the fact that the component currently in use may have been installed at some earlier renewal time, making the full renewal-theoretic formula (from the previous subsection) necessary.

Renewal processes and applications

Ordinary and delayed renewal processes

In an ordinary renewal process, the first inter-arrival time $X_1$ has the same distribution $F$ as all subsequent inter-arrival times. The process starts "fresh" at time 0.

In a delayed (or modified) renewal process, the first inter-arrival time $X_1$ has a different distribution $G$, while $X_2, X_3, \ldots$ are still i.i.d. with distribution $F$. The renewal equation becomes:

$m_D(t) = G(t) + \int_0^t m(t-x) \, dG(x)$

where $m(t)$ on the right is the ordinary renewal function. A particularly useful special case: if $G = F_e$ (the equilibrium distribution), the resulting process is called an equilibrium renewal process, and it has the property that $m_D(t) = t/\mu$ for all $t$, not just asymptotically.

Poisson process as renewal process

The Poisson process with rate $\lambda$ is the renewal process with exponential inter-arrival times ($F(t) = 1 - e^{-\lambda t}$). It's the only renewal process with:

• A linear renewal function: $m(t) = \lambda t$
• A constant renewal density: $u(t) = \lambda$
• The memoryless property: $\gamma_t$ is always exponential with rate $\lambda$, regardless of $t$ or the history

These properties make the Poisson process both the simplest and most tractable renewal process. It serves as the baseline against which other renewal processes are compared.

Applications in reliability theory

Renewal processes model systems where failed components are immediately replaced with statistically identical new ones:

• $m(t)$ gives the expected number of replacements by time $t$
• The renewal density $u(t)$ gives the instantaneous failure rate of the system
• Maintenance policies (e.g., age replacement, block replacement) are optimized using renewal-theoretic results
• Warranty cost analysis uses $m(t)$ to estimate the expected number of claims during a warranty period of length $t$

Renewal-reward processes

A renewal-reward process associates a random reward $R_n$ with the $n$th renewal cycle. The total reward accumulated by time $t$ is $R(t) = \sum_{n=1}^{N(t)} R_n$.

The renewal-reward theorem states:

$\lim_{t \to \infty} \frac{E[R(t)]}{t} = \frac{E[R]}{E[X]}$

That is, the long-run average reward per unit time equals the expected reward per cycle divided by the expected cycle length. This result is widely used in cost analysis, inventory models, and performance evaluation of systems.

Key renewal theorem

The key renewal theorem describes the asymptotic behavior of solutions to renewal-type equations, not just the renewal function itself. It's the workhorse result for extracting long-run behavior from renewal models.

Elementary renewal theorem

The elementary renewal theorem states:

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

where $\mu = E[X_i]$. The proof uses Wald's equation and the strong law of large numbers applied to $S_{N(t)}/N(t) \to \mu$ a.s., combined with $S_{N(t)} \approx t$.

This tells you the long-run average rate of renewals, but says nothing about the finer-grained behavior of $m(t)$.

Blackwell's theorem

Blackwell's theorem provides a stronger statement. If the inter-arrival distribution $F$ is non-lattice (not concentrated on multiples of some fixed $d > 0$), then for any $h > 0$:

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

For lattice distributions with span $d$:

$\lim_{n \to \infty} [m(nd) - m((n-1)d)] = \frac{d}{\mu}$

Blackwell's theorem says that the expected number of renewals in any interval of fixed length $h$ converges to $h/\mu$ as you move that interval far into the future. This is strictly stronger than the elementary renewal theorem.

Key renewal theorem (general form)

The key renewal theorem generalizes Blackwell's result to renewal-type equations. Suppose $Z(t)$ satisfies:

$Z(t) = z(t) + \int_0^t Z(t-x) \, dF(x)$

where $z(t)$ is a directly Riemann integrable function. If $F$ is non-lattice, then:

$\lim_{t \to \infty} Z(t) = \frac{1}{\mu} \int_0^\infty z(t) \, dt$

This is extremely useful because many quantities of interest (excess life distributions, reward rates, etc.) satisfy renewal-type equations. The key renewal theorem lets you read off their limiting values without solving the equation explicitly.

Applications of renewal theorems

• Queueing theory: Long-run average waiting times and queue lengths via renewal-reward arguments
• Reliability engineering: Asymptotic failure rates and steady-state availability of repairable systems
• Insurance mathematics: Ruin probabilities and the adjustment coefficient in the Cramér-Lundberg model use renewal-theoretic asymptotics
• Inventory theory: Long-run average cost under various ordering policies
• General methodology: Any time you need the limiting behavior of a quantity that satisfies a renewal-type equation, the key renewal theorem is the tool to use