Stochastic Processes
Point Processes and Event Streams
Цели урока
- Build the renewal counter N(t) and the renewal function m(t)
- Apply the LLN and Blackwell's theorem to compute long-run characteristics
- Use the renewal-reward theorem to optimize replacement policies
- Explain the inspection paradox and its engineering consequences
Предварительные знания
- Poisson processes
- Law of large numbers
- Markov chains
A bus arrives every 10 minutes on average. The average wait should be 5 minutes. But real passengers wait longer. This is not statistical noise. It is a mathematical law.
- Boeing: engine replacement scheduling via Blackwell's theorem
- AWS EC2: SLA calculation for spot instances using the inspection paradox correction
- Insurance: reserve estimation through renewal-based ruin probability
- Kubernetes: long-run service availability via alternating renewal processes
From gambling to reliability engineering
Renewal theory grew from reliability problems of the 1940s. David Blackwell proved the fundamental theorem bearing his name in 1948. William Feller systematized the theory in his classic 1966 textbook. In the 1970s renewal theory became the foundation of actuarial mathematics and engineering reliability analysis. Today it appears in ML: the long-run average reward in RL is a direct consequence of the renewal-reward theorem.
Renewal Process and Core Theorems
This lesson moves from classical renewal theory to general point processes: intensity models, self-exciting Hawkes processes, and marked processes for event sequences. Boeing does not schedule engine maintenance by intuition - by theorem. Mean time between failures for a 787 engine: 25,000 hours. The renewal law of large numbers gives the exact forecast of replacements over any period - no simulation, no half-century of data.
A renewal process is a sequence of i.i.d. random inter-event intervals. Classic example: a queue of component failures where each failed part is immediately replaced by a new one.
Actuarial mathematics: ruin probability
Applying the renewal function to reserve estimation
An insurer receives premiums at rate c and pays claims at intensity lambda. The ruin probability with initial reserve u is expressed through the renewal function. At u = 0: ruin probability equals lambda / (c * mu_claim). A direct consequence of the elementary renewal theorem.
The renewal equation m = F + F * m is solved via the Laplace transform: m_hat(s) = F_hat(s) / (1 - F_hat(s)). This is the geometric series analog in Laplace space.
Blackwell's theorem requires a non-lattice distribution. For lattice distributions (integer-valued intervals), an analogous result is given by the Erdos-Feller-Pollard theorem.
What does the elementary renewal theorem state?
The renewal LLN: N(t)/t converges to 1/mu almost surely as t tends to infinity. This follows from applying the ordinary LLN to S_n and using N(t) >= n iff S_n <= t.
The Renewal-Reward Theorem and Its Applications
Google's data center: each server rewards the cluster with computation while running and costs resources when replaced. How to compute the long-run average throughput? The renewal-reward theorem answers in one line.
Optimal equipment replacement policy
Minimizing long-run maintenance costs
A machine costs c_f at emergency failure and c_p < c_f at planned replacement at age T. Long-run cost: C(T) = (c_p * F_bar(T) + c_f * F(T)) / (mu(T) + T * F_bar(T)), where mu(T) is the truncated mean. Optimal T* minimizes C(T). Analog: ML model refresh policies in production under data drift.
| Distribution X | E[X] | E[X^2] | Coefficient of variation |
|---|---|---|---|
| Exponential(lambda) | 1/lambda | 2/lambda^2 | 1 |
| Gamma(k, theta) | k*theta | k(k+1)*theta^2 | 1/sqrt(k) |
| Weibull(alpha, beta) | beta*Gamma(1+1/alpha) | - | depends on alpha |
| Log-normal(mu, sigma) | exp(mu + sigma^2/2) | exp(2mu + 2sigma^2) | sqrt(e^sigma^2 - 1) |
The renewal-reward theorem is a direct precursor to the Bellman equation in RL. The long-run average reward in an MDP with discount gamma -> 1 reduces to Smith's theorem.
R(t)/t converges to E[Y]/E[X]. What happens when Y_n = X_n (reward equals cycle length)?
With Y_n = X_n, reward per cycle equals its length. Then E[Y]/E[X] = 1 and R(t) approaches t almost surely - the reward coincides with elapsed time.
Alternating Renewal Processes and Stationary Availability
Kubernetes balances load between active and idle replicas. Each replica alternates between on and off periods. What is the long-run fraction of time the system is available? The alternating renewal process gives the answer.
The inspection paradox is not a bug - it is a feature. AWS EC2 spot instances: if a request arrives at a random moment, the expected remaining time until the next spot interruption is longer than the mean. Engineers apply this correction to SLA calculations to get accurate guarantees.
The inspection paradox is universal: GitHub Actions wait for a runner longer than the average interval between runs. Fix: use the size-biased distribution F_e(x) = (1/mu) * int_0^x P(X > t) dt.
Why is the expected length of the current interval longer than the mean when observed at a random time t*?
A random moment lands in an interval with probability proportional to its length. The observed interval has the size-biased distribution with E[X_e] = E[X^2] / (2*E[X]) >= E[X].
Connections to other topics
Renewal theory links probabilistic analysis, actuarial mathematics, and reliability engineering
- Reliability theory — Related topic
- Actuarial mathematics — Related topic
- Queueing theory — Related topic
- RL: average reward — Related topic
Итоги
- N(t)/t converges to 1/mu almost surely - event intensity converges to the reciprocal mean inter-event time
- Blackwell's theorem: m(t+h) - m(t) approaches h/mu - renewal density stabilizes
- Renewal-reward theorem: R(t)/t approaches E[Y]/E[X] regardless of distributions
- Inspection paradox: a random observation lands in a longer interval with higher probability
Вопросы для размышления
- Why does event intensity converge to 1/mu rather than mu?
- How does the renewal-reward theorem relate to the Bellman equation in RL?
- What happens to the inspection paradox when the variance of the intervals is zero?