Renewal Theory

Core Idea

A renewal process N(t) counts occurrences of events where inter-arrival times X₁, X₂, ... are i.i.d. positive random variables (not necessarily exponential). The elementary renewal theorem states N(t)/t → 1/μ almost surely as t → ∞, where μ = E[X₁]. The renewal-reward theorem extends this to cumulative rewards: total reward/time → E[reward]/E[cycle length]. Renewal theory provides the limit theorems for counting processes and is the foundation for analyzing replacement policies, queuing systems, and regenerative processes.

Explainer

Renewal theory generalizes the Poisson process by allowing inter-arrival times to have any distribution, not just exponential. A renewal process N(t) = max{n : S_n ≤ t}, where S_n = X₁ + ... + X_n and X₁, X₂, ... are i.i.d. positive random variables with mean μ and variance σ², counts the number of "renewals" (events, replacements, regenerations) up to time t. The Poisson process is the special case X_i ~ Exponential(λ) with μ = 1/λ. Renewal theory asks: what happens to N(t) for large t?

The elementary renewal theorem answers the first question: N(t)/t → 1/μ almost surely. The proof connects to the strong law of large numbers: S_n/n → μ a.s. (SLLN), and since N(t) is essentially the inverse function of S_n, we get N(t)/t → 1/μ. The renewal function m(t) = E[N(t)] satisfies the renewal equation m(t) = F(t) + ∫₀ᵗ m(t-s)dF(s), where F is the CDF of X₁. This integral equation, solvable via Laplace transforms, gives the exact expected count. For large t, m(t) ≈ t/μ + (σ² - μ²)/(2μ²) — the leading term is the elementary renewal theorem, and the correction is a constant that depends on the variance.

The renewal-reward theorem is the workhorse for applications. If a reward R_i (possibly random, possibly correlated with X_i) is earned in the i-th cycle, the long-run average reward rate is E[R₁]/E[X₁]. This applies to replacement policies (R_i = cost of i-th replacement, X_i = lifetime), queuing systems (R_i = work served in the i-th busy cycle), and regenerative processes (any quantity accumulated per cycle). The theorem reduces long-run average calculations to single-cycle expectations, which are often tractable.

The inspection paradox (or length-biased sampling) is a counterintuitive but fundamental result. If you arrive at a random time, the inter-arrival interval containing your arrival has expected length E[X²]/E[X] ≥ E[X], strictly greater unless the inter-arrival distribution is deterministic. Longer intervals are more likely to contain your arrival, biasing the sample upward. In the bus-waiting context: if buses arrive with mean interval 10 minutes but with high variance, your expected wait is much more than 5 minutes. Only for perfectly regular (deterministic) intervals is the expected wait exactly half the interval. The inspection paradox has wide-ranging implications in epidemiology (prevalent cases have longer durations), networking (packet capture biases toward longer flows), and survey design.