Renewal theory

Renewal theory is a branch of probability theory that analyzes renewal processes, which are stochastic models describing the timing of successive events where the inter-event times are independent and identically distributed positive random variables.^[1] In a renewal process, the renewal epochs S_n = \sum_{i=1}^n X_i mark the times of events, with N(t) denoting the number of renewals by time t, and the process often assumes an ordinary start at S_0 = 0 or a delayed form with a different initial distribution.^[2] The theory addresses both arithmetic cases (lattice-distributed interarrivals) and non-arithmetic cases (continuous or aperiodic distributions), providing tools to study long-term behavior, such as the renewal rate \lambda = 1 / \mathbb{E}[X].^[3] Central to renewal theory are several foundational theorems that quantify asymptotic properties. The elementary renewal theorem states that \lim_{t \to \infty} \mathbb{E}[N(t)] / t = \lambda, establishing the expected renewal rate in the long run.^[1] The strong law for renewal processes extends this almost surely: \lim_{t \to \infty} N(t) / t = \lambda with probability 1, assuming finite mean interarrival time.^[3] Blackwell's theorem further refines this for non-arithmetic distributions, showing that the expected number of renewals in intervals of fixed length \delta > 0 approaches \delta \lambda as t \to \infty.^[3] The inspection paradox highlights a bias in observed intervals: the length of the interval containing a random time t has expectation at least as large as the typical interarrival, \mathbb{E}[X_{N(t)+1}] \geq \mathbb{E}[X], due to length-biased sampling.^[1] Additionally, the renewal reward theorem applies to processes with rewards R_n per cycle, yielding \lim_{t \to \infty} R(t) / t = \mathbb{E}[R] / \mathbb{E}[X] almost surely, where R(t) is the cumulative reward by time t.^[1] Renewal theory finds broad applications in modeling real-world phenomena involving recurrent events, such as queueing systems (e.g., G/G/1 arrivals), reliability engineering (e.g., equipment failure times), and inventory management (e.g., replenishment policies).^[3] It also connects to Markov chains, where return times to states form renewal processes, and to pattern analysis in sequences of random variables.^[2] When interarrivals are exponentially distributed, the renewal process reduces to a Poisson process, bridging to more specialized counting processes.^[1] These tools enable precise analysis of age, residual life, and total life distributions, essential for optimization in stochastic systems.^[2]

Renewal Processes

Definition and Interpretation

A renewal process is a counting process that models the occurrence of successive events, where the times between events, known as interarrival times \{X_i\}_{i=1}^\infty, are independent and identically distributed (i.i.d.) positive random variables with finite mean \mu = \mathbb{E}[X_i] > 0. The renewal epochs are defined as S_n = X_1 + \cdots + X_n for n \geq 1, with S_0 = 0, marking the times of the events. The number of renewals by time t \geq 0 is given by N(t) = \sup\{n \geq 0 : S_n \leq t\}, which counts how many events have occurred up to and including time t.^[3]^[1] The process assumes an ordinary renewal at time 0, but a delayed (or equilibrium) version can start with the first interarrival drawn from a different distribution to model steady-state conditions. Renewal processes capture systems with recurrent events that "restart" probabilistically after each occurrence, independent of prior history beyond the last event. This framework applies to scenarios like equipment failures in reliability engineering, where X_i represents time to failure, or customer arrivals in queueing systems, where N(t) tracks arrivals up to time t. The assumption of finite mean ensures a stable long-term rate, while the i.i.d. property implies no dependence between cycles.^[3]^[2]

Interarrival Times and Examples

In renewal theory, the interarrival times X_i for i = 1, 2, \dots represent the durations between consecutive renewal events in a process, where each X_i > 0 almost surely to ensure positive progression of time.^[1]^[3] These times are assumed to be independent and identically distributed (i.i.d.) with a common cumulative distribution function F(x) = P(X_1 \leq x) and finite mean \mu = E[X_i] > 0, which guarantees the process has a well-defined long-term rate $1/\mu.^[4]^[3] The i.i.d. property ensures that the process exhibits stationarity after the first renewal, meaning the statistical behavior restarts identically at each event, while the variance \sigma^2 = \text{Var}(X_i) and higher moments influence the variability and clustering of renewals.^[1]^[3] Common distributions for interarrival times include the exponential distribution, which arises in the Poisson process with rate \lambda > 0, where F(x) = 1 - e^{-\lambda x} for x \geq 0 and \mu = 1/\lambda, imparting the memoryless property that the remaining time to the next renewal is independent of elapsed time.^[3]^[4] Deterministic distributions, such as P(X_i = c) = 1 for some constant c > 0, model fixed-interval renewals like scheduled events.^[1] Uniform distributions, for instance X_i \sim \text{Uniform}(a, b) with $0 < a < b < \infty and \mu = (a + b)/2, capture scenarios with bounded randomness, while general distributions F(x) allow for arbitrary forms as long as \mu < \infty.^[4] Illustrative examples highlight the versatility of renewal processes driven by interarrival times. In a Poisson process, exponential interarrivals model random events like radioactive decay counts, where decays occur independently at constant average rate \lambda, leading to the renewal counting process N(t) that tracks the number of decays up to time t.^[3] For bus waiting times, deterministic interarrivals represent fixed schedules (e.g., buses every 10 minutes), whereas random schedules might use uniform or general F(x) to reflect variability in arrival patterns.^[1]^[3] To analyze stationary regimes, the delayed (or equilibrium) renewal process modifies the standard setup by drawing the first interarrival from the equilibrium distribution F_e(x) = \frac{1}{\mu} \int_0^x [1 - F(u)] \, du for x \geq 0, which represents the forward recurrence time distribution in steady state and ensures the process is stationary from time zero.^[1]^[3] This distribution has mean E[X_e] = E[X_1^2] / (2\mu), which exceeds \mu unless the interarrivals are deterministic.^[1]

Core Quantities and Equations

Renewal Times and Counting Process

In renewal theory, the renewal times, denoted S_n for n = 1, 2, \dots, represent the epochs at which the nth renewal occurs and are defined as the partial sums of the interarrival times:

S_n = \sum_{i=1}^n X_i,

where the X_i are independent and identically distributed positive random variables with finite mean \mu = E[X_i] < \infty.^[3] Under this condition, S_n \to \infty almost surely as n \to \infty, ensuring the process continues indefinitely without termination.^[2] The counting process N(t), which tracks the number of renewals by time t \geq 0, is given by

N(t) = \sum_{n=1}^\infty \mathbf{1}_{\{S_n \leq t\}},

or equivalently, N(t) = \sup\{n \geq 0 : S_n \leq t\} with S_0 = 0.^[3]^[2] This process is non-decreasing, integer-valued, and starts at N(0) = 0; it is right-continuous with left limits, jumping upward by 1 at each renewal epoch.^[2] A key probabilistic relation is that N(t) \geq 0 almost surely and P(N(t) \geq n) = P(S_n \leq t) for each integer n \geq 1.^[3] Associated with N(t) are the residual life (or overshoot) R(t) = S_{N(t)+1} - t, which measures the time from t until the next renewal, and the age A(t) = t - S_{N(t)}, which measures the time elapsed since the most recent renewal before or at t.^[3]^[2] Both R(t) and A(t) are non-negative, and note that A(t) + R(t) = X_{N(t)+1}, the length of the interarrival interval containing t. The renewal function, defined as the expected value E[N(t)], provides the mean number of renewals by time t.^[3] For finite t > 0, the joint distributions of quantities like N(t), A(t), and R(t) can be computed exactly when the interarrival distribution has a density f_X, through successive convolutions of the density: the distribution of S_n is the n-fold convolution f_X^{(n)}, and probabilities such as P(S_n \leq t) follow from integrating this density up to t.^[3] This convolutional structure reflects the additive nature of the renewal times and underpins the probabilistic analysis of the counting process.^[2]

Renewal Function and Renewal Equation

The renewal function, denoted m(t), is defined as the expected number of renewals by time t, that is, m(t) = \mathbb{E}[N(t)], where N(t) is the counting process for the renewal times.^[3] This function is non-decreasing in t, satisfies m(0) = 0, and provides a fundamental measure of the long-term activity in the process.^[3] Moreover, m(t) \geq F(t), where F is the cumulative distribution function of the interarrival time X_1, reflecting that the expected number of renewals exceeds the probability of at least one renewal.^[3] The renewal function satisfies the integral renewal equation, derived by conditioning on the time of the first renewal:

m(t) = F(t) + \int_0^t m(t - u) \, dF(u).

This equation, originally developed in the context of recurrent events, holds in Stieltjes integral form and captures the recursive structure of the process.^[5] ^[3] An equivalent representation expresses m(t) as an infinite sum of convolutions:

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

where F^{*n} denotes the n-fold convolution of F with itself, corresponding to the distribution of the n-th renewal time.^[6] This convolution form highlights the additive nature of successive interarrival times. Explicit solutions for m(t) are available in special cases. For exponential interarrivals with rate \lambda, the process is a Poisson process, and m(t) = \lambda t.^[3] In general, the Laplace transform provides a useful tool for solving the renewal equation: the transform \hat{m}(s) = \frac{\hat{f}(s)}{s(1 - \hat{f}(s))}, where \hat{f}(s) is the Laplace transform of the interarrival density, allows inversion—often numerically—for arbitrary distributions.^[6] For finite t, bounds on m(t) aid in approximations when exact computation is infeasible. Assuming finite mean \mu = \mathbb{E}[X_1] > 0 and variance \sigma^2 = \mathrm{Var}(X_1) < \infty, an upper bound is m(t) < t / \mu + 3(1 + \sigma^2 / \mu^2).^[7] Such inequalities leverage moments to control the function's growth without requiring full distributional knowledge. As t \to \infty, the normalized renewal function m(t)/t approaches $1/\mu, consistent with the elementary renewal theorem.^[3]

Asymptotic Theorems

Elementary Renewal Theorem

The elementary renewal theorem provides a fundamental asymptotic result for the renewal function m(t) = \mathbb{E}[N(t)], where N(t) denotes the number of renewals by time t in a renewal process with i.i.d. positive interarrival times X_i having finite mean \mu = \mathbb{E}[X_1] < \infty. Specifically, it states that

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

This limit holds for both non-arithmetic (aperiodic) distributions, where the support of the interarrival distribution is not concentrated on a lattice, and arithmetic (periodic) cases, where the support lies on multiples of some span a > 0.^[1]^[3] A standard proof sketch relies on Wald's identity, which equates \mathbb{E}[S_{N(t)+1}] = \mu \mathbb{E}[N(t) + 1], where S_n = \sum_{i=1}^n X_i is the time of the nth renewal. Since S_{N(t)} \leq t < S_{N(t)+1}, it follows that t < \mathbb{E}[S_{N(t)+1}] \leq t + \mathbb{E}[X] under finite mean, yielding a lower bound m(t)/t \geq (t - \mu)/(\mu t) \to 1/\mu. For the upper bound, truncation of large interarrivals (e.g., capping at \sqrt{t}) handles potential heavy tails, combined with monotone convergence to show m(t)/t \leq 1/\mu + o(1). An alternative approach uses coupling with an auxiliary renewal process starting at time 0 and the strong law of large numbers on stopped sums.^[8]^[3]^[1] The theorem implies that the long-run renewal rate, or frequency of renewals per unit time, converges to $1/\mu, representing the reciprocal of the average interarrival time. This result is robust and applies even when the variance \mathrm{Var}(X_1) = \infty, as the proof requires only finite mean for the strong law to hold on positive random variables. In the arithmetic case with span a, the theorem extends to

\lim_{n \to \infty} \frac{m(na)}{n} = \frac{a}{\mu},

reflecting the scaled rate along lattice points, consistent with the overall asymptotic density.^[9]^[8]

Key Renewal Theorem

The Key Renewal Theorem establishes an asymptotic limit for convolutions of a suitable test function with the renewal measure in non-arithmetic renewal processes. For a renewal process with non-arithmetic interarrival distribution F having finite mean \mu = \mathbb{E}[X_i] < \infty, and a non-negative function g that is directly Riemann integrable with \int_0^\infty |g(u)| \, du < \infty, the theorem states that

\lim_{t \to \infty} \int_0^t g(t - u) \, dm(u) = \frac{1}{\mu} \int_0^\infty g(u) \, du,

where m(t) = \mathbb{E}[N(t)] is the renewal function representing the expected number of renewals by time t.^[10]/15:_Renewal_Processes/15.03:_Renewal_Limit_Theorems) The renewal measure U is the measure induced by the renewal counting process, given by U(dt) = \sum_{n=0}^\infty dF^{*n}(t), so that U((0,t]) = 1 + m(t). The theorem applies equivalently to the convolution form

\lim_{t \to \infty} \int_0^t g(t - u) \, U(du) = \frac{1}{\mu} \int_0^\infty g(u) \, du,

since the contribution from the Dirac measure at zero vanishes in the limit due to the integrability of g./15:_Renewal_Processes/15.03:_Renewal_Limit_Theorems)^[11] This result extends the Elementary Renewal Theorem, which follows as a special case by taking g \equiv 1 (with suitable truncation for integrability)./15:_Renewal_Processes/15.03:_Renewal_Limit_Theorems) The proof relies on Blackwell's theorem as a foundational precursor, which asserts that for any fixed h > 0,

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

This is recovered from the Key Renewal Theorem by applying it to the indicator function g(u) = \mathbf{1}_{[0,h]}(u). For the general case, directly Riemann integrable functions g are approximated by linear combinations of such indicators over a partition of [0, \infty) into intervals of length \delta > 0; the convolution integrals for these step functions are then bounded using successive applications of Blackwell's theorem, with the approximation error controlled as \delta \to 0.^[10] In the arithmetic case, where the support of F lies on multiples of a span d > 0, the theorem adapts to a discrete limit: for g satisfying analogous summability conditions,

\lim_{n \to \infty} \sum_{k=0}^{nd} g(nd - k) \, \Delta m(k) = \frac{d}{\mu} \sum_{k=0}^\infty g(kd),

where the sum is over the lattice points and \Delta m(k) = m(k) - m(k-).^[10]

Renewal-Reward Processes

Definition and Interpretation

A renewal-reward process extends the basic renewal process by associating a random reward with each renewal event. In a standard renewal process, renewals occur at times S_n = X_1 + \cdots + X_n, where the interarrival times \{X_i\}_{i=1}^\infty are independent and identically distributed (i.i.d.) nonnegative random variables with finite mean \mu = \mathbb{E}[X_i] > 0. To incorporate rewards, let \{R_n\}_{n=1}^\infty be an i.i.d. sequence of random variables, independent of the \{X_i\}, representing the reward incurred at the nth renewal, with \mathbb{E}[|R_n|] < \infty. The cumulative reward up to time t is then defined as the discrete sum Y(t) = \sum_{n=1}^{N(t)} R_n, where N(t) = \sup\{n \geq 0 : S_n \leq t\} is the number of renewals by time t.^[12]^[13] For continuous-time rewards earned at a rate r(s) during the intervals between renewals, the cumulative reward takes the integral form Y(t) = \int_0^t r(s) \, ds, where the rate function r(s) may depend on the age or other state within the current cycle. In both cases, the rewards are assumed to be integrable, \mathbb{E}[|R_n|] < \infty, ensuring the cumulative process is well-defined, and often positivity is imposed (R_n \geq 0) to model beneficial outcomes. The process ties the rewards to the underlying cycle lengths \{X_i\} through the counting mechanism N(t), as longer cycles reduce the number of rewards accumulated over fixed time t.^[14] This framework interprets real-world systems where each renewal cycle generates a stochastic cost or benefit, such as maintenance expenses in reliability engineering—where X_i is the time until equipment failure and R_n is the repair cost—or throughput in queueing systems, with X_i as service times and R_n as customer values processed. The long-run average reward rate, \lim_{t \to \infty} Y(t)/t, captures the steady-state efficiency of such cycles, providing insight into operational performance without delving into specific limits. Representative examples include alternating renewal processes for on-off systems, where rewards accrue differently during operational and downtime phases.^[13]^[15]

Asymptotic Properties for Rewards

In renewal-reward processes, the expected cumulative reward up to time t, denoted M(t) = \mathbb{E}[Y(t)], where Y(t) is the total reward accumulated by time t, satisfies the renewal equation

M(t) = \mathbb{E}[R_1] F(t) + \int_0^t M(t - u) \, dF(u),

with R_1 the reward in the first cycle, F the cumulative distribution function of the interarrival times, and no adjustment needed if rewards are realized only upon cycle completion; otherwise, an additional term accounts for the partial reward in the incomplete final cycle.^[16]^[12] A key asymptotic result is that

\lim_{t \to \infty} \frac{M(t)}{t} = \frac{\mathbb{E}[R]}{\mu},

where \mathbb{E}[R] = \mathbb{E}[R_1] is the expected reward per cycle and \mu = \mathbb{E}[X_1] > 0 is the mean interarrival time, assuming finite means; this limit holds almost surely for the sample path reward Y(t)/t as well.^[16]^[3] The result follows from applying the key renewal theorem to the solution of the reward renewal equation.^[11] To sketch the proof, decompose Y(t) as the sum of rewards over the N(t) complete cycles plus the reward in the residual (incomplete) cycle up to time t. The contribution from complete cycles is \sum_{i=1}^{N(t)} R_i, whose expectation scales as \mathbb{E}[R] m(t) with m(t) = \mathbb{E}[N(t)]; by the elementary renewal theorem, m(t)/t \to 1/\mu. The residual term is bounded (under non-negativity assumptions) and its contribution per unit time vanishes as t \to \infty by bounded convergence, yielding the limit.^[3]^[16] Variants include alternating renewal-reward processes, where cycles alternate between two types with distinct reward distributions (e.g., "on" and "off" states), yielding long-run rates \mathbb{E}[R]/\mu adjusted for the alternating structure.^[3] State-dependent rewards, as in semi-Markov processes, generalize the setup by allowing rewards to depend on the current state at renewal. If variances \mathrm{Var}(X_1) and \mathrm{Var}(R_1) are finite, a central limit theorem holds: [Y(t) - t \mathbb{E}[R]/\mu ] / \sqrt{t} converges in distribution to a normal random variable with mean 0 and variance \frac{ \mathrm{Var}(R_1) + (\mathbb{E}[R])^2 \mathrm{Var}(X_1)/\mu^2 - 2 \mathbb{E}[R] \mathrm{Cov}(X_1, R_1)/\mu }{ \mu }.^[11]

Special Phenomena and Extensions

Inspection Paradox

In renewal theory, the inspection paradox describes the counterintuitive phenomenon where the inter-renewal interval containing a randomly selected time t appears longer on average than a typical inter-renewal time X. This occurs because longer intervals are more likely to encompass the observation point t, leading to a biased sample. Formally, the length of this interval is given by A(t) + R(t), where A(t) is the age (time elapsed since the last renewal before t) and R(t) is the residual life (time until the next renewal after t). As t \to \infty, the expected length satisfies

\lim_{t \to \infty} \mathbb{E}[A(t) + R(t)] = \frac{\mathbb{E}[X^2]}{\mathbb{E}[X]},

which exceeds \mathbb{E}[X] whenever \mathrm{Var}(X) > 0.^[17] The underlying cause is length-biased sampling, where the probability of landing in a particular interval is proportional to its length. Consequently, the limiting distribution of the observed interval length \beta_t = A(t) + R(t) has density

f_{\beta}(b) = \frac{b f_X(b)}{\mathbb{E}[X]}, \quad b > 0,

assuming X has density f_X; the expectation of this length-biased random variable is \mathbb{E}[X^2]/\mathbb{E}[X]. Similarly, the limiting marginal densities for the age and residual life are

f_A(a) = f_R(r) = \frac{1 - F_X(r)}{\mathbb{E}[X]}, \quad a, r > 0,

yielding

\lim_{t \to \infty} \mathbb{E}[A(t)] = \lim_{t \to \infty} \mathbb{E}[R(t)] = \frac{\mathbb{E}[X^2]}{2 \mathbb{E}[X]}.

These results derive from the joint limiting distribution of (A(t), R(t)), which has density f_{A,R}(a,r) = f_X(a + r)/\mathbb{E}[X] for a, r > 0.^[17]^[18] A classic illustration is the bus waiting paradox: if buses arrive according to a renewal process with mean interarrival time \mu = \mathbb{E}[X], a passenger arriving at random time t expects to wait \mathbb{E}[R(t)] \to \mathbb{E}[X^2]/(2 \mathbb{E}[X]), which exceeds \mu/2 due to the bias toward longer gaps. For exponential interarrivals (memoryless case), this equals \mu, but the total observed interval is $2\mu. Another example is inspecting light bulbs in a large installation: the bulb in use at time t has expected remaining life biased upward, suggesting longer lifetimes than average.^[17]^[18] To resolve the paradox and obtain unbiased estimates, one may analyze an equilibrium renewal process, where inter-renewal times are drawn from the length-biased distribution from the outset, or consider the forward and backward recurrence times in a stationary setting. This approach ensures the process is in steady state, avoiding transient biases from the initial conditions. The inspection paradox also connects to renewal-reward processes by interpreting observed intervals as rewards weighted by length.^[1]^[18]

Superposition of Processes

The superposition of renewal processes refers to the merging of multiple independent renewal processes into a single point process. Consider k independent renewal processes \{N_j(t), t \geq 0\} for j = 1, \dots, k, each with interarrival distributions F_j and mean interarrival times \mu_j = \int_0^\infty (1 - F_j(x)) \, dx < \infty. The superposed counting process is defined as N(t) = \sum_{j=1}^k N_j(t), which counts the total number of events from all processes up to time t. The interarrival times of this merged process are determined by the minimum of the residual lifetimes (forward recurrence times) from each component process at any given time.^[19] A key property is that the superposition preserves the renewal structure only under specific conditions. If each N_j(t) is a homogeneous Poisson process with rate \lambda_j, then N(t) is also a Poisson process with rate \sum_{j=1}^k \lambda_j, due to the memoryless property of exponential interarrivals.^[20] However, for general renewal processes, the superposition N(t) is typically not itself a renewal process, as the interarrival times become dependent unless the component processes are Poisson processes (possibly with different rates). In the case of identical non-Poisson renewals, the merged process exhibits clustering or bunching of events, reflecting the synchronization of renewal epochs across processes.^[19] For large k, the Palm–Khintchine theorem states that the superposition of k independent renewal processes, each with finite mean \mu_j, converges in distribution to a Poisson process with rate \sum_{j=1}^k 1/\mu_j as k \to \infty, under mild conditions on the interarrival tails. This approximation arises because the minimum of many independent residual lifetimes behaves like an exponential random variable, mimicking the memoryless property. Asymptotically, the renewal function of the superposed process satisfies m(t) = \mathbb{E}[N(t)] \sim \left( \sum_{j=1}^k 1/\mu_j \right) t as t \to \infty, following from the additivity of expectations and the elementary renewal theorem applied to each component. Heterogeneous rates among the processes can lead to event clustering, where bursts from high-rate components dominate local behavior.^[21] Extensions include thinning, the dual operation to superposition, where points from a renewal process are retained independently with probability p \in (0,1). For a renewal input, the thinned process remains renewal with adjusted interarrival distribution, specifically a geometric mixture of the original interarrivals. Delayed superpositions account for initial offsets in the starting times of component processes, preserving the overall asymptotic properties but introducing transient effects in the early renewal function.^[22]

Renewal theory

Renewal Processes

Definition and Interpretation

Interarrival Times and Examples

Core Quantities and Equations

Renewal Times and Counting Process

Renewal Function and Renewal Equation

Asymptotic Theorems

Elementary Renewal Theorem

Key Renewal Theorem

Renewal-Reward Processes

Definition and Interpretation

Asymptotic Properties for Rewards

Special Phenomena and Extensions

Inspection Paradox

Superposition of Processes

References